kRbBase.h@ 35

Last change on this file since 35 was 35, checked in by bird, 15 years ago
Templated red-black trees - kick off.
Property svn:eol-style set to `native` Property svn:keywords set to `Id Revision`
File size: 16.6 KB

Line
1	/* $Id: kRbBase.h 35 2009-11-08 19:39:03Z 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	#define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
150
151	/** @def KRB_GET_POINTER
152	* Reads a 'pointer' value.
153	*
154	* @returns The native pointer.
155	* @param pp Pointer to the pointer to read.
156	* @internal
157	*/
158
159	/** @def KRB_GET_POINTER_NULL
160	* Reads a 'pointer' value which can be KRB_NULL.
161	*
162	* @returns The native pointer.
163	* @returns NULL pointer if KRB_NULL.
164	* @param pp Pointer to the pointer to read.
165	* @internal
166	*/
167
168	/** @def KRB_SET_POINTER
169	* Writes a 'pointer' value.
170	* For offset-based schemes offset relative to pp is calculated and assigned to *pp.
171	*
172	* @returns stored pointer.
173	* @param pp Pointer to where to store the pointer.
174	* @param p Native pointer to assign to *pp.
175	* @internal
176	*/
177
178	/** @def KRB_SET_POINTER_NULL
179	* Writes a 'pointer' value which can be KRB_NULL.
180	*
181	* For offset-based schemes offset relative to pp is calculated and assigned to *pp,
182	* if p is not KRB_NULL of course.
183	*
184	* @returns stored pointer.
185	* @param pp Pointer to where to store the pointer.
186	* @param pp2 Pointer to where to pointer to assign to pp. This can be KRB_NULL
187	* @internal
188	*/
189
190	#ifndef KRBTREEPTR
191	# define KRBTREEPTR KRBNODE *
192	#endif
193
194	#ifndef KRBROOT
195	# define KRBROOT KRB_TYPE(,ROOT)
196	# define KRB_NEED_KRBROOT
197	#endif
198
199	#ifdef KRB_CACHE_SIZE
200	# ifndef KRB_CACHE_HASH
201	# define KRB_CACHE_HASH(Key) ( (Key) % (KRB_CACHE_SIZE) )
202	# endif
203	#elif defined(KRB_CACHE_HASH)
204	# error "KRB_CACHE_HASH without KRB_CACHE_SIZE!"
205	#endif
206
207	#ifdef KRB_CACHE_SIZE
208	# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) \
209	do { \
210	KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \
211	if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \
212	*ppEntry = KRB_NULL; \
213	} while (0)
214	#else
215	# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
216	#endif
217
218	#ifndef KRB_LOCKED
219	# define KRB_WRITE_LOCK(pRoot) do { } while (0)
220	# define KRB_WRITE_UNLOCK(pRoot) do { } while (0)
221	# define KRB_READ_LOCK(pRoot) do { } while (0)
222	# define KRB_READ_UNLOCK(pRoot) do { } while (0)
223	#endif
224
225	#ifdef KRB_OFFSET
226	# define KRB_GET_POINTER(pp) ( (KRBNODE )((KIPTR)(pp) + (pp)) )
227	# define KRB_GET_POINTER_NULL(pp) ( *(pp) != KRB_NULL ? KRB_GET_POINTER(pp) : NULL )
228	# define KRB_SET_POINTER(pp, p) ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
229	# define KRB_SET_POINTER_NULL(pp, pp2) ( ((pp)) = (pp2) != KRB_NULL ? (KIPTR)KRB_GET_POINTER(pp2) - (KIPTR)(pp) : KRB_NULL )
230	#else
231	# define KRB_GET_POINTER(pp) ( *(pp) )
232	# define KRB_GET_POINTER_NULL(pp) ( *(pp) )
233	# define KRB_SET_POINTER(pp, p) ( (*(pp)) = (p) )
234	# define KRB_SET_POINTER_NULL(pp, pp2) ( ((pp)) = (pp2) )
235	#endif
236
237
238	/** @def KRB_NULL
239	* The NULL 'pointer' equivalent.
240	*/
241	#ifdef KRB_OFFSET
242	# define KRB_NULL 0
243	#else
244	# define KRB_NULL NULL
245	#endif
246
247	#ifdef KRB_STD_KEY_COMP
248	# define KRB_CMP_G(key1, key2) ( (key1) > (key2) )
249	# define KRB_CMP_E(key1, key2) ( (key1) == (key2) )
250	# define KRB_CMP_NE(key1, key2) ( (key1) != (key2) )
251	# ifdef KRB_RANGE
252	# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) )
253	# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) )
254	# define KRB_R_IS_IN_RANGE(key1B, key1E, key2) KRB_R_IS_INTERSECTING(key1B, key2, key1E, key2)
255	# endif
256	#endif
257
258	#ifndef KRB_RANGE
259	# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B)
260	# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B)
261	#endif
262
263
264
265	/*******************************************************************************
266	* Structures and Typedefs *
267	*******************************************************************************/
268	/**
269	* Stack used to avoid recursive calls during insert and removal.
270	*/
271	typedef struct
272	{
273	unsigned cEntries;
274	KRBTREEPTR *aEntries[KRB_MAX_STACK];
275	} KRB_INT(STACK);
276
277	/**
278	* The callback used by the Destroy and DoWithAll functions.
279	*/
280	typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE , void );
281
282	#ifdef KRB_NEED_KRBROOT
283	/**
284	* The Red-Black tree root structure.
285	*/
286	typedef struct
287	{
288	KRBTREEPTR mpRoot;
289	# ifdef KRB_CACHE_SIZE
290	KRBTREEPTR maLookthru[KRB_CACHE_SIZE];
291	# endif
292	} KRBROOT;
293	#endif
294
295
296
297	/**
298	* Initializes the root of the Red-Black tree.
299	*
300	* @param pTree Pointer to the root structure.
301	*/
302	KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot)
303	{
304	#ifdef KRB_CACHE_SIZE
305	unsigned i;
306	#endif
307
308	pRoot->mpRoot = KRB_NULL;
309	#ifdef KRB_CACHE_SIZE
310	for (i = 0; i < (KRB_CACHE_SIZE); i++)
311	pRoot->maLookthru[i] = KRB_NULL;
312	#endif
313	}
314
315
316	/**
317	* Inserts a node into the Red-Black tree.
318	* @returns K_TRUE if inserted.
319	* K_FALSE if node exists in tree.
320	* @param pRoot Pointer to the Red-Back tree's root structure.
321	* @param pNode Pointer to the node which is to be added.
322	* @sketch Find the location of the node (using binary tree algorithm.):
323	* LOOP until NULL leaf pointer
324	* BEGIN
325	* Add node pointer pointer to the AVL-stack.
326	* IF new-node-key < node key THEN
327	* left
328	* ELSE
329	* right
330	* END
331	* Fill in leaf node and insert it.
332	* Rebalance the tree.
333	*/
334	KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT pRoot, KRBNODE pNode)
335	{
336	KRB_INT(STACK) Stack;
337	KRBTREEPTR *ppCurNode = &pRoot->mpRoot;
338	register KRBKEY Key = pNode->mKey;
339	#ifdef KRB_RANGE
340	register KRBKEY KeyLast = pNode->mKeyLast;
341	#endif
342
343	#ifdef KRB_RANGE
344	if (Key > KeyLast)
345	return false;
346	#endif
347
348	KRB_WRITE_LOCK(pRoot);
349
350	Stack.cEntries = 0;
351	while (*ppCurNode != KRB_NULL)
352	{
353	register KRBNODE *pCurNode = KRB_GET_POINTER(ppCurNode);
354
355	kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
356	Stack.aEntries[Stack.cEntries++] = ppCurNode;
357	#ifdef KRB_EQUAL_ALLOWED
358	if (KRB_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
359	{
360	/*
361	* If equal then we'll use a list of equal nodes.
362	*/
363	pNode->mpLeft = pNode->mpRight = KRB_NULL;
364	pNode->mHeight = 0;
365	KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
366	KRB_SET_POINTER(&pCurNode->mpList, pNode);
367	KRB_WRITE_UNLOCK(pRoot);
368	return K_TRUE;
369	}
370	#endif
371	#ifdef KRB_CHECK_FOR_EQUAL_INSERT
372	if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
373	{
374	KRB_WRITE_UNLOCK(pRoot);
375	return K_FALSE;
376	}
377	#endif
378	if (KRB_CMP_G(pCurNode->mKey, Key))
379	ppCurNode = &pCurNode->mpLeft;
380	else
381	ppCurNode = &pCurNode->mpRight;
382	}
383
384	pNode->mpLeft = pNode->mpRight = KRB_NULL;
385	#ifdef KRB_EQUAL_ALLOWED
386	pNode->mpList = KRB_NULL;
387	#endif
388	pNode->mHeight = 1;
389	KRB_SET_POINTER(ppCurNode, pNode);
390
391	KRB_FN(Rebalance)(&Stack);
392
393	KRB_WRITE_UNLOCK(pRoot);
394	return K_TRUE;
395	}
396
397
398	/**
399	* Removes a node from the Red-Black tree.
400	* @returns Pointer to the node.
401	* @param pRoot Pointer to the Red-Back tree's root structure.
402	* @param Key Key value of the node which is to be removed.
403	* @sketch Find the node which is to be removed:
404	* LOOP until not found
405	* BEGIN
406	* Add node pointer pointer to the AVL-stack.
407	* IF the keys matches THEN break!
408	* IF remove key < node key THEN
409	* left
410	* ELSE
411	* right
412	* END
413	* IF found THEN
414	* BEGIN
415	* IF left node not empty THEN
416	* BEGIN
417	* Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
418	* Start at left node.
419	* LOOP until right node is empty
420	* BEGIN
421	* Add to stack.
422	* go right.
423	* END
424	* Link out the found node.
425	* Replace the node which is to be removed with the found node.
426	* Correct the stack entry for the pointer to the left tree.
427	* END
428	* ELSE
429	* BEGIN
430	* Move up right node.
431	* Remove last stack entry.
432	* END
433	* Balance tree using stack.
434	* END
435	* return pointer to the removed node (if found).
436	*/
437	KRB_DECL(KRBNODE ) KRB_FN(Remove)(KRBROOT pRoot, KRBKEY Key)
438	{
439	KRB_INT(STACK) Stack;
440	KRBTREEPTR *ppDeleteNode = &pRoot->mpRoot;
441	register KRBNODE *pDeleteNode;
442
443	KRB_WRITE_LOCK(pRoot);
444
445	Stack.cEntries = 0;
446	for (;;)
447	{
448	if (*ppDeleteNode == KRB_NULL)
449	{
450	KRB_WRITE_UNLOCK(pRoot);
451	return NULL;
452	}
453	pDeleteNode = KRB_GET_POINTER(ppDeleteNode);
454
455	kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
456	Stack.aEntries[Stack.cEntries++] = ppDeleteNode;
457	if (KRB_CMP_E(pDeleteNode->mKey, Key))
458	break;
459
460	if (KRB_CMP_G(pDeleteNode->mKey, Key))
461	ppDeleteNode = &pDeleteNode->mpLeft;
462	else
463	ppDeleteNode = &pDeleteNode->mpRight;
464	}
465
466	if (pDeleteNode->mpLeft != KRB_NULL)
467	{
468	/* find the rightmost node in the left tree. */
469	const unsigned iStackEntry = Stack.cEntries;
470	KRBTREEPTR *ppLeftLeast = &pDeleteNode->mpLeft;
471	register KRBNODE *pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
472
473	while (pLeftLeast->mpRight != KRB_NULL)
474	{
475	kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
476	Stack.aEntries[Stack.cEntries++] = ppLeftLeast;
477	ppLeftLeast = &pLeftLeast->mpRight;
478	pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
479	}
480
481	/* link out pLeftLeast */
482	KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
483
484	/* link it in place of the delete node. */
485	KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
486	KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
487	pLeftLeast->mHeight = pDeleteNode->mHeight;
488	KRB_SET_POINTER(ppDeleteNode, pLeftLeast);
489	Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
490	}
491	else
492	{
493	KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
494	Stack.cEntries--;
495	}
496
497	KRB_FN(Rebalance)(&Stack);
498
499	KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
500
501	KRB_WRITE_UNLOCK(pRoot);
502	return pDeleteNode;
503	}
504

Note: See TracBrowser for help on using the repository browser.

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

Download in other formats: