aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/linden/indra/llcommon/llskipmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'linden/indra/llcommon/llskipmap.h')
-rw-r--r--linden/indra/llcommon/llskipmap.h1023
1 files changed, 1023 insertions, 0 deletions
diff --git a/linden/indra/llcommon/llskipmap.h b/linden/indra/llcommon/llskipmap.h
new file mode 100644
index 0000000..85a84e5
--- /dev/null
+++ b/linden/indra/llcommon/llskipmap.h
@@ -0,0 +1,1023 @@
1/**
2 * @file llskipmap.h
3 * @brief Associative container based on the skiplist algorithm.
4 *
5 * Copyright (c) 2003-2007, Linden Research, Inc.
6 *
7 * The source code in this file ("Source Code") is provided by Linden Lab
8 * to you under the terms of the GNU General Public License, version 2.0
9 * ("GPL"), unless you have obtained a separate licensing agreement
10 * ("Other License"), formally executed by you and Linden Lab. Terms of
11 * the GPL can be found in doc/GPL-license.txt in this distribution, or
12 * online at http://secondlife.com/developers/opensource/gplv2
13 *
14 * There are special exceptions to the terms and conditions of the GPL as
15 * it is applied to this Source Code. View the full text of the exception
16 * in the file doc/FLOSS-exception.txt in this software distribution, or
17 * online at http://secondlife.com/developers/opensource/flossexception
18 *
19 * By copying, modifying or distributing this software, you acknowledge
20 * that you have read and understood your obligations described above,
21 * and agree to abide by those obligations.
22 *
23 * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
24 * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
25 * COMPLETENESS OR PERFORMANCE.
26 */
27
28#ifndef LL_LLSKIPMAP_H
29#define LL_LLSKIPMAP_H
30
31#include "llerror.h"
32
33template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH = 8>
34class LLSkipMap
35{
36public:
37 // basic constructor
38 LLSkipMap();
39
40 // basic constructor including sorter
41 LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second),
42 BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));
43
44 ~LLSkipMap();
45
46 void setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second));
47 void setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));
48
49 DATA_TYPE &addData(const INDEX_TYPE &index, DATA_TYPE datap);
50 DATA_TYPE &addData(const INDEX_TYPE &index);
51 DATA_TYPE &getData(const INDEX_TYPE &index);
52 DATA_TYPE &operator[](const INDEX_TYPE &index);
53
54 // If index present, returns data.
55 // If index not present, adds <index,NULL> and returns NULL.
56 DATA_TYPE &getData(const INDEX_TYPE &index, BOOL &b_new_entry);
57
58 // Returns TRUE if data present in map.
59 BOOL checkData(const INDEX_TYPE &index);
60
61 // Returns TRUE if key is present in map. This is useful if you
62 // are potentially storing NULL pointers in the map
63 BOOL checkKey(const INDEX_TYPE &index);
64
65 // If there, returns the data.
66 // If not, returns NULL.
67 // Never adds entries to the map.
68 DATA_TYPE getIfThere(const INDEX_TYPE &index);
69
70 INDEX_TYPE reverseLookup(const DATA_TYPE datap);
71
72 // returns number of items in the list
73 S32 getLength(); // WARNING! getLength is O(n), not O(1)!
74
75 BOOL removeData(const INDEX_TYPE &index);
76
77 // remove all nodes from the list but do not delete data
78 void removeAllData();
79
80 // place mCurrentp on first node
81 void resetList();
82
83 // return the data currently pointed to
84 DATA_TYPE getCurrentDataWithoutIncrement();
85
86 // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
87 DATA_TYPE getCurrentData();
88
89 // same as getCurrentData() but a more intuitive name for the operation
90 DATA_TYPE getNextData();
91
92 INDEX_TYPE getNextKey();
93
94 // return the key currently pointed to
95 INDEX_TYPE getCurrentKeyWithoutIncrement();
96
97 // The internal iterator is at the end of the list.
98 BOOL notDone() const;
99
100 // remove the Node at mCurentOperatingp
101 // leave mCurrentp and mCurentOperatingp on the next entry
102 void removeCurrentData();
103
104 void deleteCurrentData();
105
106 // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
107 DATA_TYPE getFirstData();
108
109 INDEX_TYPE getFirstKey();
110
111 class LLSkipMapNode
112 {
113 public:
114 LLSkipMapNode()
115 {
116 S32 i;
117 for (i = 0; i < BINARY_DEPTH; i++)
118 {
119 mForward[i] = NULL;
120 }
121
122 U8 *zero = (U8 *)&mIndex;
123
124 for (i = 0; i < (S32)sizeof(INDEX_TYPE); i++)
125 {
126 *(zero + i) = 0;
127 }
128
129 zero = (U8 *)&mData;
130
131 for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
132 {
133 *(zero + i) = 0;
134 }
135 }
136
137 LLSkipMapNode(const INDEX_TYPE &index)
138 : mIndex(index)
139 {
140
141 S32 i;
142 for (i = 0; i < BINARY_DEPTH; i++)
143 {
144 mForward[i] = NULL;
145 }
146
147 U8 *zero = (U8 *)&mData;
148
149 for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
150 {
151 *(zero + i) = 0;
152 }
153 }
154
155 LLSkipMapNode(const INDEX_TYPE &index, DATA_TYPE datap)
156 : mIndex(index)
157 {
158
159 S32 i;
160 for (i = 0; i < BINARY_DEPTH; i++)
161 {
162 mForward[i] = NULL;
163 }
164
165 mData = datap;
166 }
167
168 ~LLSkipMapNode()
169 {
170 }
171
172
173 INDEX_TYPE mIndex;
174 DATA_TYPE mData;
175 LLSkipMapNode *mForward[BINARY_DEPTH];
176
177 private:
178 // Disallow copying of LLSkipMapNodes by not implementing these methods.
179 LLSkipMapNode(const LLSkipMapNode &);
180 LLSkipMapNode &operator=(const LLSkipMapNode &rhs);
181 };
182
183 static BOOL defaultEquals(const INDEX_TYPE &first, const INDEX_TYPE &second)
184 {
185 return first == second;
186 }
187
188private:
189 // don't generate implicit copy constructor or copy assignment
190 LLSkipMap(const LLSkipMap &);
191 LLSkipMap &operator=(const LLSkipMap &);
192
193private:
194 LLSkipMapNode mHead;
195 LLSkipMapNode *mUpdate[BINARY_DEPTH];
196 LLSkipMapNode *mCurrentp;
197 LLSkipMapNode *mCurrentOperatingp;
198 S32 mLevel;
199 BOOL (*mInsertFirst)(const INDEX_TYPE &first, const INDEX_TYPE &second);
200 BOOL (*mEquals)(const INDEX_TYPE &first, const INDEX_TYPE &second);
201 S32 mNumberOfSteps;
202};
203
204//////////////////////////////////////////////////
205//
206// LLSkipMap implementation
207//
208
209template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
210inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap()
211 : mInsertFirst(NULL),
212 mEquals(defaultEquals)
213{
214 // Skipmaps must have binary depth of at least 2
215 cassert(BINARY_DEPTH >= 2);
216
217 S32 i;
218 for (i = 0; i < BINARY_DEPTH; i++)
219 {
220 mUpdate[i] = NULL;
221 }
222 mLevel = 1;
223 mCurrentp = *(mHead.mForward);
224 mCurrentOperatingp = *(mHead.mForward);
225}
226
227template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
228inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second),
229 BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second))
230 : mInsertFirst(insert_first),
231 mEquals(equals)
232{
233 // Skipmaps must have binary depth of at least 2
234 cassert(BINARY_DEPTH >= 2);
235
236 mLevel = 1;
237 S32 i;
238 for (i = 0; i < BINARY_DEPTH; i++)
239 {
240 mHead.mForward[i] = NULL;
241 mUpdate[i] = NULL;
242 }
243 mCurrentp = *(mHead.mForward);
244 mCurrentOperatingp = *(mHead.mForward);
245}
246
247template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
248inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::~LLSkipMap()
249{
250 removeAllData();
251}
252
253template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
254inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second))
255{
256 mInsertFirst = insert_first;
257}
258
259template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
260inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second))
261{
262 mEquals = equals;
263}
264
265template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
266inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index, DATA_TYPE datap)
267{
268 S32 level;
269 LLSkipMapNode *current = &mHead;
270 LLSkipMapNode *temp;
271
272 // find the pointer one in front of the one we want
273 if (mInsertFirst)
274 {
275 for (level = mLevel - 1; level >= 0; level--)
276 {
277 temp = *(current->mForward + level);
278 while ( (temp)
279 &&(mInsertFirst(temp->mIndex, index)))
280 {
281 current = temp;
282 temp = *(current->mForward + level);
283 }
284 *(mUpdate + level) = current;
285 }
286 }
287 else
288 {
289 for (level = mLevel - 1; level >= 0; level--)
290 {
291 temp = *(current->mForward + level);
292 while ( (temp)
293 &&(temp->mIndex < index))
294 {
295 current = temp;
296 temp = *(current->mForward + level);
297 }
298 *(mUpdate + level) = current;
299 }
300 }
301
302 // we're now just in front of where we want to be . . . take one step forward
303 current = *current->mForward;
304
305 // replace the existing data if a node is already there
306 if ( (current)
307 &&(mEquals(current->mIndex, index)))
308 {
309 current->mData = datap;
310 return current->mData;
311 }
312
313 // now add the new node
314 S32 newlevel;
315 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
316 {
317 if (rand() & 1)
318 {
319 break;
320 }
321 }
322
323 LLSkipMapNode *snode = new LLSkipMapNode(index, datap);
324
325 if (newlevel > mLevel)
326 {
327 mHead.mForward[mLevel] = NULL;
328 mUpdate[mLevel] = &mHead;
329 mLevel = newlevel;
330 }
331
332 for (level = 0; level < newlevel; level++)
333 {
334 snode->mForward[level] = mUpdate[level]->mForward[level];
335 mUpdate[level]->mForward[level] = snode;
336 }
337 return snode->mData;
338}
339
340template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
341inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index)
342{
343 S32 level;
344 LLSkipMapNode *current = &mHead;
345 LLSkipMapNode *temp;
346
347 // find the pointer one in front of the one we want
348 if (mInsertFirst)
349 {
350 for (level = mLevel - 1; level >= 0; level--)
351 {
352 temp = *(current->mForward + level);
353 while ( (temp)
354 &&(mInsertFirst(temp->mIndex, index)))
355 {
356 current = temp;
357 temp = *(current->mForward + level);
358 }
359 *(mUpdate + level) = current;
360 }
361 }
362 else
363 {
364 for (level = mLevel - 1; level >= 0; level--)
365 {
366 temp = *(current->mForward + level);
367 while ( (temp)
368 &&(temp->mIndex < index))
369 {
370 current = temp;
371 temp = *(current->mForward + level);
372 }
373 *(mUpdate + level) = current;
374 }
375 }
376
377 // we're now just in front of where we want to be . . . take one step forward
378 current = *current->mForward;
379
380 // now add the new node
381 S32 newlevel;
382 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
383 {
384 if (rand() & 1)
385 break;
386 }
387
388 LLSkipMapNode *snode = new LLSkipMapNode(index);
389
390 if (newlevel > mLevel)
391 {
392 mHead.mForward[mLevel] = NULL;
393 mUpdate[mLevel] = &mHead;
394 mLevel = newlevel;
395 }
396
397 for (level = 0; level < newlevel; level++)
398 {
399 snode->mForward[level] = mUpdate[level]->mForward[level];
400 mUpdate[level]->mForward[level] = snode;
401 }
402 return snode->mData;
403}
404
405template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
406inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index)
407{
408 S32 level;
409 LLSkipMapNode *current = &mHead;
410 LLSkipMapNode *temp;
411
412 mNumberOfSteps = 0;
413
414 // find the pointer one in front of the one we want
415 if (mInsertFirst)
416 {
417 for (level = mLevel - 1; level >= 0; level--)
418 {
419 temp = *(current->mForward + level);
420 while ( (temp)
421 &&(mInsertFirst(temp->mIndex, index)))
422 {
423 current = temp;
424 temp = *(current->mForward + level);
425 mNumberOfSteps++;
426 }
427 *(mUpdate + level) = current;
428 }
429 }
430 else
431 {
432 for (level = mLevel - 1; level >= 0; level--)
433 {
434 temp = *(current->mForward + level);
435 while ( (temp)
436 &&(temp->mIndex < index))
437 {
438 current = temp;
439 temp = *(current->mForward + level);
440 mNumberOfSteps++;
441 }
442 *(mUpdate + level) = current;
443 }
444 }
445
446 // we're now just in front of where we want to be . . . take one step forward
447 current = *current->mForward;
448 mNumberOfSteps++;
449
450 if ( (current)
451 &&(mEquals(current->mIndex, index)))
452 {
453
454 return current->mData;
455 }
456
457 // now add the new node
458 S32 newlevel;
459 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
460 {
461 if (rand() & 1)
462 break;
463 }
464
465 LLSkipMapNode *snode = new LLSkipMapNode(index);
466
467 if (newlevel > mLevel)
468 {
469 mHead.mForward[mLevel] = NULL;
470 mUpdate[mLevel] = &mHead;
471 mLevel = newlevel;
472 }
473
474 for (level = 0; level < newlevel; level++)
475 {
476 snode->mForward[level] = mUpdate[level]->mForward[level];
477 mUpdate[level]->mForward[level] = snode;
478 }
479
480 return snode->mData;
481}
482
483template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
484inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::operator[](const INDEX_TYPE &index)
485{
486
487 return getData(index);
488}
489
490// If index present, returns data.
491// If index not present, adds <index,NULL> and returns NULL.
492template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
493inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index, BOOL &b_new_entry)
494{
495 S32 level;
496 LLSkipMapNode *current = &mHead;
497 LLSkipMapNode *temp;
498
499 mNumberOfSteps = 0;
500
501 // find the pointer one in front of the one we want
502 if (mInsertFirst)
503 {
504 for (level = mLevel - 1; level >= 0; level--)
505 {
506 temp = *(current->mForward + level);
507 while ( (temp)
508 &&(mInsertFirst(temp->mIndex, index)))
509 {
510 current = temp;
511 temp = *(current->mForward + level);
512 mNumberOfSteps++;
513 }
514 *(mUpdate + level) = current;
515 }
516 }
517 else
518 {
519 for (level = mLevel - 1; level >= 0; level--)
520 {
521 temp = *(current->mForward + level);
522 while ( (temp)
523 &&(temp->mIndex < index))
524 {
525 current = temp;
526 temp = *(current->mForward + level);
527 mNumberOfSteps++;
528 }
529 *(mUpdate + level) = current;
530 }
531 }
532
533 // we're now just in front of where we want to be . . . take one step forward
534 mNumberOfSteps++;
535 current = *current->mForward;
536
537 if ( (current)
538 &&(mEquals(current->mIndex, index)))
539 {
540
541 return current->mData;
542 }
543 b_new_entry = TRUE;
544 addData(index);
545
546 return current->mData;
547}
548
549// Returns TRUE if data present in map.
550template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
551inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkData(const INDEX_TYPE &index)
552{
553 S32 level;
554 LLSkipMapNode *current = &mHead;
555 LLSkipMapNode *temp;
556
557 // find the pointer one in front of the one we want
558 if (mInsertFirst)
559 {
560 for (level = mLevel - 1; level >= 0; level--)
561 {
562 temp = *(current->mForward + level);
563 while ( (temp)
564 &&(mInsertFirst(temp->mIndex, index)))
565 {
566 current = temp;
567 temp = *(current->mForward + level);
568 }
569 *(mUpdate + level) = current;
570 }
571 }
572 else
573 {
574 for (level = mLevel - 1; level >= 0; level--)
575 {
576 temp = *(current->mForward + level);
577 while ( (temp)
578 &&(temp->mIndex < index))
579 {
580 current = temp;
581 temp = *(current->mForward + level);
582 }
583 *(mUpdate + level) = current;
584 }
585 }
586
587 // we're now just in front of where we want to be . . . take one step forward
588 current = *current->mForward;
589
590 if (current)
591 {
592 // Gets rid of some compiler ambiguity for the LLPointer<> templated class.
593 if (current->mData)
594 {
595 return mEquals(current->mIndex, index);
596 }
597 }
598
599 return FALSE;
600}
601
602// Returns TRUE if key is present in map. This is useful if you
603// are potentially storing NULL pointers in the map
604template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
605inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkKey(const INDEX_TYPE &index)
606{
607 S32 level;
608 LLSkipMapNode *current = &mHead;
609 LLSkipMapNode *temp;
610
611 // find the pointer one in front of the one we want
612 if (mInsertFirst)
613 {
614 for (level = mLevel - 1; level >= 0; level--)
615 {
616 temp = *(current->mForward + level);
617 while ( (temp)
618 &&(mInsertFirst(temp->mIndex, index)))
619 {
620 current = temp;
621 temp = *(current->mForward + level);
622 }
623 *(mUpdate + level) = current;
624 }
625 }
626 else
627 {
628 for (level = mLevel - 1; level >= 0; level--)
629 {
630 temp = *(current->mForward + level);
631 while ( (temp)
632 &&(temp->mIndex < index))
633 {
634 current = temp;
635 temp = *(current->mForward + level);
636 }
637 *(mUpdate + level) = current;
638 }
639 }
640
641 // we're now just in front of where we want to be . . . take one step forward
642 current = *current->mForward;
643
644 if (current)
645 {
646 return mEquals(current->mIndex, index);
647 }
648
649 return FALSE;
650}
651
652// If there, returns the data.
653// If not, returns NULL.
654// Never adds entries to the map.
655template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
656inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getIfThere(const INDEX_TYPE &index)
657{
658 S32 level;
659 LLSkipMapNode *current = &mHead;
660 LLSkipMapNode *temp;
661
662 mNumberOfSteps = 0;
663
664 // find the pointer one in front of the one we want
665 if (mInsertFirst)
666 {
667 for (level = mLevel - 1; level >= 0; level--)
668 {
669 temp = *(current->mForward + level);
670 while ( (temp)
671 &&(mInsertFirst(temp->mIndex, index)))
672 {
673 current = temp;
674 temp = *(current->mForward + level);
675 mNumberOfSteps++;
676 }
677 *(mUpdate + level) = current;
678 }
679 }
680 else
681 {
682 for (level = mLevel - 1; level >= 0; level--)
683 {
684 temp = *(current->mForward + level);
685 while ( (temp)
686 &&(temp->mIndex < index))
687 {
688 current = temp;
689 temp = *(current->mForward + level);
690 mNumberOfSteps++;
691 }
692 *(mUpdate + level) = current;
693 }
694 }
695
696 // we're now just in front of where we want to be . . . take one step forward
697 mNumberOfSteps++;
698 current = *current->mForward;
699
700 if (current)
701 {
702 if (mEquals(current->mIndex, index))
703 {
704 return current->mData;
705 }
706 }
707
708 // Avoid Linux compiler warning on returning NULL.
709 return DATA_TYPE();
710}
711
712template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
713inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::reverseLookup(const DATA_TYPE datap)
714{
715 LLSkipMapNode *current = &mHead;
716
717 while (current)
718 {
719 if (datap == current->mData)
720 {
721
722 return current->mIndex;
723 }
724 current = *current->mForward;
725 }
726
727 // not found! return NULL
728 return INDEX_TYPE();
729}
730
731// returns number of items in the list
732template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
733inline S32 LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getLength()
734{
735 U32 length = 0;
736 for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
737 {
738 length++;
739 }
740
741 return length;
742}
743
744template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
745inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeData(const INDEX_TYPE &index)
746{
747 S32 level;
748 LLSkipMapNode *current = &mHead;
749 LLSkipMapNode *temp;
750
751 // find the pointer one in front of the one we want
752 if (mInsertFirst)
753 {
754 for (level = mLevel - 1; level >= 0; level--)
755 {
756 temp = *(current->mForward + level);
757 while ( (temp)
758 &&(mInsertFirst(temp->mIndex, index)))
759 {
760 current = temp;
761 temp = *(current->mForward + level);
762 }
763 *(mUpdate + level) = current;
764 }
765 }
766 else
767 {
768 for (level = mLevel - 1; level >= 0; level--)
769 {
770 temp = *(current->mForward + level);
771 while ( (temp)
772 &&(temp->mIndex < index))
773 {
774 current = temp;
775 temp = *(current->mForward + level);
776 }
777 *(mUpdate + level) = current;
778 }
779 }
780
781 // we're now just in front of where we want to be . . . take one step forward
782 current = *current->mForward;
783
784 if (!current)
785 {
786 // empty list or beyond the end!
787
788 return FALSE;
789 }
790
791 // is this the one we want?
792 if (!mEquals(current->mIndex, index))
793 {
794 // nope!
795
796 return FALSE;
797 }
798 else
799 {
800 // do we need to fix current or currentop?
801 if (current == mCurrentp)
802 {
803 mCurrentp = *current->mForward;
804 }
805
806 if (current == mCurrentOperatingp)
807 {
808 mCurrentOperatingp = *current->mForward;
809 }
810 // yes it is! change pointers as required
811 for (level = 0; level < mLevel; level++)
812 {
813 if (*((*(mUpdate + level))->mForward + level) != current)
814 {
815 // cool, we've fixed all the pointers!
816 break;
817 }
818 *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
819 }
820
821 delete current;
822
823 // clean up mHead
824 while ( (mLevel > 1)
825 &&(!*(mHead.mForward + mLevel - 1)))
826 {
827 mLevel--;
828 }
829 }
830
831 return TRUE;
832}
833
834
835// remove all nodes from the list but do not delete data
836template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
837void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeAllData()
838{
839 LLSkipMapNode *temp;
840 // reset mCurrentp
841 mCurrentp = *(mHead.mForward);
842
843 while (mCurrentp)
844 {
845 temp = mCurrentp->mForward[0];
846 delete mCurrentp;
847 mCurrentp = temp;
848 }
849
850 S32 i;
851 for (i = 0; i < BINARY_DEPTH; i++)
852 {
853 mHead.mForward[i] = NULL;
854 mUpdate[i] = NULL;
855 }
856
857 mCurrentp = *(mHead.mForward);
858 mCurrentOperatingp = *(mHead.mForward);
859}
860
861
862// place mCurrentp on first node
863template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
864inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::resetList()
865{
866 mCurrentp = *(mHead.mForward);
867 mCurrentOperatingp = *(mHead.mForward);
868}
869
870
871// return the data currently pointed to
872template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
873inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentDataWithoutIncrement()
874{
875 if (mCurrentOperatingp)
876 {
877 return mCurrentOperatingp->mData;
878 }
879 else
880 {
881 return DATA_TYPE();
882 }
883}
884
885// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
886template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
887inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentData()
888{
889 if (mCurrentp)
890 {
891 mCurrentOperatingp = mCurrentp;
892 mCurrentp = mCurrentp->mForward[0];
893 return mCurrentOperatingp->mData;
894 }
895 else
896 {
897 // Basic types, like int, have default constructors that initialize
898 // them to zero. g++ 2.95 supports this. "int()" is zero.
899 // This also is nice for LLUUID()
900 return DATA_TYPE();
901 }
902}
903
904// same as getCurrentData() but a more intuitive name for the operation
905template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
906inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextData()
907{
908 if (mCurrentp)
909 {
910 mCurrentOperatingp = mCurrentp;
911 mCurrentp = mCurrentp->mForward[0];
912 return mCurrentOperatingp->mData;
913 }
914 else
915 {
916 // Basic types, like int, have default constructors that initialize
917 // them to zero. g++ 2.95 supports this. "int()" is zero.
918 // This also is nice for LLUUID()
919 return DATA_TYPE();
920 }
921}
922
923template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
924inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextKey()
925{
926 if (mCurrentp)
927 {
928 mCurrentOperatingp = mCurrentp;
929 mCurrentp = mCurrentp->mForward[0];
930 return mCurrentOperatingp->mIndex;
931 }
932 else
933 {
934 return mHead.mIndex;
935 }
936}
937
938// return the key currently pointed to
939template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
940inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentKeyWithoutIncrement()
941{
942 if (mCurrentOperatingp)
943 {
944 return mCurrentOperatingp->mIndex;
945 }
946 else
947 {
948 // See comment for getNextData()
949 return INDEX_TYPE();
950 }
951}
952
953template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
954inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::notDone() const
955{
956 if (mCurrentOperatingp)
957 {
958 return TRUE;
959 }
960 else
961 {
962 return FALSE;
963 }
964}
965
966
967// remove the Node at mCurentOperatingp
968// leave mCurrentp and mCurentOperatingp on the next entry
969template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
970inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeCurrentData()
971{
972 if (mCurrentOperatingp)
973 {
974 removeData(mCurrentOperatingp->mIndex);
975 }
976}
977
978template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
979inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::deleteCurrentData()
980{
981 if (mCurrentOperatingp)
982 {
983 deleteData(mCurrentOperatingp->mIndex);
984 }
985}
986
987// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
988template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
989inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstData()
990{
991 mCurrentp = *(mHead.mForward);
992 mCurrentOperatingp = *(mHead.mForward);
993 if (mCurrentp)
994 {
995 mCurrentOperatingp = mCurrentp;
996 mCurrentp = mCurrentp->mForward[0];
997 return mCurrentOperatingp->mData;
998 }
999 else
1000 {
1001 // See comment for getNextData()
1002 return DATA_TYPE();
1003 }
1004}
1005
1006template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
1007inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstKey()
1008{
1009 mCurrentp = *(mHead.mForward);
1010 mCurrentOperatingp = *(mHead.mForward);
1011 if (mCurrentp)
1012 {
1013 mCurrentOperatingp = mCurrentp;
1014 mCurrentp = mCurrentp->mForward[0];
1015 return mCurrentOperatingp->mIndex;
1016 }
1017 else
1018 {
1019 return mHead.mIndex;
1020 }
1021}
1022
1023#endif
generated by cgit v1.1 at 2024-11-15 08:26:24 +0000