Daniele Lacamera / PicoTCP Featured

Free (GPLv2) TCP/IP stack developed by TASS Belgium

Dependents:   lpc1768-picotcp-demo ZeroMQ_PicoTCP_Publisher_demo TCPSocket_HelloWorld_PicoTCP Pico_TCP_UDP_Test ... more

PicoTCP. Copyright (c) 2013 TASS Belgium NV.

Released under the GNU General Public License, version 2.

Different licensing models may exist, at the sole discretion of the Copyright holders.

Official homepage: http://www.picotcp.com

Bug tracker: https://github.com/tass-belgium/picotcp/issues

Development steps:

  • initial integration with mbed RTOS
  • generic mbed Ethernet driver
  • high performance NXP LPC1768 specific Ethernet driver
  • Multi-threading support for mbed RTOS
  • Berkeley sockets and integration with the New Socket API
  • Fork of the apps running on top of the New Socket API
  • Scheduling optimizations
  • Debugging/benchmarking/testing

Demo application (measuring TCP sender performance):

Import programlpc1768-picotcp-demo

A PicoTCP demo app testing the ethernet throughput on the lpc1768 mbed board.

Last commit 17 May 2013 by TASS Belgium

stack/pico_tree.c@131:4758606c9316, 2013-12-16 (annotated)

Committer:
TASS Belgium NV
Date:
Mon Dec 16 11:25:54 2013 +0100
Revision:
131:4758606c9316
Parent:
68:0847e35d08a6
Child:
149:5f4cb161cec3
Syncronized with master branch

Who changed what in which revision?

UserRevisionLine numberNew contents of line
tass 68:0847e35d08a6 1 /*********************************************************************
TASS Belgium NV 131:4758606c9316 2 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
TASS Belgium NV 131:4758606c9316 3 See LICENSE and COPYING for usage.
tass 68:0847e35d08a6 4
TASS Belgium NV 131:4758606c9316 5 Author: Andrei Carp <andrei.carp@tass.be>
TASS Belgium NV 131:4758606c9316 6 *********************************************************************/
tass 68:0847e35d08a6 7
tass 68:0847e35d08a6 8 #include "pico_tree.h"
tass 68:0847e35d08a6 9 #include "pico_config.h"
tass 68:0847e35d08a6 10 #include "pico_protocol.h"
tass 68:0847e35d08a6 11
TASS Belgium NV 131:4758606c9316 12 #define RED 0
tass 68:0847e35d08a6 13 #define BLACK 1
tass 68:0847e35d08a6 14
TASS Belgium NV 131:4758606c9316 15 /* By default the null leafs are black */
tass 68:0847e35d08a6 16 struct pico_tree_node LEAF = {
TASS Belgium NV 131:4758606c9316 17 NULL, /* key */
TASS Belgium NV 131:4758606c9316 18 &LEAF, &LEAF, &LEAF, /* parent, left,right */
TASS Belgium NV 131:4758606c9316 19 BLACK, /* color */
tass 68:0847e35d08a6 20 };
tass 68:0847e35d08a6 21
tass 68:0847e35d08a6 22 #define IS_LEAF(x) (x == &LEAF)
tass 68:0847e35d08a6 23 #define IS_NOT_LEAF(x) (x != &LEAF)
tass 68:0847e35d08a6 24 #define INIT_LEAF (&LEAF)
tass 68:0847e35d08a6 25
tass 68:0847e35d08a6 26 #define AM_I_LEFT_CHILD(x) (x == x->parent->leftChild)
tass 68:0847e35d08a6 27 #define AM_I_RIGHT_CHILD(x) (x == x->parent->rightChild)
tass 68:0847e35d08a6 28
tass 68:0847e35d08a6 29 #define PARENT(x) (x->parent)
tass 68:0847e35d08a6 30 #define GRANPA(x) (x->parent->parent)
tass 68:0847e35d08a6 31
tass 68:0847e35d08a6 32 /*
tass 68:0847e35d08a6 33 * Local Functions
tass 68:0847e35d08a6 34 */
TASS Belgium NV 131:4758606c9316 35 static struct pico_tree_node *create_node(struct pico_tree *tree, void *key);
TASS Belgium NV 131:4758606c9316 36 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 37 static void rotateToRight(struct pico_tree*root, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 38 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 39 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node);
TASS Belgium NV 131:4758606c9316 40 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB);
tass 68:0847e35d08a6 41
tass 68:0847e35d08a6 42 /*
tass 68:0847e35d08a6 43 * Exported functions
tass 68:0847e35d08a6 44 */
tass 68:0847e35d08a6 45
TASS Belgium NV 131:4758606c9316 46 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node)
tass 68:0847e35d08a6 47 {
TASS Belgium NV 131:4758606c9316 48 while(IS_NOT_LEAF(node->leftChild))
TASS Belgium NV 131:4758606c9316 49 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 50 return node;
tass 68:0847e35d08a6 51 }
tass 68:0847e35d08a6 52
TASS Belgium NV 131:4758606c9316 53 struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node)
tass 68:0847e35d08a6 54 {
TASS Belgium NV 131:4758606c9316 55 while(IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 56 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 57 return node;
tass 68:0847e35d08a6 58 }
tass 68:0847e35d08a6 59
TASS Belgium NV 131:4758606c9316 60 struct pico_tree_node *pico_tree_next(struct pico_tree_node *node)
tass 68:0847e35d08a6 61 {
TASS Belgium NV 131:4758606c9316 62 if(IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 63 {
TASS Belgium NV 131:4758606c9316 64 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 65 while(IS_NOT_LEAF(node->leftChild))
TASS Belgium NV 131:4758606c9316 66 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 67 }
TASS Belgium NV 131:4758606c9316 68 else
TASS Belgium NV 131:4758606c9316 69 {
TASS Belgium NV 131:4758606c9316 70 if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node))
TASS Belgium NV 131:4758606c9316 71 node = node->parent;
TASS Belgium NV 131:4758606c9316 72 else {
TASS Belgium NV 131:4758606c9316 73 while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
TASS Belgium NV 131:4758606c9316 74 node = node->parent;
TASS Belgium NV 131:4758606c9316 75 node = node->parent;
TASS Belgium NV 131:4758606c9316 76 }
TASS Belgium NV 131:4758606c9316 77 }
tass 68:0847e35d08a6 78
TASS Belgium NV 131:4758606c9316 79 return node;
tass 68:0847e35d08a6 80 }
tass 68:0847e35d08a6 81
TASS Belgium NV 131:4758606c9316 82 struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node)
tass 68:0847e35d08a6 83 {
TASS Belgium NV 131:4758606c9316 84 if (IS_NOT_LEAF(node->leftChild)) {
TASS Belgium NV 131:4758606c9316 85 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 86 while (IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 87 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 88 } else {
TASS Belgium NV 131:4758606c9316 89 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
TASS Belgium NV 131:4758606c9316 90 node = node->parent;
TASS Belgium NV 131:4758606c9316 91 else {
TASS Belgium NV 131:4758606c9316 92 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
TASS Belgium NV 131:4758606c9316 93 node = node->parent;
TASS Belgium NV 131:4758606c9316 94 node = node->parent;
TASS Belgium NV 131:4758606c9316 95 }
TASS Belgium NV 131:4758606c9316 96 }
tass 68:0847e35d08a6 97
TASS Belgium NV 131:4758606c9316 98 return node;
tass 68:0847e35d08a6 99 }
tass 68:0847e35d08a6 100
TASS Belgium NV 131:4758606c9316 101 void *pico_tree_insert(struct pico_tree*tree, void *key)
TASS Belgium NV 131:4758606c9316 102 {
tass 68:0847e35d08a6 103
TASS Belgium NV 131:4758606c9316 104 struct pico_tree_node *last_node = INIT_LEAF;
TASS Belgium NV 131:4758606c9316 105 struct pico_tree_node *temp = tree->root;
TASS Belgium NV 131:4758606c9316 106 struct pico_tree_node *insert;
TASS Belgium NV 131:4758606c9316 107 void *LocalKey;
TASS Belgium NV 131:4758606c9316 108 int result = 0;
tass 68:0847e35d08a6 109
TASS Belgium NV 131:4758606c9316 110 LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree, key) : NULL);
TASS Belgium NV 131:4758606c9316 111 /* if node already in, bail out */
TASS Belgium NV 131:4758606c9316 112 if(LocalKey)
TASS Belgium NV 131:4758606c9316 113 return LocalKey;
TASS Belgium NV 131:4758606c9316 114 else
TASS Belgium NV 131:4758606c9316 115 {
TASS Belgium NV 131:4758606c9316 116 insert = create_node(tree, key);
TASS Belgium NV 131:4758606c9316 117 if(!insert)
TASS Belgium NV 131:4758606c9316 118 {
TASS Belgium NV 131:4758606c9316 119 pico_err = PICO_ERR_ENOMEM;
TASS Belgium NV 131:4758606c9316 120 /* to let the user know that it couldn't insert */
TASS Belgium NV 131:4758606c9316 121 return (void *)&LEAF;
TASS Belgium NV 131:4758606c9316 122 }
TASS Belgium NV 131:4758606c9316 123 }
tass 68:0847e35d08a6 124
TASS Belgium NV 131:4758606c9316 125 /* search for the place to insert the new node */
TASS Belgium NV 131:4758606c9316 126 while(IS_NOT_LEAF(temp))
TASS Belgium NV 131:4758606c9316 127 {
TASS Belgium NV 131:4758606c9316 128 last_node = temp;
TASS Belgium NV 131:4758606c9316 129 result = tree->compare(insert->keyValue, temp->keyValue);
tass 68:0847e35d08a6 130
TASS Belgium NV 131:4758606c9316 131 temp = (result < 0 ? temp->leftChild : temp->rightChild);
TASS Belgium NV 131:4758606c9316 132 }
TASS Belgium NV 131:4758606c9316 133 /* make the needed connections */
TASS Belgium NV 131:4758606c9316 134 insert->parent = last_node;
tass 68:0847e35d08a6 135
TASS Belgium NV 131:4758606c9316 136 if(IS_LEAF(last_node))
TASS Belgium NV 131:4758606c9316 137 tree->root = insert;
TASS Belgium NV 131:4758606c9316 138 else{
TASS Belgium NV 131:4758606c9316 139 result = tree->compare(insert->keyValue, last_node->keyValue);
TASS Belgium NV 131:4758606c9316 140 if(result < 0)
TASS Belgium NV 131:4758606c9316 141 last_node->leftChild = insert;
TASS Belgium NV 131:4758606c9316 142 else
TASS Belgium NV 131:4758606c9316 143 last_node->rightChild = insert;
TASS Belgium NV 131:4758606c9316 144 }
tass 68:0847e35d08a6 145
TASS Belgium NV 131:4758606c9316 146 /* fix colour issues */
TASS Belgium NV 131:4758606c9316 147 fix_insert_collisions(tree, insert);
tass 68:0847e35d08a6 148
TASS Belgium NV 131:4758606c9316 149 return NULL;
tass 68:0847e35d08a6 150 }
tass 68:0847e35d08a6 151
TASS Belgium NV 131:4758606c9316 152 struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 153 {
TASS Belgium NV 131:4758606c9316 154 struct pico_tree_node *found;
tass 68:0847e35d08a6 155
TASS Belgium NV 131:4758606c9316 156 found = tree->root;
tass 68:0847e35d08a6 157
TASS Belgium NV 131:4758606c9316 158 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 159 {
TASS Belgium NV 131:4758606c9316 160 int result;
TASS Belgium NV 131:4758606c9316 161 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 162 if(result == 0)
TASS Belgium NV 131:4758606c9316 163 {
TASS Belgium NV 131:4758606c9316 164 return found;
TASS Belgium NV 131:4758606c9316 165 }
TASS Belgium NV 131:4758606c9316 166 else if(result < 0)
TASS Belgium NV 131:4758606c9316 167 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 168 else
TASS Belgium NV 131:4758606c9316 169 found = found->leftChild;
TASS Belgium NV 131:4758606c9316 170 }
TASS Belgium NV 131:4758606c9316 171 return NULL;
tass 68:0847e35d08a6 172 }
tass 68:0847e35d08a6 173
TASS Belgium NV 131:4758606c9316 174 void *pico_tree_findKey(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 175 {
TASS Belgium NV 131:4758606c9316 176 struct pico_tree_node *found;
tass 68:0847e35d08a6 177
tass 68:0847e35d08a6 178
TASS Belgium NV 131:4758606c9316 179 found = tree->root;
tass 68:0847e35d08a6 180
TASS Belgium NV 131:4758606c9316 181 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 182 {
TASS Belgium NV 131:4758606c9316 183 int result;
tass 68:0847e35d08a6 184
TASS Belgium NV 131:4758606c9316 185 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 186 if(result == 0)
TASS Belgium NV 131:4758606c9316 187 return found->keyValue;
TASS Belgium NV 131:4758606c9316 188 else if(result < 0)
TASS Belgium NV 131:4758606c9316 189 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 190 else
TASS Belgium NV 131:4758606c9316 191 found = found->leftChild;
tass 68:0847e35d08a6 192
TASS Belgium NV 131:4758606c9316 193 }
TASS Belgium NV 131:4758606c9316 194 return NULL;
tass 68:0847e35d08a6 195 }
tass 68:0847e35d08a6 196
TASS Belgium NV 131:4758606c9316 197 void *pico_tree_first(struct pico_tree *tree)
tass 68:0847e35d08a6 198 {
TASS Belgium NV 131:4758606c9316 199 return pico_tree_firstNode(tree->root)->keyValue;
tass 68:0847e35d08a6 200 }
tass 68:0847e35d08a6 201
TASS Belgium NV 131:4758606c9316 202 void *pico_tree_last(struct pico_tree *tree)
tass 68:0847e35d08a6 203 {
TASS Belgium NV 131:4758606c9316 204 return pico_tree_lastNode(tree->root)->keyValue;
tass 68:0847e35d08a6 205 }
tass 68:0847e35d08a6 206
TASS Belgium NV 131:4758606c9316 207 void *pico_tree_delete(struct pico_tree *tree, void *key)
TASS Belgium NV 131:4758606c9316 208 {
tass 68:0847e35d08a6 209
TASS Belgium NV 131:4758606c9316 210 uint8_t nodeColor; /* keeps the color of the node to be deleted */
TASS Belgium NV 131:4758606c9316 211 void *lkey; /* keeps a copy of the key which will be removed */
TASS Belgium NV 131:4758606c9316 212 struct pico_tree_node *delete; /* keeps a copy of the node to be extracted */
TASS Belgium NV 131:4758606c9316 213 struct pico_tree_node *temp; /* temporary */
TASS Belgium NV 131:4758606c9316 214 struct pico_tree_node *ltemp; /* used for switching nodes, as a copy */
tass 68:0847e35d08a6 215
TASS Belgium NV 131:4758606c9316 216 delete = pico_tree_findNode(tree, key);
TASS Belgium NV 131:4758606c9316 217 ltemp = delete;
tass 68:0847e35d08a6 218
TASS Belgium NV 131:4758606c9316 219 /* this key isn't in the tree, bail out */
TASS Belgium NV 131:4758606c9316 220 if(!delete)
TASS Belgium NV 131:4758606c9316 221 return NULL;
tass 68:0847e35d08a6 222
TASS Belgium NV 131:4758606c9316 223 lkey = delete->keyValue;
TASS Belgium NV 131:4758606c9316 224 nodeColor = delete->color;
tass 68:0847e35d08a6 225
TASS Belgium NV 131:4758606c9316 226 if(IS_LEAF(delete->leftChild))
TASS Belgium NV 131:4758606c9316 227 {
TASS Belgium NV 131:4758606c9316 228 temp = ltemp->rightChild;
TASS Belgium NV 131:4758606c9316 229 switchNodes(tree, ltemp, ltemp->rightChild);
TASS Belgium NV 131:4758606c9316 230 }
TASS Belgium NV 131:4758606c9316 231 else
tass 68:0847e35d08a6 232 if(IS_LEAF(delete->rightChild))
tass 68:0847e35d08a6 233 {
TASS Belgium NV 131:4758606c9316 234 struct pico_tree_node *_ltemp = delete;
TASS Belgium NV 131:4758606c9316 235 temp = _ltemp->leftChild;
TASS Belgium NV 131:4758606c9316 236 switchNodes(tree, _ltemp, _ltemp->leftChild);
tass 68:0847e35d08a6 237 }
tass 68:0847e35d08a6 238 else{
TASS Belgium NV 131:4758606c9316 239 struct pico_tree_node *min;
TASS Belgium NV 131:4758606c9316 240 min = pico_tree_firstNode(delete->rightChild);
TASS Belgium NV 131:4758606c9316 241 nodeColor = min->color;
tass 68:0847e35d08a6 242
TASS Belgium NV 131:4758606c9316 243 temp = min->rightChild;
TASS Belgium NV 131:4758606c9316 244 if(min->parent == ltemp && IS_NOT_LEAF(temp))
TASS Belgium NV 131:4758606c9316 245 temp->parent = min;
TASS Belgium NV 131:4758606c9316 246 else{
TASS Belgium NV 131:4758606c9316 247 switchNodes(tree, min, min->rightChild);
TASS Belgium NV 131:4758606c9316 248 min->rightChild = ltemp->rightChild;
TASS Belgium NV 131:4758606c9316 249 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
TASS Belgium NV 131:4758606c9316 250 }
TASS Belgium NV 131:4758606c9316 251
TASS Belgium NV 131:4758606c9316 252 switchNodes(tree, ltemp, min);
TASS Belgium NV 131:4758606c9316 253 min->leftChild = ltemp->leftChild;
TASS Belgium NV 131:4758606c9316 254 if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min;
TASS Belgium NV 131:4758606c9316 255
TASS Belgium NV 131:4758606c9316 256 min->color = ltemp->color;
tass 68:0847e35d08a6 257 }
tass 68:0847e35d08a6 258
TASS Belgium NV 131:4758606c9316 259 /* deleted node is black, this will mess up the black path property */
TASS Belgium NV 131:4758606c9316 260 if(nodeColor == BLACK)
TASS Belgium NV 131:4758606c9316 261 fix_delete_collisions(tree, temp);
tass 68:0847e35d08a6 262
TASS Belgium NV 131:4758606c9316 263 pico_free(delete);
tass 68:0847e35d08a6 264
TASS Belgium NV 131:4758606c9316 265 return lkey;
tass 68:0847e35d08a6 266 }
tass 68:0847e35d08a6 267
TASS Belgium NV 131:4758606c9316 268 int pico_tree_empty(struct pico_tree *tree)
tass 68:0847e35d08a6 269 {
TASS Belgium NV 131:4758606c9316 270 return (!tree->root || IS_LEAF(tree->root));
tass 68:0847e35d08a6 271 }
tass 68:0847e35d08a6 272
tass 68:0847e35d08a6 273 /*
tass 68:0847e35d08a6 274 * Private functions
tass 68:0847e35d08a6 275 */
TASS Belgium NV 131:4758606c9316 276 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node)
tass 68:0847e35d08a6 277 {
TASS Belgium NV 131:4758606c9316 278 struct pico_tree_node*temp;
tass 68:0847e35d08a6 279
TASS Belgium NV 131:4758606c9316 280 temp = node->rightChild;
tass 68:0847e35d08a6 281
TASS Belgium NV 131:4758606c9316 282 if(temp == &LEAF) return;
tass 68:0847e35d08a6 283
TASS Belgium NV 131:4758606c9316 284 node->rightChild = temp->leftChild;
tass 68:0847e35d08a6 285
TASS Belgium NV 131:4758606c9316 286 if(IS_NOT_LEAF(temp->leftChild))
TASS Belgium NV 131:4758606c9316 287 temp->leftChild->parent = node;
tass 68:0847e35d08a6 288
TASS Belgium NV 131:4758606c9316 289 temp->parent = node->parent;
tass 68:0847e35d08a6 290
TASS Belgium NV 131:4758606c9316 291 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 292 tree->root = temp;
TASS Belgium NV 131:4758606c9316 293 else
tass 68:0847e35d08a6 294 if(node == node->parent->leftChild)
TASS Belgium NV 131:4758606c9316 295 node->parent->leftChild = temp;
tass 68:0847e35d08a6 296 else
TASS Belgium NV 131:4758606c9316 297 node->parent->rightChild = temp;
tass 68:0847e35d08a6 298
TASS Belgium NV 131:4758606c9316 299 temp->leftChild = node;
TASS Belgium NV 131:4758606c9316 300 node->parent = temp;
tass 68:0847e35d08a6 301 }
tass 68:0847e35d08a6 302
tass 68:0847e35d08a6 303
TASS Belgium NV 131:4758606c9316 304 static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 305 {
TASS Belgium NV 131:4758606c9316 306 struct pico_tree_node*temp;
tass 68:0847e35d08a6 307
TASS Belgium NV 131:4758606c9316 308 temp = node->leftChild;
TASS Belgium NV 131:4758606c9316 309 node->leftChild = temp->rightChild;
tass 68:0847e35d08a6 310
TASS Belgium NV 131:4758606c9316 311 if(temp == &LEAF) return;
tass 68:0847e35d08a6 312
TASS Belgium NV 131:4758606c9316 313 if(IS_NOT_LEAF(temp->rightChild))
TASS Belgium NV 131:4758606c9316 314 temp->rightChild->parent = node;
tass 68:0847e35d08a6 315
TASS Belgium NV 131:4758606c9316 316 temp->parent = node->parent;
tass 68:0847e35d08a6 317
TASS Belgium NV 131:4758606c9316 318 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 319 tree->root = temp;
TASS Belgium NV 131:4758606c9316 320 else
tass 68:0847e35d08a6 321 if(node == node->parent->rightChild)
TASS Belgium NV 131:4758606c9316 322 node->parent->rightChild = temp;
tass 68:0847e35d08a6 323 else
TASS Belgium NV 131:4758606c9316 324 node->parent->leftChild = temp;
tass 68:0847e35d08a6 325
TASS Belgium NV 131:4758606c9316 326 temp->rightChild = node;
TASS Belgium NV 131:4758606c9316 327 node->parent = temp;
TASS Belgium NV 131:4758606c9316 328 return;
tass 68:0847e35d08a6 329 }
tass 68:0847e35d08a6 330
TASS Belgium NV 131:4758606c9316 331 static struct pico_tree_node *create_node(struct pico_tree *tree, void*key)
tass 68:0847e35d08a6 332 {
TASS Belgium NV 131:4758606c9316 333 struct pico_tree_node *temp;
TASS Belgium NV 131:4758606c9316 334 IGNORE_PARAMETER(tree);
TASS Belgium NV 131:4758606c9316 335 temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node));
tass 68:0847e35d08a6 336
TASS Belgium NV 131:4758606c9316 337 if(!temp)
TASS Belgium NV 131:4758606c9316 338 return NULL;
tass 68:0847e35d08a6 339
TASS Belgium NV 131:4758606c9316 340 temp->keyValue = key;
TASS Belgium NV 131:4758606c9316 341 temp->parent = &LEAF;
TASS Belgium NV 131:4758606c9316 342 temp->leftChild = &LEAF;
TASS Belgium NV 131:4758606c9316 343 temp->rightChild = &LEAF;
TASS Belgium NV 131:4758606c9316 344 /* by default every new node is red */
TASS Belgium NV 131:4758606c9316 345 temp->color = RED;
TASS Belgium NV 131:4758606c9316 346 return temp;
tass 68:0847e35d08a6 347 }
tass 68:0847e35d08a6 348
tass 68:0847e35d08a6 349 /*
tass 68:0847e35d08a6 350 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 351 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 352 */
TASS Belgium NV 131:4758606c9316 353 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node)
tass 68:0847e35d08a6 354 {
TASS Belgium NV 131:4758606c9316 355 struct pico_tree_node*temp;
TASS Belgium NV 131:4758606c9316 356
TASS Belgium NV 131:4758606c9316 357 while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)))
TASS Belgium NV 131:4758606c9316 358 {
TASS Belgium NV 131:4758606c9316 359 if(AM_I_RIGHT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 360 {
TASS Belgium NV 131:4758606c9316 361 temp = GRANPA(node)->leftChild;
TASS Belgium NV 131:4758606c9316 362 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 363 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 364 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 365 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 366 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 367 }
TASS Belgium NV 131:4758606c9316 368 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 369 if(node == node->parent->leftChild) {
TASS Belgium NV 131:4758606c9316 370 node = node->parent;
TASS Belgium NV 131:4758606c9316 371 rotateToRight(tree, node);
TASS Belgium NV 131:4758606c9316 372 }
tass 68:0847e35d08a6 373
TASS Belgium NV 131:4758606c9316 374 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 375 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 376 rotateToLeft(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 377 }
TASS Belgium NV 131:4758606c9316 378 }
TASS Belgium NV 131:4758606c9316 379 else if(AM_I_LEFT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 380 {
TASS Belgium NV 131:4758606c9316 381 temp = GRANPA(node)->rightChild;
TASS Belgium NV 131:4758606c9316 382 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 383 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 384 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 385 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 386 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 387 }
TASS Belgium NV 131:4758606c9316 388 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 389 if(AM_I_RIGHT_CHILD(node)) {
TASS Belgium NV 131:4758606c9316 390 node = node->parent;
TASS Belgium NV 131:4758606c9316 391 rotateToLeft(tree, node);
TASS Belgium NV 131:4758606c9316 392 }
TASS Belgium NV 131:4758606c9316 393
TASS Belgium NV 131:4758606c9316 394 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 395 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 396 rotateToRight(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 397 }
TASS Belgium NV 131:4758606c9316 398 }
tass 68:0847e35d08a6 399 }
TASS Belgium NV 131:4758606c9316 400 /* make sure that the root of the tree stays black */
TASS Belgium NV 131:4758606c9316 401 tree->root->color = BLACK;
tass 68:0847e35d08a6 402 }
tass 68:0847e35d08a6 403
TASS Belgium NV 131:4758606c9316 404 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB)
tass 68:0847e35d08a6 405 {
tass 68:0847e35d08a6 406
TASS Belgium NV 131:4758606c9316 407 if(IS_LEAF(nodeA->parent))
TASS Belgium NV 131:4758606c9316 408 tree->root = nodeB;
tass 68:0847e35d08a6 409 else
TASS Belgium NV 131:4758606c9316 410 if(IS_NOT_LEAF(nodeA))
TASS Belgium NV 131:4758606c9316 411 {
TASS Belgium NV 131:4758606c9316 412 if(AM_I_LEFT_CHILD(nodeA))
TASS Belgium NV 131:4758606c9316 413 nodeA->parent->leftChild = nodeB;
TASS Belgium NV 131:4758606c9316 414 else
TASS Belgium NV 131:4758606c9316 415 nodeA->parent->rightChild = nodeB;
TASS Belgium NV 131:4758606c9316 416 }
tass 68:0847e35d08a6 417
TASS Belgium NV 131:4758606c9316 418 if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent;
tass 68:0847e35d08a6 419
tass 68:0847e35d08a6 420 }
tass 68:0847e35d08a6 421
tass 68:0847e35d08a6 422 /*
tass 68:0847e35d08a6 423 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 424 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 425 * In this case the function fixes the constant black path property.
tass 68:0847e35d08a6 426 */
TASS Belgium NV 131:4758606c9316 427 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 428 {
TASS Belgium NV 131:4758606c9316 429 struct pico_tree_node*temp;
TASS Belgium NV 131:4758606c9316 430
TASS Belgium NV 131:4758606c9316 431 while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
TASS Belgium NV 131:4758606c9316 432 {
TASS Belgium NV 131:4758606c9316 433 if(AM_I_LEFT_CHILD(node)) {
tass 68:0847e35d08a6 434
TASS Belgium NV 131:4758606c9316 435 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 436 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 437 {
TASS Belgium NV 131:4758606c9316 438 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 439 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 440 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 441 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 442 }
TASS Belgium NV 131:4758606c9316 443
TASS Belgium NV 131:4758606c9316 444 if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 445 {
TASS Belgium NV 131:4758606c9316 446 temp->color = RED;
TASS Belgium NV 131:4758606c9316 447 node = node->parent;
TASS Belgium NV 131:4758606c9316 448 }
TASS Belgium NV 131:4758606c9316 449 else
TASS Belgium NV 131:4758606c9316 450 {
TASS Belgium NV 131:4758606c9316 451 if(temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 452 {
TASS Belgium NV 131:4758606c9316 453 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 454 temp->color = RED;
TASS Belgium NV 131:4758606c9316 455 rotateToRight(tree, temp);
TASS Belgium NV 131:4758606c9316 456 temp = temp->parent->rightChild;
TASS Belgium NV 131:4758606c9316 457 }
tass 68:0847e35d08a6 458
TASS Belgium NV 131:4758606c9316 459 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 460 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 461 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 462 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 463 node = tree->root;
TASS Belgium NV 131:4758606c9316 464 }
TASS Belgium NV 131:4758606c9316 465 }
TASS Belgium NV 131:4758606c9316 466 else{
TASS Belgium NV 131:4758606c9316 467 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 468 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 469 {
TASS Belgium NV 131:4758606c9316 470 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 471 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 472 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 473 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 474 }
TASS Belgium NV 131:4758606c9316 475
TASS Belgium NV 131:4758606c9316 476 if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 477 {
TASS Belgium NV 131:4758606c9316 478 temp->color = RED;
TASS Belgium NV 131:4758606c9316 479 node = node->parent;
TASS Belgium NV 131:4758606c9316 480 }
TASS Belgium NV 131:4758606c9316 481 else{
TASS Belgium NV 131:4758606c9316 482 if(temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 483 {
TASS Belgium NV 131:4758606c9316 484 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 485 temp->color = RED;
TASS Belgium NV 131:4758606c9316 486 rotateToLeft(tree, temp);
TASS Belgium NV 131:4758606c9316 487 temp = temp->parent->leftChild;
TASS Belgium NV 131:4758606c9316 488 }
TASS Belgium NV 131:4758606c9316 489
TASS Belgium NV 131:4758606c9316 490 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 491 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 492 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 493 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 494 node = tree->root;
TASS Belgium NV 131:4758606c9316 495 }
TASS Belgium NV 131:4758606c9316 496 }
tass 68:0847e35d08a6 497 }
TASS Belgium NV 131:4758606c9316 498 node->color = BLACK;
tass 68:0847e35d08a6 499 }