source: trunk/include/k/kRbTmpl/kRbBase.h@ 57

Last change on this file since 57 was 38, checked in by bird, 16 years ago

kRbTmpl: Some more code.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 19.0 KB
Line 
1/* $Id: kRbBase.h 38 2009-11-10 00:01:38Z bird $ */
2/** @file
3 * kRbTmpl - Templated Red-Black Trees, The Mandatory Base Code.
4 */
5
6/*
7 * Copyright (c) 2001-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
8 *
9 * Permission is hereby granted, free of charge, to any person
10 * obtaining a copy of this software and associated documentation
11 * files (the "Software"), to deal in the Software without
12 * restriction, including without limitation the rights to use,
13 * copy, modify, merge, publish, distribute, sublicense, and/or sell
14 * copies of the Software, and to permit persons to whom the
15 * Software is furnished to do so, subject to the following
16 * conditions:
17 *
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
23 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
25 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
28 * OTHER DEALINGS IN THE SOFTWARE.
29 */
30
31/** @page pg_kAvlTmpl Template Configuration.
32 *
33 * This is a templated implementation of Red-Black trees in C. The template
34 * parameters relates to the kind of key used and how duplicates are treated.
35 *
36 * \#define KRB_EQUAL_ALLOWED
37 * Define this to tell us that equal keys are allowed.
38 * Then Equal keys will be put in a list pointed to by KRBNODE::pList.
39 * This is by default not defined.
40 *
41 * \#define KRB_CHECK_FOR_EQUAL_INSERT
42 * Define this to enable insert check for equal nodes.
43 * This is by default not defined.
44 *
45 * \#define KRB_MAX_STACK
46 * Use this to specify the max number of stack entries the stack will use when
47 * inserting and removing nodes from the tree. The size should be something like
48 * log2(<max nodes>) + 3
49 * Must be defined.
50 *
51 * \#define KRB_RANGE
52 * Define this to enable key ranges.
53 *
54 * \#define KRB_OFFSET
55 * Define this to link the tree together using self relative offset
56 * instead of memory pointers, thus making the entire tree relocatable
57 * provided all the nodes - including the root node variable - are moved
58 * the exact same distance.
59 *
60 * \#define KRB_CACHE_SIZE
61 * Define this to employ a lookthru cache (direct) to speed up lookup for
62 * some usage patterns. The value should be the number of members of the array.
63 *
64 * \#define KRB_CACHE_HASH(Key)
65 * Define this to specify a more efficient translation of the key into
66 * a lookthru array index. The default is key % size.
67 * For some key types this is required as the default will not compile.
68 *
69 * \#define KRB_LOCKED
70 * Define this if you wish for the tree to be locked via the
71 * KRB_WRITE_LOCK, KRB_WRITE_UNLOCK, KRB_READ_LOCK and
72 * KRB_READ_UNLOCK macros. If not defined the tree will not be subject
73 * do any kind of locking and the problem of concurrency is left the user.
74 *
75 * \#define KRB_WRITE_LOCK(pRoot)
76 * Lock the tree for writing.
77 *
78 * \#define KRB_WRITE_UNLOCK(pRoot)
79 * Counteracts KRB_WRITE_LOCK.
80 *
81 * \#define KRB_READ_LOCK(pRoot)
82 * Lock the tree for reading.
83 *
84 * \#define KRB_READ_UNLOCK(pRoot)
85 * Counteracts KRB_READ_LOCK.
86 *
87 * \#define KRBKEY
88 * Define this to the name of the AVL key type.
89 *
90 * \#define KRB_STD_KEY_COMP
91 * Define this to use the standard key compare macros. If not set all the
92 * compare operations for KRBKEY have to be defined: KRB_CMP_G, KRB_CMP_E, KRB_CMP_NE,
93 * KRB_R_IS_IDENTICAL, KRB_R_IS_INTERSECTING and KRB_R_IS_IN_RANGE. The
94 * latter three are only required when KRB_RANGE is defined.
95 *
96 * \#define KRBNODE
97 * Define this to the name (typedef) of the AVL node structure. This
98 * structure must have a mpLeft, mpRight, mKey and mHeight member.
99 * If KRB_RANGE is defined a mKeyLast is also required.
100 * If KRB_EQUAL_ALLOWED is defined a mpList member is required.
101 * It's possible to use other member names by redefining the names.
102 *
103 * \#define KRBTREEPTR
104 * Define this to the name (typedef) of the tree pointer type. This is
105 * required when KRB_OFFSET is defined. When not defined it defaults
106 * to KRBNODE *.
107 *
108 * \#define KRBROOT
109 * Define this to the name (typedef) of the AVL root structure. This
110 * is optional. However, if specified it must at least have a mpRoot
111 * member of KRBTREEPTR type. If KRB_CACHE_SIZE is non-zero a
112 * maLookthru[KRB_CACHE_SIZE] member of the KRBTREEPTR type is also
113 * required.
114 *
115 * \#define KRB_FN
116 * Use this to alter the names of the AVL functions.
117 * Must be defined.
118 *
119 * \#define KRB_TYPE(prefix, name)
120 * Use this to make external type names and unique. The prefix may be empty.
121 * Must be defined.
122 *
123 * \#define KRB_INT(name)
124 * Use this to make internal type names and unique. The prefix may be empty.
125 * Must be defined.
126 *
127 * \#define KRB_DECL(rettype)
128 * Function declaration macro that should be set according to the scope
129 * the instantiated template should have. For instance an inlined scope
130 * (private or public) should K_DECL_INLINE(rettype) here.
131 *
132 * This version of the kAVL tree offers the option of inlining the entire
133 * implementation. This depends on the compiler doing a decent job in both
134 * making use of the inlined code and to eliminate const variables.
135 */
136
137
138/*******************************************************************************
139* Internal Functions *
140*******************************************************************************/
141#include <k/kDefs.h>
142#include <k/kTypes.h>
143#include <k/kHlpAssert.h>
144
145
146/*******************************************************************************
147* Defined Constants And Macros *
148*******************************************************************************/
149/** @def KRB_GET_POINTER
150 * Reads a 'pointer' value.
151 *
152 * @returns The native pointer.
153 * @param pp Pointer to the pointer to read.
154 * @internal
155 */
156
157/** @def KRB_GET_POINTER_NULL
158 * Reads a 'pointer' value which can be KRB_NULL.
159 *
160 * @returns The native pointer.
161 * @returns NULL pointer if KRB_NULL.
162 * @param pp Pointer to the pointer to read.
163 * @internal
164 */
165
166/** @def KRB_SET_POINTER
167 * Writes a 'pointer' value.
168 * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
169 *
170 * @returns stored pointer.
171 * @param pp Pointer to where to store the pointer.
172 * @param p Native pointer to assign to *pp.
173 * @internal
174 */
175
176/** @def KRB_SET_POINTER_NULL
177 * Writes a 'pointer' value which can be KRB_NULL.
178 *
179 * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
180 * if p is not KRB_NULL of course.
181 *
182 * @returns stored pointer.
183 * @param pp Pointer to where to store the pointer.
184 * @param pp2 Pointer to where to pointer to assign to pp. This can be KRB_NULL
185 * @internal
186 */
187
188#ifndef KRBTREEPTR
189# define KRBTREEPTR KRBNODE *
190#endif
191
192#ifndef KRBROOT
193# define KRBROOT KRB_TYPE(,ROOT)
194# define KRB_NEED_KRBROOT
195#endif
196
197#ifdef KRB_CACHE_SIZE
198# ifndef KRB_CACHE_HASH
199# define KRB_CACHE_HASH(Key) ( (Key) % (KRB_CACHE_SIZE) )
200# endif
201#elif defined(KRB_CACHE_HASH)
202# error "KRB_CACHE_HASH without KRB_CACHE_SIZE!"
203#endif
204
205#ifdef KRB_CACHE_SIZE
206# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) \
207 do { \
208 KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \
209 if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \
210 *ppEntry = KRB_NULL; \
211 } while (0)
212#else
213# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
214#endif
215
216#ifndef KRB_LOCKED
217# define KRB_WRITE_LOCK(pRoot) do { } while (0)
218# define KRB_WRITE_UNLOCK(pRoot) do { } while (0)
219# define KRB_READ_LOCK(pRoot) do { } while (0)
220# define KRB_READ_UNLOCK(pRoot) do { } while (0)
221#endif
222
223#ifdef KRB_OFFSET
224# define KRB_GET_POINTER(pp) ( (KRBNODE *)((KIPTR)(pp) + *(pp)) )
225# define KRB_GET_POINTER_NULL(pp) ( *(pp) != KRB_NULL ? KRB_GET_POINTER(pp) : NULL )
226# define KRB_SET_POINTER(pp, p) ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
227# define KRB_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KRB_NULL ? (KIPTR)KRB_GET_POINTER(pp2) - (KIPTR)(pp) : KRB_NULL )
228#else
229# define KRB_GET_POINTER(pp) ( *(pp) )
230# define KRB_GET_POINTER_NULL(pp) ( *(pp) )
231# define KRB_SET_POINTER(pp, p) ( (*(pp)) = (p) )
232# define KRB_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) )
233#endif
234
235
236/** @def KRB_NULL
237 * The NULL 'pointer' equivalent.
238 */
239#ifdef KRB_OFFSET
240# define KRB_NULL 0
241#else
242# define KRB_NULL NULL
243#endif
244
245#ifdef KRB_STD_KEY_COMP
246# define KRB_CMP_G(key1, key2) ( (key1) > (key2) )
247# define KRB_CMP_E(key1, key2) ( (key1) == (key2) )
248# define KRB_CMP_NE(key1, key2) ( (key1) != (key2) )
249# ifdef KRB_RANGE
250# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
251# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
252# define KRB_R_IS_IN_RANGE(key1B, key1E, key2) KRB_R_IS_INTERSECTING(key1B, key2, key1E, key2)
253# endif
254#endif
255
256#ifndef KRB_RANGE
257# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B)
258# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B)
259#endif
260
261
262/** Is the node red or black?
263 * @returns true / false
264 * @param pNode Pointer to the node in question.
265 * @remarks All NULL pointers are considered black leaf nodes.
266 */
267#define KRB_IS_RED(pNode) ( (pNode) != NULL && (pNode)->mfIsRed )
268
269
270/*******************************************************************************
271* Structures and Typedefs *
272*******************************************************************************/
273/**
274 * Stack used to avoid recursive calls during insert and removal.
275 */
276typedef struct
277{
278 unsigned cEntries;
279 KRBTREEPTR *aEntries[KRB_MAX_STACK];
280} KRB_INT(STACK);
281
282/**
283 * The callback used by the Destroy and DoWithAll functions.
284 */
285typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE *, void *);
286
287#ifdef KRB_NEED_KRBROOT
288/**
289 * The Red-Black tree root structure.
290 */
291typedef struct
292{
293 KRBTREEPTR mpRoot;
294# ifdef KRB_CACHE_SIZE
295 KRBTREEPTR maLookthru[KRB_CACHE_SIZE];
296# endif
297} KRBROOT;
298#endif
299
300
301
302/**
303 * Initializes the root of the Red-Black tree.
304 *
305 * @param pTree Pointer to the root structure.
306 */
307KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot)
308{
309#ifdef KRB_CACHE_SIZE
310 unsigned i;
311#endif
312
313 pRoot->mpRoot = KRB_NULL;
314#ifdef KRB_CACHE_SIZE
315 for (i = 0; i < (KRB_CACHE_SIZE); i++)
316 pRoot->maLookthru[i] = KRB_NULL;
317#endif
318}
319
320
321/**
322 * Rotates the tree to the left (shift direction) and recolors the nodes.
323 *
324 * @pre
325 *
326 * 2 4
327 * / \ / \
328 * 1 4 ==> 2 5
329 * / \ / \
330 * 3 5 1 3
331 *
332 * @endpre
333 *
334 * @returns The new root node.
335 * @param pRoot The root node.
336 *
337 * @remarks This will not update any pointer <tt>to</tt> the root node!
338 */
339K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateLeft)(KRBNODE *pRoot)
340{
341 KRBNODE *pNewRoot = pRoot->mRight;
342 pRoot->mRight = pNewRoot->mLeft;
343 pNewRoot->mLeft = pRoot;
344
345 pRoot->mfIsRed = 1;
346 pNewRoot->mfIsRed = 0;
347 return pNewRoot;
348}
349
350
351/**
352 * Rotates the tree to the right (shift direction) and recolors the nodes.
353 *
354 * @pre
355 *
356 * 4 2
357 * / \ / \
358 * 2 5 ==> 1 4
359 * / \ / \
360 * 1 3 3 5
361 *
362 * @endpre
363 *
364 * @returns The new root node.
365 * @param pRoot The root node.
366 *
367 * @remarks This will not update any pointer <tt>to</tt> the root node!
368 */
369K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateRight)(KRBNODE *pRoot)
370{
371 KRBNODE *pNewRoot = pRoot->mLeft;
372 pRoot->mLeft = pNewRoot->mRight;
373 pNewRoot->mRight = pRoot;
374
375 pRoot->mfIsRed = 1;
376 pNewRoot->mfIsRed = 0;
377 return pNewRoot;
378}
379
380
381/**
382 * Performs a double left rotation with recoloring.
383 *
384 * @pre
385 *
386 * 2 2 4
387 * / \ / \ / \
388 * 1 6 ==> 1 4 ==> 2 6
389 * / \ / \ / \ / \
390 * 4 7 3 6 1 3 5 7
391 * / \ / \
392 * 3 5 5 7
393 * @endpre
394 *
395 * @returns The new root node.
396 * @param pRoot The root node.
397 *
398 * @remarks This will not update any pointer <tt>to</tt> the root node!
399 */
400K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateLeft)(KRBNODE *pRoot)
401{
402 pRoot->mRight = KAVL_FN(RotateRight)(pRoot->mRight);
403 return KAVL_FN(RotateLeft)(pRoot);
404}
405
406
407/**
408 * Performs a double right rotation with recoloring.
409 *
410 * @pre
411 * 6 6 4
412 * / \ / \ / \
413 * 2 7 4 7 2 6
414 * / \ ==> / \ ==> / \ / \
415 * 1 4 2 5 1 3 5 7
416 * / \ / \
417 * 3 5 1 3
418 *
419 * @endpre
420 *
421 * @returns The new root node.
422 * @param pRoot The root node.
423 *
424 * @remarks This will not update any pointer <tt>to</tt> the root node!
425 */
426K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateRight)(KRBNODE *pRoot)
427{
428 pRoot->mLeft = KAVL_FN(RotateLeft)(pRoot->mLeft);
429 return KAVL_FN(RotateRight)(pRoot);
430}
431
432
433/**
434 * Inserts a node into the Red-Black tree.
435 * @returns K_TRUE if inserted.
436 * K_FALSE if node exists in tree.
437 * @param pRoot Pointer to the Red-Back tree's root structure.
438 * @param pNode Pointer to the node which is to be added.
439 */
440KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT *pRoot, KRBNODE *pNode)
441{
442 KRBTREEPTR *ppCurNode = &pRoot->mpRoot;
443 register KRBKEY Key = pNode->mKey;
444#ifdef KRB_RANGE
445 register KRBKEY KeyLast = pNode->mKeyLast;
446#endif
447
448#ifdef KRB_RANGE
449 if (Key > KeyLast)
450 return K_FALSE;
451#endif
452
453 KRB_WRITE_LOCK(pRoot);
454
455 Stack.cEntries = 0;
456 while (*ppCurNode != KRB_NULL)
457 {
458 register KRBNODE *pCurNode = KRB_GET_POINTER(ppCurNode);
459
460 kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
461 Stack.aEntries[Stack.cEntries++] = ppCurNode;
462#ifdef KRB_EQUAL_ALLOWED
463 if (KRB_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
464 {
465 /*
466 * If equal then we'll use a list of equal nodes.
467 */
468 pNode->mpLeft = pNode->mpRight = KRB_NULL;
469 pNode->mHeight = 0;
470 KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
471 KRB_SET_POINTER(&pCurNode->mpList, pNode);
472 KRB_WRITE_UNLOCK(pRoot);
473 return K_TRUE;
474 }
475#endif
476#ifdef KRB_CHECK_FOR_EQUAL_INSERT
477 if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
478 {
479 KRB_WRITE_UNLOCK(pRoot);
480 return K_FALSE;
481 }
482#endif
483 if (KRB_CMP_G(pCurNode->mKey, Key))
484 ppCurNode = &pCurNode->mpLeft;
485 else
486 ppCurNode = &pCurNode->mpRight;
487 }
488
489 pNode->mpLeft = pNode->mpRight = KRB_NULL;
490#ifdef KRB_EQUAL_ALLOWED
491 pNode->mpList = KRB_NULL;
492#endif
493 pNode->mHeight = 1;
494 KRB_SET_POINTER(ppCurNode, pNode);
495
496 KRB_FN(Rebalance)(&Stack);
497
498 KRB_WRITE_UNLOCK(pRoot);
499 return K_TRUE;
500}
501
502
503/**
504 * Removes a node from the Red-Black tree.
505 * @returns Pointer to the node.
506 * @param pRoot Pointer to the Red-Back tree's root structure.
507 * @param Key Key value of the node which is to be removed.
508 * @sketch Find the node which is to be removed:
509 * LOOP until not found
510 * BEGIN
511 * Add node pointer pointer to the AVL-stack.
512 * IF the keys matches THEN break!
513 * IF remove key < node key THEN
514 * left
515 * ELSE
516 * right
517 * END
518 * IF found THEN
519 * BEGIN
520 * IF left node not empty THEN
521 * BEGIN
522 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
523 * Start at left node.
524 * LOOP until right node is empty
525 * BEGIN
526 * Add to stack.
527 * go right.
528 * END
529 * Link out the found node.
530 * Replace the node which is to be removed with the found node.
531 * Correct the stack entry for the pointer to the left tree.
532 * END
533 * ELSE
534 * BEGIN
535 * Move up right node.
536 * Remove last stack entry.
537 * END
538 * Balance tree using stack.
539 * END
540 * return pointer to the removed node (if found).
541 */
542KRB_DECL(KRBNODE *) KRB_FN(Remove)(KRBROOT *pRoot, KRBKEY Key)
543{
544 KRB_INT(STACK) Stack;
545 KRBTREEPTR *ppDeleteNode = &pRoot->mpRoot;
546 register KRBNODE *pDeleteNode;
547
548 KRB_WRITE_LOCK(pRoot);
549
550 Stack.cEntries = 0;
551 for (;;)
552 {
553 if (*ppDeleteNode == KRB_NULL)
554 {
555 KRB_WRITE_UNLOCK(pRoot);
556 return NULL;
557 }
558 pDeleteNode = KRB_GET_POINTER(ppDeleteNode);
559
560 kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
561 Stack.aEntries[Stack.cEntries++] = ppDeleteNode;
562 if (KRB_CMP_E(pDeleteNode->mKey, Key))
563 break;
564
565 if (KRB_CMP_G(pDeleteNode->mKey, Key))
566 ppDeleteNode = &pDeleteNode->mpLeft;
567 else
568 ppDeleteNode = &pDeleteNode->mpRight;
569 }
570
571 if (pDeleteNode->mpLeft != KRB_NULL)
572 {
573 /* find the rightmost node in the left tree. */
574 const unsigned iStackEntry = Stack.cEntries;
575 KRBTREEPTR *ppLeftLeast = &pDeleteNode->mpLeft;
576 register KRBNODE *pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
577
578 while (pLeftLeast->mpRight != KRB_NULL)
579 {
580 kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
581 Stack.aEntries[Stack.cEntries++] = ppLeftLeast;
582 ppLeftLeast = &pLeftLeast->mpRight;
583 pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
584 }
585
586 /* link out pLeftLeast */
587 KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
588
589 /* link it in place of the delete node. */
590 KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
591 KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
592 pLeftLeast->mHeight = pDeleteNode->mHeight;
593 KRB_SET_POINTER(ppDeleteNode, pLeftLeast);
594 Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
595 }
596 else
597 {
598 KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
599 Stack.cEntries--;
600 }
601
602 KRB_FN(Rebalance)(&Stack);
603
604 KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
605
606 KRB_WRITE_UNLOCK(pRoot);
607 return pDeleteNode;
608}
609
Note: See TracBrowser for help on using the repository browser.