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

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file lluuidhashmap.h
  3.  * @brief A uuid based hash map.
  4.  *
  5.  * $LicenseInfo:firstyear=2003&license=viewergpl$
  6.  * 
  7.  * Copyright (c) 2003-2010, Linden Research, Inc.
  8.  * 
  9.  * Second Life Viewer Source Code
  10.  * The source code in this file ("Source Code") is provided by Linden Lab
  11.  * to you under the terms of the GNU General Public License, version 2.0
  12.  * ("GPL"), unless you have obtained a separate licensing agreement
  13.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  14.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  15.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  16.  * 
  17.  * There are special exceptions to the terms and conditions of the GPL as
  18.  * it is applied to this Source Code. View the full text of the exception
  19.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  20.  * online at
  21.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  22.  * 
  23.  * By copying, modifying or distributing this software, you acknowledge
  24.  * that you have read and understood your obligations described above,
  25.  * and agree to abide by those obligations.
  26.  * 
  27.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  28.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  29.  * COMPLETENESS OR PERFORMANCE.
  30.  * $/LicenseInfo$
  31.  */
  32. #ifndef LL_LLUUIDHASHMAP_H
  33. #define LL_LLUUIDHASHMAP_H
  34. #include "stdtypes.h"
  35. #include "llerror.h"
  36. #include "lluuid.h"
  37. // UUID hash map
  38. /*
  39. LLUUIDHashMap<uuid_pair, 32> foo(test_equals);
  40. LLUUIDHashMapIter<uuid_pair, 32> bar(&foo);
  41. LLDynamicArray<LLUUID> source_ids;
  42. const S32 COUNT = 100000;
  43. S32 q;
  44. for (q = 0; q < COUNT; q++)
  45. {
  46. llinfos << "Creating" << llendl;
  47. LLUUID id;
  48. id.generate();
  49. //llinfos << q << ":" << id << llendl;
  50. uuid_pair pair;
  51. pair.mUUID = id;
  52. pair.mValue = q;
  53. foo.set(id, pair);
  54. source_ids.put(id);
  55. //ms_sleep(1);
  56. }
  57. uuid_pair cur;
  58. llinfos << "Iterating" << llendl;
  59. for (cur = bar.first(); !bar.done(); cur = bar.next())
  60. {
  61. if (source_ids[cur.mValue] != cur.mUUID)
  62. {
  63. llerrs << "Incorrect value iterated!" << llendl;
  64. }
  65. //llinfos << cur.mValue << ":" << cur.mUUID << llendl;
  66. //ms_sleep(1);
  67. }
  68. llinfos << "Finding" << llendl;
  69. for (q = 0; q < COUNT; q++)
  70. {
  71. cur = foo.get(source_ids[q]);
  72. if (source_ids[cur.mValue] != cur.mUUID)
  73. {
  74. llerrs << "Incorrect value found!" << llendl;
  75. }
  76. //llinfos << res.mValue << ":" << res.mUUID << llendl;
  77. //ms_sleep(1);
  78. }
  79. llinfos << "Removing" << llendl;
  80. for (q = 0; q < COUNT/2; q++)
  81. {
  82. if (!foo.remove(source_ids[q]))
  83. {
  84. llerrs << "Remove failed!" << llendl;
  85. }
  86. //ms_sleep(1);
  87. }
  88. llinfos << "Iterating" << llendl;
  89. for (cur = bar.first(); !bar.done(); cur = bar.next())
  90. {
  91. if (source_ids[cur.mValue] != cur.mUUID)
  92. {
  93. llerrs << "Incorrect value found!" << llendl;
  94. }
  95. //llinfos << cur.mValue << ":" << cur.mUUID << llendl;
  96. //ms_sleep(1);
  97. }
  98. llinfos << "Done with UUID map test" << llendl;
  99. return 0;
  100. */
  101. //
  102. // LLUUIDHashNode
  103. //
  104. template <class DATA, int SIZE>
  105. class LLUUIDHashNode
  106. {
  107. public:
  108. LLUUIDHashNode();
  109. public:
  110. S32 mCount;
  111. U8 mKey[SIZE];
  112. DATA mData[SIZE];
  113. LLUUIDHashNode<DATA, SIZE> *mNextNodep;
  114. };
  115. //
  116. // LLUUIDHashNode implementation
  117. //
  118. template <class DATA, int SIZE>
  119. LLUUIDHashNode<DATA, SIZE>::LLUUIDHashNode()
  120. {
  121. mCount = 0;
  122. mNextNodep = NULL;
  123. }
  124. template <class DATA_TYPE, int SIZE>
  125. class LLUUIDHashMap
  126. {
  127. public:
  128. // basic constructor including sorter
  129. LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data),
  130.   const DATA_TYPE &null_data);
  131. ~LLUUIDHashMap();
  132. inline DATA_TYPE &get(const LLUUID &uuid);
  133. inline BOOL check(const LLUUID &uuid) const;
  134. inline DATA_TYPE &set(const LLUUID &uuid, const DATA_TYPE &type);
  135. inline BOOL remove(const LLUUID &uuid);
  136. void removeAll();
  137. inline S32 getLength() const; // Warning, NOT O(1!)
  138. public:
  139. BOOL (*mEquals)(const LLUUID &uuid, const DATA_TYPE &data);
  140. LLUUIDHashNode<DATA_TYPE, SIZE> mNodes[256];
  141. S32 mIterCount;
  142. protected:
  143. DATA_TYPE mNull;
  144. };
  145. //
  146. // LLUUIDHashMap implementation
  147. //
  148. template <class DATA_TYPE, int SIZE>
  149. LLUUIDHashMap<DATA_TYPE, SIZE>::LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data),
  150.   const DATA_TYPE &null_data)
  151. : mEquals(equals),
  152. mIterCount(0),
  153. mNull(null_data)
  154. { }
  155. template <class DATA_TYPE, int SIZE>
  156. LLUUIDHashMap<DATA_TYPE, SIZE>::~LLUUIDHashMap()
  157. {
  158. removeAll();
  159. }
  160. template <class DATA_TYPE, int SIZE>
  161. void LLUUIDHashMap<DATA_TYPE, SIZE>::removeAll()
  162. {
  163. S32 bin;
  164. for (bin = 0; bin < 256; bin++)
  165. {
  166. LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin];
  167. BOOL first = TRUE;
  168. while (nodep)
  169. {
  170. S32 i;
  171. const S32 count = nodep->mCount;
  172. // Iterate through all members of this node
  173. for (i = 0; i < count; i++)
  174. {
  175. nodep->mData[i] = mNull;
  176. }
  177. nodep->mCount = 0;
  178. // Done with all objects in this node, go to the next.
  179. LLUUIDHashNode<DATA_TYPE, SIZE>* curp = nodep;
  180. nodep = nodep->mNextNodep;
  181. // Delete the node if it's not the first node
  182. if (first)
  183. {
  184. first = FALSE;
  185. curp->mNextNodep = NULL;
  186. }
  187. else
  188. {
  189. delete curp;
  190. }
  191. }
  192. }
  193. }
  194. template <class DATA_TYPE, int SIZE>
  195. inline S32 LLUUIDHashMap<DATA_TYPE, SIZE>::getLength() const
  196. {
  197. S32 count = 0;
  198. S32 bin;
  199. for (bin = 0; bin < 256; bin++)
  200. {
  201. LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = (LLUUIDHashNode<DATA_TYPE, SIZE>*) &mNodes[bin];
  202. while (nodep)
  203. {
  204. count += nodep->mCount;
  205. nodep = nodep->mNextNodep;
  206. }
  207. }
  208. return count;
  209. }
  210. template <class DATA_TYPE, int SIZE>
  211. inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::get(const LLUUID &uuid)
  212. {
  213. LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]];
  214. // Grab the second byte of the UUID, which is the key for the node data
  215. const S32 second_byte = uuid.mData[1];
  216. while (nodep)
  217. {
  218. S32 i;
  219. const S32 count = nodep->mCount;
  220. // Iterate through all members of this node
  221. for (i = 0; i < count; i++)
  222. {
  223. if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i]))
  224. {
  225. // The second byte matched, and our equality test passed.
  226. // We found it.
  227. return nodep->mData[i];
  228. }
  229. }
  230. // Done with all objects in this node, go to the next.
  231. nodep = nodep->mNextNodep;
  232. }
  233. return mNull;
  234. }
  235. template <class DATA_TYPE, int SIZE>
  236. inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::check(const LLUUID &uuid) const
  237. {
  238. const LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]];
  239. // Grab the second byte of the UUID, which is the key for the node data
  240. const S32 second_byte = uuid.mData[1];
  241. while (nodep)
  242. {
  243. S32 i;
  244. const S32 count = nodep->mCount;
  245. // Iterate through all members of this node
  246. for (i = 0; i < count; i++)
  247. {
  248. if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i]))
  249. {
  250. // The second byte matched, and our equality test passed.
  251. // We found it.
  252. return TRUE;
  253. }
  254. }
  255. // Done with all objects in this node, go to the next.
  256. nodep = nodep->mNextNodep;
  257. }
  258. // Didn't find anything
  259. return FALSE;
  260. }
  261. template <class DATA_TYPE, int SIZE>
  262. inline DATA_TYPE &LLUUIDHashMap<DATA_TYPE, SIZE>::set(const LLUUID &uuid, const DATA_TYPE &data)
  263. {
  264. // Set is just like a normal find, except that if we find a match
  265. // we replace it with the input value.
  266. // If we don't find a match, we append to the end of the list.
  267. LLUUIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[uuid.mData[0]];
  268. const S32 second_byte = uuid.mData[1];
  269. while (1)
  270. {
  271. const S32 count = nodep->mCount;
  272. S32 i;
  273. for (i = 0; i < count; i++)
  274. {
  275. if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i]))
  276. {
  277. // We found a match for this key, replace the data with
  278. // the incoming data.
  279. nodep->mData[i] = data;
  280. return nodep->mData[i];
  281. }
  282. }
  283. if (!nodep->mNextNodep)
  284. {
  285. // We've iterated through all of the keys without finding a match
  286. if (i < SIZE)
  287. {
  288. // There's still some space on this node, append
  289. // the key and data to it.
  290. nodep->mKey[i] = second_byte;
  291. nodep->mData[i] = data;
  292. nodep->mCount++;
  293. return nodep->mData[i];
  294. }
  295. else
  296. {
  297. // This node is full, append a new node to the end.
  298. nodep->mNextNodep = new LLUUIDHashNode<DATA_TYPE, SIZE>;
  299. nodep->mNextNodep->mKey[0] = second_byte;
  300. nodep->mNextNodep->mData[0] = data;
  301. nodep->mNextNodep->mCount = 1;
  302. return nodep->mNextNodep->mData[0];
  303. }
  304. }
  305. // No match on this node, go to the next
  306. nodep = nodep->mNextNodep;
  307. }
  308. }
  309. template <class DATA_TYPE, int SIZE>
  310. inline BOOL LLUUIDHashMap<DATA_TYPE, SIZE>::remove(const LLUUID &uuid)
  311. {
  312. if (mIterCount)
  313. {
  314. // We don't allow remove when we're iterating, it's bad karma!
  315. llerrs << "Attempted remove while an outstanding iterator in LLUUIDHashMap!" << llendl;
  316. }
  317. // Remove is the trickiest operation.
  318. // What we want to do is swap the last element of the last
  319. // node if we find the one that we want to remove, but we have
  320. // to deal with deleting the node from the tail if it's empty, but
  321. // NOT if it's the only node left.
  322. LLUUIDHashNode<DATA_TYPE, SIZE> *nodep = &mNodes[uuid.mData[0]];
  323. // Not empty, we need to search through the nodes
  324. const S32 second_byte = uuid.mData[1];
  325. // A modification of the standard search algorithm.
  326. while (nodep)
  327. {
  328. const S32 count = nodep->mCount;
  329. S32 i;
  330. for (i = 0; i < count; i++)
  331. {
  332. if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i]))
  333. {
  334. // We found the node that we want to remove.
  335. // Find the last (and next-to-last) node, and the index of the last
  336. // element.  We could conceviably start from the node we're on,
  337. // but that makes it more complicated, this is easier.
  338. LLUUIDHashNode<DATA_TYPE, SIZE> *prevp = &mNodes[uuid.mData[0]];
  339. LLUUIDHashNode<DATA_TYPE, SIZE> *lastp = prevp;
  340. // Find the last and next-to-last
  341. while (lastp->mNextNodep)
  342. {
  343. prevp = lastp;
  344. lastp = lastp->mNextNodep;
  345. }
  346. // First, swap in the last to the current location.
  347. nodep->mKey[i] = lastp->mKey[lastp->mCount - 1];
  348. nodep->mData[i] = lastp->mData[lastp->mCount - 1];
  349. // Now, we delete the entry
  350. lastp->mCount--;
  351. lastp->mData[lastp->mCount] = mNull;
  352. if (!lastp->mCount)
  353. {
  354. // We deleted the last element!
  355. if (lastp != &mNodes[uuid.mData[0]])
  356. {
  357. // Only blitz the node if it's not the head
  358. // Set the previous node to point to NULL, then
  359. // blitz the empty last node
  360. prevp->mNextNodep = NULL;
  361. delete lastp;
  362. }
  363. }
  364. return TRUE;
  365. }
  366. }
  367. // Iterate to the next node, we've scanned all the entries in this one.
  368. nodep = nodep->mNextNodep;
  369. }
  370. return FALSE;
  371. }
  372. //
  373. // LLUUIDHashMapIter
  374. //
  375. template <class DATA_TYPE, int SIZE>
  376. class LLUUIDHashMapIter
  377. {
  378. public:
  379. LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp);
  380. ~LLUUIDHashMapIter();
  381. inline void reset();
  382. inline void first();
  383. inline void next();
  384. inline BOOL done() const;
  385. DATA_TYPE& operator*() const
  386. {
  387. return mCurHashNodep->mData[mCurHashNodeKey];
  388. }
  389. DATA_TYPE* operator->() const
  390. {
  391. return &(operator*());
  392. }
  393. protected:
  394. LLUUIDHashMap<DATA_TYPE, SIZE> *mHashMapp;
  395. LLUUIDHashNode<DATA_TYPE, SIZE> *mCurHashNodep;
  396. S32 mCurHashMapNodeNum;
  397. S32 mCurHashNodeKey;
  398. DATA_TYPE mNull;
  399. };
  400. //
  401. // LLUUIDHashMapIter Implementation
  402. //
  403. template <class DATA_TYPE, int SIZE>
  404. LLUUIDHashMapIter<DATA_TYPE, SIZE>::LLUUIDHashMapIter(LLUUIDHashMap<DATA_TYPE, SIZE> *hash_mapp)
  405. {
  406. mHashMapp = hash_mapp;
  407. mCurHashNodep = NULL;
  408. mCurHashMapNodeNum = 0;
  409. mCurHashNodeKey = 0;
  410. }
  411. template <class DATA_TYPE, int SIZE>
  412. LLUUIDHashMapIter<DATA_TYPE, SIZE>::~LLUUIDHashMapIter()
  413. {
  414. reset();
  415. }
  416. template <class DATA_TYPE, int SIZE>
  417. inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::reset()
  418. {
  419. if (mCurHashNodep)
  420. {
  421. // We're partway through an iteration, we can clean up now
  422. mHashMapp->mIterCount--;
  423. mCurHashNodep = NULL;
  424. }
  425. }
  426. template <class DATA_TYPE, int SIZE>
  427. inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::first()
  428. {
  429. // Iterate through until we find the first non-empty node;
  430. S32 i;
  431. for (i = 0; i < 256; i++)
  432. {
  433. if (mHashMapp->mNodes[i].mCount)
  434. {
  435. if (!mCurHashNodep)
  436. {
  437. // Increment, since it's no longer safe for us to do a remove
  438. mHashMapp->mIterCount++;
  439. }
  440. mCurHashNodep = &mHashMapp->mNodes[i];
  441. mCurHashMapNodeNum = i;
  442. mCurHashNodeKey = 0;
  443. //return mCurHashNodep->mData[0];
  444. return;
  445. }
  446. }
  447. // Completely empty!
  448. mCurHashNodep = NULL;
  449. //return mNull;
  450. return;
  451. }
  452. template <class DATA_TYPE, int SIZE>
  453. inline BOOL LLUUIDHashMapIter<DATA_TYPE, SIZE>::done() const
  454. {
  455. return mCurHashNodep ? FALSE : TRUE;
  456. }
  457. template <class DATA_TYPE, int SIZE>
  458. inline void LLUUIDHashMapIter<DATA_TYPE, SIZE>::next()
  459. {
  460. // No current entry, this iterator is done
  461. if (!mCurHashNodep)
  462. {
  463. //return mNull;
  464. return;
  465. }
  466. // Go to the next element
  467. mCurHashNodeKey++;
  468. if (mCurHashNodeKey < mCurHashNodep->mCount)
  469. {
  470. // We're not done with this node, return the current element
  471. //return mCurHashNodep->mData[mCurHashNodeKey];
  472. return;
  473. }
  474. // Done with this node, move to the next
  475. mCurHashNodep = mCurHashNodep->mNextNodep;
  476. if (mCurHashNodep)
  477. {
  478. // Return the first element
  479. mCurHashNodeKey = 0;
  480. //return mCurHashNodep->mData[0];
  481. return;
  482. }
  483. // Find the next non-empty node (keyed on the first byte)
  484. mCurHashMapNodeNum++;
  485. S32 i;
  486. for (i = mCurHashMapNodeNum; i < 256; i++)
  487. {
  488. if (mHashMapp->mNodes[i].mCount)
  489. {
  490. // We found one that wasn't empty
  491. mCurHashNodep = &mHashMapp->mNodes[i];
  492. mCurHashMapNodeNum = i;
  493. mCurHashNodeKey = 0;
  494. //return mCurHashNodep->mData[0];
  495. return;
  496. }
  497. }
  498. // OK, we're done, nothing else to iterate
  499. mCurHashNodep = NULL;
  500. mHashMapp->mIterCount--; // Decrement since we're safe to do removes now
  501. //return mNull;
  502. }
  503. #endif // LL_LLUUIDHASHMAP_H