From 6945f3749927053ee70b47133b2998557a452f75 Mon Sep 17 00:00:00 2001 From: Holger Schemel Date: Fri, 25 Apr 2003 00:23:24 +0200 Subject: [PATCH] rnd-20030425-1-src --- src/conftime.h | 2 +- src/files.c | 56 +++---- src/libgame/Makefile | 2 + src/libgame/hash.c | 366 +++++++++++++++++++++++++++++++++++++++++++ src/libgame/hash.h | 278 ++++++++++++++++++++++++++++++++ src/libgame/misc.c | 115 ++++++++++---- src/libgame/setup.c | 269 ++++++++++++++++++++----------- src/libgame/setup.h | 34 +++- 8 files changed, 966 insertions(+), 156 deletions(-) create mode 100644 src/libgame/hash.c create mode 100644 src/libgame/hash.h diff --git a/src/conftime.h b/src/conftime.h index 63ab6096..3d1c12ce 100644 --- a/src/conftime.h +++ b/src/conftime.h @@ -1 +1 @@ -#define COMPILE_DATE_STRING "[2003-04-23 21:28]" +#define COMPILE_DATE_STRING "[2003-04-25 00:20]" diff --git a/src/files.c b/src/files.c index 6038711a..87c4204f 100644 --- a/src/files.c +++ b/src/files.c @@ -1700,32 +1700,32 @@ static void setSetupInfoToDefaults(struct SetupInfo *si) si->options.verbose = FALSE; } -static void decodeSetupFileList(struct SetupFileList *setup_file_list) +static void decodeSetupFileHash(SetupFileHash *setup_file_hash) { int i, pnr; - if (!setup_file_list) + if (!setup_file_hash) return; /* global setup */ si = setup; for (i=0; i + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its documentation and acknowledgment shall be + * given in the documentation and software packages that this Software was + * used. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * */ + +#include +#include +#include + +#include "hash.h" + + +/*****************************************************************************/ +struct hashtable * +create_hashtable(unsigned int minsize, float maxloadfactor, + unsigned int (*hashf) (void*), + int (*eqf) (void*,void*)) +{ + struct hashtable *h; + unsigned int i, size = 1u; + /* Check requested hashtable isn't too large */ + if (minsize > (1u << 31)) return NULL; + /* Enforce size as power of 2 */ + while (size < minsize) size <<= 1; + h = (struct hashtable *)malloc(sizeof(struct hashtable)); + if (NULL == h) return NULL; /*oom*/ + h->table = (struct entry **)malloc(sizeof(struct entry*) * size); + if (NULL == h->table) { free(h); return NULL; } /*oom*/ + for (i=0;itable[i] = NULL; } + h->tablelength = size; + h->entrycount = 0; + h->hashfn = hashf; + h->eqfn = eqf; + h->loadlimit = (unsigned int) ((float)size * maxloadfactor); + return h; +} + +/*****************************************************************************/ +static unsigned int +hash(struct hashtable *h, void *k) +{ + /* Aim to protect against poor hash functions by adding logic here + * - logic taken from java 1.4 hashtable source */ + unsigned int i = h->hashfn(k); + i += ~(i << 9); + i ^= ((i >> 14) | (i << 18)); /* >>> */ + i += (i << 4); + i ^= ((i >> 10) | (i << 22)); /* >>> */ + return i; +} +/*****************************************************************************/ +static unsigned int +indexFor(unsigned int tablelength, unsigned int hashvalue) +{ + /* Only works if tablelength == 2^N */ + return (hashvalue & (tablelength - 1u)); +} + +/*****************************************************************************/ +static int +hashtable_expand(struct hashtable *h) +{ + /* Double the size of the table to accomodate more entries */ + struct entry **newtable; + struct entry *e; + struct entry **pE; + unsigned int newsize, i, index; + /* Check we're not hitting max capacity */ + if (0 == (newsize = (h->tablelength << 1))) return 0; + + newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize); + if (NULL != newtable) + { + memset(newtable, 0, newsize * sizeof(struct entry *)); + /* This algorithm is not 'stable'. ie. it reverses the list + * when it transfers entries between the tables */ + for (i = 0; i < h->tablelength; i++) { + while (NULL != (e = h->table[i])) { + h->table[i] = e->next; + index = indexFor(newsize,e->h); + e->next = newtable[index]; + newtable[index] = e; + } + } + free(h->table); + h->table = newtable; + } + /* Plan B: realloc instead */ + else + { + newtable = (struct entry **) + realloc(h->table, newsize * sizeof(struct entry *)); + if (NULL == newtable) return 0; + h->table = newtable; + for (i = h->tablelength; i < newsize; i++) { + newtable[i] = NULL; + } + for (i = 0; i < h->tablelength; i++) { + for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) { + index = indexFor(newsize,e->h); + if (index == i) + { + pE = &(e->next); + } + else + { + *pE = e->next; + e->next = newtable[index]; + newtable[index] = e; + } + } + } + } + h->tablelength = newsize; + h->loadlimit <<= 1; + return -1; +} + +/*****************************************************************************/ +unsigned int +hashtable_count(struct hashtable *h) +{ + return h->entrycount; +} + +/*****************************************************************************/ +int +hashtable_insert(struct hashtable *h, void *k, void *v) +{ + /* This method allows duplicate keys - but they shouldn't be used */ + unsigned int index; + struct entry *e; + if (++(h->entrycount) > h->loadlimit) + { + /* Ignore the return value. If expand fails, we should + * still try cramming just this value into the existing table + * -- we may not have memory for a larger table, but one more + * element may be ok. Next time we insert, we'll try expanding again.*/ + hashtable_expand(h); + } + e = (struct entry *)malloc(sizeof(struct entry)); + if (NULL == e) { --(h->entrycount); return 0; } /*oom*/ + e->h = hash(h,k); + index = indexFor(h->tablelength,e->h); + e->k = k; + e->v = v; + e->next = h->table[index]; + h->table[index] = e; + return -1; +} + +/*****************************************************************************/ +int +hashtable_change(struct hashtable *h, void *k, void *v) +{ + struct entry *e; + unsigned int hashvalue, index; + hashvalue = hash(h,k); + index = indexFor(h->tablelength,hashvalue); + e = h->table[index]; + while (NULL != e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue == e->h) && (h->eqfn(k, e->k))) + { + free(e->v); + e->v = v; + return -1; + } + e = e->next; + } + return 0; +} + +/*****************************************************************************/ +void * /* returns value associated with key */ +hashtable_search(struct hashtable *h, void *k) +{ + struct entry *e; + unsigned int hashvalue, index; + hashvalue = hash(h,k); + index = indexFor(h->tablelength,hashvalue); + e = h->table[index]; + while (NULL != e) + { + /* Check hash value to short circuit heavier comparison */ + if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v; + e = e->next; + } + return NULL; +} + +/*****************************************************************************/ +void * /* returns value associated with key */ +hashtable_remove(struct hashtable *h, void *k) +{ + /* TODO: consider compacting the table when the load factor drops enough, + * or provide a 'compact' method. */ + + struct entry *e; + struct entry **pE; + void *v; + + unsigned int index = indexFor(h->tablelength,hash(h,k)); + pE = &(h->table[index]); + e = *pE; + while (NULL != e) + { + if (h->eqfn(k, e->k)) + { + *pE = e->next; + h->entrycount--; + v = e->v; + free(e->k); + free(e); + return v; + } + pE = &(e->next); + e = e->next; + } + return NULL; +} + +/*****************************************************************************/ +/* destroy */ +void +hashtable_destroy(struct hashtable *h, int free_values) +{ + unsigned int i; + struct entry *e, *f; + struct entry **table = h->table; + if (free_values) + { + for (i = 0; i < h->tablelength; i++) + { + e = table[i]; + while (NULL != e) + { f = e; e = e->next; free(f->k); free(f->v); free(f); } + } + } + else + { + for (i = 0; i < h->tablelength; i++) + { + e = table[i]; + while (NULL != e) + { f = e; e = e->next; free(f->k); free(f); } + } + } +} + + +/*****************************************************************************/ +/* hashtable_iterator - iterator constructor */ + +struct hashtable_itr * +hashtable_iterator(struct hashtable *h) +{ + unsigned int i, tablelength; + struct hashtable_itr *itr = (struct hashtable_itr *) + malloc(sizeof(struct hashtable_itr)); + if (NULL == itr) return NULL; + itr->h = h; + itr->e = NULL; + tablelength = h->tablelength; + itr->index = tablelength; + if (0 == h->entrycount) return itr; + + for (i = 0; i < tablelength; i++) + { + if (NULL != h->table[i]) + { + itr->e = h->table[i]; + itr->index = i; + break; + } + } + return itr; +} + +/*****************************************************************************/ +/* key - return the key of the (key,value) pair at the current position */ + +void * +hashtable_iterator_key(struct hashtable_itr *i) +{ + return i->e->k; +} + +/*****************************************************************************/ +/* value - return the value of the (key,value) pair at the current position */ + +void * +hashtable_iterator_value(struct hashtable_itr *i) +{ + return i->e->v; +} + +/*****************************************************************************/ +/* advance - advance the iterator to the next element + * returns zero if advanced to end of table */ + +int +hashtable_iterator_advance(struct hashtable_itr *itr) +{ + unsigned int j,tablelength; + struct entry **table; + struct entry *next; + if (NULL == itr->e) return 0; /* stupidity check */ + + next = itr->e->next; + if (NULL != next) + { + itr->e = next; + return -1; + } + tablelength = itr->h->tablelength; + if (tablelength <= (j = ++(itr->index))) + { + itr->e = NULL; + return 0; + } + table = itr->h->table; + while (NULL == (next = table[j])) + { + if (++j >= tablelength) + { + itr->index = tablelength; + return 0; + } + } + itr->index = j; + itr->e = next; + return -1; +} diff --git a/src/libgame/hash.h b/src/libgame/hash.h new file mode 100644 index 00000000..4be5cc8d --- /dev/null +++ b/src/libgame/hash.h @@ -0,0 +1,278 @@ +/*********************************************************** +* Artsoft Retro-Game Library * +*----------------------------------------------------------* +* (c) 1994-2003 Artsoft Entertainment * +* Holger Schemel * +* Detmolder Strasse 189 * +* 33604 Bielefeld * +* Germany * +* e-mail: info@artsoft.org * +*----------------------------------------------------------* +* hash.h * +***********************************************************/ + +/* + * Copyright (C) 2002 Christopher Clark + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its documentation and acknowledgment shall be + * given in the documentation and software packages that this Software was + * used. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * */ + +#ifndef HASH_H +#define HASH_H + + +/* Example of use: + * + * struct hashtable *h; + * struct some_key *k; + * struct some_value *v; + * + * static unsigned int hash_from_key_fn( void *k ); + * static int keys_equal_fn ( void *key1, void *key2 ); + * + * h = create_hashtable(16, 0.75, hash_from_key_fn, keys_equal_fn); + * k = (struct some_key *) malloc(sizeof(struct some_key)); + * v = (struct some_value *) malloc(sizeof(struct some_value)); + * + * (initialise k and v to suitable values) + * + * if (! hashtable_insert(h,k,v) ) + * { exit(-1); } + * + * if (NULL == (found = hashtable_search(h,k) )) + * { printf("not found!"); } + * + * if (NULL == (found = hashtable_remove(h,k) )) + * { printf("Not found\n"); } + * + */ + +/* Macros may be used to define type-safe(r) hashtable access functions, with + * methods specialized to take known key and value types as parameters. + * + * Example: + * + * Insert this at the start of your file: + * + * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value); + * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value); + * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value); + * + * This defines the functions 'insert_some', 'search_some' and 'remove_some'. + * These operate just like hashtable_insert etc., with the same parameters, + * but their function signatures have 'struct some_key *' rather than + * 'void *', and hence can generate compile time errors if your program is + * supplying incorrect data as a key (and similarly for value). + * + * Note that the hash and key equality functions passed to create_hashtable + * still take 'void *' parameters instead of 'some key *'. This shouldn't be + * a difficult issue as they're only defined and passed once, and the other + * functions will ensure that only valid keys are supplied to them. + * + * The cost for this checking is increased code size and runtime overhead + * - if performance is important, it may be worth switching back to the + * unsafe methods once your program has been debugged with the safe methods. + * This just requires switching to some simple alternative defines - eg: + * #define insert_some hashtable_insert + * + */ + + +/*****************************************************************************/ +struct entry +{ + void *k, *v; + unsigned int h; + struct entry *next; +}; + +struct hashtable { + unsigned int tablelength; + struct entry **table; + unsigned int entrycount; + unsigned int loadlimit; + unsigned int (*hashfn) (void *k); + int (*eqfn) (void *k1, void *k2); +}; + +/*****************************************************************************/ +struct hashtable_itr +{ + struct hashtable *h; + struct entry *e; + unsigned int index; +}; + + +/***************************************************************************** + * create_hashtable + + * @name create_hashtable + * @param minsize minimum initial size of hashtable + * @param maxloadfactor maximum ratio entries / tablesize + * @param hashfunction function for hashing keys + * @param key_eq_fn function for determining key equality + * @return newly created hashtable or NULL on failure + */ + +struct hashtable * +create_hashtable(unsigned int minsize, float maxloadfactor, + unsigned int (*hashfunction) (void*), + int (*key_eq_fn) (void*,void*)); + +/***************************************************************************** + * hashtable_insert + + * @name hashtable_insert + * @param h the hashtable to insert into + * @param k the key - hashtable claims ownership and will free on removal + * @param v the value - does not claim ownership + * @return non-zero for successful insertion + * + * This function will cause the table to expand if the insertion would take + * the ratio of entries to table size over the maximum load factor. + * + * This function does not check for repeated insertions with a duplicate key. + * The value returned when using a duplicate key is undefined -- when + * the hashtable changes size, the order of retrieval of duplicate key + * entries is reversed. + * If in doubt, remove before insert. + */ + +int +hashtable_insert(struct hashtable *h, void *k, void *v); + +#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \ +int fnname (struct hashtable *h, keytype *k, valuetype *v) \ +{ \ + return hashtable_insert(h,k,v); \ +} + +/***************************************************************************** + * hashtable_change + + * @name hashtable_change + * @param h the hashtable to search + * @param k the key of the entry to change + * @param v the new value + * @return non-zero for successful change + */ + +int +hashtable_change(struct hashtable *h, void *k, void *v); + +#define DEFINE_HASHTABLE_CHANGE(fnname, keytype, valuetype) \ +int fnname (struct hashtable *h, keytype *k, valuetype *v) \ +{ \ + return hashtable_change(h,k,v); \ +} + +/***************************************************************************** + * hashtable_search + + * @name hashtable_search + * @param h the hashtable to search + * @param k the key to search for - does not claim ownership + * @return the value associated with the key, or NULL if none found + */ + +void * +hashtable_search(struct hashtable *h, void *k); + +#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \ +valuetype * fnname (struct hashtable *h, keytype *k) \ +{ \ + return (valuetype *) (hashtable_search(h,k)); \ +} + +/***************************************************************************** + * hashtable_remove + + * @name hashtable_remove + * @param h the hashtable to remove the item from + * @param k the key to search for - does not claim ownership + * @return the value associated with the key, or NULL if none found + */ + +void * /* returns value */ +hashtable_remove(struct hashtable *h, void *k); + +#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \ +valuetype * fnname (struct hashtable *h, keytype *k) \ +{ \ + return (valuetype *) (hashtable_remove(h,k)); \ +} + + +/***************************************************************************** + * hashtable_count + + * @name hashtable_count + * @return the number of items stored in the hashtable + */ +unsigned int +hashtable_count(struct hashtable *h); + + +/***************************************************************************** + * hashtable_destroy + + * @name hashtable_destroy + * @param free_values whether to call 'free' on the remaining values + */ + +void +hashtable_destroy(struct hashtable *h, int free_values); + + +/*****************************************************************************/ +/* hashtable_iterator + */ + +struct hashtable_itr * +hashtable_iterator(struct hashtable *h); + +/*****************************************************************************/ +/* hashtable_iterator_key + * - return the value of the (key,value) pair at the current position */ + +extern inline void * +hashtable_iterator_key(struct hashtable_itr *i) +{ + return i->e->k; +} + +/*****************************************************************************/ +/* value - return the value of the (key,value) pair at the current position */ + +extern inline void * +hashtable_iterator_value(struct hashtable_itr *i) +{ + return i->e->v; +} + +/*****************************************************************************/ +/* advance - advance the iterator to the next element + * returns zero if advanced to end of table */ + +int +hashtable_iterator_advance(struct hashtable_itr *itr); + +#endif diff --git a/src/libgame/misc.c b/src/libgame/misc.c index efb56bba..11c0c185 100644 --- a/src/libgame/misc.c +++ b/src/libgame/misc.c @@ -1777,12 +1777,12 @@ static boolean token_suffix_match(char *token, char *suffix, int start_pos) #define KNOWN_TOKEN_VALUE "[KNOWN_TOKEN]" -static void read_token_parameters(struct SetupFileList *setup_file_list, +static void read_token_parameters(SetupFileHash *setup_file_hash, struct ConfigInfo *suffix_list, struct FileInfo *file_list_entry) { /* check for config token that is the base token without any suffixes */ - char *filename = getTokenValue(setup_file_list, file_list_entry->token); + char *filename = getHashEntry(setup_file_hash, file_list_entry->token); char *known_token_value = KNOWN_TOKEN_VALUE; int i; @@ -1797,7 +1797,7 @@ static void read_token_parameters(struct SetupFileList *setup_file_list, file_list_entry->redefined = TRUE; /* mark config file token as well known from default config */ - setTokenValue(setup_file_list, file_list_entry->token, known_token_value); + setHashEntry(setup_file_hash, file_list_entry->token, known_token_value); } else setString(&file_list_entry->filename, file_list_entry->default_filename); @@ -1806,14 +1806,14 @@ static void read_token_parameters(struct SetupFileList *setup_file_list, for (i=0; suffix_list[i].token != NULL; i++) { char *token = getStringCat2(file_list_entry->token, suffix_list[i].token); - char *value = getTokenValue(setup_file_list, token); + char *value = getHashEntry(setup_file_hash, token); if (value != NULL) { setString(&file_list_entry->parameter[i], value); /* mark config file token as well known from default config */ - setTokenValue(setup_file_list, token, known_token_value); + setHashEntry(setup_file_hash, token, known_token_value); } free(token); @@ -1822,7 +1822,7 @@ static void read_token_parameters(struct SetupFileList *setup_file_list, static void add_dynamic_file_list_entry(struct FileInfo **list, int *num_list_entries, - struct SetupFileList *extra_file_list, + SetupFileHash *extra_file_hash, struct ConfigInfo *suffix_list, int num_suffix_list_entries, char *token) @@ -1843,7 +1843,7 @@ static void add_dynamic_file_list_entry(struct FileInfo **list, new_list_entry->filename = NULL; new_list_entry->parameter = checked_calloc(parameter_array_size); - read_token_parameters(extra_file_list, suffix_list, new_list_entry); + read_token_parameters(extra_file_hash, suffix_list, new_list_entry); } static void add_property_mapping(struct PropertyMapping **list, @@ -1884,9 +1884,11 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) int num_ext3_suffixes = artwork_info->num_ext3_suffixes; int num_ignore_tokens = artwork_info->num_ignore_tokens; char *filename = getCustomArtworkConfigFilename(artwork_info->type); - struct SetupFileList *setup_file_list; - struct SetupFileList *extra_file_list = NULL; - struct SetupFileList *list; + SetupFileHash *setup_file_hash; + SetupFileHash *extra_file_hash = NULL; +#if 0 + SetupFileHash *list; +#endif char *known_token_value = KNOWN_TOKEN_VALUE; int i, j, k, l; @@ -1934,35 +1936,60 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) if (filename == NULL) return; - if ((setup_file_list = loadSetupFileList(filename)) == NULL) + printf("::: THIS 0\n"); + + if ((setup_file_hash = loadSetupFileHash(filename)) == NULL) return; + printf("::: THIS 1 [%d]\n", num_file_list_entries); + /* read parameters for all known config file tokens */ for (i=0; inext) +#if 0 + for (list = setup_file_hash; list != NULL; list = list->next) { if (strcmp(list->value, known_token_value) != 0) { - if (extra_file_list == NULL) - extra_file_list = newSetupFileList(list->token, list->value); + if (extra_file_hash == NULL) + extra_file_hash = newSetupFileHash(list->token, list->value); else - setTokenValue(extra_file_list, list->token, list->value); + setHashEntry(extra_file_hash, list->token, list->value); } } +#else + BEGIN_HASH_ITERATION(setup_file_hash, itr) + { + if (strcmp(HASH_ITERATION_VALUE(itr), known_token_value) != 0) + { + if (extra_file_hash == NULL) + extra_file_hash = newSetupFileHash(); + + setHashEntry(extra_file_hash, + HASH_ITERATION_TOKEN(itr), HASH_ITERATION_VALUE(itr)); + } + } + END_HASH_ITERATION(setup_file_hash, itr) +#endif /* at this point, we do not need the config file list anymore -- free it */ - freeSetupFileList(setup_file_list); + freeSetupFileHash(setup_file_hash); /* now try to determine valid, dynamically defined config tokens */ - for (list = extra_file_list; list != NULL; list = list->next) +#if 0 + for (list = extra_file_hash; list != NULL; list = list->next) +#endif + + BEGIN_HASH_ITERATION(extra_file_hash, itr) { struct FileInfo **dynamic_file_list = &artwork_info->dynamic_file_list; @@ -1975,7 +2002,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) int current_summarized_file_list_entry = artwork_info->num_file_list_entries + artwork_info->num_dynamic_file_list_entries; - char *token = list->token; + char *token = HASH_ITERATION_TOKEN(itr); int len_token = strlen(token); int start_pos; boolean base_prefix_found = FALSE; @@ -2032,7 +2059,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) add_dynamic_file_list_entry(dynamic_file_list, num_dynamic_file_list_entries, - extra_file_list, + extra_file_hash, suffix_list, num_suffix_list_entries, token); @@ -2069,7 +2096,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) add_dynamic_file_list_entry(dynamic_file_list, num_dynamic_file_list_entries, - extra_file_list, + extra_file_hash, suffix_list, num_suffix_list_entries, token); @@ -2111,7 +2138,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) add_dynamic_file_list_entry(dynamic_file_list, num_dynamic_file_list_entries, - extra_file_list, + extra_file_hash, suffix_list, num_suffix_list_entries, token); @@ -2153,7 +2180,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) add_dynamic_file_list_entry(dynamic_file_list, num_dynamic_file_list_entries, - extra_file_list, + extra_file_hash, suffix_list, num_suffix_list_entries, token); @@ -2166,6 +2193,7 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) } } } + END_HASH_ITERATION(extra_file_hash, itr) if (artwork_info->num_dynamic_file_list_entries > 0) { @@ -2174,18 +2202,23 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) artwork_info->sizeof_artwork_list_entry); } - if (extra_file_list != NULL && options.verbose && IS_PARENT_PROCESS()) + if (extra_file_hash != NULL && options.verbose && IS_PARENT_PROCESS()) { boolean dynamic_tokens_found = FALSE; boolean unknown_tokens_found = FALSE; - for (list = extra_file_list; list != NULL; list = list->next) +#if 0 + for (list = extra_file_hash; list != NULL; list = list->next) +#endif + + BEGIN_HASH_ITERATION(extra_file_hash, itr) { - if (strcmp(list->value, known_token_value) == 0) + if (strcmp(HASH_ITERATION_VALUE(itr), known_token_value) == 0) dynamic_tokens_found = TRUE; else unknown_tokens_found = TRUE; } + END_HASH_ITERATION(extra_file_hash, itr) #if DEBUG if (dynamic_tokens_found) @@ -2193,9 +2226,16 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) Error(ERR_RETURN_LINE, "-"); Error(ERR_RETURN, "dynamic token(s) found:"); - for (list = extra_file_list; list != NULL; list = list->next) - if (strcmp(list->value, known_token_value) == 0) - Error(ERR_RETURN, "- dynamic token: '%s'", list->token); +#if 0 + for (list = extra_file_hash; list != NULL; list = list->next) +#endif + + BEGIN_HASH_ITERATION(extra_file_hash, itr) + { + if (strcmp(HASH_ITERATION_VALUE(itr), known_token_value) == 0) + Error(ERR_RETURN, "- dynamic token: '%s'",HASH_ITERATION_TOKEN(itr)); + } + END_HASH_ITERATION(extra_file_hash, itr) Error(ERR_RETURN_LINE, "-"); } @@ -2207,15 +2247,22 @@ void LoadArtworkConfig(struct ArtworkListInfo *artwork_info) Error(ERR_RETURN, "warning: unknown token(s) found in config file:"); Error(ERR_RETURN, "- config file: '%s'", filename); - for (list = extra_file_list; list != NULL; list = list->next) - if (strcmp(list->value, known_token_value) != 0) - Error(ERR_RETURN, "- unknown token: '%s'", list->token); +#if 0 + for (list = extra_file_hash; list != NULL; list = list->next) +#endif + + BEGIN_HASH_ITERATION(extra_file_hash, itr) + { + if (strcmp(HASH_ITERATION_VALUE(itr), known_token_value) != 0) + Error(ERR_RETURN, "- unknown token: '%s'",HASH_ITERATION_TOKEN(itr)); + } + END_HASH_ITERATION(extra_file_hash, itr) Error(ERR_RETURN_LINE, "-"); } } - freeSetupFileList(extra_file_list); + freeSetupFileHash(extra_file_hash); #if 0 for (i=0; itoken) - free(setup_file_list->token); - if (setup_file_list->value) - free(setup_file_list->value); - if (setup_file_list->next) - freeSetupFileList(setup_file_list->next); - free(setup_file_list); + if (list->token) + free(list->token); + if (list->value) + free(list->value); + if (list->next) + freeSetupFileList(list->next); + free(list); } -struct SetupFileList *newSetupFileList(char *token, char *value) +SetupFileList *newSetupFileList(char *token, char *value) { - struct SetupFileList *new = checked_malloc(sizeof(struct SetupFileList)); + SetupFileList *new = checked_malloc(sizeof(SetupFileList)); new->token = getStringCopy(token); new->value = getStringCopy(value); @@ -1065,56 +1066,167 @@ struct SetupFileList *newSetupFileList(char *token, char *value) return new; } -char *getTokenValue(struct SetupFileList *setup_file_list, char *token) +char *getTokenValue(SetupFileList *list, char *token) { - if (setup_file_list == NULL) + if (list == NULL) return NULL; - if (strcmp(setup_file_list->token, token) == 0) - return setup_file_list->value; + if (strcmp(list->token, token) == 0) + return list->value; else - return getTokenValue(setup_file_list->next, token); + return getTokenValue(list->next, token); } -void setTokenValue(struct SetupFileList *setup_file_list, - char *token, char *value) +void setTokenValue(SetupFileList *list, char *token, char *value) { - if (setup_file_list == NULL) + if (list == NULL) return; - if (strcmp(setup_file_list->token, token) == 0) + if (strcmp(list->token, token) == 0) { - if (setup_file_list->value) - free(setup_file_list->value); + if (list->value) + free(list->value); - setup_file_list->value = getStringCopy(value); + list->value = getStringCopy(value); } - else if (setup_file_list->next == NULL) - setup_file_list->next = newSetupFileList(token, value); + else if (list->next == NULL) + list->next = newSetupFileList(token, value); else - setTokenValue(setup_file_list->next, token, value); + setTokenValue(list->next, token, value); } #ifdef DEBUG -static void printSetupFileList(struct SetupFileList *setup_file_list) +static void printSetupFileList(SetupFileList *list) { - if (!setup_file_list) + if (!list) return; - printf("token: '%s'\n", setup_file_list->token); - printf("value: '%s'\n", setup_file_list->value); + printf("token: '%s'\n", list->token); + printf("value: '%s'\n", list->value); - printSetupFileList(setup_file_list->next); + printSetupFileList(list->next); } #endif -struct SetupFileList *loadSetupFileList(char *filename) +#ifdef DEBUG +DEFINE_HASHTABLE_INSERT(insert_hash_entry, char, char); +DEFINE_HASHTABLE_SEARCH(search_hash_entry, char, char); +DEFINE_HASHTABLE_CHANGE(change_hash_entry, char, char); +DEFINE_HASHTABLE_REMOVE(remove_hash_entry, char, char); +#else +#define insert_hash_entry hashtable_insert +#define search_hash_entry hashtable_search +#define change_hash_entry hashtable_change +#define remove_hash_entry hashtable_remove +#endif + +static unsigned int get_hash_from_key(void *key) +{ + /* + djb2 + + this algorithm (k=33) was first reported by dan bernstein many years ago in + comp.lang.c. another version of this algorithm (now favored by bernstein) + uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why + it works better than many other constants, prime or not) has never been + adequately explained. + */ + + char *str = (char *)key; + unsigned int hash = 5381; + int c; + + while ((c = *str++)) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + + return hash; +} + +static int keys_are_equal(void *key1, void *key2) +{ + return (strcmp((char *)key1, (char *)key2) == 0); +} + +void freeSetupFileHash(SetupFileHash *hash) +{ + if (hash == NULL) + return; + + hashtable_destroy(hash, 1); /* 1 == also free values */ + free(hash); +} + +SetupFileHash *newSetupFileHash() +{ + SetupFileHash *new_hash = + create_hashtable(16, 0.75, get_hash_from_key, keys_are_equal); + + return new_hash; +} + +char *getHashEntry(SetupFileHash *hash, char *token) +{ + if (hash == NULL) + return NULL; + + return search_hash_entry(hash, token); +} + +void setHashEntry(SetupFileHash *hash, char *token, char *value) +{ + char *value_copy; + + if (hash == NULL) + return; + + value_copy = getStringCopy(value); + + /* change value; if it does not exist, insert it as new */ + if (!change_hash_entry(hash, token, value_copy)) + if (!insert_hash_entry(hash, getStringCopy(token), value_copy)) + Error(ERR_EXIT, "cannot insert into hash -- aborting"); +} + +#if 0 +#ifdef DEBUG +static void printSetupFileHash(SetupFileHash *hash) +{ +#if 0 + if (hash == NULL) + return; + + /* iterator constructor only returns valid iterator for non-empty hash */ + if (hash != NULL && hashtable_count(hash) > 0) + { + struct hashtable_itr *itr = hashtable_iterator(hash); + + do + { + printf("token: '%s'\n", (char *)hashtable_iterator_key(itr)); + printf("value: '%s'\n", (char *)hashtable_iterator_value(itr)); + } + while (hashtable_iterator_advance(itr)); + + free(itr); + } +#endif + + BEGIN_HASH_ITERATION(hash, itr) + { + printf("token: '%s'\n", HASH_ITERATION_TOKEN(itr)); + printf("value: '%s'\n", HASH_ITERATION_VALUE(itr)); + } + END_HASH_ITERATION(hash, itr) +} +#endif +#endif + +SetupFileHash *loadSetupFileHash(char *filename) { int line_len; char line[MAX_LINE_LEN]; char *token, *value, *line_ptr; - struct SetupFileList *setup_file_list = newSetupFileList("", ""); - struct SetupFileList *first_valid_list_entry; + SetupFileHash *setup_file_hash = newSetupFileHash(); FILE *file; if (!(file = fopen(filename, MODE_READ))) @@ -1176,47 +1288,26 @@ struct SetupFileList *loadSetupFileList(char *filename) break; if (*token && *value) - setTokenValue(setup_file_list, token, value); + setHashEntry(setup_file_hash, token, value); } fclose(file); - first_valid_list_entry = setup_file_list->next; - - /* free empty list header */ - setup_file_list->next = NULL; - freeSetupFileList(setup_file_list); - - if (first_valid_list_entry == NULL) + if (hashtable_count(setup_file_hash) == 0) Error(ERR_WARN, "configuration file '%s' is empty", filename); - return first_valid_list_entry; + return setup_file_hash; } -void checkSetupFileListIdentifier(struct SetupFileList *setup_file_list, +void checkSetupFileHashIdentifier(SetupFileHash *setup_file_hash, char *identifier) { - if (!setup_file_list) - return; + char *value = getHashEntry(setup_file_hash, TOKEN_STR_FILE_IDENTIFIER); - if (strcmp(setup_file_list->token, TOKEN_STR_FILE_IDENTIFIER) == 0) - { - if (!checkCookieString(setup_file_list->value, identifier)) - { - Error(ERR_WARN, "configuration file has wrong file identifier"); - return; - } - else - return; - } - - if (setup_file_list->next) - checkSetupFileListIdentifier(setup_file_list->next, identifier); - else - { + if (value == NULL) Error(ERR_WARN, "configuration file has no file identifier"); - return; - } + else if (!checkCookieString(value, identifier)) + Error(ERR_WARN, "configuration file has wrong file identifier"); } @@ -1466,11 +1557,11 @@ static boolean LoadLevelInfoFromLevelConf(TreeInfo **node_first, { char *directory_path = getPath2(level_directory, directory_name); char *filename = getPath2(directory_path, LEVELINFO_FILENAME); - struct SetupFileList *setup_file_list = loadSetupFileList(filename); + SetupFileHash *setup_file_hash = loadSetupFileHash(filename); LevelDirTree *leveldir_new = NULL; int i; - if (setup_file_list == NULL) + if (setup_file_hash == NULL) { Error(ERR_WARN, "ignoring level directory '%s'", directory_path); @@ -1489,13 +1580,13 @@ static boolean LoadLevelInfoFromLevelConf(TreeInfo **node_first, leveldir_new->filename = getStringCopy(directory_name); - checkSetupFileListIdentifier(setup_file_list, getCookie("LEVELINFO")); + checkSetupFileHashIdentifier(setup_file_hash, getCookie("LEVELINFO")); /* set all structure fields according to the token/value pairs */ ldi = *leveldir_new; for (i=0; iname, ANONYMOUS_NAME) == 0) @@ -1542,7 +1633,7 @@ static boolean LoadLevelInfoFromLevelConf(TreeInfo **node_first, pushTreeInfo(node_first, leveldir_new); - freeSetupFileList(setup_file_list); + freeSetupFileHash(setup_file_hash); if (leveldir_new->level_group) { @@ -1651,14 +1742,14 @@ static boolean LoadArtworkInfoFromArtworkConf(TreeInfo **node_first, { char *directory_path = getPath2(base_directory, directory_name); char *filename = getPath2(directory_path, ARTWORKINFO_FILENAME(type)); - struct SetupFileList *setup_file_list = NULL; + SetupFileHash *setup_file_hash = NULL; TreeInfo *artwork_new = NULL; int i; if (access(filename, F_OK) == 0) /* file exists */ - setup_file_list = loadSetupFileList(filename); + setup_file_hash = loadSetupFileHash(filename); - if (setup_file_list == NULL) /* no config file -- look for artwork files */ + if (setup_file_hash == NULL) /* no config file -- look for artwork files */ { DIR *dir; struct dirent *dir_entry; @@ -1701,17 +1792,17 @@ static boolean LoadArtworkInfoFromArtworkConf(TreeInfo **node_first, artwork_new->filename = getStringCopy(directory_name); - if (setup_file_list) /* (before defining ".color" and ".class_desc") */ + if (setup_file_hash) /* (before defining ".color" and ".class_desc") */ { #if 0 - checkSetupFileListIdentifier(setup_file_list, getCookie("...")); + checkSetupFileHashIdentifier(setup_file_hash, getCookie("...")); #endif /* set all structure fields according to the token/value pairs */ ldi = *artwork_new; for (i=0; iname, ANONYMOUS_NAME) == 0) @@ -1745,11 +1836,11 @@ static boolean LoadArtworkInfoFromArtworkConf(TreeInfo **node_first, artwork_new->user_defined = (artwork_new->basepath == OPTIONS_ARTWORK_DIRECTORY(type) ? FALSE : TRUE); - /* (may use ".sort_priority" from "setup_file_list" above) */ + /* (may use ".sort_priority" from "setup_file_hash" above) */ artwork_new->color = ARTWORKCOLOR(artwork_new); artwork_new->class_desc = getLevelClassDescription(artwork_new); - if (setup_file_list == NULL) /* (after determining ".user_defined") */ + if (setup_file_hash == NULL) /* (after determining ".user_defined") */ { if (artwork_new->name != NULL) free(artwork_new->name); @@ -1784,7 +1875,7 @@ static boolean LoadArtworkInfoFromArtworkConf(TreeInfo **node_first, pushTreeInfo(node_first, artwork_new); - freeSetupFileList(setup_file_list); + freeSetupFileHash(setup_file_hash); free(directory_path); free(filename); @@ -2158,7 +2249,7 @@ char *getSetupLine(struct TokenInfo *token_info, char *prefix, int token_nr) void LoadLevelSetup_LastSeries() { char *filename; - struct SetupFileList *level_setup_list = NULL; + SetupFileHash *level_setup_hash = NULL; /* always start with reliable default values */ leveldir_current = getFirstValidTreeInfoEntry(leveldir_first); @@ -2169,19 +2260,19 @@ void LoadLevelSetup_LastSeries() filename = getPath2(getSetupDir(), LEVELSETUP_FILENAME); - if ((level_setup_list = loadSetupFileList(filename))) + if ((level_setup_hash = loadSetupFileHash(filename))) { char *last_level_series = - getTokenValue(level_setup_list, TOKEN_STR_LAST_LEVEL_SERIES); + getHashEntry(level_setup_hash, TOKEN_STR_LAST_LEVEL_SERIES); leveldir_current = getTreeInfoFromIdentifier(leveldir_first, last_level_series); if (leveldir_current == NULL) leveldir_current = getFirstValidTreeInfoEntry(leveldir_first); - checkSetupFileListIdentifier(level_setup_list, getCookie("LEVELSETUP")); + checkSetupFileHashIdentifier(level_setup_hash, getCookie("LEVELSETUP")); - freeSetupFileList(level_setup_list); + freeSetupFileHash(level_setup_hash); } else Error(ERR_WARN, "using default setup values"); @@ -2273,7 +2364,7 @@ static void checkSeriesInfo() void LoadLevelSetup_SeriesInfo() { char *filename; - struct SetupFileList *level_setup_list = NULL; + SetupFileHash *level_setup_hash = NULL; char *level_subdir = leveldir_current->filename; /* always start with reliable default values */ @@ -2289,11 +2380,11 @@ void LoadLevelSetup_SeriesInfo() filename = getPath2(getLevelSetupDir(level_subdir), LEVELSETUP_FILENAME); - if ((level_setup_list = loadSetupFileList(filename))) + if ((level_setup_hash = loadSetupFileHash(filename))) { char *token_value; - token_value = getTokenValue(level_setup_list, TOKEN_STR_LAST_PLAYED_LEVEL); + token_value = getHashEntry(level_setup_hash, TOKEN_STR_LAST_PLAYED_LEVEL); if (token_value) { @@ -2305,7 +2396,7 @@ void LoadLevelSetup_SeriesInfo() level_nr = leveldir_current->last_level; } - token_value = getTokenValue(level_setup_list, TOKEN_STR_HANDICAP_LEVEL); + token_value = getHashEntry(level_setup_hash, TOKEN_STR_HANDICAP_LEVEL); if (token_value) { @@ -2322,9 +2413,9 @@ void LoadLevelSetup_SeriesInfo() leveldir_current->handicap_level = level_nr; } - checkSetupFileListIdentifier(level_setup_list, getCookie("LEVELSETUP")); + checkSetupFileHashIdentifier(level_setup_hash, getCookie("LEVELSETUP")); - freeSetupFileList(level_setup_list); + freeSetupFileHash(level_setup_hash); } else Error(ERR_WARN, "using default setup values"); diff --git a/src/libgame/setup.h b/src/libgame/setup.h index 618e7cb0..d6c88b29 100644 --- a/src/libgame/setup.h +++ b/src/libgame/setup.h @@ -15,6 +15,7 @@ #define SETUP_H #include "system.h" +#include "hash.h" /* values for setup file handling */ @@ -62,6 +63,25 @@ struct TokenInfo char *text; }; +/* some definitions for list and hash handling */ +typedef struct SetupFileList SetupFileList; +typedef struct hashtable SetupFileHash; + +#define BEGIN_HASH_ITERATION(hash, itr) \ + if (hash != NULL && hashtable_count(hash) > 0) \ + { \ + struct hashtable_itr *itr = hashtable_iterator(hash); \ + do { \ + +#define HASH_ITERATION_TOKEN(itr) ((char *)hashtable_iterator_key(itr)) +#define HASH_ITERATION_VALUE(itr) ((char *)hashtable_iterator_value(itr)) + +#define END_HASH_ITERATION(hash, itr) \ + } while (hashtable_iterator_advance(itr)); \ + free(itr); \ + } \ + + /* sort priorities of level series (also used as level series classes) */ #define LEVELCLASS_TUTORIAL_START 10 #define LEVELCLASS_TUTORIAL_END 99 @@ -206,12 +226,18 @@ int getFileVersionFromCookieString(const char *); boolean checkCookieString(const char *, const char *); char *getFormattedSetupEntry(char *, char *); + void freeSetupFileList(struct SetupFileList *); struct SetupFileList *newSetupFileList(char *, char *); -char *getTokenValue(struct SetupFileList *, char *); -void setTokenValue(struct SetupFileList *, char *, char *); -struct SetupFileList *loadSetupFileList(char *); -void checkSetupFileListIdentifier(struct SetupFileList *, char *); +char *getListEntry(struct SetupFileList *, char *); +void setListEntry(struct SetupFileList *, char *, char *); + +void freeSetupFileHash(SetupFileHash *); +SetupFileHash *newSetupFileHash(); +char *getHashEntry(SetupFileHash *, char *); +void setHashEntry(SetupFileHash *, char *, char *); +SetupFileHash *loadSetupFileHash(char *); +void checkSetupFileHashIdentifier(SetupFileHash *, char *); void setSetupInfo(struct TokenInfo *, int, char *); char *getSetupValue(int, void *); char *getSetupLine(struct TokenInfo *, char *, int); -- 2.34.1