kRbBase.h@ 38

Last change on this file since 38 was 38, checked in by bird, 15 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 <[email protected]>
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	*/
276	typedef 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	*/
285	typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE , void );
286
287	#ifdef KRB_NEED_KRBROOT
288	/**
289	* The Red-Black tree root structure.
290	*/
291	typedef 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	*/
307	KRB_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	*/
339	K_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	*/
369	K_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	*/
400	K_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	*/
426	K_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	*/
440	KRB_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	*/
542	KRB_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.

source: kStuff/trunk/include/k/kRbTmpl/kRbBase.h@ 38

Download in other formats: