src/localization/fhash.cpp

   1 /*
   2  * $Logfile: /Freespace2/code/localization/fhash.cpp $
   3  * $Revision$
   4  * $Date$
   5  * $Author$
   6  *
   7  *
   8  * $Log$
   9  * Revision 1.1  2002/05/03 03:28:09  root
  10  * Initial revision
  11  *
  12  *
  13  * 5     2/23/99 9:25a Dave
  14  * Stubbed out a bunch of stuff to get cfile and lcl functions in.
  15  *
  16  * 4     12/01/98 4:46p Dave
  17  * Put in targa bitmap support (16 bit).
  18  *
  19  * $NoKeywords: $
  20  */
  21
  22 #include <stdlib.h>
  23 #include <memory.h>
  24 #include <string.h>
  25 #include "pstypes.h"
  26 #include "fhash.h"
  27
  28 // -----------------------------------------------------------------------------------------------
  29 // HASH DEFINES/VARS
  30 //
  31
  32 // hash node
  33 typedef struct fhash_node {
  34         char *str;                                                      // allocated dynamically
  35         int id;                                                         // can be -1
  36         fhash_node *next, *prev;                        // for chaining in an individual hash table entry (non-circular, doubly linked list)
  37 } fhash_node;
  38
  39 // hash table itself (with chained nodes)
  40 #define HASH_TABLE_SIZE                         253                                     // works better when not a power of 2, and is prime
  41 fhash_node *Hash_table_fred[HASH_TABLE_SIZE];
  42
  43 // if the hash table is active
  44 int Fhash_active = 0;
  45
  46
  47 // -----------------------------------------------------------------------------------------------
  48 // HASH FORWARD DECLARATIONS
  49 //
  50
  51 // hash a string. return an index into the hash table where it should be inserted
  52 int fhash_get_hash_index(char *str);
  53
  54 // insert a string into hash table index N, will take care of allocating/chaining everything
  55 void fhash_insert(char *str, int id, int n);
  56
  57
  58 // -----------------------------------------------------------------------------------------------
  59 // HASH FUNCTIONS
  60 //
  61
  62 // initialize the hash table
  63 void fhash_init()
  64 {
  65         memset(Hash_table_fred, 0, sizeof(fhash_node) * HASH_TABLE_SIZE);
  66 }
  67
  68 // set the hash table to be active for parsing
  69 void fhash_activate()
  70 {
  71         Fhash_active = 1;
  72 }
  73
  74 // set the hash table to be inactive for parsing
  75 void fhash_deactivate()
  76 {
  77         Fhash_active = 0;
  78 }
  79
  80 // if the hash table is active
  81 int fhash_active()
  82 {
  83         return Fhash_active;
  84 }
  85
  86 // flush out the hash table, freeing up everything
  87 void fhash_flush()
  88 {
  89         int idx;
  90         fhash_node *moveup, *backup;
  91
  92         // go through each element
  93         for(idx=0; idx<HASH_TABLE_SIZE; idx++){
  94                 if(Hash_table_fred[idx] != NULL){
  95                         moveup = Hash_table_fred[idx];
  96                         while(moveup != NULL){
  97                                 // next element
  98                                 backup = moveup;
  99                                 moveup = moveup->next;
 100
 101                                 // free up this element
 102                                 if(backup->str != NULL){
 103                                         free(backup->str);
 104                                 }
 105                                 free(backup);
 106                         }
 107
 108                         // null this element
 109                         Hash_table_fred[idx] = NULL;
 110                 }
 111         }
 112 }
 113
 114 // add a string with the given id# to the has table
 115 void fhash_add_str(char *str, int id)
 116 {
 117         int hash_index;
 118
 119         // if the hash table isn't active, don't bother
 120         Assert(Fhash_active);
 121         if(!Fhash_active){
 122                 return;
 123         }
 124
 125         // determine where the string goes in the has table
 126         Assert(str != NULL);
 127         if(str == NULL){
 128                 return;
 129         }
 130         hash_index = fhash_get_hash_index(str);
 131
 132         // insert into the hash table
 133         fhash_insert(str, id, hash_index);
 134 }
 135
 136 // determine if the passed string exists in the table
 137 // returns : -2 if the string doesn't exit, or >= -1 as the string id # otherwise
 138 int fhash_string_exists(char *str)
 139 {
 140         int hash_index;
 141         fhash_node *moveup;
 142
 143         Assert(str != NULL);
 144         if(str == NULL){
 145                 return -2;
 146         }
 147
 148         // get the hash index for this string
 149         hash_index = fhash_get_hash_index(str);
 150
 151         // if there are no entries, it doesn't exist
 152         if(Hash_table_fred[hash_index] == NULL){
 153                 return -2;
 154         }
 155
 156         // otherwise compare against all strings in this code
 157         moveup = Hash_table_fred[hash_index];
 158         while(moveup != NULL){
 159                 // do a string compare on this item
 160                 Assert(moveup->str != NULL);
 161                 if(moveup->str != NULL){
 162                         if(!strcmp(moveup->str, str)){
 163                                 return moveup->id;
 164                         }
 165                 }
 166
 167                 // next item
 168                 moveup = moveup->next;
 169         }
 170
 171         // didn't find it
 172         return -2;
 173 }
 174
 175
 176 // -----------------------------------------------------------------------------------------------
 177 // HASH FORWARD DEFINITIONS
 178 //
 179
 180 // hash a string. return an index into the hash table where it should be inserted
 181 int fhash_get_hash_index(char *str)
 182 {
 183         int accum = 0;
 184         int idx, str_len;
 185         int ret;
 186
 187         // add up the string
 188         str_len = strlen(str);
 189         for(idx=0; idx<str_len; idx++){
 190                 accum += str[idx];
 191         }
 192
 193         ret = abs(accum) % 253;
 194         return ret;
 195 }
 196
 197 // insert a string into hash table index N, will take care of allocating/chaining everything
 198 void fhash_insert(char *str, int id, int n)
 199 {
 200         fhash_node *new_node;
 201         fhash_node *moveup;
 202
 203         // allocate the new node
 204         new_node = (fhash_node*)malloc(sizeof(fhash_node));
 205         Assert(new_node);
 206         if(new_node == NULL){
 207                 return;
 208         }
 209
 210         // fill in the node
 211         new_node->str = strdup(str);
 212         new_node->id = id;
 213         new_node->next = NULL;
 214         new_node->prev = NULL;
 215
 216         // if this hash index is NULL, just assign it
 217         if(Hash_table_fred[n] == NULL){
 218                 Hash_table_fred[n] = new_node;
 219         } else {
 220                 moveup = Hash_table_fred[n];
 221                 while(moveup->next != NULL){
 222                         moveup = moveup->next;
 223                 }
 224                 new_node->prev = moveup;
 225                 moveup->next = new_node;
 226         }
 227 }