stringTable.cpp

Public Variables

_StringTable *

_gStringTable 

Public Variables

_StringTable * _gStringTable 

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#include "core/strings/stringFunctions.h"
 25#include "core/stringTable.h"
 26#include "platform/profiler.h"
 27
 28_StringTable *_gStringTable = NULL;
 29const U32 _StringTable::csm_stInitSize = 29;
 30
 31//---------------------------------------------------------------
 32//
 33// StringTable functions
 34//
 35//---------------------------------------------------------------
 36
 37namespace {
 38bool sgInitTable = true;
 39U8   sgHashTable[256];
 40
 41void initTolowerTable()
 42{
 43   for (U32 i = 0; i < 256; i++) {
 44      U8 c = dTolower(i);
 45      sgHashTable[i] = c * c;
 46   }
 47
 48   sgInitTable = false;
 49}
 50
 51} // namespace {}
 52
 53U32 _StringTable::hashString(const char* str)
 54{
 55   if (sgInitTable)
 56      initTolowerTable();
 57
 58   if(!str) return -1;
 59
 60   U32 ret = 0;
 61   char c;
 62   while((c = *str++) != 0) {
 63      ret <<= 1;
 64      ret ^= sgHashTable[static_cast<U8>(c)];
 65   }
 66   return ret;
 67}
 68
 69U32 _StringTable::hashStringn(const char* str, S32 len)
 70{
 71   if (sgInitTable)
 72      initTolowerTable();
 73
 74   U32 ret = 0;
 75   char c;
 76   while((c = *str++) != 0 && len--) {
 77      ret <<= 1;
 78      ret ^= sgHashTable[static_cast<U8>(c)];
 79   }
 80   return ret;
 81}
 82
 83//--------------------------------------
 84_StringTable::_StringTable()
 85{
 86   buckets = (Node **) dMalloc(csm_stInitSize * sizeof(Node *));
 87   for(U32 i = 0; i < csm_stInitSize; i++) {
 88      buckets[i] = 0;
 89   }
 90
 91   numBuckets = csm_stInitSize;
 92   itemCount = 0;
 93}
 94
 95//--------------------------------------
 96_StringTable::~_StringTable()
 97{
 98   dFree(buckets);
 99}
100
101
102//--------------------------------------
103void _StringTable::create()
104{
105   //AssertFatal(_gStringTable == NULL, "StringTable::create: StringTable already exists.");
106   if(!_gStringTable)
107   {
108      _gStringTable = new _StringTable;
109      _gStringTable->_EmptyString = _gStringTable->insert("");
110   }
111}
112
113
114//--------------------------------------
115void _StringTable::destroy()
116{
117   AssertFatal(StringTable != NULL, "StringTable::destroy: StringTable does not exist.");
118   delete _gStringTable;
119   _gStringTable = NULL;
120}
121
122
123//--------------------------------------
124StringTableEntry _StringTable::insert(const char* _val, const bool caseSens)
125{
126   PROFILE_SCOPE(StringTableInsert);
127
128   // Added 3/29/2007 -- If this is undesirable behavior, let me know -patw
129   const char *val = _val;
130   if( val == NULL )
131      val = "";
132   //-
133
134   Node **walk, *temp;
135   U32 key = hashString(val);
136   walk = &buckets[key % numBuckets];
137   while((temp = *walk) != NULL)   {
138      if(caseSens && !String::compare(temp->val, val))
139         return temp->val;
140      else if(!caseSens && !dStricmp(temp->val, val))
141         return temp->val;
142      walk = &(temp->next);
143   }
144   char *ret = 0;
145   if(!*walk) {
146      dsize_t valLen = dStrlen(val) + 1;
147      *walk = (Node *) mempool.alloc(sizeof(Node));
148      (*walk)->next = 0;
149      (*walk)->val = (char *) mempool.alloc(valLen);
150      dStrcpy((*walk)->val, val, valLen);
151      ret = (*walk)->val;
152      itemCount ++;
153   }
154   if(itemCount > 2 * numBuckets) {
155      resize(4 * numBuckets - 1);
156   }
157   return ret;
158}
159
160//--------------------------------------
161StringTableEntry _StringTable::insertn(const char* src, S32 len, const bool  caseSens)
162{
163   char val[256];
164   AssertFatal(len < 255, "Invalid string to insertn");
165   dStrncpy(val, src, len);
166   val[len] = 0;
167   return insert(val, caseSens);
168}
169
170//--------------------------------------
171StringTableEntry _StringTable::lookup(const char* val, const bool  caseSens)
172{
173   PROFILE_SCOPE(StringTableLookup);
174
175   Node **walk, *temp;
176   U32 key = hashString(val);
177   walk = &buckets[key % numBuckets];
178   while((temp = *walk) != NULL)   {
179      if(caseSens && !String::compare(temp->val, val))
180            return temp->val;
181      else if(!caseSens && !dStricmp(temp->val, val))
182         return temp->val;
183      walk = &(temp->next);
184   }
185   return NULL;
186}
187
188//--------------------------------------
189StringTableEntry _StringTable::lookupn(const char* val, S32 len, const bool  caseSens)
190{
191   PROFILE_SCOPE(StringTableLookupN);
192
193   Node **walk, *temp;
194   U32 key = hashStringn(val, len);
195   walk = &buckets[key % numBuckets];
196   while((temp = *walk) != NULL) {
197      if(caseSens && !dStrncmp(temp->val, val, len) && temp->val[len] == 0)
198         return temp->val;
199      else if(!caseSens && !dStrnicmp(temp->val, val, len) && temp->val[len] == 0)
200         return temp->val;
201      walk = &(temp->next);
202   }
203   return NULL;
204}
205
206//--------------------------------------
207void _StringTable::resize(const U32 _newSize)
208{
209   /// avoid a possible 0 division
210   const U32 newSize = _newSize ? _newSize : 1;
211
212   Node *head = NULL, *walk, *temp;
213   U32 i;
214   // reverse individual bucket lists
215   // we do this because new strings are added at the end of bucket
216   // lists so that case sens strings are always after their
217   // corresponding case insens strings
218
219   for(i = 0; i < numBuckets; i++) {
220      walk = buckets[i];
221      while(walk)
222      {
223         temp = walk->next;
224         walk->next = head;
225         head = walk;
226         walk = temp;
227      }
228   }
229   buckets = (Node **) dRealloc(buckets, newSize * sizeof(Node));
230   for(i = 0; i < newSize; i++) {
231      buckets[i] = 0;
232   }
233   numBuckets = newSize;
234   walk = head;
235   while(walk) {
236      U32 key;
237      temp = walk;
238
239      walk = walk->next;
240      key = hashString(temp->val);
241      temp->next = buckets[key % newSize];
242      buckets[key % newSize] = temp;
243   }
244}
245
246