llstringtable.cpp
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:9k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file llstringtable.cpp
  3.  * @brief The LLStringTable class provides a _fast_ method for finding
  4.  * unique copies of strings.
  5.  *
  6.  * $LicenseInfo:firstyear=2001&license=viewergpl$
  7.  * 
  8.  * Copyright (c) 2001-2010, Linden Research, Inc.
  9.  * 
  10.  * Second Life Viewer Source Code
  11.  * The source code in this file ("Source Code") is provided by Linden Lab
  12.  * to you under the terms of the GNU General Public License, version 2.0
  13.  * ("GPL"), unless you have obtained a separate licensing agreement
  14.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  15.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  16.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  17.  * 
  18.  * There are special exceptions to the terms and conditions of the GPL as
  19.  * it is applied to this Source Code. View the full text of the exception
  20.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  21.  * online at
  22.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  23.  * 
  24.  * By copying, modifying or distributing this software, you acknowledge
  25.  * that you have read and understood your obligations described above,
  26.  * and agree to abide by those obligations.
  27.  * 
  28.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  29.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  30.  * COMPLETENESS OR PERFORMANCE.
  31.  * $/LicenseInfo$
  32.  */
  33. #include "linden_common.h"
  34. #include "llstringtable.h"
  35. #include "llstl.h"
  36. LLStringTable gStringTable(32768);
  37. LLStringTableEntry::LLStringTableEntry(const char *str)
  38. : mString(NULL), mCount(1)
  39. {
  40. // Copy string
  41. U32 length = (U32)strlen(str) + 1;  /*Flawfinder: ignore*/
  42. length = llmin(length, MAX_STRINGS_LENGTH);
  43. mString = new char[length];
  44. strncpy(mString, str, length);  /*Flawfinder: ignore*/
  45. mString[length - 1] = 0;
  46. }
  47. LLStringTableEntry::~LLStringTableEntry()
  48. {
  49. delete [] mString;
  50. mCount = 0;
  51. }
  52. LLStringTable::LLStringTable(int tablesize)
  53. : mUniqueEntries(0)
  54. {
  55. S32 i;
  56. if (!tablesize)
  57. tablesize = 4096; // some arbitrary default
  58. // Make sure tablesize is power of 2
  59. for (i = 31; i>0; i--)
  60. {
  61. if (tablesize & (1<<i))
  62. {
  63. if (tablesize >= (3<<(i-1)))
  64. tablesize = (1<<(i+1));
  65. else
  66. tablesize = (1<<i);
  67. break;
  68. }
  69. }
  70. mMaxEntries = tablesize;
  71. #if !STRING_TABLE_HASH_MAP
  72. // ALlocate strings
  73. mStringList = new string_list_ptr_t[mMaxEntries];
  74. // Clear strings
  75. for (i = 0; i < mMaxEntries; i++)
  76. {
  77. mStringList[i] = NULL;
  78. }
  79. #endif
  80. }
  81. LLStringTable::~LLStringTable()
  82. {
  83. #if !STRING_TABLE_HASH_MAP
  84. if (mStringList)
  85. {
  86. for (S32 i = 0; i < mMaxEntries; i++)
  87. {
  88. if (mStringList[i])
  89. {
  90. string_list_t::iterator iter;
  91. for (iter = mStringList[i]->begin(); iter != mStringList[i]->end(); iter++)
  92. delete *iter; // *iter = (LLStringTableEntry*)
  93. }
  94. delete mStringList[i];
  95. }
  96. delete [] mStringList;
  97. mStringList = NULL;
  98. }
  99. #else
  100. // Need to clean up the string hash
  101. for_each(mStringHash.begin(), mStringHash.end(), DeletePairedPointer());
  102. mStringHash.clear();
  103. #endif
  104. }
  105. static U32 hash_my_string(const char *str, int max_entries)
  106. {
  107. U32 retval = 0;
  108. #if 0
  109. while (*str)
  110. {
  111. retval <<= 1;
  112. retval += *str++;
  113. }
  114. #else
  115. while (*str)
  116. {
  117. retval = (retval<<4) + *str;
  118. U32 x = (retval & 0xf0000000);
  119. if (x) retval = retval ^ (x>>24);
  120. retval = retval & (~x);
  121. str++;
  122. }
  123. #endif
  124. return (retval & (max_entries-1)); // max_entries is gauranteed to be power of 2
  125. }
  126. char* LLStringTable::checkString(const std::string& str)
  127. {
  128. return checkString(str.c_str());
  129. }
  130. char* LLStringTable::checkString(const char *str)
  131. {
  132.     LLStringTableEntry* entry = checkStringEntry(str);
  133.     if (entry)
  134.     {
  135. return entry->mString;
  136.     }
  137.     else
  138.     {
  139. return NULL;
  140.     }
  141. }
  142. LLStringTableEntry* LLStringTable::checkStringEntry(const std::string& str)
  143. {
  144.     return checkStringEntry(str.c_str());
  145. }
  146. LLStringTableEntry* LLStringTable::checkStringEntry(const char *str)
  147. {
  148. if (str)
  149. {
  150. char *ret_val;
  151. LLStringTableEntry *entry;
  152. U32 hash_value = hash_my_string(str, mMaxEntries);
  153. #if STRING_TABLE_HASH_MAP
  154. #if 1 // Microsoft
  155. string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
  156. string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
  157. #else // stlport
  158. std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
  159. string_hash_t::iterator lower = P.first;
  160. string_hash_t::iterator upper = P.second;
  161. #endif
  162. for (string_hash_t::iterator iter = lower; iter != upper; iter++)
  163. {
  164. entry = iter->second;
  165. ret_val = entry->mString;
  166. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  167. {
  168. return entry;
  169. }
  170. }
  171. #else
  172. string_list_t *strlist = mStringList[hash_value];
  173. if (strlist)
  174. {
  175. string_list_t::iterator iter;
  176. for (iter = strlist->begin(); iter != strlist->end(); iter++)
  177. {
  178. entry = *iter;
  179. ret_val = entry->mString;
  180. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  181. {
  182. return entry;
  183. }
  184. }
  185. }
  186. #endif
  187. }
  188. return NULL;
  189. }
  190. char* LLStringTable::addString(const std::string& str)
  191. {
  192. //RN: safe to use temporary c_str since string is copied
  193. return addString(str.c_str());
  194. }
  195. char* LLStringTable::addString(const char *str)
  196. {
  197.     LLStringTableEntry* entry = addStringEntry(str);
  198.     if (entry)
  199.     {
  200. return entry->mString;
  201.     }
  202.     else
  203.     {
  204. return NULL;
  205.     }
  206. }
  207. LLStringTableEntry* LLStringTable::addStringEntry(const std::string& str)
  208. {
  209.     return addStringEntry(str.c_str());
  210. }
  211. LLStringTableEntry* LLStringTable::addStringEntry(const char *str)
  212. {
  213. if (str)
  214. {
  215. char *ret_val = NULL;
  216. LLStringTableEntry *entry;
  217. U32 hash_value = hash_my_string(str, mMaxEntries);
  218. #if STRING_TABLE_HASH_MAP
  219. #if 1 // Microsoft
  220. string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
  221. string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
  222. #else // stlport
  223. std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
  224. string_hash_t::iterator lower = P.first;
  225. string_hash_t::iterator upper = P.second;
  226. #endif
  227. for (string_hash_t::iterator iter = lower; iter != upper; iter++)
  228. {
  229. entry = iter->second;
  230. ret_val = entry->mString;
  231. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  232. {
  233. entry->incCount();
  234. return entry;
  235. }
  236. }
  237. // not found, so add!
  238. LLStringTableEntry* newentry = new LLStringTableEntry(str);
  239. ret_val = newentry->mString;
  240. mStringHash.insert(string_hash_t::value_type(hash_value, newentry));
  241. #else
  242. string_list_t *strlist = mStringList[hash_value];
  243. if (strlist)
  244. {
  245. string_list_t::iterator iter;
  246. for (iter = strlist->begin(); iter != strlist->end(); iter++)
  247. {
  248. entry = *iter;
  249. ret_val = entry->mString;
  250. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  251. {
  252. entry->incCount();
  253. return entry;
  254. }
  255. }
  256. }
  257. else
  258. {
  259. mStringList[hash_value] = new string_list_t;
  260. strlist = mStringList[hash_value];
  261. }
  262. // not found, so add!
  263. LLStringTableEntry *newentry = new LLStringTableEntry(str);
  264. //ret_val = newentry->mString;
  265. strlist->push_front(newentry);
  266. #endif
  267. mUniqueEntries++;
  268. return newentry;
  269. }
  270. else
  271. {
  272. return NULL;
  273. }
  274. }
  275. void LLStringTable::removeString(const char *str)
  276. {
  277. if (str)
  278. {
  279. char *ret_val;
  280. LLStringTableEntry *entry;
  281. U32 hash_value = hash_my_string(str, mMaxEntries);
  282. #if STRING_TABLE_HASH_MAP
  283. {
  284. #if 1 // Microsoft
  285. string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
  286. string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
  287. #else // stlport
  288. std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
  289. string_hash_t::iterator lower = P.first;
  290. string_hash_t::iterator upper = P.second;
  291. #endif
  292. for (string_hash_t::iterator iter = lower; iter != upper; iter++)
  293. {
  294. entry = iter->second;
  295. ret_val = entry->mString;
  296. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  297. {
  298. if (!entry->decCount())
  299. {
  300. mUniqueEntries--;
  301. if (mUniqueEntries < 0)
  302. {
  303. llerror("LLStringTable:removeString trying to remove too many strings!", 0);
  304. }
  305. delete iter->second;
  306. mStringHash.erase(iter);
  307. }
  308. return;
  309. }
  310. }
  311. }
  312. #else
  313. string_list_t *strlist = mStringList[hash_value];
  314. if (strlist)
  315. {
  316. string_list_t::iterator iter;
  317. for (iter = strlist->begin(); iter != strlist->end(); iter++)
  318. {
  319. entry = *iter;
  320. ret_val = entry->mString;
  321. if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
  322. {
  323. if (!entry->decCount())
  324. {
  325. mUniqueEntries--;
  326. if (mUniqueEntries < 0)
  327. {
  328. llerror("LLStringTable:removeString trying to remove too many strings!", 0);
  329. }
  330. strlist->remove(entry);
  331. delete entry;
  332. }
  333. return;
  334. }
  335. }
  336. }
  337. #endif
  338. }
  339. }