开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 游戏引擎 > 查看源码
llptrskipmap.h
资源名称：snowglobe-src-viewer-2.0.0-r0.tar.gz　[点击查看]
上传用户：king477883
上传日期：2021-03-01
资源大小：9553k
文件大小：28k
源码类别：

游戏引擎

开发平台：

C++ Builder

llptrskipmap.h：源码内容
  1. /** 
  2.  * @file llptrskipmap.h
  3.  * @brief Just like a LLSkipMap, but since it's pointers, you can call
  4.  * deleteAllData
  5.  *
  6.  * $LicenseInfo:firstyear=2003&license=viewergpl$
  7.  * 
  8.  * Copyright (c) 2003-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. #ifndef LL_LLPTRSKIPMAP_H
  34. #define LL_LLPTRSKIPMAP_H
  36. #include "llerror.h"
  37. #include "llrand.h"
  39. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8> 
  40. class LLPtrSkipMapNode
  41. {
  42. public:
  43. LLPtrSkipMapNode()
  44. {
  45. S32 i;
  46. for (i = 0; i < BINARY_DEPTH; i++)
  47. {
  48. mForward[i] = NULL;
  49. }
  51. U8  *zero = (U8 *)&mIndex;
  53. for (i = 0; i < (S32)sizeof(INDEX_T); i++)
  54. {
  55. *(zero + i) = 0;
  56. }
  58. zero = (U8 *)&mData;
  60. for (i = 0; i < (S32)sizeof(DATA_T); i++)
  61. {
  62. *(zero + i) = 0;
  63. }
  64. }
  66. LLPtrSkipMapNode(const INDEX_T &index)
  67. : mIndex(index)
  68. {
  70. S32 i;
  71. for (i = 0; i < BINARY_DEPTH; i++)
  72. {
  73. mForward[i] = NULL;
  74. }
  76. U8 *zero = (U8 *)&mData;
  78. for (i = 0; i < (S32)sizeof(DATA_T); i++)
  79. {
  80. *(zero + i) = 0;
  81. }
  82. }
  84. LLPtrSkipMapNode(const INDEX_T &index, DATA_T datap)
  85. : mIndex(index)
  86. {
  88. S32 i;
  89. for (i = 0; i < BINARY_DEPTH; i++)
  90. {
  91. mForward[i] = NULL;
  92. }
  94. mData = datap;
  95. }
  97. ~LLPtrSkipMapNode()
  98. {
  99. }
  101. // delete associated data and NULLs out pointer
  102. void deleteData()
  103. {
  104. delete mData;
  105. mData = 0;
  106. }
  108. // NULLs out pointer
  109. void removeData()
  110. {
  111. mData = 0;
  112. }
  114. INDEX_T mIndex;
  115. DATA_T mData;
  116. LLPtrSkipMapNode *mForward[BINARY_DEPTH];
  118. private:
  119. // Disallow copying of LLPtrSkipMapNodes by not implementing these methods.
  120. LLPtrSkipMapNode(const LLPtrSkipMapNode &);
  121. LLPtrSkipMapNode &operator=(const LLPtrSkipMapNode &rhs);
  122. };
  124. //---------------------------------------------------------------------------
  126. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8> 
  127. class LLPtrSkipMap
  128. {
  129. public:
  130. typedef BOOL (*compare)(const DATA_T& first, const DATA_T& second);
  131. typedef compare insert_func;
  132. typedef compare equals_func;
  134. void init();
  136. // basic constructor
  137. LLPtrSkipMap();
  139. // basic constructor including sorter
  140. LLPtrSkipMap(insert_func insert_first, equals_func equals);
  142. ~LLPtrSkipMap();
  144. void setInsertFirst(insert_func insert_first);
  145. void setEquals(equals_func equals);
  147. DATA_T &addData(const INDEX_T &index, DATA_T datap);
  148. DATA_T &addData(const INDEX_T &index);
  149. DATA_T &getData(const INDEX_T &index);
  150. DATA_T &operator[](const INDEX_T &index);
  152. // If index present, returns data.
  153. // If index not present, adds <index,NULL> and returns NULL.
  154. DATA_T &getData(const INDEX_T &index, BOOL &b_new_entry);
  156. // returns data entry before and after index
  157. BOOL getInterval(const INDEX_T &index, INDEX_T &index_before, INDEX_T &index_after,
  158. DATA_T &data_before, DATA_T &data_after );
  160. // Returns TRUE if data present in map.
  161. BOOL checkData(const INDEX_T &index);
  163. // Returns TRUE if key is present in map. This is useful if you
  164. // are potentially storing NULL pointers in the map
  165. BOOL checkKey(const INDEX_T &index);
  167. // If there, returns the data.
  168. // If not, returns NULL.
  169. // Never adds entries to the map.
  170. DATA_T getIfThere(const INDEX_T &index);
  172. INDEX_T reverseLookup(const DATA_T datap);
  174. // returns number of items in the list
  175. S32 getLength(); // WARNING!  getLength is O(n), not O(1)!
  177. BOOL removeData(const INDEX_T &index);
  178. BOOL deleteData(const INDEX_T &index);
  180. // remove all nodes from the list but do not delete data
  181. void removeAllData();
  182. void deleteAllData();
  184. // place mCurrentp on first node
  185. void resetList();
  187. // return the data currently pointed to
  188. DATA_T getCurrentDataWithoutIncrement();
  190. // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
  191. DATA_T getCurrentData();
  193. // same as getCurrentData() but a more intuitive name for the operation
  194. DATA_T getNextData();
  196. INDEX_T getNextKey();
  198. // return the key currently pointed to
  199. INDEX_T getCurrentKeyWithoutIncrement();
  201. // remove the Node at mCurentOperatingp
  202. // leave mCurrentp and mCurentOperatingp on the next entry
  203. void removeCurrentData();
  205. void deleteCurrentData();
  207. // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
  208. DATA_T getFirstData();
  210. INDEX_T getFirstKey();
  212. static BOOL defaultEquals(const INDEX_T &first, const INDEX_T &second)
  213. {
  214. return first == second;
  215. }
  217. private:
  218. // don't generate implicit copy constructor or copy assignment
  219. LLPtrSkipMap(const LLPtrSkipMap &);
  220. LLPtrSkipMap &operator=(const LLPtrSkipMap &);
  222. private:
  223. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> mHead;
  224. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mUpdate[BINARY_DEPTH];
  225. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentp;
  226. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentOperatingp;
  227. S32 mLevel;
  228. BOOL (*mInsertFirst)(const INDEX_T &first, const INDEX_T &second);
  229. BOOL (*mEquals)(const INDEX_T &first, const INDEX_T &second);
  230. S32 mNumberOfSteps;
  231. };
  233. //////////////////////////////////////////////////
  234. //
  235. // LLPtrSkipMap implementation
  236. //
  237. //
  239. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  240. inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap()
  241. : mInsertFirst(NULL),
  242. mEquals(defaultEquals),
  243. mNumberOfSteps(0)
  244. {
  245. if (BINARY_DEPTH < 2)
  246. {
  247. llerrs << "Trying to create skip list with too little depth, "
  248. "must be 2 or greater" << llendl;
  249. }
  250. S32 i;
  251. for (i = 0; i < BINARY_DEPTH; i++)
  252. {
  253. mUpdate[i] = NULL;
  254. }
  255. mLevel = 1;
  256. mCurrentp = *(mHead.mForward);
  257. mCurrentOperatingp = *(mHead.mForward);
  258. }
  260. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  261. inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap(insert_func insert_first, 
  262.  equals_func equals) 
  263. : mInsertFirst(insert_first),
  264. mEquals(equals),
  265. mNumberOfSteps(0)
  266. {
  267. if (BINARY_DEPTH < 2)
  268. {
  269. llerrs << "Trying to create skip list with too little depth, "
  270. "must be 2 or greater" << llendl;
  271. }
  272. mLevel = 1;
  273. S32 i;
  274. for (i = 0; i < BINARY_DEPTH; i++)
  275. {
  276. mHead.mForward[i] = NULL;
  277. mUpdate[i] = NULL;
  278. }
  279. mCurrentp = *(mHead.mForward);
  280. mCurrentOperatingp = *(mHead.mForward);
  281. }
  283. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  284. inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::~LLPtrSkipMap()
  285. {
  286. removeAllData();
  287. }
  289. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  290. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setInsertFirst(insert_func insert_first)
  291. {
  292. mInsertFirst = insert_first;
  293. }
  295. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  296. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setEquals(equals_func equals)
  297. {
  298. mEquals = equals;
  299. }
  301. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  302. inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index, DATA_T datap)
  303. {
  304. S32 level;
  305. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  306. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  308. // find the pointer one in front of the one we want
  309. if (mInsertFirst)
  310. {
  311. for (level = mLevel - 1; level >= 0; level--)
  312. {
  313. temp = *(current->mForward + level);
  314. while (  (temp)
  315.    &&(mInsertFirst(temp->mIndex, index)))
  316. {
  317. current = temp;
  318. temp = *(current->mForward + level);
  319. }
  320. *(mUpdate + level) = current;
  321. }
  322. }
  323. else
  324. {
  325. for (level = mLevel - 1; level >= 0; level--)
  326. {
  327. temp = *(current->mForward + level);
  328. while (  (temp)
  329.    &&(temp->mIndex < index))
  330. {
  331. current = temp;
  332. temp = *(current->mForward + level);
  333. }
  334. *(mUpdate + level) = current;
  335. }
  336. }
  338. // we're now just in front of where we want to be . . . take one step forward
  339. current = *current->mForward;
  341. // replace the existing data if a node is already there
  342. if (  (current)
  343. &&(mEquals(current->mIndex, index)))
  344. {
  345. current->mData = datap;
  346. return current->mData;
  347. }
  349. // now add the new node
  350. S32 newlevel;
  351. for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
  352. {
  353. if (ll_frand() < 0.5f)
  354. {
  355. break;
  356. }
  357. }
  359. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode 
  360. = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index, datap);
  362. if (newlevel > mLevel)
  363. {
  364. mHead.mForward[mLevel] = NULL;
  365. mUpdate[mLevel] = &mHead;
  366. mLevel = newlevel;
  367. }
  369. for (level = 0; level < newlevel; level++)
  370. {
  371. snode->mForward[level] = mUpdate[level]->mForward[level];
  372. mUpdate[level]->mForward[level] = snode;
  373. }
  374. return snode->mData;
  375. }
  377. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  378. inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index)
  379. {
  380. S32 level;
  381. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  382. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  384. // find the pointer one in front of the one we want
  385. if (mInsertFirst)
  386. {
  387. for (level = mLevel - 1; level >= 0; level--)
  388. {
  389. temp = *(current->mForward + level);
  390. while (  (temp)
  391.    &&(mInsertFirst(temp->mIndex, index)))
  392. {
  393. current = temp;
  394. temp = *(current->mForward + level);
  395. }
  396. *(mUpdate + level) = current;
  397. }
  398. }
  399. else
  400. {
  401. for (level = mLevel - 1; level >= 0; level--)
  402. {
  403. temp = *(current->mForward + level);
  404. while (  (temp)
  405.    &&(temp->mIndex < index))
  406. {
  407. current = temp;
  408. temp = *(current->mForward + level);
  409. }
  410. *(mUpdate + level) = current;
  411. }
  412. }
  414. // we're now just in front of where we want to be . . . take one step forward
  415. current = *current->mForward;
  417. // now add the new node
  418. S32 newlevel;
  419. for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
  420. {
  421. if (ll_frand() < 0.5f)
  422. break;
  423. }
  425. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode 
  426. = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index);
  428. if (newlevel > mLevel)
  429. {
  430. mHead.mForward[mLevel] = NULL;
  431. mUpdate[mLevel] = &mHead;
  432. mLevel = newlevel;
  433. }
  435. for (level = 0; level < newlevel; level++)
  436. {
  437. snode->mForward[level] = mUpdate[level]->mForward[level];
  438. mUpdate[level]->mForward[level] = snode;
  439. }
  440. return snode->mData;
  441. }
  443. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  444. inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index)
  445. {
  446. S32 level;
  447. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  448. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  450. mNumberOfSteps = 0;
  452. // find the pointer one in front of the one we want
  453. if (mInsertFirst)
  454. {
  455. for (level = mLevel - 1; level >= 0; level--)
  456. {
  457. temp = *(current->mForward + level);
  458. while (  (temp)
  459.    &&(mInsertFirst(temp->mIndex, index)))
  460. {
  461. current = temp;
  462. temp = *(current->mForward + level);
  463. mNumberOfSteps++;
  464. }
  465. *(mUpdate + level) = current;
  466. }
  467. }
  468. else
  469. {
  470. for (level = mLevel - 1; level >= 0; level--)
  471. {
  472. temp = *(current->mForward + level);
  473. while (  (temp)
  474.    &&(temp->mIndex < index))
  475. {
  476. current = temp;
  477. temp = *(current->mForward + level);
  478. mNumberOfSteps++;
  479. }
  480. *(mUpdate + level) = current;
  481. }
  482. }
  484. // we're now just in front of where we want to be . . . take one step forward
  485. current = *current->mForward;
  486. mNumberOfSteps++;
  488. if (  (current)
  489. &&(mEquals(current->mIndex, index)))
  490. {
  492. return current->mData;
  493. }
  495. // now add the new node
  496. S32 newlevel;
  497. for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
  498. {
  499. if (ll_frand() < 0.5f)
  500. break;
  501. }
  503. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode 
  504. = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index);
  506. if (newlevel > mLevel)
  507. {
  508. mHead.mForward[mLevel] = NULL;
  509. mUpdate[mLevel] = &mHead;
  510. mLevel = newlevel;
  511. }
  513. for (level = 0; level < newlevel; level++)
  514. {
  515. snode->mForward[level] = mUpdate[level]->mForward[level];
  516. mUpdate[level]->mForward[level] = snode;
  517. }
  519. return snode->mData;
  520. }
  522. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  523. inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getInterval(const INDEX_T &index, 
  524.  INDEX_T &index_before, 
  525.  INDEX_T &index_after, 
  526.  DATA_T &data_before, 
  527.  DATA_T &data_after)
  528. {
  529. S32 level;
  530. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  531. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  533. mNumberOfSteps = 0;
  535. // find the pointer one in front of the one we want
  536. if (mInsertFirst)
  537. {
  538. for (level = mLevel - 1; level >= 0; level--)
  539. {
  540. temp = *(current->mForward + level);
  541. while (  (temp)
  542.    &&(mInsertFirst(temp->mIndex, index)))
  543. {
  544. current = temp;
  545. temp = *(current->mForward + level);
  546. mNumberOfSteps++;
  547. }
  548. *(mUpdate + level) = current;
  549. }
  550. }
  551. else
  552. {
  553. for (level = mLevel - 1; level >= 0; level--)
  554. {
  555. temp = *(current->mForward + level);
  556. while (  (temp)
  557.    &&(temp->mIndex < index))
  558. {
  559. current = temp;
  560. temp = *(current->mForward + level);
  561. mNumberOfSteps++;
  562. }
  563. *(mUpdate + level) = current;
  564. }
  565. }
  567. BOOL both_found = TRUE;
  569. if (current != &mHead)
  570. {
  571. index_before = current->mIndex;
  572. data_before = current->mData;
  573. }
  574. else
  575. {
  576. data_before = 0;
  577. index_before = 0;
  578. both_found = FALSE;
  579. }
  581. // we're now just in front of where we want to be . . . take one step forward
  582. mNumberOfSteps++;
  583. current = *current->mForward;
  585. if (current)
  586. {
  587. data_after = current->mData;
  588. index_after = current->mIndex;
  589. }
  590. else
  591. {
  592. data_after = 0;
  593. index_after = 0;
  594. both_found = FALSE;
  595. }
  597. return both_found;
  598. }
  601. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  602. inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::operator[](const INDEX_T &index)
  603. {
  605. return getData(index);
  606. }
  608. // If index present, returns data.
  609. // If index not present, adds <index,NULL> and returns NULL.
  610. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  611. inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index, BOOL &b_new_entry)
  612. {
  613. S32 level;
  614. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  615. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  617. mNumberOfSteps = 0;
  619. // find the pointer one in front of the one we want
  620. if (mInsertFirst)
  621. {
  622. for (level = mLevel - 1; level >= 0; level--)
  623. {
  624. temp = *(current->mForward + level);
  625. while (  (temp)
  626.    &&(mInsertFirst(temp->mIndex, index)))
  627. {
  628. current = temp;
  629. temp = *(current->mForward + level);
  630. mNumberOfSteps++;
  631. }
  632. *(mUpdate + level) = current;
  633. }
  634. }
  635. else
  636. {
  637. for (level = mLevel - 1; level >= 0; level--)
  638. {
  639. temp = *(current->mForward + level);
  640. while (  (temp)
  641.    &&(temp->mIndex < index))
  642. {
  643. current = temp;
  644. temp = *(current->mForward + level);
  645. mNumberOfSteps++;
  646. }
  647. *(mUpdate + level) = current;
  648. }
  649. }
  651. // we're now just in front of where we want to be . . . take one step forward
  652. mNumberOfSteps++;
  653. current = *current->mForward;
  655. if (  (current)
  656. &&(mEquals(current->mIndex, index)))
  657. {
  659. return current->mData;
  660. }
  661. b_new_entry = TRUE;
  662. addData(index);
  664. return current->mData;
  665. }
  667. // Returns TRUE if data present in map.
  668. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  669. inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkData(const INDEX_T &index)
  670. {
  671. S32 level;
  672. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  673. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  675. // find the pointer one in front of the one we want
  676. if (mInsertFirst)
  677. {
  678. for (level = mLevel - 1; level >= 0; level--)
  679. {
  680. temp = *(current->mForward + level);
  681. while (  (temp)
  682.    &&(mInsertFirst(temp->mIndex, index)))
  683. {
  684. current = temp;
  685. temp = *(current->mForward + level);
  686. }
  687. *(mUpdate + level) = current;
  688. }
  689. }
  690. else
  691. {
  692. for (level = mLevel - 1; level >= 0; level--)
  693. {
  694. temp = *(current->mForward + level);
  695. while (  (temp)
  696.    &&(temp->mIndex < index))
  697. {
  698. current = temp;
  699. temp = *(current->mForward + level);
  700. }
  701. *(mUpdate + level) = current;
  702. }
  703. }
  705. // we're now just in front of where we want to be . . . take one step forward
  706. current = *current->mForward;
  708. if (current)
  709. {
  710. // Gets rid of some compiler ambiguity for the LLPointer<> templated class.
  711. if (current->mData)
  712. {
  713. return mEquals(current->mIndex, index);
  714. }
  715. }
  717. return FALSE;
  718. }
  720. // Returns TRUE if key is present in map. This is useful if you
  721. // are potentially storing NULL pointers in the map
  722. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  723. inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkKey(const INDEX_T &index)
  724. {
  725. S32 level;
  726. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  727. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  729. // find the pointer one in front of the one we want
  730. if (mInsertFirst)
  731. {
  732. for (level = mLevel - 1; level >= 0; level--)
  733. {
  734. temp = *(current->mForward + level);
  735. while (  (temp)
  736.    &&(mInsertFirst(temp->mIndex, index)))
  737. {
  738. current = temp;
  739. temp = *(current->mForward + level);
  740. }
  741. *(mUpdate + level) = current;
  742. }
  743. }
  744. else
  745. {
  746. for (level = mLevel - 1; level >= 0; level--)
  747. {
  748. temp = *(current->mForward + level);
  749. while (  (temp)
  750.    &&(temp->mIndex < index))
  751. {
  752. current = temp;
  753. temp = *(current->mForward + level);
  754. }
  755. *(mUpdate + level) = current;
  756. }
  757. }
  759. // we're now just in front of where we want to be . . . take one step forward
  760. current = *current->mForward;
  762. if (current)
  763. {
  764. return mEquals(current->mIndex, index);
  765. }
  767. return FALSE;
  768. }
  770. // If there, returns the data.
  771. // If not, returns NULL.
  772. // Never adds entries to the map.
  773. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  774. inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getIfThere(const INDEX_T &index)
  775. {
  776. S32 level;
  777. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  778. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  780. mNumberOfSteps = 0;
  782. // find the pointer one in front of the one we want
  783. if (mInsertFirst)
  784. {
  785. for (level = mLevel - 1; level >= 0; level--)
  786. {
  787. temp = *(current->mForward + level);
  788. while (  (temp)
  789.    &&(mInsertFirst(temp->mIndex, index)))
  790. {
  791. current = temp;
  792. temp = *(current->mForward + level);
  793. mNumberOfSteps++;
  794. }
  795. *(mUpdate + level) = current;
  796. }
  797. }
  798. else
  799. {
  800. for (level = mLevel - 1; level >= 0; level--)
  801. {
  802. temp = *(current->mForward + level);
  803. while (  (temp)
  804.    &&(temp->mIndex < index))
  805. {
  806. current = temp;
  807. temp = *(current->mForward + level);
  808. mNumberOfSteps++;
  809. }
  810. *(mUpdate + level) = current;
  811. }
  812. }
  814. // we're now just in front of where we want to be . . . take one step forward
  815. mNumberOfSteps++;
  816. current = *current->mForward;
  818. if (current)
  819. {
  820. if (mEquals(current->mIndex, index))
  821. {
  822. return current->mData;
  823. }
  824. }
  826. // Avoid Linux compiler warning on returning NULL.
  827. return (DATA_T)0;
  828. }
  830. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  831. inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::reverseLookup(const DATA_T datap)
  832. {
  833. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  835. while (current)
  836. {
  837. if (datap == current->mData)
  838. {
  840. return current->mIndex;
  841. }
  842. current = *current->mForward;
  843. }
  845. // not found! return NULL
  846. return INDEX_T();
  847. }
  849. // returns number of items in the list
  850. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  851. inline S32 LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getLength()
  852. {
  853. U32 length = 0;
  854. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>* temp;
  855. for (temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
  856. {
  857. length++;
  858. }
  860. return length;
  861. }
  863. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  864. inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeData(const INDEX_T &index)
  865. {
  866. S32 level;
  867. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  868. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  870. // find the pointer one in front of the one we want
  871. if (mInsertFirst)
  872. {
  873. for (level = mLevel - 1; level >= 0; level--)
  874. {
  875. temp = *(current->mForward + level);
  876. while (  (temp)
  877.    &&(mInsertFirst(temp->mIndex, index)))
  878. {
  879. current = temp;
  880. temp = *(current->mForward + level);
  881. }
  882. *(mUpdate + level) = current;
  883. }
  884. }
  885. else
  886. {
  887. for (level = mLevel - 1; level >= 0; level--)
  888. {
  889. temp = *(current->mForward + level);
  890. while (  (temp)
  891.    &&(temp->mIndex < index))
  892. {
  893. current = temp;
  894. temp = *(current->mForward + level);
  895. }
  896. *(mUpdate + level) = current;
  897. }
  898. }
  900. // we're now just in front of where we want to be . . . take one step forward
  901. current = *current->mForward;
  903. if (!current)
  904. {
  905. // empty list or beyond the end!
  907. return FALSE;
  908. }
  910. // is this the one we want?
  911. if (!mEquals(current->mIndex, index))
  912. {
  913. // nope!
  915. return FALSE;
  916. }
  917. else
  918. {
  919. // do we need to fix current or currentop?
  920. if (current == mCurrentp)
  921. {
  922. mCurrentp = *current->mForward;
  923. }
  925. if (current == mCurrentOperatingp)
  926. {
  927. mCurrentOperatingp = *current->mForward;
  928. }
  929. // yes it is!  change pointers as required
  930. for (level = 0; level < mLevel; level++)
  931. {
  932. if (*((*(mUpdate + level))->mForward + level) != current)
  933. {
  934. // cool, we've fixed all the pointers!
  935. break;
  936. }
  937. *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
  938. }
  940. // clean up cuurent
  941. current->removeData();
  942. delete current;
  944. // clean up mHead
  945. while (  (mLevel > 1)
  946.    &&(!*(mHead.mForward + mLevel - 1)))
  947. {
  948. mLevel--;
  949. }
  950. }
  952. return TRUE;
  953. }
  955. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  956. inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteData(const INDEX_T &index)
  957. {
  958. S32 level;
  959. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
  960. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  962. // find the pointer one in front of the one we want
  963. if (mInsertFirst)
  964. {
  965. for (level = mLevel - 1; level >= 0; level--)
  966. {
  967. temp = *(current->mForward + level);
  968. while (  (temp)
  969.    &&(mInsertFirst(temp->mIndex, index)))
  970. {
  971. current = temp;
  972. temp = *(current->mForward + level);
  973. }
  974. *(mUpdate + level) = current;
  975. }
  976. }
  977. else
  978. {
  979. for (level = mLevel - 1; level >= 0; level--)
  980. {
  981. temp = *(current->mForward + level);
  982. while (  (temp)
  983.    &&(temp->mIndex < index))
  984. {
  985. current = temp;
  986. temp = *(current->mForward + level);
  987. }
  988. *(mUpdate + level) = current;
  989. }
  990. }
  992. // we're now just in front of where we want to be . . . take one step forward
  993. current = *current->mForward;
  995. if (!current)
  996. {
  997. // empty list or beyond the end!
  999. return FALSE;
  1000. }
  1002. // is this the one we want?
  1003. if (!mEquals(current->mIndex, index))
  1004. {
  1005. // nope!
  1007. return FALSE;
  1008. }
  1009. else
  1010. {
  1011. // do we need to fix current or currentop?
  1012. if (current == mCurrentp)
  1013. {
  1014. mCurrentp = *current->mForward;
  1015. }
  1017. if (current == mCurrentOperatingp)
  1018. {
  1019. mCurrentOperatingp = *current->mForward;
  1020. }
  1021. // yes it is!  change pointers as required
  1022. for (level = 0; level < mLevel; level++)
  1023. {
  1024. if (*((*(mUpdate + level))->mForward + level) != current)
  1025. {
  1026. // cool, we've fixed all the pointers!
  1027. break;
  1028. }
  1029. *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
  1030. }
  1032. // clean up cuurent
  1033. current->deleteData();
  1034. delete current;
  1036. // clean up mHead
  1037. while (  (mLevel > 1)
  1038.    &&(!*(mHead.mForward + mLevel - 1)))
  1039. {
  1040. mLevel--;
  1041. }
  1042. }
  1044. return TRUE;
  1045. }
  1047. // remove all nodes from the list but do not delete data
  1048. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1049. void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeAllData()
  1050. {
  1051. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  1052. // reset mCurrentp
  1053. mCurrentp = *(mHead.mForward);
  1055. while (mCurrentp)
  1056. {
  1057. temp = mCurrentp->mForward[0];
  1058. mCurrentp->removeData();
  1059. delete mCurrentp;
  1060. mCurrentp = temp;
  1061. }
  1063. S32 i;
  1064. for (i = 0; i < BINARY_DEPTH; i++)
  1065. {
  1066. mHead.mForward[i] = NULL;
  1067. mUpdate[i] = NULL;
  1068. }
  1070. mCurrentp = *(mHead.mForward);
  1071. mCurrentOperatingp = *(mHead.mForward);
  1072. }
  1074. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1075. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteAllData()
  1076. {
  1077. LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
  1078. // reset mCurrentp
  1079. mCurrentp = *(mHead.mForward);
  1081. while (mCurrentp)
  1082. {
  1083. temp = mCurrentp->mForward[0];
  1084. mCurrentp->deleteData();
  1085. delete mCurrentp;
  1086. mCurrentp = temp;
  1087. }
  1089. S32 i;
  1090. for (i = 0; i < BINARY_DEPTH; i++)
  1091. {
  1092. mHead.mForward[i] = NULL;
  1093. mUpdate[i] = NULL;
  1094. }
  1096. mCurrentp = *(mHead.mForward);
  1097. mCurrentOperatingp = *(mHead.mForward);
  1098. }
  1100. // place mCurrentp on first node
  1101. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1102. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::resetList()
  1103. {
  1104. mCurrentp = *(mHead.mForward);
  1105. mCurrentOperatingp = *(mHead.mForward);
  1106. }
  1109. // return the data currently pointed to
  1110. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1111. inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentDataWithoutIncrement()
  1112. {
  1113. if (mCurrentOperatingp)
  1114. {
  1115. return mCurrentOperatingp->mData;
  1116. }
  1117. else
  1118. {
  1119. //return NULL;  // causes warning
  1120. return (DATA_T)0; // equivalent, but no warning
  1121. }
  1122. }
  1124. // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
  1125. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1126. inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentData()
  1127. {
  1128. if (mCurrentp)
  1129. {
  1130. mCurrentOperatingp = mCurrentp;
  1131. mCurrentp = mCurrentp->mForward[0];
  1132. return mCurrentOperatingp->mData;
  1133. }
  1134. else
  1135. {
  1136. //return NULL;  // causes warning
  1137. return (DATA_T)0; // equivalent, but no warning
  1138. }
  1139. }
  1141. // same as getCurrentData() but a more intuitive name for the operation
  1142. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1143. inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextData()
  1144. {
  1145. if (mCurrentp)
  1146. {
  1147. mCurrentOperatingp = mCurrentp;
  1148. mCurrentp = mCurrentp->mForward[0];
  1149. return mCurrentOperatingp->mData;
  1150. }
  1151. else
  1152. {
  1153. //return NULL; // causes compile warning
  1154. return (DATA_T)0; // equivalent, but removes warning
  1155. }
  1156. }
  1158. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1159. inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextKey()
  1160. {
  1161. if (mCurrentp)
  1162. {
  1163. mCurrentOperatingp = mCurrentp;
  1164. mCurrentp = mCurrentp->mForward[0];
  1165. return mCurrentOperatingp->mIndex;
  1166. }
  1167. else
  1168. {
  1169. return mHead.mIndex;
  1170. }
  1171. }
  1173. // return the key currently pointed to
  1174. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1175. inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentKeyWithoutIncrement()
  1176. {
  1177. if (mCurrentOperatingp)
  1178. {
  1179. return mCurrentOperatingp->mIndex;
  1180. }
  1181. else
  1182. {
  1183. //return NULL; // causes compile warning
  1184. return (INDEX_T)0; // equivalent, but removes warning
  1185. }
  1186. }
  1189. // remove the Node at mCurentOperatingp
  1190. // leave mCurrentp and mCurentOperatingp on the next entry
  1191. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1192. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeCurrentData()
  1193. {
  1194. if (mCurrentOperatingp)
  1195. {
  1196. removeData(mCurrentOperatingp->mIndex);
  1197. }
  1198. }
  1200. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1201. inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteCurrentData()
  1202. {
  1203. if (mCurrentOperatingp)
  1204. {
  1205. deleteData(mCurrentOperatingp->mIndex);
  1206. }
  1207. }
  1209. // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
  1210. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1211. inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getFirstData()
  1212. {
  1213. mCurrentp = *(mHead.mForward);
  1214. mCurrentOperatingp = *(mHead.mForward);
  1215. if (mCurrentp)
  1216. {
  1217. mCurrentOperatingp = mCurrentp;
  1218. mCurrentp = mCurrentp->mForward[0];
  1219. return mCurrentOperatingp->mData;
  1220. }
  1221. else
  1222. {
  1223. //return NULL; // causes compile warning
  1224. return (DATA_T)0; // equivalent, but removes warning
  1225. }
  1226. }
  1228. template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
  1229. inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getFirstKey()
  1230. {
  1231. mCurrentp = *(mHead.mForward);
  1232. mCurrentOperatingp = *(mHead.mForward);
  1233. if (mCurrentp)
  1234. {
  1235. mCurrentOperatingp = mCurrentp;
  1236. mCurrentp = mCurrentp->mForward[0];
  1237. return mCurrentOperatingp->mIndex;
  1238. }
  1239. else
  1240. {
  1241. return mHead.mIndex;
  1242. }
  1243. }
  1245. #endif