diff options
Diffstat (limited to 'src/lib/kStuff/include/k/kRbTmpl')
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbAssert.h | 136 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbBase.h | 609 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbDestroy.h | 129 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbDoWithAll.h | 166 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbEnum.h | 187 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbGet.h | 89 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbGetBestFit.h | 112 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbGetWithParent.h | 65 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbRemove2.h | 133 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbRemoveBestFit.h | 70 | ||||
| -rw-r--r-- | src/lib/kStuff/include/k/kRbTmpl/kRbUndef.h | 79 |
11 files changed, 1775 insertions, 0 deletions
diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbAssert.h b/src/lib/kStuff/include/k/kRbTmpl/kRbAssert.h new file mode 100644 index 0000000..03c17a4 --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbAssert.h @@ -0,0 +1,136 @@ +/* $Id: kRbAssert.h 38 2009-11-10 00:01:38Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Assert Valid Tree. + */ + +/* + * Copyright (c) 2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + + +/** + * Internal helper for KRB_FN(Assert) + * + * @returns The number of black nodes. -1 is return if the tree is invalid. + * @param pRoot The root of the (sub-)tree to assert. + */ +K_DECL_INLINE(int) KRB_FN(AssertRecurse)(KRBNODE *pRoot) +{ + int cLeft; + int cRight; + + if (!pRoot) + /* leafs are black. */ + return 1; + +#ifdef KRB_EQUAL_ALLOWED + /* equal nodes are equal :) */ + if (pNode->mpList != KRB_NULL) + { + KRBROOT *pEqual; + for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->mpList)) + kHlpAssertReturn(K_CMP_E(pEqual->mKey, pNode->mKey), -1); + } +#endif + + /* binary tree. */ + kHlpAssertReturn(pRoot->mpLeft != KRB_NULL && KRB_CMP_G(KRB_GET_POINTER(&pRoot->mpLeft)->mpKey, pRoot->mKey), -1); + kHlpAssertReturn(pRoot->mpRight != KRB_NULL && KRB_CMP_G(pRoot->mKey, KRB_GET_POINTER(&pRoot->mpRigth)->mpKey), -1); + + /* both children of red nodes are black. */ + kHlpAssertReturn(!KRB_IS_RED(pRoot) || (!KRB_IS_RED(pRoot->mpLeft) && !KRB_IS_RED(pRoot->mpRight)), -1); + + /* all paths to leafs contains the same number of black nodes. */ + cLeft = KRB_FN(AssertRecurse)(KRB_GET_POINTER_NULL(&pRoot->mpLeft)); + cRight = KRB_FN(AssertRecurse)(KRB_GET_POINTER_NULL(&pRoot->mpRight)); + kHlpAssertMsgReturn(cLeft == cRight || cLeft == -1 || cRight == -1, ("%d vs. %d\n", cLeft, cRight), -1); + + return cLeft + !KRB_IS_RED(pRoot); +} + + +/** + * Asserts the validity of the Red-Black tree. + * + * This method is using recursion and may therefore consume quite a bit of stack + * on a large tree. + * + * @returns K_TRUE if valid. + * @returns K_FALSE if invalid, assertion raised on each violation. + * @param pRoot Pointer to the Red-Back tree's root structure. + */ +KRB_DECL(KBOOL) KRB_FN(Assert)(KRBROOT *pRoot) +{ + KBOOL fRc = K_TRUE; +#ifdef KRB_CACHE_SIZE + unsigned i; +#endif + KRBNODE *pNode; + + KRB_READ_LOCK(pRoot); + if (pRoot->mpRoot == KRB_NULL) + { + KRB_READ_UNLOCK(pRoot); + return 0; + } + +#ifdef KRB_CACHE_SIZE + /* + * Validate the cache. + */ + for (i = 0; i < (KRB_CACHE_SIZE); i++) + if (pRoot->maLookthru[i] != KRB_NULL) + { + KRBNODE pCache = KRB_GET_POINTER(&pRoot->maLookthru[i]); + + /** @todo ranges */ + kHlpAssertMsgStmt(i == KRB_CACHE_HASH(pCache->Key), ("Invalid cache entry %u, hashed to %u\n", i, KRB_CACHE_HASH(pCache->Key)), fRc = K_FALSE); + + pNode = KRB_GET_POINTER(&pRoot->mpRoot); + while (pNode) + { + if (KRB_CMP_E(pCache->mKey, pNode->mKey)) + { + kHlpAssertMsgStmt(pNode == pCache, ("Invalid cache entry %u=%p, found %p\n", i, pCache, pNode), fRc = K_FALSE); + break; + } + if (KRB_CMP_G(pCache->mKey, pNode->mKey)) + pNode = KRB_GET_POINTER_NULL(&pNode->mRight); + else + pNode = KRB_GET_POINTER_NULL(&pNode->mLeft); + } + kHlpAssertMsgStmt(pNode, ("Invalid cache entry %u/%p - not found\n", i, pCache), fRc = K_FALSE); + } +#endif + + /* + * Recurse thru the tree. + */ + if (KRB_FN(AssertRecurse)(KRB_GET_POINTER(&pRoot->mpRoot)) == -1) + fRc = K_FALSE; + + KRB_READ_UNLOCK(pRoot); + return fRc; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbBase.h b/src/lib/kStuff/include/k/kRbTmpl/kRbBase.h new file mode 100644 index 0000000..c79f7ce --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbBase.h @@ -0,0 +1,609 @@ +/* $Id: kRbBase.h 38 2009-11-10 00:01:38Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, The Mandatory Base Code. + */ + +/* + * Copyright (c) 2001-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** @page pg_kAvlTmpl Template Configuration. + * + * This is a templated implementation of Red-Black trees in C. The template + * parameters relates to the kind of key used and how duplicates are treated. + * + * \#define KRB_EQUAL_ALLOWED + * Define this to tell us that equal keys are allowed. + * Then Equal keys will be put in a list pointed to by KRBNODE::pList. + * This is by default not defined. + * + * \#define KRB_CHECK_FOR_EQUAL_INSERT + * Define this to enable insert check for equal nodes. + * This is by default not defined. + * + * \#define KRB_MAX_STACK + * Use this to specify the max number of stack entries the stack will use when + * inserting and removing nodes from the tree. The size should be something like + * log2(<max nodes>) + 3 + * Must be defined. + * + * \#define KRB_RANGE + * Define this to enable key ranges. + * + * \#define KRB_OFFSET + * Define this to link the tree together using self relative offset + * instead of memory pointers, thus making the entire tree relocatable + * provided all the nodes - including the root node variable - are moved + * the exact same distance. + * + * \#define KRB_CACHE_SIZE + * Define this to employ a lookthru cache (direct) to speed up lookup for + * some usage patterns. The value should be the number of members of the array. + * + * \#define KRB_CACHE_HASH(Key) + * Define this to specify a more efficient translation of the key into + * a lookthru array index. The default is key % size. + * For some key types this is required as the default will not compile. + * + * \#define KRB_LOCKED + * Define this if you wish for the tree to be locked via the + * KRB_WRITE_LOCK, KRB_WRITE_UNLOCK, KRB_READ_LOCK and + * KRB_READ_UNLOCK macros. If not defined the tree will not be subject + * do any kind of locking and the problem of concurrency is left the user. + * + * \#define KRB_WRITE_LOCK(pRoot) + * Lock the tree for writing. + * + * \#define KRB_WRITE_UNLOCK(pRoot) + * Counteracts KRB_WRITE_LOCK. + * + * \#define KRB_READ_LOCK(pRoot) + * Lock the tree for reading. + * + * \#define KRB_READ_UNLOCK(pRoot) + * Counteracts KRB_READ_LOCK. + * + * \#define KRBKEY + * Define this to the name of the AVL key type. + * + * \#define KRB_STD_KEY_COMP + * Define this to use the standard key compare macros. If not set all the + * compare operations for KRBKEY have to be defined: KRB_CMP_G, KRB_CMP_E, KRB_CMP_NE, + * KRB_R_IS_IDENTICAL, KRB_R_IS_INTERSECTING and KRB_R_IS_IN_RANGE. The + * latter three are only required when KRB_RANGE is defined. + * + * \#define KRBNODE + * Define this to the name (typedef) of the AVL node structure. This + * structure must have a mpLeft, mpRight, mKey and mHeight member. + * If KRB_RANGE is defined a mKeyLast is also required. + * If KRB_EQUAL_ALLOWED is defined a mpList member is required. + * It's possible to use other member names by redefining the names. + * + * \#define KRBTREEPTR + * Define this to the name (typedef) of the tree pointer type. This is + * required when KRB_OFFSET is defined. When not defined it defaults + * to KRBNODE *. + * + * \#define KRBROOT + * Define this to the name (typedef) of the AVL root structure. This + * is optional. However, if specified it must at least have a mpRoot + * member of KRBTREEPTR type. If KRB_CACHE_SIZE is non-zero a + * maLookthru[KRB_CACHE_SIZE] member of the KRBTREEPTR type is also + * required. + * + * \#define KRB_FN + * Use this to alter the names of the AVL functions. + * Must be defined. + * + * \#define KRB_TYPE(prefix, name) + * Use this to make external type names and unique. The prefix may be empty. + * Must be defined. + * + * \#define KRB_INT(name) + * Use this to make internal type names and unique. The prefix may be empty. + * Must be defined. + * + * \#define KRB_DECL(rettype) + * Function declaration macro that should be set according to the scope + * the instantiated template should have. For instance an inlined scope + * (private or public) should K_DECL_INLINE(rettype) here. + * + * This version of the kAVL tree offers the option of inlining the entire + * implementation. This depends on the compiler doing a decent job in both + * making use of the inlined code and to eliminate const variables. + */ + + +/******************************************************************************* +* Internal Functions * +*******************************************************************************/ +#include <k/kDefs.h> +#include <k/kTypes.h> +#include <k/kHlpAssert.h> + + +/******************************************************************************* +* Defined Constants And Macros * +*******************************************************************************/ +/** @def KRB_GET_POINTER + * Reads a 'pointer' value. + * + * @returns The native pointer. + * @param pp Pointer to the pointer to read. + * @internal + */ + +/** @def KRB_GET_POINTER_NULL + * Reads a 'pointer' value which can be KRB_NULL. + * + * @returns The native pointer. + * @returns NULL pointer if KRB_NULL. + * @param pp Pointer to the pointer to read. + * @internal + */ + +/** @def KRB_SET_POINTER + * Writes a 'pointer' value. + * For offset-based schemes offset relative to pp is calculated and assigned to *pp. + * + * @returns stored pointer. + * @param pp Pointer to where to store the pointer. + * @param p Native pointer to assign to *pp. + * @internal + */ + +/** @def KRB_SET_POINTER_NULL + * Writes a 'pointer' value which can be KRB_NULL. + * + * For offset-based schemes offset relative to pp is calculated and assigned to *pp, + * if p is not KRB_NULL of course. + * + * @returns stored pointer. + * @param pp Pointer to where to store the pointer. + * @param pp2 Pointer to where to pointer to assign to pp. This can be KRB_NULL + * @internal + */ + +#ifndef KRBTREEPTR +# define KRBTREEPTR KRBNODE * +#endif + +#ifndef KRBROOT +# define KRBROOT KRB_TYPE(,ROOT) +# define KRB_NEED_KRBROOT +#endif + +#ifdef KRB_CACHE_SIZE +# ifndef KRB_CACHE_HASH +# define KRB_CACHE_HASH(Key) ( (Key) % (KRB_CACHE_SIZE) ) +# endif +#elif defined(KRB_CACHE_HASH) +# error "KRB_CACHE_HASH without KRB_CACHE_SIZE!" +#endif + +#ifdef KRB_CACHE_SIZE +# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) \ + do { \ + KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \ + if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \ + *ppEntry = KRB_NULL; \ + } while (0) +#else +# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0) +#endif + +#ifndef KRB_LOCKED +# define KRB_WRITE_LOCK(pRoot) do { } while (0) +# define KRB_WRITE_UNLOCK(pRoot) do { } while (0) +# define KRB_READ_LOCK(pRoot) do { } while (0) +# define KRB_READ_UNLOCK(pRoot) do { } while (0) +#endif + +#ifdef KRB_OFFSET +# define KRB_GET_POINTER(pp) ( (KRBNODE *)((KIPTR)(pp) + *(pp)) ) +# define KRB_GET_POINTER_NULL(pp) ( *(pp) != KRB_NULL ? KRB_GET_POINTER(pp) : NULL ) +# define KRB_SET_POINTER(pp, p) ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) ) +# define KRB_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KRB_NULL ? (KIPTR)KRB_GET_POINTER(pp2) - (KIPTR)(pp) : KRB_NULL ) +#else +# define KRB_GET_POINTER(pp) ( *(pp) ) +# define KRB_GET_POINTER_NULL(pp) ( *(pp) ) +# define KRB_SET_POINTER(pp, p) ( (*(pp)) = (p) ) +# define KRB_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) ) +#endif + + +/** @def KRB_NULL + * The NULL 'pointer' equivalent. + */ +#ifdef KRB_OFFSET +# define KRB_NULL 0 +#else +# define KRB_NULL NULL +#endif + +#ifdef KRB_STD_KEY_COMP +# define KRB_CMP_G(key1, key2) ( (key1) > (key2) ) +# define KRB_CMP_E(key1, key2) ( (key1) == (key2) ) +# define KRB_CMP_NE(key1, key2) ( (key1) != (key2) ) +# ifdef KRB_RANGE +# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) ( (key1B) == (key2B) && (key1E) == (key2E) ) +# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) ( (key1B) <= (key2E) && (key1E) >= (key2B) ) +# define KRB_R_IS_IN_RANGE(key1B, key1E, key2) KRB_R_IS_INTERSECTING(key1B, key2, key1E, key2) +# endif +#endif + +#ifndef KRB_RANGE +# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B) +# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KRB_CMP_E(key1B, key2B) +#endif + + +/** Is the node red or black? + * @returns true / false + * @param pNode Pointer to the node in question. + * @remarks All NULL pointers are considered black leaf nodes. + */ +#define KRB_IS_RED(pNode) ( (pNode) != NULL && (pNode)->mfIsRed ) + + +/******************************************************************************* +* Structures and Typedefs * +*******************************************************************************/ +/** + * Stack used to avoid recursive calls during insert and removal. + */ +typedef struct +{ + unsigned cEntries; + KRBTREEPTR *aEntries[KRB_MAX_STACK]; +} KRB_INT(STACK); + +/** + * The callback used by the Destroy and DoWithAll functions. + */ +typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE *, void *); + +#ifdef KRB_NEED_KRBROOT +/** + * The Red-Black tree root structure. + */ +typedef struct +{ + KRBTREEPTR mpRoot; +# ifdef KRB_CACHE_SIZE + KRBTREEPTR maLookthru[KRB_CACHE_SIZE]; +# endif +} KRBROOT; +#endif + + + +/** + * Initializes the root of the Red-Black tree. + * + * @param pTree Pointer to the root structure. + */ +KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot) +{ +#ifdef KRB_CACHE_SIZE + unsigned i; +#endif + + pRoot->mpRoot = KRB_NULL; +#ifdef KRB_CACHE_SIZE + for (i = 0; i < (KRB_CACHE_SIZE); i++) + pRoot->maLookthru[i] = KRB_NULL; +#endif +} + + +/** + * Rotates the tree to the left (shift direction) and recolors the nodes. + * + * @pre + * + * 2 4 + * / \ / \ + * 1 4 ==> 2 5 + * / \ / \ + * 3 5 1 3 + * + * @endpre + * + * @returns The new root node. + * @param pRoot The root node. + * + * @remarks This will not update any pointer <tt>to</tt> the root node! + */ +K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateLeft)(KRBNODE *pRoot) +{ + KRBNODE *pNewRoot = pRoot->mRight; + pRoot->mRight = pNewRoot->mLeft; + pNewRoot->mLeft = pRoot; + + pRoot->mfIsRed = 1; + pNewRoot->mfIsRed = 0; + return pNewRoot; +} + + +/** + * Rotates the tree to the right (shift direction) and recolors the nodes. + * + * @pre + * + * 4 2 + * / \ / \ + * 2 5 ==> 1 4 + * / \ / \ + * 1 3 3 5 + * + * @endpre + * + * @returns The new root node. + * @param pRoot The root node. + * + * @remarks This will not update any pointer <tt>to</tt> the root node! + */ +K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateRight)(KRBNODE *pRoot) +{ + KRBNODE *pNewRoot = pRoot->mLeft; + pRoot->mLeft = pNewRoot->mRight; + pNewRoot->mRight = pRoot; + + pRoot->mfIsRed = 1; + pNewRoot->mfIsRed = 0; + return pNewRoot; +} + + +/** + * Performs a double left rotation with recoloring. + * + * @pre + * + * 2 2 4 + * / \ / \ / \ + * 1 6 ==> 1 4 ==> 2 6 + * / \ / \ / \ / \ + * 4 7 3 6 1 3 5 7 + * / \ / \ + * 3 5 5 7 + * @endpre + * + * @returns The new root node. + * @param pRoot The root node. + * + * @remarks This will not update any pointer <tt>to</tt> the root node! + */ +K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateLeft)(KRBNODE *pRoot) +{ + pRoot->mRight = KAVL_FN(RotateRight)(pRoot->mRight); + return KAVL_FN(RotateLeft)(pRoot); +} + + +/** + * Performs a double right rotation with recoloring. + * + * @pre + * 6 6 4 + * / \ / \ / \ + * 2 7 4 7 2 6 + * / \ ==> / \ ==> / \ / \ + * 1 4 2 5 1 3 5 7 + * / \ / \ + * 3 5 1 3 + * + * @endpre + * + * @returns The new root node. + * @param pRoot The root node. + * + * @remarks This will not update any pointer <tt>to</tt> the root node! + */ +K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateRight)(KRBNODE *pRoot) +{ + pRoot->mLeft = KAVL_FN(RotateLeft)(pRoot->mLeft); + return KAVL_FN(RotateRight)(pRoot); +} + + +/** + * Inserts a node into the Red-Black tree. + * @returns K_TRUE if inserted. + * K_FALSE if node exists in tree. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param pNode Pointer to the node which is to be added. + */ +KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT *pRoot, KRBNODE *pNode) +{ + KRBTREEPTR *ppCurNode = &pRoot->mpRoot; + register KRBKEY Key = pNode->mKey; +#ifdef KRB_RANGE + register KRBKEY KeyLast = pNode->mKeyLast; +#endif + +#ifdef KRB_RANGE + if (Key > KeyLast) + return K_FALSE; +#endif + + KRB_WRITE_LOCK(pRoot); + + Stack.cEntries = 0; + while (*ppCurNode != KRB_NULL) + { + register KRBNODE *pCurNode = KRB_GET_POINTER(ppCurNode); + + kHlpAssert(Stack.cEntries < KRB_MAX_STACK); + Stack.aEntries[Stack.cEntries++] = ppCurNode; +#ifdef KRB_EQUAL_ALLOWED + if (KRB_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast)) + { + /* + * If equal then we'll use a list of equal nodes. + */ + pNode->mpLeft = pNode->mpRight = KRB_NULL; + pNode->mHeight = 0; + KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList); + KRB_SET_POINTER(&pCurNode->mpList, pNode); + KRB_WRITE_UNLOCK(pRoot); + return K_TRUE; + } +#endif +#ifdef KRB_CHECK_FOR_EQUAL_INSERT + if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast)) + { + KRB_WRITE_UNLOCK(pRoot); + return K_FALSE; + } +#endif + if (KRB_CMP_G(pCurNode->mKey, Key)) + ppCurNode = &pCurNode->mpLeft; + else + ppCurNode = &pCurNode->mpRight; + } + + pNode->mpLeft = pNode->mpRight = KRB_NULL; +#ifdef KRB_EQUAL_ALLOWED + pNode->mpList = KRB_NULL; +#endif + pNode->mHeight = 1; + KRB_SET_POINTER(ppCurNode, pNode); + + KRB_FN(Rebalance)(&Stack); + + KRB_WRITE_UNLOCK(pRoot); + return K_TRUE; +} + + +/** + * Removes a node from the Red-Black tree. + * @returns Pointer to the node. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param Key Key value of the node which is to be removed. + * @sketch Find the node which is to be removed: + * LOOP until not found + * BEGIN + * Add node pointer pointer to the AVL-stack. + * IF the keys matches THEN break! + * IF remove key < node key THEN + * left + * ELSE + * right + * END + * IF found THEN + * BEGIN + * IF left node not empty THEN + * BEGIN + * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack: + * Start at left node. + * LOOP until right node is empty + * BEGIN + * Add to stack. + * go right. + * END + * Link out the found node. + * Replace the node which is to be removed with the found node. + * Correct the stack entry for the pointer to the left tree. + * END + * ELSE + * BEGIN + * Move up right node. + * Remove last stack entry. + * END + * Balance tree using stack. + * END + * return pointer to the removed node (if found). + */ +KRB_DECL(KRBNODE *) KRB_FN(Remove)(KRBROOT *pRoot, KRBKEY Key) +{ + KRB_INT(STACK) Stack; + KRBTREEPTR *ppDeleteNode = &pRoot->mpRoot; + register KRBNODE *pDeleteNode; + + KRB_WRITE_LOCK(pRoot); + + Stack.cEntries = 0; + for (;;) + { + if (*ppDeleteNode == KRB_NULL) + { + KRB_WRITE_UNLOCK(pRoot); + return NULL; + } + pDeleteNode = KRB_GET_POINTER(ppDeleteNode); + + kHlpAssert(Stack.cEntries < KRB_MAX_STACK); + Stack.aEntries[Stack.cEntries++] = ppDeleteNode; + if (KRB_CMP_E(pDeleteNode->mKey, Key)) + break; + + if (KRB_CMP_G(pDeleteNode->mKey, Key)) + ppDeleteNode = &pDeleteNode->mpLeft; + else + ppDeleteNode = &pDeleteNode->mpRight; + } + + if (pDeleteNode->mpLeft != KRB_NULL) + { + /* find the rightmost node in the left tree. */ + const unsigned iStackEntry = Stack.cEntries; + KRBTREEPTR *ppLeftLeast = &pDeleteNode->mpLeft; + register KRBNODE *pLeftLeast = KRB_GET_POINTER(ppLeftLeast); + + while (pLeftLeast->mpRight != KRB_NULL) + { + kHlpAssert(Stack.cEntries < KRB_MAX_STACK); + Stack.aEntries[Stack.cEntries++] = ppLeftLeast; + ppLeftLeast = &pLeftLeast->mpRight; + pLeftLeast = KRB_GET_POINTER(ppLeftLeast); + } + + /* link out pLeftLeast */ + KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft); + + /* link it in place of the delete node. */ + KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft); + KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight); + pLeftLeast->mHeight = pDeleteNode->mHeight; + KRB_SET_POINTER(ppDeleteNode, pLeftLeast); + Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft; + } + else + { + KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight); + Stack.cEntries--; + } + + KRB_FN(Rebalance)(&Stack); + + KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key); + + KRB_WRITE_UNLOCK(pRoot); + return pDeleteNode; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbDestroy.h b/src/lib/kStuff/include/k/kRbTmpl/kRbDestroy.h new file mode 100644 index 0000000..0300a9a --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbDestroy.h @@ -0,0 +1,129 @@ +/* $Id: kRbDestroy.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Destroy the tree. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Destroys the specified tree, starting with the root node and working our way down. + * + * @returns 0 on success. + * @returns Return value from callback on failure. On failure, the tree will be in + * an unbalanced condition and only further calls to the Destroy should be + * made on it. Note that the node we fail on will be considered dead and + * no action is taken to link it back into the tree. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param pfnCallBack Pointer to callback function. + * @param pvUser User parameter passed on to the callback function. + */ +KRB_DECL(int) KRB_FN(Destroy)(KRBROOT *pRoot, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) +{ +#ifdef KRB_CACHE_SIZE + unsigned i; +#endif + unsigned cEntries; + KRBNODE *apEntries[KRB_MAX_STACK]; + int rc; + + KRB_WRITE_LOCK(pRoot); + if (pRoot->mpRoot == KRB_NULL) + { + KRB_WRITE_UNLOCK(pRoot); + return 0; + } + +#ifdef KRB_CACHE_SIZE + /* + * Kill the lookthru cache. + */ + for (i = 0; i < (KRB_CACHE_SIZE); i++) + pRoot->maLookthru[i] = KRB_NULL; +#endif + + cEntries = 1; + apEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot); + while (cEntries > 0) + { + /* + * Process the subtrees first. + */ + KRBNODE *pNode = apEntries[cEntries - 1]; + if (pNode->mpLeft != KRB_NULL) + apEntries[cEntries++] = KRB_GET_POINTER(&pNode->mpLeft); + else if (pNode->mpRight != KRB_NULL) + apEntries[cEntries++] = KRB_GET_POINTER(&pNode->mpRight); + else + { +#ifdef KRB_EQUAL_ALLOWED + /* + * Process nodes with the same key. + */ + while (pNode->pList != KRB_NULL) + { + KRBNODE *pEqual = KRB_GET_POINTER(&pNode->pList); + KRB_SET_POINTER(&pNode->pList, KRB_GET_POINTER_NULL(&pEqual->pList)); + pEqual->pList = KRB_NULL; + + rc = pfnCallBack(pEqual, pvUser); + if (rc) + { + KRB_WRITE_UNLOCK(pRoot); + return rc; + } + } +#endif + + /* + * Unlink the node. + */ + if (--cEntries > 0) + { + KRBNODE *pParent = apEntries[cEntries - 1]; + if (KRB_GET_POINTER(&pParent->mpLeft) == pNode) + pParent->mpLeft = KRB_NULL; + else + pParent->mpRight = KRB_NULL; + } + else + pRoot->mpRoot = KRB_NULL; + + kHlpAssert(pNode->mpLeft == KRB_NULL); + kHlpAssert(pNode->mpRight == KRB_NULL); + rc = pfnCallBack(pNode, pvUser); + if (rc) + { + KRB_WRITE_UNLOCK(pRoot); + return rc; + } + } + } /* while */ + kHlpAssert(pRoot->mpRoot == KRB_NULL); + + KRB_WRITE_UNLOCK(pRoot); + return 0; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbDoWithAll.h b/src/lib/kStuff/include/k/kRbTmpl/kRbDoWithAll.h new file mode 100644 index 0000000..a9de71c --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbDoWithAll.h @@ -0,0 +1,166 @@ +/* $Id: kRbDoWithAll.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, The Callback Iterator. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/******************************************************************************* +* Structures and Typedefs * +*******************************************************************************/ +/** + * Stack used by DoWithAll to avoid recusive function calls. + */ +typedef struct +{ + unsigned cEntries; + KRBNODE *aEntries[KRB_MAX_STACK]; + char achFlags[KRB_MAX_STACK]; + KRBROOT pRoot; +} KRB_INT(STACK2); + + +/** + * Iterates thru all nodes in the given tree. + * + * @returns 0 on success. Return from callback on failure. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param fFromLeft K_TRUE: Left to right. + * K_FALSE: Right to left. + * @param pfnCallBack Pointer to callback function. + * @param pvUser User parameter passed on to the callback function. + */ +KRB_DECL(int) KRB_FN(DoWithAll)(KRBROOT *pRoot, KBOOL fFromLeft, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser) +{ + KRB_INT(STACK2) Stack; + KRBNODE *pNode; +#ifdef KRB_EQUAL_ALLOWED + KRBNODE *pEqual; +#endif + int rc; + + KRB_READ_LOCK(pRoot); + if (pRoot->mpRoot == KRB_NULL) + { + KRB_READ_UNLOCK(pRoot); + return 0; + } + + Stack.cEntries = 1; + Stack.achFlags[0] = 0; + Stack.aEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot); + + if (fFromLeft) + { /* from left */ + while (Stack.cEntries > 0) + { + pNode = Stack.aEntries[Stack.cEntries - 1]; + + /* left */ + if (!Stack.achFlags[Stack.cEntries - 1]++) + { + if (pNode->mpLeft != KRB_NULL) + { + Stack.achFlags[Stack.cEntries] = 0; /* 0 first, 1 last */ + Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft); + continue; + } + } + + /* center */ + rc = pfnCallBack(pNode, pvUser); + if (rc) + return rc; +#ifdef KRB_EQUAL_ALLOWED + if (pNode->mpList != KRB_NULL) + for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->mpList)) + { + rc = pfnCallBack(pEqual, pvUser); + if (rc) + { + KRB_READ_UNLOCK(pRoot); + return rc; + } + } +#endif + + /* right */ + Stack.cEntries--; + if (pNode->mpRight != KRB_NULL) + { + Stack.achFlags[Stack.cEntries] = 0; + Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight); + } + } /* while */ + } + else + { /* from right */ + while (Stack.cEntries > 0) + { + pNode = Stack.aEntries[Stack.cEntries - 1]; + + /* right */ + if (!Stack.achFlags[Stack.cEntries - 1]++) + { + if (pNode->mpRight != KRB_NULL) + { + Stack.achFlags[Stack.cEntries] = 0; /* 0 first, 1 last */ + Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight); + continue; + } + } + + /* center */ + rc = pfnCallBack(pNode, pvUser); + if (rc) + return rc; +#ifdef KRB_EQUAL_ALLOWED + if (pNode->mpList != KRB_NULL) + for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->pList)) + { + rc = pfnCallBack(pEqual, pvUser); + if (rc) + { + KRB_READ_UNLOCK(pRoot); + return rc; + } + } +#endif + + /* left */ + Stack.cEntries--; + if (pNode->mpLeft != KRB_NULL) + { + Stack.achFlags[Stack.cEntries] = 0; + Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft); + } + } /* while */ + } + + KRB_READ_UNLOCK(pRoot); + return 0; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbEnum.h b/src/lib/kStuff/include/k/kRbTmpl/kRbEnum.h new file mode 100644 index 0000000..d022410 --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbEnum.h @@ -0,0 +1,187 @@ +/* $Id: kRbEnum.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Node Enumeration. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/******************************************************************************* +* Structures and Typedefs * +*******************************************************************************/ +/** + * Enumeration control data. + * + * This is initialized by BeginEnum and used by GetNext to figure out what + * to do next. + */ +typedef struct KRB_TYPE(,ENUMDATA) +{ + KBOOL fFromLeft; + KI8 cEntries; + KU8 achFlags[KRB_MAX_STACK]; + KRBNODE * aEntries[KRB_MAX_STACK]; +} KRB_TYPE(,ENUMDATA), *KRB_TYPE(P,ENUMDATA); + + +/** + * Ends an enumeration. + * + * The purpose of this function is to unlock the tree should the Red-Black tree + * implementation include locking. It's good practice to call it anyway even if + * the tree doesn't do any locking. + * + * @param pEnumData Pointer to enumeration control data. + */ +KRB_DECL(void) KRB_FN(EndEnum)(KRB_TYPE(,ENUMDATA) *pEnumData) +{ + KRBROOT pRoot = pEnumData->pRoot; + pEnumData->pRoot = NULL; + if (pRoot) + KRB_READ_UNLOCK(pEnumData->pRoot); +} + + +/** + * Get the next node in the tree enumeration. + * + * The current implementation of this function willl not walk the mpList + * chain like the DoWithAll function does. This may be changed later. + * + * @returns Pointer to the next node in the tree. + * NULL is returned when the end of the tree has been reached, + * it is not necessary to call EndEnum in this case. + * @param pEnumData Pointer to enumeration control data. + */ +KRB_DECL(KRBNODE *) KRB_FN(GetNext)(KRB_TYPE(,ENUMDATA) *pEnumData) +{ + if (pEnumData->fFromLeft) + { /* from left */ + while (pEnumData->cEntries > 0) + { + KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1]; + + /* left */ + if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0) + { + pEnumData->achFlags[pEnumData->cEntries - 1]++; + if (pNode->mpLeft != KRB_NULL) + { + pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */ + pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft); + continue; + } + } + + /* center */ + if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1) + { + pEnumData->achFlags[pEnumData->cEntries - 1]++; + return pNode; + } + + /* right */ + pEnumData->cEntries--; + if (pNode->mpRight != KRB_NULL) + { + pEnumData->achFlags[pEnumData->cEntries] = 0; + pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight); + } + } /* while */ + } + else + { /* from right */ + while (pEnumData->cEntries > 0) + { + KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1]; + + /* right */ + if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0) + { + pEnumData->achFlags[pEnumData->cEntries - 1]++; + if (pNode->mpRight != KRB_NULL) + { + pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 right, 1 center, 2 left */ + pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight); + continue; + } + } + + /* center */ + if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1) + { + pEnumData->achFlags[pEnumData->cEntries - 1]++; + return pNode; + } + + /* left */ + pEnumData->cEntries--; + if (pNode->mpLeft != KRB_NULL) + { + pEnumData->achFlags[pEnumData->cEntries] = 0; + pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft); + } + } /* while */ + } + + /* + * Call EndEnum. + */ + KRB_FN(EndEnum)(pEnumData); + return NULL; +} + + +/** + * Starts an enumeration of all nodes in the given tree. + * + * The current implementation of this function will not walk the mpList + * chain like the DoWithAll function does. This may be changed later. + * + * @returns Pointer to the first node in the enumeration. + * If NULL is returned the tree is empty calling EndEnum isn't + * strictly necessary (although it will do no harm). + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param pEnumData Pointer to enumeration control data. + * @param fFromLeft K_TRUE: Left to right. + * K_FALSE: Right to left. + */ +KRB_DECL(KRBNODE *) KRB_FN(BeginEnum)(KRBROOT *pRoot, KRB_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft) +{ + KRB_READ_LOCK(pRoot); + pEnumData->pRoot = pRoot; + if (pRoot->mpRoot != KRB_NULL) + { + pEnumData->fFromLeft = fFromLeft; + pEnumData->cEntries = 1; + pEnumData->aEntries[0] = KRB_GET_POINTER(pRoot->mpRoot); + pEnumData->achFlags[0] = 0; + } + else + pEnumData->cEntries = 0; + + return KRB_FN(GetNext)(pEnumData); +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbGet.h b/src/lib/kStuff/include/k/kRbTmpl/kRbGet.h new file mode 100644 index 0000000..b03d4e1 --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbGet.h @@ -0,0 +1,89 @@ +/* $Id: kRbGet.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Get a Node. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Gets a node from the tree (does not remove it!) + * + * @returns Pointer to the node holding the given key. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param Key Key value of the node which is to be found. + */ +KRB_DECL(KRBNODE *) KRB_FN(Get)(KRBROOT *pRoot, KRBKEY Key) +{ + KRBNODE *pNode; +#ifdef KRB_CACHE_SIZE + KRBTREEPTR *ppEntry; +#endif + + KRB_READ_LOCK(pRoot); + if (pRoot->mpRoot == KRB_NULL) + { + KRB_READ_UNLOCK(pRoot); + return NULL; + } + +#ifdef KRB_CACHE_SIZE + ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; + pNode = KRB_GET_POINTER_NULL(ppEntry); + if (!pNode || KRB_CMP_NE(pNode->mKey, Key)) +#endif + { + pNode = KRB_GET_POINTER(&pRoot->mpRoot); + while (KRB_CMP_NE(pNode->mKey, Key)) + { + if (KRB_CMP_G(pNode->mKey, Key)) + { + if (pNode->mpLeft == KRB_NULL) + { + KRB_READ_UNLOCK(pRoot); + return NULL; + } + pNode = KRB_GET_POINTER(&pNode->mpLeft); + } + else + { + if (pNode->mpRight == KRB_NULL) + { + KRB_READ_UNLOCK(pRoot); + return NULL; + } + pNode = KRB_GET_POINTER(&pNode->mpRight); + } + } + +#ifdef KRB_CACHE_SIZE + KRB_SET_POINTER(ppEntry, pNode); +#endif + } + + KRB_READ_UNLOCK(pRoot); + return pNode; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbGetBestFit.h b/src/lib/kStuff/include/k/kRbTmpl/kRbGetBestFit.h new file mode 100644 index 0000000..bfda27a --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbGetBestFit.h @@ -0,0 +1,112 @@ +/* $Id: kRbGetBestFit.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Get Best Fitting Node. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Finds the best fitting node in the tree for the given Key value. + * + * @returns Pointer to the best fitting node found. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param Key The Key of which is to be found a best fitting match for.. + * @param fAbove K_TRUE: Returned node is have the closest key to Key from above. + * K_FALSE: Returned node is have the closest key to Key from below. + * @sketch The best fitting node is always located in the searchpath above you. + * >= (above): The node where you last turned left. + * <= (below): the node where you last turned right. + */ +KRB_DECL(KRBNODE *) KRB_FN(GetBestFit)(KRBROOT *pRoot, KRBKEY Key, KBOOL fAbove) +{ + register KRBNODE *pNode; + KRBNODE *pNodeLast; + + KRB_READ_LOCK(pLook); + if (pRoot->mpRoot == KRB_NULL) + { + KRB_READ_UNLOCK(pLook); + return NULL; + } + + pNode = KRB_GET_POINTER(&pRoot->mpRoot); + pNodeLast = NULL; + if (fAbove) + { /* pNode->mKey >= Key */ + while (KRB_CMP_NE(pNode->mKey, Key)) + { + if (KRB_CMP_G(pNode->mKey, Key)) + { + if (pNode->mpLeft == KRB_NULL) + { + KRB_READ_UNLOCK(pLook); + return pNode; + } + pNodeLast = pNode; + pNode = KRB_GET_POINTER(&pNode->mpLeft); + } + else + { + if (pNode->mpRight == KRB_NULL) + { + KRB_READ_UNLOCK(pLook); + return pNodeLast; + } + pNode = KRB_GET_POINTER(&pNode->mpRight); + } + } + } + else + { /* pNode->mKey <= Key */ + while (KRB_CMP_NE(pNode->mKey, Key)) + { + if (KRB_CMP_G(pNode->mKey, Key)) + { + if (pNode->mpLeft == KRB_NULL) + { + KRB_READ_UNLOCK(pLook); + return pNodeLast; + } + pNode = KRB_GET_POINTER(&pNode->mpLeft); + } + else + { + if (pNode->mpRight == KRB_NULL) + { + KRB_READ_UNLOCK(pLook); + return pNode; + } + pNodeLast = pNode; + pNode = KRB_GET_POINTER(&pNode->mpRight); + } + } + } + + /* perfect match or nothing. */ + KRB_READ_UNLOCK(pLook); + return pNode; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbGetWithParent.h b/src/lib/kStuff/include/k/kRbTmpl/kRbGetWithParent.h new file mode 100644 index 0000000..05a7d8c --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbGetWithParent.h @@ -0,0 +1,65 @@ +/* $Id: kRbGetWithParent.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Get Node With Parent. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Gets a node from the tree and its parent node (if any). + * The tree remains unchanged. + * + * @returns Pointer to the node holding the given key. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param ppParent Pointer to a variable which will hold the pointer to the partent node on + * return. When no node is found, this will hold the last searched node. + * @param Key Key value of the node which is to be found. + */ +KRB_DECL(KRBNODE *) KRB_FN(GetWithParent)(KRBROOT *pRoot, KRBNODE **ppParent, KRBKEY Key) +{ + register KRBNODE *pNode; + register KRBNODE *pParent; + + KRB_READ_LOCK(pRoot); + + pParent = NULL; + pNode = KRB_GET_POINTER_NULL(&pRoot->mpRoot); + while ( pNode != NULL + && KRB_CMP_NE(pNode->mKey, Key)) + { + pParent = pNode; + if (KRB_CMP_G(pNode->mKey, Key)) + pNode = KRB_GET_POINTER_NULL(&pNode->mpLeft); + else + pNode = KRB_GET_POINTER_NULL(&pNode->mpRight); + } + + KRB_READ_UNLOCK(pRoot); + + *ppParent = pParent; + return pNode; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbRemove2.h b/src/lib/kStuff/include/k/kRbTmpl/kRbRemove2.h new file mode 100644 index 0000000..deed81d --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbRemove2.h @@ -0,0 +1,133 @@ +/* $Id: kRbRemove2.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Remove A Specific Node. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Removes the specified node from the tree. + * + * @returns Pointer to the removed node (NULL if not in the tree) + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param Key The Key of which is to be found a best fitting match for.. + * + * @remark This implementation isn't the most efficient, but this short and + * easier to manage. + */ +KRB_DECL(KRBNODE *) KRB_FN(Remove2)(KRBROOT *pRoot, KRBNODE *pNode) +{ +#ifdef KRB_EQUAL_ALLOWED + /* + * Find the right node by key and see if it's what we want. + */ + KRBNODE *pParent; + KRBNODE *pCurNode = KRB_FN(GetWithParent)(pRoot, pNode->mKey, &pParent); + if (!pCurNode) + return NULL; + KRB_WRITE_LOCK(pRoot); /** @todo the locking here isn't 100% sane. The only way to archive that is by no calling worker functions. */ + if (pCurNode != pNode) + { + /* + * It's not the one we want, but it could be in the duplicate list. + */ + while (pCurNode->mpList != KRB_NULL) + { + KRBNODE *pNext = KRB_GET_POINTER(&pCurNode->mpList); + if (pNext == pNode) + { + KRB_SET_POINTER_NULL(&pCurNode->mpList, KRB_GET_POINTER_NULL(&pNode->mpList)); + pNode->mpList = KRB_NULL; + KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KRB_WRITE_UNLOCK(pRoot); + return pNode; + } + pCurNode = pNext; + } + KRB_WRITE_UNLOCK(pRoot); + return NULL; + } + + /* + * Ok, it's the one we want alright. + * + * Simply remove it if it's the only one with they Key, + * if there are duplicates we'll have to unlink it and + * insert the first duplicate in our place. + */ + if (pNode->mpList == KRB_NULL) + { + KRB_WRITE_UNLOCK(pRoot); + KRB_FN(Remove)(pRoot, pNode->mKey); + } + else + { + KRBNODE *pNewUs = KRB_GET_POINTER(&pNode->mpList); + + pNewUs->mHeight = pNode->mHeight; + + if (pNode->mpLeft != KRB_NULL) + KRB_SET_POINTER(&pNewUs->mpLeft, KRB_GET_POINTER(&pNode->mpLeft)) + else + pNewUs->mpLeft = KRB_NULL; + + if (pNode->mpRight != KRB_NULL) + KRB_SET_POINTER(&pNewUs->mpRight, KRB_GET_POINTER(&pNode->mpRight)) + else + pNewUs->mpRight = KRB_NULL; + + if (pParent) + { + if (KRB_GET_POINTER_NULL(&pParent->mpLeft) == pNode) + KRB_SET_POINTER(&pParent->mpLeft, pNewUs); + else + KRB_SET_POINTER(&pParent->mpRight, pNewUs); + } + else + KRB_SET_POINTER(&pRoot->mpRoot, pNewUs); + + KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KRB_WRITE_UNLOCK(pRoot); + } + + return pNode; + +#else + /* + * Delete it, if we got the wrong one, reinsert it. + * + * This ASSUMS that the caller is NOT going to hand us a lot + * of wrong nodes but just uses this API for his convenience. + */ + KRBNODE *pRemovedNode = KRB_FN(Remove)(pRoot, pNode->mKey); + if (pRemovedNode == pNode) + return pRemovedNode; + + KRB_FN(Insert)(pRoot, pRemovedNode); + return NULL; +#endif +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbRemoveBestFit.h b/src/lib/kStuff/include/k/kRbTmpl/kRbRemoveBestFit.h new file mode 100644 index 0000000..17fc66d --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbRemoveBestFit.h @@ -0,0 +1,70 @@ +/* $Id: kRbRemoveBestFit.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Templated Red-Black Trees, Remove Best Fitting Node. + */ + +/* + * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * Finds the best fitting node in the tree for the given Key value and removes the node. + * + * @returns Pointer to the removed node. + * @param pRoot Pointer to the Red-Back tree's root structure. + * @param Key The Key of which is to be found a best fitting match for.. + * @param fAbove K_TRUE: Returned node is have the closest key to Key from above. + * K_FALSE: Returned node is have the closest key to Key from below. + * + * @remark This implementation uses GetBestFit and then Remove and might therefore + * not be the most optimal kind of implementation, but it reduces the complexity + * code size, and the likelyhood for bugs. + */ +KRB_DECL(KRBNODE *) KRB_FN(RemoveBestFit)(KRBROOT *pRoot, KRBKEY Key, KBOOL fAbove) +{ + /* + * If we find anything we'll have to remove the node and return it. + * Now, if duplicate keys are allowed we'll remove a duplicate before + * removing the in-tree node as this is way cheaper. + */ + KRBNODE *pNode = KRB_FN(GetBestFit)(pRoot, Key, fAbove); + if (pNode != NULL) + { +#ifdef KRB_EQUAL_ALLOWED + KRB_WRITE_LOCK(pRoot); /** @todo the locking isn't quite sane here. :-/ */ + if (pNode->mpList != KRB_NULL) + { + KRBNODE *pRet = KRB_GET_POINTER(&pNode->mpList); + KRB_SET_POINTER_NULL(&pNode->mpList, &pRet->mpList); + KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey); + KRB_WRITE_UNLOCK(pRoot); + return pRet; + } + KRB_WRITE_UNLOCK(pRoot); +#endif + pNode = KRB_FN(Remove)(pRoot, pNode->mKey); + } + return pNode; +} + diff --git a/src/lib/kStuff/include/k/kRbTmpl/kRbUndef.h b/src/lib/kStuff/include/k/kRbTmpl/kRbUndef.h new file mode 100644 index 0000000..793108b --- /dev/null +++ b/src/lib/kStuff/include/k/kRbTmpl/kRbUndef.h @@ -0,0 +1,79 @@ +/* $Id: kRbUndef.h 35 2009-11-08 19:39:03Z bird $ */ +/** @file + * kRbTmpl - Undefines All Macros (both config and temp). + */ + +/* + * Copyright (c) 2006-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net> + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +/* + * The configuration. + */ +#undef KRB_EQUAL_ALLOWED +#undef KRB_CHECK_FOR_EQUAL_INSERT +#undef KRB_MAX_STACK +#undef KRB_RANGE +#undef KRB_OFFSET +#undef KRB_STD_KEY_COMP +#undef KRB_CACHE_SIZE +#undef KRB_CACHE_HASH +#undef KRB_LOCKED +#undef KRB_WRITE_LOCK +#undef KRB_WRITE_UNLOCK +#undef KRB_READ_LOCK +#undef KRB_READ_UNLOCK +#undef KRBKEY +#undef KRBNODE +#undef KRBTREEPTR +#undef KRBROOT +#undef KRB_FN +#undef KRB_TYPE +#undef KRB_INT +#undef KRB_DECL +#undef mKey +#undef mKeyLast +#undef mfIsRed +#undef mpLeft +#undef mpRight +#undef mpList +#undef mpRoot +#undef maLookthru +#undef KRB_CMP_G +#undef KRB_CMP_E +#undef KRB_CMP_NE +#undef KRB_R_IS_IDENTICAL +#undef KRB_R_IS_INTERSECTING +#undef KRB_R_IS_IN_RANGE + +/* + * Internal ones. + */ +#undef KRB_IS_RED +#undef KRB_NULL +#undef KRB_GET_POINTER +#undef KRB_GET_POINTER_NULL +#undef KRB_SET_POINTER +#undef KRB_SET_POINTER_NULL + |