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@149:5f4cb161cec3, 2014-04-09 (annotated)

Committer:
tass picotcp@tass.be
Date:
Wed Apr 09 14:31:41 2014 +0200
Revision:
149:5f4cb161cec3
Parent:
131:4758606c9316
Child:
152:a3d286bf94e5
Update from git masterbranch

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 picotcp@tass.be 149:5f4cb161cec3 11 #include "pico_mm.h"
tass 68:0847e35d08a6 12
TASS Belgium NV 131:4758606c9316 13 #define RED 0
tass 68:0847e35d08a6 14 #define BLACK 1
tass 68:0847e35d08a6 15
TASS Belgium NV 131:4758606c9316 16 /* By default the null leafs are black */
tass 68:0847e35d08a6 17 struct pico_tree_node LEAF = {
TASS Belgium NV 131:4758606c9316 18 NULL, /* key */
TASS Belgium NV 131:4758606c9316 19 &LEAF, &LEAF, &LEAF, /* parent, left,right */
TASS Belgium NV 131:4758606c9316 20 BLACK, /* color */
tass 68:0847e35d08a6 21 };
tass 68:0847e35d08a6 22
tass 68:0847e35d08a6 23 #define IS_LEAF(x) (x == &LEAF)
tass 68:0847e35d08a6 24 #define IS_NOT_LEAF(x) (x != &LEAF)
tass 68:0847e35d08a6 25 #define INIT_LEAF (&LEAF)
tass 68:0847e35d08a6 26
tass 68:0847e35d08a6 27 #define AM_I_LEFT_CHILD(x) (x == x->parent->leftChild)
tass 68:0847e35d08a6 28 #define AM_I_RIGHT_CHILD(x) (x == x->parent->rightChild)
tass 68:0847e35d08a6 29
tass 68:0847e35d08a6 30 #define PARENT(x) (x->parent)
tass 68:0847e35d08a6 31 #define GRANPA(x) (x->parent->parent)
tass 68:0847e35d08a6 32
tass 68:0847e35d08a6 33 /*
tass 68:0847e35d08a6 34 * Local Functions
tass 68:0847e35d08a6 35 */
tass picotcp@tass.be 149:5f4cb161cec3 36 static struct pico_tree_node *create_node(struct pico_tree *tree, void *key, uint8_t allocator);
TASS Belgium NV 131:4758606c9316 37 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 38 static void rotateToRight(struct pico_tree*root, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 39 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node);
TASS Belgium NV 131:4758606c9316 40 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node);
TASS Belgium NV 131:4758606c9316 41 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB);
tass picotcp@tass.be 149:5f4cb161cec3 42 void *pico_tree_insert_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
tass picotcp@tass.be 149:5f4cb161cec3 43 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
tass picotcp@tass.be 149:5f4cb161cec3 44
tass picotcp@tass.be 149:5f4cb161cec3 45 #ifdef PICO_SUPPORT_MM
tass picotcp@tass.be 149:5f4cb161cec3 46 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
tass picotcp@tass.be 149:5f4cb161cec3 47 * These nodes should be placed in the manager page which is in a different memory region then the nodes
tass picotcp@tass.be 149:5f4cb161cec3 48 * which are used for the pico stack in general.
tass picotcp@tass.be 149:5f4cb161cec3 49 * Therefore the following 2 functions are created so that pico_tree can use them to to put these nodes
tass picotcp@tass.be 149:5f4cb161cec3 50 * into the correct memory regions.
tass picotcp@tass.be 149:5f4cb161cec3 51 * If pico_tree_insert is called from the memory manager module, then create_node should use
tass picotcp@tass.be 149:5f4cb161cec3 52 * pico_mem_page0_zalloc to create a node. The same for pico_tree_delete.
tass picotcp@tass.be 149:5f4cb161cec3 53 */
tass picotcp@tass.be 149:5f4cb161cec3 54 extern void*pico_mem_page0_zalloc(size_t len);
tass picotcp@tass.be 149:5f4cb161cec3 55 extern void pico_mem_page0_free(void*ptr);
tass picotcp@tass.be 149:5f4cb161cec3 56 #endif /* PICO_SUPPORT_MM */
tass 68:0847e35d08a6 57
tass 68:0847e35d08a6 58 /*
tass 68:0847e35d08a6 59 * Exported functions
tass 68:0847e35d08a6 60 */
tass 68:0847e35d08a6 61
TASS Belgium NV 131:4758606c9316 62 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node)
tass 68:0847e35d08a6 63 {
TASS Belgium NV 131:4758606c9316 64 while(IS_NOT_LEAF(node->leftChild))
TASS Belgium NV 131:4758606c9316 65 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 66 return node;
tass 68:0847e35d08a6 67 }
tass 68:0847e35d08a6 68
TASS Belgium NV 131:4758606c9316 69 struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node)
tass 68:0847e35d08a6 70 {
TASS Belgium NV 131:4758606c9316 71 while(IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 72 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 73 return node;
tass 68:0847e35d08a6 74 }
tass 68:0847e35d08a6 75
TASS Belgium NV 131:4758606c9316 76 struct pico_tree_node *pico_tree_next(struct pico_tree_node *node)
tass 68:0847e35d08a6 77 {
TASS Belgium NV 131:4758606c9316 78 if(IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 79 {
TASS Belgium NV 131:4758606c9316 80 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 81 while(IS_NOT_LEAF(node->leftChild))
TASS Belgium NV 131:4758606c9316 82 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 83 }
TASS Belgium NV 131:4758606c9316 84 else
TASS Belgium NV 131:4758606c9316 85 {
TASS Belgium NV 131:4758606c9316 86 if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node))
TASS Belgium NV 131:4758606c9316 87 node = node->parent;
TASS Belgium NV 131:4758606c9316 88 else {
TASS Belgium NV 131:4758606c9316 89 while (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 node = node->parent;
TASS Belgium NV 131:4758606c9316 92 }
TASS Belgium NV 131:4758606c9316 93 }
tass 68:0847e35d08a6 94
TASS Belgium NV 131:4758606c9316 95 return node;
tass 68:0847e35d08a6 96 }
tass 68:0847e35d08a6 97
TASS Belgium NV 131:4758606c9316 98 struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node)
tass 68:0847e35d08a6 99 {
TASS Belgium NV 131:4758606c9316 100 if (IS_NOT_LEAF(node->leftChild)) {
TASS Belgium NV 131:4758606c9316 101 node = node->leftChild;
TASS Belgium NV 131:4758606c9316 102 while (IS_NOT_LEAF(node->rightChild))
TASS Belgium NV 131:4758606c9316 103 node = node->rightChild;
TASS Belgium NV 131:4758606c9316 104 } else {
TASS Belgium NV 131:4758606c9316 105 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
TASS Belgium NV 131:4758606c9316 106 node = node->parent;
TASS Belgium NV 131:4758606c9316 107 else {
TASS Belgium NV 131:4758606c9316 108 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
TASS Belgium NV 131:4758606c9316 109 node = node->parent;
TASS Belgium NV 131:4758606c9316 110 node = node->parent;
TASS Belgium NV 131:4758606c9316 111 }
TASS Belgium NV 131:4758606c9316 112 }
tass 68:0847e35d08a6 113
TASS Belgium NV 131:4758606c9316 114 return node;
tass 68:0847e35d08a6 115 }
tass 68:0847e35d08a6 116
tass picotcp@tass.be 149:5f4cb161cec3 117 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
tass picotcp@tass.be 149:5f4cb161cec3 118 * These nodes should be placed in the manager page which is in a different memory region then the nodes
tass picotcp@tass.be 149:5f4cb161cec3 119 * which are used for the pico stack in general.
tass picotcp@tass.be 149:5f4cb161cec3 120 * Therefore the following wrapper for pico_tree_insert is created.
tass picotcp@tass.be 149:5f4cb161cec3 121 * The actual implementation can be found in pico_tree_insert_implementation.
tass picotcp@tass.be 149:5f4cb161cec3 122 */
tass picotcp@tass.be 149:5f4cb161cec3 123 void *pico_tree_insert(struct pico_tree *tree, void *key)
TASS Belgium NV 131:4758606c9316 124 {
tass picotcp@tass.be 149:5f4cb161cec3 125 return pico_tree_insert_implementation(tree, key, USE_PICO_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 126 }
tass 68:0847e35d08a6 127
tass picotcp@tass.be 149:5f4cb161cec3 128 void *pico_tree_insert_implementation(struct pico_tree*tree, void *key, uint8_t allocator)
tass picotcp@tass.be 149:5f4cb161cec3 129 {
TASS Belgium NV 131:4758606c9316 130 struct pico_tree_node *last_node = INIT_LEAF;
TASS Belgium NV 131:4758606c9316 131 struct pico_tree_node *temp = tree->root;
TASS Belgium NV 131:4758606c9316 132 struct pico_tree_node *insert;
TASS Belgium NV 131:4758606c9316 133 void *LocalKey;
TASS Belgium NV 131:4758606c9316 134 int result = 0;
tass 68:0847e35d08a6 135
TASS Belgium NV 131:4758606c9316 136 LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree, key) : NULL);
TASS Belgium NV 131:4758606c9316 137 /* if node already in, bail out */
TASS Belgium NV 131:4758606c9316 138 if(LocalKey)
TASS Belgium NV 131:4758606c9316 139 return LocalKey;
TASS Belgium NV 131:4758606c9316 140 else
TASS Belgium NV 131:4758606c9316 141 {
tass picotcp@tass.be 149:5f4cb161cec3 142 if(allocator == USE_PICO_PAGE0_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 143 insert = create_node(tree, key, USE_PICO_PAGE0_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 144 else
tass picotcp@tass.be 149:5f4cb161cec3 145 insert = create_node(tree, key, USE_PICO_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 146
TASS Belgium NV 131:4758606c9316 147 if(!insert)
TASS Belgium NV 131:4758606c9316 148 {
TASS Belgium NV 131:4758606c9316 149 pico_err = PICO_ERR_ENOMEM;
TASS Belgium NV 131:4758606c9316 150 /* to let the user know that it couldn't insert */
TASS Belgium NV 131:4758606c9316 151 return (void *)&LEAF;
TASS Belgium NV 131:4758606c9316 152 }
TASS Belgium NV 131:4758606c9316 153 }
tass 68:0847e35d08a6 154
TASS Belgium NV 131:4758606c9316 155 /* search for the place to insert the new node */
TASS Belgium NV 131:4758606c9316 156 while(IS_NOT_LEAF(temp))
TASS Belgium NV 131:4758606c9316 157 {
TASS Belgium NV 131:4758606c9316 158 last_node = temp;
TASS Belgium NV 131:4758606c9316 159 result = tree->compare(insert->keyValue, temp->keyValue);
tass 68:0847e35d08a6 160
tass picotcp@tass.be 149:5f4cb161cec3 161 temp = (result < 0) ? (temp->leftChild) : (temp->rightChild);
TASS Belgium NV 131:4758606c9316 162 }
TASS Belgium NV 131:4758606c9316 163 /* make the needed connections */
TASS Belgium NV 131:4758606c9316 164 insert->parent = last_node;
tass 68:0847e35d08a6 165
TASS Belgium NV 131:4758606c9316 166 if(IS_LEAF(last_node))
TASS Belgium NV 131:4758606c9316 167 tree->root = insert;
TASS Belgium NV 131:4758606c9316 168 else{
TASS Belgium NV 131:4758606c9316 169 result = tree->compare(insert->keyValue, last_node->keyValue);
TASS Belgium NV 131:4758606c9316 170 if(result < 0)
TASS Belgium NV 131:4758606c9316 171 last_node->leftChild = insert;
TASS Belgium NV 131:4758606c9316 172 else
TASS Belgium NV 131:4758606c9316 173 last_node->rightChild = insert;
TASS Belgium NV 131:4758606c9316 174 }
tass 68:0847e35d08a6 175
TASS Belgium NV 131:4758606c9316 176 /* fix colour issues */
TASS Belgium NV 131:4758606c9316 177 fix_insert_collisions(tree, insert);
tass 68:0847e35d08a6 178
TASS Belgium NV 131:4758606c9316 179 return NULL;
tass 68:0847e35d08a6 180 }
tass 68:0847e35d08a6 181
TASS Belgium NV 131:4758606c9316 182 struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 183 {
TASS Belgium NV 131:4758606c9316 184 struct pico_tree_node *found;
tass 68:0847e35d08a6 185
TASS Belgium NV 131:4758606c9316 186 found = tree->root;
tass 68:0847e35d08a6 187
TASS Belgium NV 131:4758606c9316 188 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 189 {
TASS Belgium NV 131:4758606c9316 190 int result;
TASS Belgium NV 131:4758606c9316 191 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 192 if(result == 0)
TASS Belgium NV 131:4758606c9316 193 {
TASS Belgium NV 131:4758606c9316 194 return found;
TASS Belgium NV 131:4758606c9316 195 }
TASS Belgium NV 131:4758606c9316 196 else if(result < 0)
TASS Belgium NV 131:4758606c9316 197 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 198 else
TASS Belgium NV 131:4758606c9316 199 found = found->leftChild;
TASS Belgium NV 131:4758606c9316 200 }
TASS Belgium NV 131:4758606c9316 201 return NULL;
tass 68:0847e35d08a6 202 }
tass 68:0847e35d08a6 203
TASS Belgium NV 131:4758606c9316 204 void *pico_tree_findKey(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 205 {
TASS Belgium NV 131:4758606c9316 206 struct pico_tree_node *found;
tass 68:0847e35d08a6 207
tass 68:0847e35d08a6 208
TASS Belgium NV 131:4758606c9316 209 found = tree->root;
tass 68:0847e35d08a6 210
TASS Belgium NV 131:4758606c9316 211 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 212 {
TASS Belgium NV 131:4758606c9316 213 int result;
tass 68:0847e35d08a6 214
TASS Belgium NV 131:4758606c9316 215 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 216 if(result == 0)
TASS Belgium NV 131:4758606c9316 217 return found->keyValue;
TASS Belgium NV 131:4758606c9316 218 else if(result < 0)
TASS Belgium NV 131:4758606c9316 219 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 220 else
TASS Belgium NV 131:4758606c9316 221 found = found->leftChild;
tass 68:0847e35d08a6 222
TASS Belgium NV 131:4758606c9316 223 }
TASS Belgium NV 131:4758606c9316 224 return NULL;
tass 68:0847e35d08a6 225 }
tass 68:0847e35d08a6 226
TASS Belgium NV 131:4758606c9316 227 void *pico_tree_first(struct pico_tree *tree)
tass 68:0847e35d08a6 228 {
TASS Belgium NV 131:4758606c9316 229 return pico_tree_firstNode(tree->root)->keyValue;
tass 68:0847e35d08a6 230 }
tass 68:0847e35d08a6 231
TASS Belgium NV 131:4758606c9316 232 void *pico_tree_last(struct pico_tree *tree)
tass 68:0847e35d08a6 233 {
TASS Belgium NV 131:4758606c9316 234 return pico_tree_lastNode(tree->root)->keyValue;
tass 68:0847e35d08a6 235 }
tass 68:0847e35d08a6 236
tass picotcp@tass.be 149:5f4cb161cec3 237 static uint8_t pico_tree_delete_node(struct pico_tree *tree, struct pico_tree_node *d, struct pico_tree_node **temp)
TASS Belgium NV 131:4758606c9316 238 {
tass picotcp@tass.be 149:5f4cb161cec3 239 struct pico_tree_node *min;
tass picotcp@tass.be 149:5f4cb161cec3 240 struct pico_tree_node *ltemp = d;
tass picotcp@tass.be 149:5f4cb161cec3 241 uint8_t nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 242 min = pico_tree_firstNode(d->rightChild);
tass picotcp@tass.be 149:5f4cb161cec3 243 nodeColor = min->color;
tass 68:0847e35d08a6 244
tass picotcp@tass.be 149:5f4cb161cec3 245 *temp = min->rightChild;
tass picotcp@tass.be 149:5f4cb161cec3 246 if(min->parent == ltemp && IS_NOT_LEAF(*temp))
tass picotcp@tass.be 149:5f4cb161cec3 247 (*temp)->parent = min;
tass picotcp@tass.be 149:5f4cb161cec3 248 else{
tass picotcp@tass.be 149:5f4cb161cec3 249 switchNodes(tree, min, min->rightChild);
tass picotcp@tass.be 149:5f4cb161cec3 250 min->rightChild = ltemp->rightChild;
tass picotcp@tass.be 149:5f4cb161cec3 251 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
tass picotcp@tass.be 149:5f4cb161cec3 252 }
tass picotcp@tass.be 149:5f4cb161cec3 253
tass picotcp@tass.be 149:5f4cb161cec3 254 switchNodes(tree, ltemp, min);
tass picotcp@tass.be 149:5f4cb161cec3 255 min->leftChild = ltemp->leftChild;
tass 68:0847e35d08a6 256
tass picotcp@tass.be 149:5f4cb161cec3 257 if(IS_NOT_LEAF(min->leftChild))
tass picotcp@tass.be 149:5f4cb161cec3 258 min->leftChild->parent = min;
tass 68:0847e35d08a6 259
tass picotcp@tass.be 149:5f4cb161cec3 260 min->color = ltemp->color;
tass picotcp@tass.be 149:5f4cb161cec3 261 return nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 262 }
tass 68:0847e35d08a6 263
tass picotcp@tass.be 149:5f4cb161cec3 264 static uint8_t pico_tree_delete_check_switch(struct pico_tree *tree, struct pico_tree_node *delete, struct pico_tree_node **temp)
tass picotcp@tass.be 149:5f4cb161cec3 265 {
tass picotcp@tass.be 149:5f4cb161cec3 266 struct pico_tree_node *ltemp = delete;
tass picotcp@tass.be 149:5f4cb161cec3 267 uint8_t nodeColor = delete->color;
TASS Belgium NV 131:4758606c9316 268 if(IS_LEAF(delete->leftChild))
TASS Belgium NV 131:4758606c9316 269 {
tass picotcp@tass.be 149:5f4cb161cec3 270 *temp = ltemp->rightChild;
TASS Belgium NV 131:4758606c9316 271 switchNodes(tree, ltemp, ltemp->rightChild);
TASS Belgium NV 131:4758606c9316 272 }
TASS Belgium NV 131:4758606c9316 273 else
tass 68:0847e35d08a6 274 if(IS_LEAF(delete->rightChild))
tass 68:0847e35d08a6 275 {
TASS Belgium NV 131:4758606c9316 276 struct pico_tree_node *_ltemp = delete;
tass picotcp@tass.be 149:5f4cb161cec3 277 *temp = _ltemp->leftChild;
TASS Belgium NV 131:4758606c9316 278 switchNodes(tree, _ltemp, _ltemp->leftChild);
tass 68:0847e35d08a6 279 }
tass 68:0847e35d08a6 280 else{
tass picotcp@tass.be 149:5f4cb161cec3 281 nodeColor = pico_tree_delete_node(tree, delete, temp);
tass picotcp@tass.be 149:5f4cb161cec3 282 }
tass picotcp@tass.be 149:5f4cb161cec3 283
tass picotcp@tass.be 149:5f4cb161cec3 284 return nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 285
tass picotcp@tass.be 149:5f4cb161cec3 286 }
tass picotcp@tass.be 149:5f4cb161cec3 287
tass picotcp@tass.be 149:5f4cb161cec3 288 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
tass picotcp@tass.be 149:5f4cb161cec3 289 * These nodes should be placed in the manager page which is in a different memory region then the nodes
tass picotcp@tass.be 149:5f4cb161cec3 290 * which are used for the pico stack in general.
tass picotcp@tass.be 149:5f4cb161cec3 291 * Therefore the following wrapper for pico_tree_delete is created.
tass picotcp@tass.be 149:5f4cb161cec3 292 * The actual implementation can be found in pico_tree_delete_implementation.
tass picotcp@tass.be 149:5f4cb161cec3 293 */
tass picotcp@tass.be 149:5f4cb161cec3 294 void *pico_tree_delete(struct pico_tree *tree, void *key)
tass picotcp@tass.be 149:5f4cb161cec3 295 {
tass picotcp@tass.be 149:5f4cb161cec3 296 return pico_tree_delete_implementation(tree, key, USE_PICO_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 297 }
tass 68:0847e35d08a6 298
tass picotcp@tass.be 149:5f4cb161cec3 299 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator)
tass picotcp@tass.be 149:5f4cb161cec3 300 {
tass picotcp@tass.be 149:5f4cb161cec3 301 struct pico_tree_node *temp;
tass picotcp@tass.be 149:5f4cb161cec3 302 uint8_t nodeColor; /* keeps the color of the node to be deleted */
tass picotcp@tass.be 149:5f4cb161cec3 303 void *lkey; /* keeps a copy of the key which will be removed */
tass picotcp@tass.be 149:5f4cb161cec3 304 struct pico_tree_node *delete; /* keeps a copy of the node to be extracted */
TASS Belgium NV 131:4758606c9316 305
tass picotcp@tass.be 149:5f4cb161cec3 306 if (!key)
tass picotcp@tass.be 149:5f4cb161cec3 307 return NULL;
tass picotcp@tass.be 149:5f4cb161cec3 308
tass picotcp@tass.be 149:5f4cb161cec3 309 delete = pico_tree_findNode(tree, key);
TASS Belgium NV 131:4758606c9316 310
tass picotcp@tass.be 149:5f4cb161cec3 311 /* this key isn't in the tree, bail out */
tass picotcp@tass.be 149:5f4cb161cec3 312 if(!delete)
tass picotcp@tass.be 149:5f4cb161cec3 313 return NULL;
tass picotcp@tass.be 149:5f4cb161cec3 314
tass picotcp@tass.be 149:5f4cb161cec3 315 lkey = delete->keyValue;
tass picotcp@tass.be 149:5f4cb161cec3 316 nodeColor = pico_tree_delete_check_switch(tree, delete, &temp);
tass 68:0847e35d08a6 317
TASS Belgium NV 131:4758606c9316 318 /* deleted node is black, this will mess up the black path property */
TASS Belgium NV 131:4758606c9316 319 if(nodeColor == BLACK)
TASS Belgium NV 131:4758606c9316 320 fix_delete_collisions(tree, temp);
tass 68:0847e35d08a6 321
tass picotcp@tass.be 149:5f4cb161cec3 322 if(allocator == USE_PICO_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 323 PICO_FREE(delete);
tass 68:0847e35d08a6 324
tass picotcp@tass.be 149:5f4cb161cec3 325 #ifdef PICO_SUPPORT_MM
tass picotcp@tass.be 149:5f4cb161cec3 326 else
tass picotcp@tass.be 149:5f4cb161cec3 327 pico_mem_page0_free(delete);
tass picotcp@tass.be 149:5f4cb161cec3 328 #endif
TASS Belgium NV 131:4758606c9316 329 return lkey;
tass 68:0847e35d08a6 330 }
tass 68:0847e35d08a6 331
TASS Belgium NV 131:4758606c9316 332 int pico_tree_empty(struct pico_tree *tree)
tass 68:0847e35d08a6 333 {
TASS Belgium NV 131:4758606c9316 334 return (!tree->root || IS_LEAF(tree->root));
tass 68:0847e35d08a6 335 }
tass 68:0847e35d08a6 336
tass 68:0847e35d08a6 337 /*
tass 68:0847e35d08a6 338 * Private functions
tass 68:0847e35d08a6 339 */
TASS Belgium NV 131:4758606c9316 340 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node)
tass 68:0847e35d08a6 341 {
TASS Belgium NV 131:4758606c9316 342 struct pico_tree_node*temp;
tass 68:0847e35d08a6 343
TASS Belgium NV 131:4758606c9316 344 temp = node->rightChild;
tass 68:0847e35d08a6 345
TASS Belgium NV 131:4758606c9316 346 if(temp == &LEAF) return;
tass 68:0847e35d08a6 347
TASS Belgium NV 131:4758606c9316 348 node->rightChild = temp->leftChild;
tass 68:0847e35d08a6 349
TASS Belgium NV 131:4758606c9316 350 if(IS_NOT_LEAF(temp->leftChild))
TASS Belgium NV 131:4758606c9316 351 temp->leftChild->parent = node;
tass 68:0847e35d08a6 352
TASS Belgium NV 131:4758606c9316 353 temp->parent = node->parent;
tass 68:0847e35d08a6 354
TASS Belgium NV 131:4758606c9316 355 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 356 tree->root = temp;
TASS Belgium NV 131:4758606c9316 357 else
tass 68:0847e35d08a6 358 if(node == node->parent->leftChild)
TASS Belgium NV 131:4758606c9316 359 node->parent->leftChild = temp;
tass 68:0847e35d08a6 360 else
TASS Belgium NV 131:4758606c9316 361 node->parent->rightChild = temp;
tass 68:0847e35d08a6 362
TASS Belgium NV 131:4758606c9316 363 temp->leftChild = node;
TASS Belgium NV 131:4758606c9316 364 node->parent = temp;
tass 68:0847e35d08a6 365 }
tass 68:0847e35d08a6 366
tass 68:0847e35d08a6 367
TASS Belgium NV 131:4758606c9316 368 static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 369 {
TASS Belgium NV 131:4758606c9316 370 struct pico_tree_node*temp;
tass 68:0847e35d08a6 371
TASS Belgium NV 131:4758606c9316 372 temp = node->leftChild;
TASS Belgium NV 131:4758606c9316 373 node->leftChild = temp->rightChild;
tass 68:0847e35d08a6 374
TASS Belgium NV 131:4758606c9316 375 if(temp == &LEAF) return;
tass 68:0847e35d08a6 376
TASS Belgium NV 131:4758606c9316 377 if(IS_NOT_LEAF(temp->rightChild))
TASS Belgium NV 131:4758606c9316 378 temp->rightChild->parent = node;
tass 68:0847e35d08a6 379
TASS Belgium NV 131:4758606c9316 380 temp->parent = node->parent;
tass 68:0847e35d08a6 381
TASS Belgium NV 131:4758606c9316 382 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 383 tree->root = temp;
TASS Belgium NV 131:4758606c9316 384 else
tass 68:0847e35d08a6 385 if(node == node->parent->rightChild)
TASS Belgium NV 131:4758606c9316 386 node->parent->rightChild = temp;
tass 68:0847e35d08a6 387 else
TASS Belgium NV 131:4758606c9316 388 node->parent->leftChild = temp;
tass 68:0847e35d08a6 389
TASS Belgium NV 131:4758606c9316 390 temp->rightChild = node;
TASS Belgium NV 131:4758606c9316 391 node->parent = temp;
TASS Belgium NV 131:4758606c9316 392 return;
tass 68:0847e35d08a6 393 }
tass 68:0847e35d08a6 394
tass picotcp@tass.be 149:5f4cb161cec3 395 static struct pico_tree_node *create_node(struct pico_tree *tree, void*key, uint8_t allocator)
tass 68:0847e35d08a6 396 {
tass picotcp@tass.be 149:5f4cb161cec3 397 struct pico_tree_node *temp = NULL;
TASS Belgium NV 131:4758606c9316 398 IGNORE_PARAMETER(tree);
tass picotcp@tass.be 149:5f4cb161cec3 399 if(allocator == USE_PICO_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 400 temp = (struct pico_tree_node *)PICO_ZALLOC(sizeof(struct pico_tree_node));
tass picotcp@tass.be 149:5f4cb161cec3 401
tass picotcp@tass.be 149:5f4cb161cec3 402 #ifdef PICO_SUPPORT_MM
tass picotcp@tass.be 149:5f4cb161cec3 403 else
tass picotcp@tass.be 149:5f4cb161cec3 404 temp = (struct pico_tree_node *)pico_mem_page0_zalloc(sizeof(struct pico_tree_node));
tass picotcp@tass.be 149:5f4cb161cec3 405 #endif
tass 68:0847e35d08a6 406
TASS Belgium NV 131:4758606c9316 407 if(!temp)
TASS Belgium NV 131:4758606c9316 408 return NULL;
tass 68:0847e35d08a6 409
TASS Belgium NV 131:4758606c9316 410 temp->keyValue = key;
TASS Belgium NV 131:4758606c9316 411 temp->parent = &LEAF;
TASS Belgium NV 131:4758606c9316 412 temp->leftChild = &LEAF;
TASS Belgium NV 131:4758606c9316 413 temp->rightChild = &LEAF;
TASS Belgium NV 131:4758606c9316 414 /* by default every new node is red */
TASS Belgium NV 131:4758606c9316 415 temp->color = RED;
TASS Belgium NV 131:4758606c9316 416 return temp;
tass 68:0847e35d08a6 417 }
tass 68:0847e35d08a6 418
tass 68:0847e35d08a6 419 /*
tass 68:0847e35d08a6 420 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 421 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 422 */
TASS Belgium NV 131:4758606c9316 423 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node)
tass 68:0847e35d08a6 424 {
TASS Belgium NV 131:4758606c9316 425 struct pico_tree_node*temp;
TASS Belgium NV 131:4758606c9316 426
TASS Belgium NV 131:4758606c9316 427 while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)))
TASS Belgium NV 131:4758606c9316 428 {
TASS Belgium NV 131:4758606c9316 429 if(AM_I_RIGHT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 430 {
TASS Belgium NV 131:4758606c9316 431 temp = GRANPA(node)->leftChild;
TASS Belgium NV 131:4758606c9316 432 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 433 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 434 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 435 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 436 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 437 }
TASS Belgium NV 131:4758606c9316 438 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 439 if(node == node->parent->leftChild) {
TASS Belgium NV 131:4758606c9316 440 node = node->parent;
TASS Belgium NV 131:4758606c9316 441 rotateToRight(tree, node);
TASS Belgium NV 131:4758606c9316 442 }
tass 68:0847e35d08a6 443
TASS Belgium NV 131:4758606c9316 444 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 445 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 446 rotateToLeft(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 447 }
TASS Belgium NV 131:4758606c9316 448 }
TASS Belgium NV 131:4758606c9316 449 else if(AM_I_LEFT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 450 {
TASS Belgium NV 131:4758606c9316 451 temp = GRANPA(node)->rightChild;
TASS Belgium NV 131:4758606c9316 452 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 453 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 454 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 455 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 456 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 457 }
TASS Belgium NV 131:4758606c9316 458 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 459 if(AM_I_RIGHT_CHILD(node)) {
TASS Belgium NV 131:4758606c9316 460 node = node->parent;
TASS Belgium NV 131:4758606c9316 461 rotateToLeft(tree, node);
TASS Belgium NV 131:4758606c9316 462 }
TASS Belgium NV 131:4758606c9316 463
TASS Belgium NV 131:4758606c9316 464 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 465 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 466 rotateToRight(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 467 }
TASS Belgium NV 131:4758606c9316 468 }
tass 68:0847e35d08a6 469 }
TASS Belgium NV 131:4758606c9316 470 /* make sure that the root of the tree stays black */
TASS Belgium NV 131:4758606c9316 471 tree->root->color = BLACK;
tass 68:0847e35d08a6 472 }
tass 68:0847e35d08a6 473
TASS Belgium NV 131:4758606c9316 474 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB)
tass 68:0847e35d08a6 475 {
tass 68:0847e35d08a6 476
TASS Belgium NV 131:4758606c9316 477 if(IS_LEAF(nodeA->parent))
TASS Belgium NV 131:4758606c9316 478 tree->root = nodeB;
tass 68:0847e35d08a6 479 else
TASS Belgium NV 131:4758606c9316 480 if(IS_NOT_LEAF(nodeA))
TASS Belgium NV 131:4758606c9316 481 {
TASS Belgium NV 131:4758606c9316 482 if(AM_I_LEFT_CHILD(nodeA))
TASS Belgium NV 131:4758606c9316 483 nodeA->parent->leftChild = nodeB;
TASS Belgium NV 131:4758606c9316 484 else
TASS Belgium NV 131:4758606c9316 485 nodeA->parent->rightChild = nodeB;
TASS Belgium NV 131:4758606c9316 486 }
tass 68:0847e35d08a6 487
TASS Belgium NV 131:4758606c9316 488 if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent;
tass 68:0847e35d08a6 489
tass 68:0847e35d08a6 490 }
tass 68:0847e35d08a6 491
tass 68:0847e35d08a6 492 /*
tass 68:0847e35d08a6 493 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 494 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 495 * In this case the function fixes the constant black path property.
tass 68:0847e35d08a6 496 */
TASS Belgium NV 131:4758606c9316 497 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 498 {
TASS Belgium NV 131:4758606c9316 499 struct pico_tree_node*temp;
TASS Belgium NV 131:4758606c9316 500
TASS Belgium NV 131:4758606c9316 501 while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
TASS Belgium NV 131:4758606c9316 502 {
TASS Belgium NV 131:4758606c9316 503 if(AM_I_LEFT_CHILD(node)) {
tass 68:0847e35d08a6 504
TASS Belgium NV 131:4758606c9316 505 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 506 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 507 {
TASS Belgium NV 131:4758606c9316 508 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 509 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 510 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 511 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 512 }
TASS Belgium NV 131:4758606c9316 513
TASS Belgium NV 131:4758606c9316 514 if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 515 {
TASS Belgium NV 131:4758606c9316 516 temp->color = RED;
TASS Belgium NV 131:4758606c9316 517 node = node->parent;
TASS Belgium NV 131:4758606c9316 518 }
TASS Belgium NV 131:4758606c9316 519 else
TASS Belgium NV 131:4758606c9316 520 {
TASS Belgium NV 131:4758606c9316 521 if(temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 522 {
TASS Belgium NV 131:4758606c9316 523 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 524 temp->color = RED;
TASS Belgium NV 131:4758606c9316 525 rotateToRight(tree, temp);
TASS Belgium NV 131:4758606c9316 526 temp = temp->parent->rightChild;
TASS Belgium NV 131:4758606c9316 527 }
tass 68:0847e35d08a6 528
TASS Belgium NV 131:4758606c9316 529 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 530 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 531 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 532 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 533 node = tree->root;
TASS Belgium NV 131:4758606c9316 534 }
TASS Belgium NV 131:4758606c9316 535 }
TASS Belgium NV 131:4758606c9316 536 else{
TASS Belgium NV 131:4758606c9316 537 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 538 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 539 {
TASS Belgium NV 131:4758606c9316 540 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 541 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 542 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 543 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 544 }
TASS Belgium NV 131:4758606c9316 545
TASS Belgium NV 131:4758606c9316 546 if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 547 {
TASS Belgium NV 131:4758606c9316 548 temp->color = RED;
TASS Belgium NV 131:4758606c9316 549 node = node->parent;
TASS Belgium NV 131:4758606c9316 550 }
TASS Belgium NV 131:4758606c9316 551 else{
TASS Belgium NV 131:4758606c9316 552 if(temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 553 {
TASS Belgium NV 131:4758606c9316 554 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 555 temp->color = RED;
TASS Belgium NV 131:4758606c9316 556 rotateToLeft(tree, temp);
TASS Belgium NV 131:4758606c9316 557 temp = temp->parent->leftChild;
TASS Belgium NV 131:4758606c9316 558 }
TASS Belgium NV 131:4758606c9316 559
TASS Belgium NV 131:4758606c9316 560 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 561 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 562 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 563 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 564 node = tree->root;
TASS Belgium NV 131:4758606c9316 565 }
TASS Belgium NV 131:4758606c9316 566 }
tass 68:0847e35d08a6 567 }
TASS Belgium NV 131:4758606c9316 568 node->color = BLACK;
tass 68:0847e35d08a6 569 }