llstringtable.cpp

Go to the documentation of this file.
00001 
00033 #include "linden_common.h"
00034 
00035 #include "llstringtable.h"
00036 #include "llstl.h"
00037 
00038 LLStringTable gStringTable(32768);
00039 
00040 LLStringTable::LLStringTable(int tablesize)
00041 : mUniqueEntries(0)
00042 {
00043         S32 i;
00044         if (!tablesize)
00045                 tablesize = 4096; // some arbitrary default
00046         // Make sure tablesize is power of 2
00047         for (i = 31; i>0; i--)
00048         {
00049                 if (tablesize & (1<<i))
00050                 {
00051                         if (tablesize >= (3<<(i-1)))
00052                                 tablesize = (1<<(i+1));
00053                         else
00054                                 tablesize = (1<<i);
00055                         break;
00056                 }
00057         }
00058         mMaxEntries = tablesize;
00059 
00060 #if !STRING_TABLE_HASH_MAP
00061         // ALlocate strings
00062         mStringList = new string_list_ptr_t[mMaxEntries];
00063         // Clear strings
00064         for (i = 0; i < mMaxEntries; i++)
00065         {
00066                 mStringList[i] = NULL;
00067         }
00068 #endif
00069 }
00070 
00071 LLStringTable::~LLStringTable()
00072 {
00073 #if !STRING_TABLE_HASH_MAP
00074         if (mStringList)
00075         {
00076                 for (S32 i = 0; i < mMaxEntries; i++)
00077                 {
00078                         if (mStringList[i])
00079                         {
00080                                 string_list_t::iterator iter;
00081                                 for (iter = mStringList[i]->begin(); iter != mStringList[i]->end(); iter++)
00082                                         delete *iter; // *iter = (LLStringTableEntry*)
00083                         }
00084                         delete mStringList[i];
00085                 }
00086                 delete [] mStringList;
00087                 mStringList = NULL;
00088         }
00089 #else
00090         // Need to clean up the string hash
00091         for_each(mStringHash.begin(), mStringHash.end(), DeletePairedPointer());
00092         mStringHash.clear();
00093 #endif
00094 }
00095 
00096 
00097 static U32 hash_my_string(const char *str, int max_entries)
00098 {
00099         U32 retval = 0;
00100 #if 0
00101         while (*str)
00102         {
00103                 retval <<= 1;
00104                 retval += *str++;
00105         }
00106 #else
00107         while (*str)
00108         {
00109                 retval = (retval<<4) + *str;
00110                 U32 x = (retval & 0xf0000000);
00111                 if (x) retval = retval ^ (x>>24);
00112                 retval = retval & (~x);
00113                 str++;
00114         }
00115 #endif
00116         return (retval & (max_entries-1)); // max_entries is gauranteed to be power of 2
00117 }
00118 
00119 char* LLStringTable::checkString(const std::string& str)
00120 {
00121         return checkString(str.c_str());
00122 }
00123 
00124 char* LLStringTable::checkString(const char *str)
00125 {
00126     LLStringTableEntry* entry = checkStringEntry(str);
00127     if (entry)
00128     {
00129         return entry->mString;
00130     }
00131     else
00132     {
00133         return NULL;
00134     }
00135 }
00136 
00137 LLStringTableEntry* LLStringTable::checkStringEntry(const std::string& str)
00138 {
00139     return checkStringEntry(str.c_str());
00140 }
00141 
00142 LLStringTableEntry* LLStringTable::checkStringEntry(const char *str)
00143 {
00144         if (str)
00145         {
00146                 char *ret_val;
00147                 LLStringTableEntry      *entry;
00148                 U32                                     hash_value = hash_my_string(str, mMaxEntries);
00149 #if STRING_TABLE_HASH_MAP
00150 #if 1 // Microsoft
00151                 string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
00152                 string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
00153 #else // stlport
00154                 std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
00155                 string_hash_t::iterator lower = P.first;
00156                 string_hash_t::iterator upper = P.second;
00157 #endif
00158                 for (string_hash_t::iterator iter = lower; iter != upper; iter++)
00159                 {
00160                         entry = iter->second;
00161                         ret_val = entry->mString;
00162                         if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00163                         {
00164                                 return entry;
00165                         }
00166                 }
00167 #else
00168                 string_list_t           *strlist = mStringList[hash_value];
00169                 if (strlist)
00170                 {
00171                         string_list_t::iterator iter;
00172                         for (iter = strlist->begin(); iter != strlist->end(); iter++)
00173                         {
00174                                 entry = *iter;
00175                                 ret_val = entry->mString;
00176                                 if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00177                                 {
00178                                         return entry;
00179                                 }
00180                         }
00181                 }
00182 #endif
00183         }
00184         return NULL;
00185 }
00186 
00187 char* LLStringTable::addString(const std::string& str)
00188 {
00189         //RN: safe to use temporary c_str since string is copied
00190         return addString(str.c_str());
00191 }
00192 
00193 char* LLStringTable::addString(const char *str)
00194 {
00195 
00196     LLStringTableEntry* entry = addStringEntry(str);
00197     if (entry)
00198     {
00199         return entry->mString;
00200     }
00201     else
00202     {
00203         return NULL;
00204     }
00205 }
00206 
00207 LLStringTableEntry* LLStringTable::addStringEntry(const std::string& str)
00208 {
00209     return addStringEntry(str.c_str());
00210 }
00211 
00212 LLStringTableEntry* LLStringTable::addStringEntry(const char *str)
00213 {
00214         if (str)
00215         {
00216                 char *ret_val = NULL;
00217                 LLStringTableEntry      *entry;
00218                 U32                                     hash_value = hash_my_string(str, mMaxEntries);
00219 #if STRING_TABLE_HASH_MAP
00220 #if 1 // Microsoft
00221                 string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
00222                 string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
00223 #else // stlport
00224                 std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
00225                 string_hash_t::iterator lower = P.first;
00226                 string_hash_t::iterator upper = P.second;
00227 #endif
00228                 for (string_hash_t::iterator iter = lower; iter != upper; iter++)
00229                 {
00230                         entry = iter->second;
00231                         ret_val = entry->mString;
00232                         if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00233                         {
00234                                 entry->incCount();
00235                                 return entry;
00236                         }
00237                 }
00238 
00239                 // not found, so add!
00240                 LLStringTableEntry* newentry = new LLStringTableEntry(str);
00241                 ret_val = newentry->mString;
00242                 mStringHash.insert(string_hash_t::value_type(hash_value, newentry));
00243 #else
00244                 string_list_t           *strlist = mStringList[hash_value];
00245 
00246                 if (strlist)
00247                 {
00248                         string_list_t::iterator iter;
00249                         for (iter = strlist->begin(); iter != strlist->end(); iter++)
00250                         {
00251                                 entry = *iter;
00252                                 ret_val = entry->mString;
00253                                 if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00254                                 {
00255                                         entry->incCount();
00256                                         return entry;
00257                                 }
00258                         }
00259                 }
00260                 else
00261                 {
00262                         mStringList[hash_value] = new string_list_t;
00263                         strlist = mStringList[hash_value];
00264                 }
00265 
00266                 // not found, so add!
00267                 LLStringTableEntry *newentry = new LLStringTableEntry(str);
00268                 //ret_val = newentry->mString;
00269                 strlist->push_front(newentry);
00270 #endif
00271                 mUniqueEntries++;
00272                 return newentry;
00273         }
00274         else
00275         {
00276                 return NULL;
00277         }
00278 }
00279 
00280 void LLStringTable::removeString(const char *str)
00281 {
00282         if (str)
00283         {
00284                 char *ret_val;
00285                 LLStringTableEntry      *entry;
00286                 U32                                     hash_value = hash_my_string(str, mMaxEntries);
00287 #if STRING_TABLE_HASH_MAP
00288                 {
00289 #if 1 // Microsoft
00290                         string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
00291                         string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
00292 #else // stlport
00293                         std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
00294                         string_hash_t::iterator lower = P.first;
00295                         string_hash_t::iterator upper = P.second;
00296 #endif
00297                         for (string_hash_t::iterator iter = lower; iter != upper; iter++)
00298                         {
00299                                 entry = iter->second;
00300                                 ret_val = entry->mString;
00301                                 if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00302                                 {
00303                                         if (!entry->decCount())
00304                                         {
00305                                                 mUniqueEntries--;
00306                                                 if (mUniqueEntries < 0)
00307                                                 {
00308                                                         llerror("LLStringTable:removeString trying to remove too many strings!", 0);
00309                                                 }
00310                                                 delete iter->second;
00311                                                 mStringHash.erase(iter);
00312                                         }
00313                                         return;
00314                                 }
00315                         }
00316                 }
00317 #else
00318                 string_list_t           *strlist = mStringList[hash_value];
00319 
00320                 if (strlist)
00321                 {
00322                         string_list_t::iterator iter;
00323                         for (iter = strlist->begin(); iter != strlist->end(); iter++)
00324                         {
00325                                 entry = *iter;
00326                                 ret_val = entry->mString;
00327                                 if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
00328                                 {
00329                                         if (!entry->decCount())
00330                                         {
00331                                                 mUniqueEntries--;
00332                                                 if (mUniqueEntries < 0)
00333                                                 {
00334                                                         llerror("LLStringTable:removeString trying to remove too many strings!", 0);
00335                                                 }
00336                                                 strlist->remove(entry);
00337                                                 delete entry;
00338                                         }
00339                                         return;
00340                                 }
00341                         }
00342                 }
00343 #endif
00344         }
00345 }
00346 

Generated on Thu Jul 1 06:09:14 2010 for Second Life Viewer by  doxygen 1.4.7