src/localization/fhash.cpp

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