stringTable.cpp

Public Variables

_StringTable *

_gStringTable

Detailed Description

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 && !dStrcmp(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      *walk = (Node *) mempool.alloc(sizeof(Node));
147      (*walk)->next = 0;
148      (*walk)->val = (char *) mempool.alloc(dStrlen(val) + 1);
149      dStrcpy((*walk)->val, val);
150      ret = (*walk)->val;
151      itemCount ++;
152   }
153   if(itemCount > 2 * numBuckets) {
154      resize(4 * numBuckets - 1);
155   }
156   return ret;
157}
158
159//--------------------------------------
160StringTableEntry _StringTable::insertn(const char* src, S32 len, const bool  caseSens)
161{
162   char val[256];
163   AssertFatal(len < 255, "Invalid string to insertn");
164   dStrncpy(val, src, len);
165   val[len] = 0;
166   return insert(val, caseSens);
167}
168
169//--------------------------------------
170StringTableEntry _StringTable::lookup(const char* val, const bool  caseSens)
171{
172   PROFILE_SCOPE(StringTableLookup);
173
174   Node **walk, *temp;
175   U32 key = hashString(val);
176   walk = &buckets[key % numBuckets];
177   while((temp = *walk) != NULL)   {
178      if(caseSens && !dStrcmp(temp->val, val))
179            return temp->val;
180      else if(!caseSens && !dStricmp(temp->val, val))
181         return temp->val;
182      walk = &(temp->next);
183   }
184   return NULL;
185}
186
187//--------------------------------------
188StringTableEntry _StringTable::lookupn(const char* val, S32 len, const bool  caseSens)
189{
190   PROFILE_SCOPE(StringTableLookupN);
191
192   Node **walk, *temp;
193   U32 key = hashStringn(val, len);
194   walk = &buckets[key % numBuckets];
195   while((temp = *walk) != NULL) {
196      if(caseSens && !dStrncmp(temp->val, val, len) && temp->val[len] == 0)
197         return temp->val;
198      else if(!caseSens && !dStrnicmp(temp->val, val, len) && temp->val[len] == 0)
199         return temp->val;
200      walk = &(temp->next);
201   }
202   return NULL;
203}
204
205//--------------------------------------
206void _StringTable::resize(const U32 _newSize)
207{
208   /// avoid a possible 0 division
209   const U32 newSize = _newSize ? _newSize : 1;
210
211   Node *head = NULL, *walk, *temp;
212   U32 i;
213   // reverse individual bucket lists
214   // we do this because new strings are added at the end of bucket
215   // lists so that case sens strings are always after their
216   // corresponding case insens strings
217
218   for(i = 0; i < numBuckets; i++) {
219      walk = buckets[i];
220      while(walk)
221      {
222         temp = walk->next;
223         walk->next = head;
224         head = walk;
225         walk = temp;
226      }
227   }
228   buckets = (Node **) dRealloc(buckets, newSize * sizeof(Node));
229   for(i = 0; i < newSize; i++) {
230      buckets[i] = 0;
231   }
232   numBuckets = newSize;
233   walk = head;
234   while(walk) {
235      U32 key;
236      Node *temp = walk;
237
238      walk = walk->next;
239      key = hashString(temp->val);
240      temp->next = buckets[key % newSize];
241      buckets[key % newSize] = temp;
242   }
243}
244
245