| [2] | 1 | /* $Id: kRbBase.h 38 2009-11-10 00:01:38Z bird $ */
|
|---|
| 2 | /** @file
|
|---|
| [35] | 3 | * kRbTmpl - Templated Red-Black Trees, The Mandatory Base Code.
|
|---|
| [2] | 4 | */
|
|---|
| 5 |
|
|---|
| 6 | /*
|
|---|
| [29] | 7 | * Copyright (c) 2001-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
|
|---|
| [2] | 8 | *
|
|---|
| [29] | 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:
|
|---|
| [2] | 17 | *
|
|---|
| [29] | 18 | * The above copyright notice and this permission notice shall be
|
|---|
| 19 | * included in all copies or substantial portions of the Software.
|
|---|
| [2] | 20 | *
|
|---|
| [29] | 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.
|
|---|
| [2] | 29 | */
|
|---|
| 30 |
|
|---|
| 31 | /** @page pg_kAvlTmpl Template Configuration.
|
|---|
| 32 | *
|
|---|
| [35] | 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.
|
|---|
| [2] | 35 | *
|
|---|
| [35] | 36 | * \#define KRB_EQUAL_ALLOWED
|
|---|
| [2] | 37 | * Define this to tell us that equal keys are allowed.
|
|---|
| [35] | 38 | * Then Equal keys will be put in a list pointed to by KRBNODE::pList.
|
|---|
| [2] | 39 | * This is by default not defined.
|
|---|
| 40 | *
|
|---|
| [35] | 41 | * \#define KRB_CHECK_FOR_EQUAL_INSERT
|
|---|
| [2] | 42 | * Define this to enable insert check for equal nodes.
|
|---|
| 43 | * This is by default not defined.
|
|---|
| 44 | *
|
|---|
| [35] | 45 | * \#define KRB_MAX_STACK
|
|---|
| [7] | 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
|
|---|
| [2] | 48 | * log2(<max nodes>) + 3
|
|---|
| 49 | * Must be defined.
|
|---|
| 50 | *
|
|---|
| [35] | 51 | * \#define KRB_RANGE
|
|---|
| [2] | 52 | * Define this to enable key ranges.
|
|---|
| 53 | *
|
|---|
| [35] | 54 | * \#define KRB_OFFSET
|
|---|
| [2] | 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 | *
|
|---|
| [35] | 60 | * \#define KRB_CACHE_SIZE
|
|---|
| [7] | 61 | * Define this to employ a lookthru cache (direct) to speed up lookup for
|
|---|
| [35] | 62 | * some usage patterns. The value should be the number of members of the array.
|
|---|
| [7] | 63 | *
|
|---|
| [35] | 64 | * \#define KRB_CACHE_HASH(Key)
|
|---|
| [29] | 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 | *
|
|---|
| [35] | 69 | * \#define KRB_LOCKED
|
|---|
| [29] | 70 | * Define this if you wish for the tree to be locked via the
|
|---|
| [35] | 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
|
|---|
| [7] | 73 | * do any kind of locking and the problem of concurrency is left the user.
|
|---|
| [29] | 74 | *
|
|---|
| [35] | 75 | * \#define KRB_WRITE_LOCK(pRoot)
|
|---|
| [7] | 76 | * Lock the tree for writing.
|
|---|
| [29] | 77 | *
|
|---|
| [35] | 78 | * \#define KRB_WRITE_UNLOCK(pRoot)
|
|---|
| 79 | * Counteracts KRB_WRITE_LOCK.
|
|---|
| [29] | 80 | *
|
|---|
| [35] | 81 | * \#define KRB_READ_LOCK(pRoot)
|
|---|
| [7] | 82 | * Lock the tree for reading.
|
|---|
| [29] | 83 | *
|
|---|
| [35] | 84 | * \#define KRB_READ_UNLOCK(pRoot)
|
|---|
| 85 | * Counteracts KRB_READ_LOCK.
|
|---|
| [29] | 86 | *
|
|---|
| [35] | 87 | * \#define KRBKEY
|
|---|
| [2] | 88 | * Define this to the name of the AVL key type.
|
|---|
| 89 | *
|
|---|
| [35] | 90 | * \#define KRB_STD_KEY_COMP
|
|---|
| [2] | 91 | * Define this to use the standard key compare macros. If not set all the
|
|---|
| [35] | 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.
|
|---|
| [2] | 95 | *
|
|---|
| [35] | 96 | * \#define KRBNODE
|
|---|
| [2] | 97 | * Define this to the name (typedef) of the AVL node structure. This
|
|---|
| 98 | * structure must have a mpLeft, mpRight, mKey and mHeight member.
|
|---|
| [35] | 99 | * If KRB_RANGE is defined a mKeyLast is also required.
|
|---|
| 100 | * If KRB_EQUAL_ALLOWED is defined a mpList member is required.
|
|---|
| [2] | 101 | * It's possible to use other member names by redefining the names.
|
|---|
| 102 | *
|
|---|
| [35] | 103 | * \#define KRBTREEPTR
|
|---|
| [2] | 104 | * Define this to the name (typedef) of the tree pointer type. This is
|
|---|
| [35] | 105 | * required when KRB_OFFSET is defined. When not defined it defaults
|
|---|
| 106 | * to KRBNODE *.
|
|---|
| [2] | 107 | *
|
|---|
| [35] | 108 | * \#define KRBROOT
|
|---|
| [29] | 109 | * Define this to the name (typedef) of the AVL root structure. This
|
|---|
| [7] | 110 | * is optional. However, if specified it must at least have a mpRoot
|
|---|
| [35] | 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
|
|---|
| [7] | 113 | * required.
|
|---|
| 114 | *
|
|---|
| [35] | 115 | * \#define KRB_FN
|
|---|
| [2] | 116 | * Use this to alter the names of the AVL functions.
|
|---|
| 117 | * Must be defined.
|
|---|
| 118 | *
|
|---|
| [35] | 119 | * \#define KRB_TYPE(prefix, name)
|
|---|
| [2] | 120 | * Use this to make external type names and unique. The prefix may be empty.
|
|---|
| 121 | * Must be defined.
|
|---|
| 122 | *
|
|---|
| [35] | 123 | * \#define KRB_INT(name)
|
|---|
| [2] | 124 | * Use this to make internal type names and unique. The prefix may be empty.
|
|---|
| 125 | * Must be defined.
|
|---|
| 126 | *
|
|---|
| [35] | 127 | * \#define KRB_DECL(rettype)
|
|---|
| [2] | 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 | *******************************************************************************/
|
|---|
| [35] | 149 | /** @def KRB_GET_POINTER
|
|---|
| [2] | 150 | * Reads a 'pointer' value.
|
|---|
| 151 | *
|
|---|
| 152 | * @returns The native pointer.
|
|---|
| 153 | * @param pp Pointer to the pointer to read.
|
|---|
| 154 | * @internal
|
|---|
| 155 | */
|
|---|
| 156 |
|
|---|
| [35] | 157 | /** @def KRB_GET_POINTER_NULL
|
|---|
| 158 | * Reads a 'pointer' value which can be KRB_NULL.
|
|---|
| [2] | 159 | *
|
|---|
| 160 | * @returns The native pointer.
|
|---|
| [35] | 161 | * @returns NULL pointer if KRB_NULL.
|
|---|
| [2] | 162 | * @param pp Pointer to the pointer to read.
|
|---|
| 163 | * @internal
|
|---|
| 164 | */
|
|---|
| 165 |
|
|---|
| [35] | 166 | /** @def KRB_SET_POINTER
|
|---|
| [2] | 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 |
|
|---|
| [35] | 176 | /** @def KRB_SET_POINTER_NULL
|
|---|
| 177 | * Writes a 'pointer' value which can be KRB_NULL.
|
|---|
| [2] | 178 | *
|
|---|
| 179 | * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
|
|---|
| [35] | 180 | * if p is not KRB_NULL of course.
|
|---|
| [2] | 181 | *
|
|---|
| 182 | * @returns stored pointer.
|
|---|
| 183 | * @param pp Pointer to where to store the pointer.
|
|---|
| [35] | 184 | * @param pp2 Pointer to where to pointer to assign to pp. This can be KRB_NULL
|
|---|
| [2] | 185 | * @internal
|
|---|
| 186 | */
|
|---|
| 187 |
|
|---|
| [35] | 188 | #ifndef KRBTREEPTR
|
|---|
| 189 | # define KRBTREEPTR KRBNODE *
|
|---|
| [2] | 190 | #endif
|
|---|
| 191 |
|
|---|
| [35] | 192 | #ifndef KRBROOT
|
|---|
| 193 | # define KRBROOT KRB_TYPE(,ROOT)
|
|---|
| 194 | # define KRB_NEED_KRBROOT
|
|---|
| [7] | 195 | #endif
|
|---|
| 196 |
|
|---|
| [35] | 197 | #ifdef KRB_CACHE_SIZE
|
|---|
| 198 | # ifndef KRB_CACHE_HASH
|
|---|
| 199 | # define KRB_CACHE_HASH(Key) ( (Key) % (KRB_CACHE_SIZE) )
|
|---|
| [7] | 200 | # endif
|
|---|
| [35] | 201 | #elif defined(KRB_CACHE_HASH)
|
|---|
| 202 | # error "KRB_CACHE_HASH without KRB_CACHE_SIZE!"
|
|---|
| [7] | 203 | #endif
|
|---|
| 204 |
|
|---|
| [35] | 205 | #ifdef KRB_CACHE_SIZE
|
|---|
| 206 | # define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) \
|
|---|
| [7] | 207 | do { \
|
|---|
| [35] | 208 | KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \
|
|---|
| 209 | if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \
|
|---|
| 210 | *ppEntry = KRB_NULL; \
|
|---|
| [7] | 211 | } while (0)
|
|---|
| 212 | #else
|
|---|
| [35] | 213 | # define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
|
|---|
| [7] | 214 | #endif
|
|---|
| 215 |
|
|---|
| [35] | 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)
|
|---|
| [7] | 221 | #endif
|
|---|
| 222 |
|
|---|
| [35] | 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 )
|
|---|
| [2] | 228 | #else
|
|---|
| [35] | 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) )
|
|---|
| [2] | 233 | #endif
|
|---|
| 234 |
|
|---|
| 235 |
|
|---|
| [35] | 236 | /** @def KRB_NULL
|
|---|
| [2] | 237 | * The NULL 'pointer' equivalent.
|
|---|
| 238 | */
|
|---|
| [35] | 239 | #ifdef KRB_OFFSET
|
|---|
| 240 | # define KRB_NULL 0
|
|---|
| [2] | 241 | #else
|
|---|
| [35] | 242 | # define KRB_NULL NULL
|
|---|
| [2] | 243 | #endif
|
|---|
| 244 |
|
|---|
| [35] | 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)
|
|---|
| [2] | 253 | # endif
|
|---|
| 254 | #endif
|
|---|
| 255 |
|
|---|
| [35] | 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)
|
|---|
| [2] | 259 | #endif
|
|---|
| 260 |
|
|---|
| 261 |
|
|---|
| [38] | 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 )
|
|---|
| [2] | 268 |
|
|---|
| [38] | 269 |
|
|---|
| [2] | 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;
|
|---|
| [35] | 279 | KRBTREEPTR *aEntries[KRB_MAX_STACK];
|
|---|
| 280 | } KRB_INT(STACK);
|
|---|
| [2] | 281 |
|
|---|
| 282 | /**
|
|---|
| 283 | * The callback used by the Destroy and DoWithAll functions.
|
|---|
| 284 | */
|
|---|
| [35] | 285 | typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE *, void *);
|
|---|
| [2] | 286 |
|
|---|
| [35] | 287 | #ifdef KRB_NEED_KRBROOT
|
|---|
| [7] | 288 | /**
|
|---|
| [35] | 289 | * The Red-Black tree root structure.
|
|---|
| [7] | 290 | */
|
|---|
| 291 | typedef struct
|
|---|
| 292 | {
|
|---|
| [35] | 293 | KRBTREEPTR mpRoot;
|
|---|
| 294 | # ifdef KRB_CACHE_SIZE
|
|---|
| 295 | KRBTREEPTR maLookthru[KRB_CACHE_SIZE];
|
|---|
| [7] | 296 | # endif
|
|---|
| [35] | 297 | } KRBROOT;
|
|---|
| [7] | 298 | #endif
|
|---|
| [2] | 299 |
|
|---|
| 300 |
|
|---|
| 301 |
|
|---|
| 302 | /**
|
|---|
| [35] | 303 | * Initializes the root of the Red-Black tree.
|
|---|
| [29] | 304 | *
|
|---|
| [7] | 305 | * @param pTree Pointer to the root structure.
|
|---|
| 306 | */
|
|---|
| [35] | 307 | KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot)
|
|---|
| [7] | 308 | {
|
|---|
| [35] | 309 | #ifdef KRB_CACHE_SIZE
|
|---|
| [7] | 310 | unsigned i;
|
|---|
| [29] | 311 | #endif
|
|---|
| [7] | 312 |
|
|---|
| [35] | 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;
|
|---|
| [7] | 317 | #endif
|
|---|
| 318 | }
|
|---|
| 319 |
|
|---|
| 320 |
|
|---|
| 321 | /**
|
|---|
| [38] | 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 | /**
|
|---|
| [35] | 434 | * Inserts a node into the Red-Black tree.
|
|---|
| [7] | 435 | * @returns K_TRUE if inserted.
|
|---|
| 436 | * K_FALSE if node exists in tree.
|
|---|
| [35] | 437 | * @param pRoot Pointer to the Red-Back tree's root structure.
|
|---|
| [7] | 438 | * @param pNode Pointer to the node which is to be added.
|
|---|
| [2] | 439 | */
|
|---|
| [35] | 440 | KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT *pRoot, KRBNODE *pNode)
|
|---|
| [2] | 441 | {
|
|---|
| [35] | 442 | KRBTREEPTR *ppCurNode = &pRoot->mpRoot;
|
|---|
| [38] | 443 | register KRBKEY Key = pNode->mKey;
|
|---|
| [35] | 444 | #ifdef KRB_RANGE
|
|---|
| [38] | 445 | register KRBKEY KeyLast = pNode->mKeyLast;
|
|---|
| [2] | 446 | #endif
|
|---|
| 447 |
|
|---|
| [35] | 448 | #ifdef KRB_RANGE
|
|---|
| [2] | 449 | if (Key > KeyLast)
|
|---|
| [38] | 450 | return K_FALSE;
|
|---|
| [2] | 451 | #endif
|
|---|
| 452 |
|
|---|
| [35] | 453 | KRB_WRITE_LOCK(pRoot);
|
|---|
| [7] | 454 |
|
|---|
| [35] | 455 | Stack.cEntries = 0;
|
|---|
| 456 | while (*ppCurNode != KRB_NULL)
|
|---|
| [2] | 457 | {
|
|---|
| [35] | 458 | register KRBNODE *pCurNode = KRB_GET_POINTER(ppCurNode);
|
|---|
| [2] | 459 |
|
|---|
| [35] | 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))
|
|---|
| [2] | 464 | {
|
|---|
| 465 | /*
|
|---|
| 466 | * If equal then we'll use a list of equal nodes.
|
|---|
| 467 | */
|
|---|
| [35] | 468 | pNode->mpLeft = pNode->mpRight = KRB_NULL;
|
|---|
| [2] | 469 | pNode->mHeight = 0;
|
|---|
| [35] | 470 | KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
|
|---|
| 471 | KRB_SET_POINTER(&pCurNode->mpList, pNode);
|
|---|
| 472 | KRB_WRITE_UNLOCK(pRoot);
|
|---|
| [2] | 473 | return K_TRUE;
|
|---|
| 474 | }
|
|---|
| 475 | #endif
|
|---|
| [35] | 476 | #ifdef KRB_CHECK_FOR_EQUAL_INSERT
|
|---|
| 477 | if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
|
|---|
| [7] | 478 | {
|
|---|
| [35] | 479 | KRB_WRITE_UNLOCK(pRoot);
|
|---|
| [2] | 480 | return K_FALSE;
|
|---|
| [7] | 481 | }
|
|---|
| [2] | 482 | #endif
|
|---|
| [35] | 483 | if (KRB_CMP_G(pCurNode->mKey, Key))
|
|---|
| [2] | 484 | ppCurNode = &pCurNode->mpLeft;
|
|---|
| 485 | else
|
|---|
| 486 | ppCurNode = &pCurNode->mpRight;
|
|---|
| 487 | }
|
|---|
| 488 |
|
|---|
| [35] | 489 | pNode->mpLeft = pNode->mpRight = KRB_NULL;
|
|---|
| 490 | #ifdef KRB_EQUAL_ALLOWED
|
|---|
| 491 | pNode->mpList = KRB_NULL;
|
|---|
| [2] | 492 | #endif
|
|---|
| 493 | pNode->mHeight = 1;
|
|---|
| [35] | 494 | KRB_SET_POINTER(ppCurNode, pNode);
|
|---|
| [2] | 495 |
|
|---|
| [35] | 496 | KRB_FN(Rebalance)(&Stack);
|
|---|
| [7] | 497 |
|
|---|
| [35] | 498 | KRB_WRITE_UNLOCK(pRoot);
|
|---|
| [2] | 499 | return K_TRUE;
|
|---|
| 500 | }
|
|---|
| 501 |
|
|---|
| 502 |
|
|---|
| 503 | /**
|
|---|
| [35] | 504 | * Removes a node from the Red-Black tree.
|
|---|
| [2] | 505 | * @returns Pointer to the node.
|
|---|
| [35] | 506 | * @param pRoot Pointer to the Red-Back tree's root structure.
|
|---|
| [7] | 507 | * @param Key Key value of the node which is to be removed.
|
|---|
| [2] | 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 | */
|
|---|
| [35] | 542 | KRB_DECL(KRBNODE *) KRB_FN(Remove)(KRBROOT *pRoot, KRBKEY Key)
|
|---|
| [2] | 543 | {
|
|---|
| [35] | 544 | KRB_INT(STACK) Stack;
|
|---|
| 545 | KRBTREEPTR *ppDeleteNode = &pRoot->mpRoot;
|
|---|
| 546 | register KRBNODE *pDeleteNode;
|
|---|
| [2] | 547 |
|
|---|
| [35] | 548 | KRB_WRITE_LOCK(pRoot);
|
|---|
| [7] | 549 |
|
|---|
| [35] | 550 | Stack.cEntries = 0;
|
|---|
| [2] | 551 | for (;;)
|
|---|
| 552 | {
|
|---|
| [35] | 553 | if (*ppDeleteNode == KRB_NULL)
|
|---|
| [7] | 554 | {
|
|---|
| [35] | 555 | KRB_WRITE_UNLOCK(pRoot);
|
|---|
| [2] | 556 | return NULL;
|
|---|
| [7] | 557 | }
|
|---|
| [35] | 558 | pDeleteNode = KRB_GET_POINTER(ppDeleteNode);
|
|---|
| [2] | 559 |
|
|---|
| [35] | 560 | kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
|
|---|
| 561 | Stack.aEntries[Stack.cEntries++] = ppDeleteNode;
|
|---|
| 562 | if (KRB_CMP_E(pDeleteNode->mKey, Key))
|
|---|
| [2] | 563 | break;
|
|---|
| 564 |
|
|---|
| [35] | 565 | if (KRB_CMP_G(pDeleteNode->mKey, Key))
|
|---|
| [2] | 566 | ppDeleteNode = &pDeleteNode->mpLeft;
|
|---|
| 567 | else
|
|---|
| 568 | ppDeleteNode = &pDeleteNode->mpRight;
|
|---|
| 569 | }
|
|---|
| 570 |
|
|---|
| [35] | 571 | if (pDeleteNode->mpLeft != KRB_NULL)
|
|---|
| [2] | 572 | {
|
|---|
| 573 | /* find the rightmost node in the left tree. */
|
|---|
| [35] | 574 | const unsigned iStackEntry = Stack.cEntries;
|
|---|
| 575 | KRBTREEPTR *ppLeftLeast = &pDeleteNode->mpLeft;
|
|---|
| 576 | register KRBNODE *pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
|
|---|
| [2] | 577 |
|
|---|
| [35] | 578 | while (pLeftLeast->mpRight != KRB_NULL)
|
|---|
| [2] | 579 | {
|
|---|
| [35] | 580 | kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
|
|---|
| 581 | Stack.aEntries[Stack.cEntries++] = ppLeftLeast;
|
|---|
| [2] | 582 | ppLeftLeast = &pLeftLeast->mpRight;
|
|---|
| [35] | 583 | pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
|
|---|
| [2] | 584 | }
|
|---|
| 585 |
|
|---|
| 586 | /* link out pLeftLeast */
|
|---|
| [35] | 587 | KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
|
|---|
| [2] | 588 |
|
|---|
| 589 | /* link it in place of the delete node. */
|
|---|
| [35] | 590 | KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
|
|---|
| 591 | KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
|
|---|
| [2] | 592 | pLeftLeast->mHeight = pDeleteNode->mHeight;
|
|---|
| [35] | 593 | KRB_SET_POINTER(ppDeleteNode, pLeftLeast);
|
|---|
| 594 | Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
|
|---|
| [2] | 595 | }
|
|---|
| 596 | else
|
|---|
| 597 | {
|
|---|
| [35] | 598 | KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
|
|---|
| 599 | Stack.cEntries--;
|
|---|
| [2] | 600 | }
|
|---|
| 601 |
|
|---|
| [35] | 602 | KRB_FN(Rebalance)(&Stack);
|
|---|
| [7] | 603 |
|
|---|
| [35] | 604 | KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
|
|---|
| [7] | 605 |
|
|---|
| [35] | 606 | KRB_WRITE_UNLOCK(pRoot);
|
|---|
| [2] | 607 | return pDeleteNode;
|
|---|
| 608 | }
|
|---|
| 609 |
|
|---|
