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@155:a70f34550c34, 2016-01-28 (annotated)

Committer:
tass
Date:
Thu Jan 28 15:12:00 2016 +0100
Revision:
155:a70f34550c34
Parent:
152:a3d286bf94e5 
Adding TCP flag for FIN.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
tass 68:0847e35d08a6 1 /*********************************************************************
tass 152:a3d286bf94e5 2 PicoTCP. Copyright (c) 2012-2015 Altran Intelligent Systems. 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 152:a3d286bf94e5 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 152:a3d286bf94e5 137
TASS Belgium NV 131:4758606c9316 138 /* if node already in, bail out */
tass 152:a3d286bf94e5 139 if(LocalKey) {
TASS Belgium NV 131:4758606c9316 140 return LocalKey;
tass 152:a3d286bf94e5 141 }
TASS Belgium NV 131:4758606c9316 142 else
TASS Belgium NV 131:4758606c9316 143 {
tass picotcp@tass.be 149:5f4cb161cec3 144 if(allocator == USE_PICO_PAGE0_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 145 insert = create_node(tree, key, USE_PICO_PAGE0_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 146 else
tass picotcp@tass.be 149:5f4cb161cec3 147 insert = create_node(tree, key, USE_PICO_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 148
TASS Belgium NV 131:4758606c9316 149 if(!insert)
TASS Belgium NV 131:4758606c9316 150 {
TASS Belgium NV 131:4758606c9316 151 pico_err = PICO_ERR_ENOMEM;
TASS Belgium NV 131:4758606c9316 152 /* to let the user know that it couldn't insert */
TASS Belgium NV 131:4758606c9316 153 return (void *)&LEAF;
TASS Belgium NV 131:4758606c9316 154 }
TASS Belgium NV 131:4758606c9316 155 }
tass 68:0847e35d08a6 156
TASS Belgium NV 131:4758606c9316 157 /* search for the place to insert the new node */
TASS Belgium NV 131:4758606c9316 158 while(IS_NOT_LEAF(temp))
TASS Belgium NV 131:4758606c9316 159 {
TASS Belgium NV 131:4758606c9316 160 last_node = temp;
TASS Belgium NV 131:4758606c9316 161 result = tree->compare(insert->keyValue, temp->keyValue);
tass 68:0847e35d08a6 162
tass picotcp@tass.be 149:5f4cb161cec3 163 temp = (result < 0) ? (temp->leftChild) : (temp->rightChild);
TASS Belgium NV 131:4758606c9316 164 }
TASS Belgium NV 131:4758606c9316 165 /* make the needed connections */
TASS Belgium NV 131:4758606c9316 166 insert->parent = last_node;
tass 68:0847e35d08a6 167
TASS Belgium NV 131:4758606c9316 168 if(IS_LEAF(last_node))
TASS Belgium NV 131:4758606c9316 169 tree->root = insert;
TASS Belgium NV 131:4758606c9316 170 else{
TASS Belgium NV 131:4758606c9316 171 result = tree->compare(insert->keyValue, last_node->keyValue);
TASS Belgium NV 131:4758606c9316 172 if(result < 0)
TASS Belgium NV 131:4758606c9316 173 last_node->leftChild = insert;
TASS Belgium NV 131:4758606c9316 174 else
TASS Belgium NV 131:4758606c9316 175 last_node->rightChild = insert;
TASS Belgium NV 131:4758606c9316 176 }
tass 68:0847e35d08a6 177
TASS Belgium NV 131:4758606c9316 178 /* fix colour issues */
TASS Belgium NV 131:4758606c9316 179 fix_insert_collisions(tree, insert);
tass 68:0847e35d08a6 180
TASS Belgium NV 131:4758606c9316 181 return NULL;
tass 68:0847e35d08a6 182 }
tass 68:0847e35d08a6 183
TASS Belgium NV 131:4758606c9316 184 struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 185 {
TASS Belgium NV 131:4758606c9316 186 struct pico_tree_node *found;
tass 68:0847e35d08a6 187
TASS Belgium NV 131:4758606c9316 188 found = tree->root;
tass 68:0847e35d08a6 189
TASS Belgium NV 131:4758606c9316 190 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 191 {
TASS Belgium NV 131:4758606c9316 192 int result;
TASS Belgium NV 131:4758606c9316 193 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 194 if(result == 0)
TASS Belgium NV 131:4758606c9316 195 {
TASS Belgium NV 131:4758606c9316 196 return found;
TASS Belgium NV 131:4758606c9316 197 }
TASS Belgium NV 131:4758606c9316 198 else if(result < 0)
TASS Belgium NV 131:4758606c9316 199 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 200 else
TASS Belgium NV 131:4758606c9316 201 found = found->leftChild;
TASS Belgium NV 131:4758606c9316 202 }
TASS Belgium NV 131:4758606c9316 203 return NULL;
tass 68:0847e35d08a6 204 }
tass 68:0847e35d08a6 205
TASS Belgium NV 131:4758606c9316 206 void *pico_tree_findKey(struct pico_tree *tree, void *key)
tass 68:0847e35d08a6 207 {
TASS Belgium NV 131:4758606c9316 208 struct pico_tree_node *found;
tass 68:0847e35d08a6 209
tass 68:0847e35d08a6 210
TASS Belgium NV 131:4758606c9316 211 found = tree->root;
TASS Belgium NV 131:4758606c9316 212 while(IS_NOT_LEAF(found))
TASS Belgium NV 131:4758606c9316 213 {
TASS Belgium NV 131:4758606c9316 214 int result;
tass 68:0847e35d08a6 215
TASS Belgium NV 131:4758606c9316 216 result = tree->compare(found->keyValue, key);
TASS Belgium NV 131:4758606c9316 217 if(result == 0)
TASS Belgium NV 131:4758606c9316 218 return found->keyValue;
TASS Belgium NV 131:4758606c9316 219 else if(result < 0)
TASS Belgium NV 131:4758606c9316 220 found = found->rightChild;
TASS Belgium NV 131:4758606c9316 221 else
TASS Belgium NV 131:4758606c9316 222 found = found->leftChild;
tass 68:0847e35d08a6 223
TASS Belgium NV 131:4758606c9316 224 }
TASS Belgium NV 131:4758606c9316 225 return NULL;
tass 68:0847e35d08a6 226 }
tass 68:0847e35d08a6 227
TASS Belgium NV 131:4758606c9316 228 void *pico_tree_first(struct pico_tree *tree)
tass 68:0847e35d08a6 229 {
TASS Belgium NV 131:4758606c9316 230 return pico_tree_firstNode(tree->root)->keyValue;
tass 68:0847e35d08a6 231 }
tass 68:0847e35d08a6 232
TASS Belgium NV 131:4758606c9316 233 void *pico_tree_last(struct pico_tree *tree)
tass 68:0847e35d08a6 234 {
TASS Belgium NV 131:4758606c9316 235 return pico_tree_lastNode(tree->root)->keyValue;
tass 68:0847e35d08a6 236 }
tass 68:0847e35d08a6 237
tass picotcp@tass.be 149:5f4cb161cec3 238 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 239 {
tass picotcp@tass.be 149:5f4cb161cec3 240 struct pico_tree_node *min;
tass picotcp@tass.be 149:5f4cb161cec3 241 struct pico_tree_node *ltemp = d;
tass picotcp@tass.be 149:5f4cb161cec3 242 uint8_t nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 243 min = pico_tree_firstNode(d->rightChild);
tass picotcp@tass.be 149:5f4cb161cec3 244 nodeColor = min->color;
tass 68:0847e35d08a6 245
tass picotcp@tass.be 149:5f4cb161cec3 246 *temp = min->rightChild;
tass picotcp@tass.be 149:5f4cb161cec3 247 if(min->parent == ltemp && IS_NOT_LEAF(*temp))
tass picotcp@tass.be 149:5f4cb161cec3 248 (*temp)->parent = min;
tass picotcp@tass.be 149:5f4cb161cec3 249 else{
tass picotcp@tass.be 149:5f4cb161cec3 250 switchNodes(tree, min, min->rightChild);
tass picotcp@tass.be 149:5f4cb161cec3 251 min->rightChild = ltemp->rightChild;
tass picotcp@tass.be 149:5f4cb161cec3 252 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
tass picotcp@tass.be 149:5f4cb161cec3 253 }
tass picotcp@tass.be 149:5f4cb161cec3 254
tass picotcp@tass.be 149:5f4cb161cec3 255 switchNodes(tree, ltemp, min);
tass picotcp@tass.be 149:5f4cb161cec3 256 min->leftChild = ltemp->leftChild;
tass 68:0847e35d08a6 257
tass picotcp@tass.be 149:5f4cb161cec3 258 if(IS_NOT_LEAF(min->leftChild))
tass picotcp@tass.be 149:5f4cb161cec3 259 min->leftChild->parent = min;
tass 68:0847e35d08a6 260
tass picotcp@tass.be 149:5f4cb161cec3 261 min->color = ltemp->color;
tass picotcp@tass.be 149:5f4cb161cec3 262 return nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 263 }
tass 68:0847e35d08a6 264
tass picotcp@tass.be 149:5f4cb161cec3 265 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 266 {
tass picotcp@tass.be 149:5f4cb161cec3 267 struct pico_tree_node *ltemp = delete;
tass picotcp@tass.be 149:5f4cb161cec3 268 uint8_t nodeColor = delete->color;
TASS Belgium NV 131:4758606c9316 269 if(IS_LEAF(delete->leftChild))
TASS Belgium NV 131:4758606c9316 270 {
tass picotcp@tass.be 149:5f4cb161cec3 271 *temp = ltemp->rightChild;
TASS Belgium NV 131:4758606c9316 272 switchNodes(tree, ltemp, ltemp->rightChild);
TASS Belgium NV 131:4758606c9316 273 }
TASS Belgium NV 131:4758606c9316 274 else
tass 68:0847e35d08a6 275 if(IS_LEAF(delete->rightChild))
tass 68:0847e35d08a6 276 {
TASS Belgium NV 131:4758606c9316 277 struct pico_tree_node *_ltemp = delete;
tass picotcp@tass.be 149:5f4cb161cec3 278 *temp = _ltemp->leftChild;
TASS Belgium NV 131:4758606c9316 279 switchNodes(tree, _ltemp, _ltemp->leftChild);
tass 68:0847e35d08a6 280 }
tass 68:0847e35d08a6 281 else{
tass picotcp@tass.be 149:5f4cb161cec3 282 nodeColor = pico_tree_delete_node(tree, delete, temp);
tass picotcp@tass.be 149:5f4cb161cec3 283 }
tass picotcp@tass.be 149:5f4cb161cec3 284
tass picotcp@tass.be 149:5f4cb161cec3 285 return nodeColor;
tass picotcp@tass.be 149:5f4cb161cec3 286
tass picotcp@tass.be 149:5f4cb161cec3 287 }
tass picotcp@tass.be 149:5f4cb161cec3 288
tass picotcp@tass.be 149:5f4cb161cec3 289 /* 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 290 * 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 291 * which are used for the pico stack in general.
tass picotcp@tass.be 149:5f4cb161cec3 292 * Therefore the following wrapper for pico_tree_delete is created.
tass picotcp@tass.be 149:5f4cb161cec3 293 * The actual implementation can be found in pico_tree_delete_implementation.
tass picotcp@tass.be 149:5f4cb161cec3 294 */
tass picotcp@tass.be 149:5f4cb161cec3 295 void *pico_tree_delete(struct pico_tree *tree, void *key)
tass picotcp@tass.be 149:5f4cb161cec3 296 {
tass picotcp@tass.be 149:5f4cb161cec3 297 return pico_tree_delete_implementation(tree, key, USE_PICO_ZALLOC);
tass picotcp@tass.be 149:5f4cb161cec3 298 }
tass 68:0847e35d08a6 299
tass 152:a3d286bf94e5 300 static inline void if_nodecolor_black_fix_collisions(struct pico_tree *tree, struct pico_tree_node *temp, uint8_t nodeColor)
tass 152:a3d286bf94e5 301 {
tass 152:a3d286bf94e5 302 /* deleted node is black, this will mess up the black path property */
tass 152:a3d286bf94e5 303 if(nodeColor == BLACK)
tass 152:a3d286bf94e5 304 fix_delete_collisions(tree, temp);
tass 152:a3d286bf94e5 305 }
tass 152:a3d286bf94e5 306
tass picotcp@tass.be 149:5f4cb161cec3 307 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator)
tass picotcp@tass.be 149:5f4cb161cec3 308 {
tass picotcp@tass.be 149:5f4cb161cec3 309 struct pico_tree_node *temp;
tass picotcp@tass.be 149:5f4cb161cec3 310 uint8_t nodeColor; /* keeps the color of the node to be deleted */
tass picotcp@tass.be 149:5f4cb161cec3 311 void *lkey; /* keeps a copy of the key which will be removed */
tass picotcp@tass.be 149:5f4cb161cec3 312 struct pico_tree_node *delete; /* keeps a copy of the node to be extracted */
tass picotcp@tass.be 149:5f4cb161cec3 313 if (!key)
tass picotcp@tass.be 149:5f4cb161cec3 314 return NULL;
tass picotcp@tass.be 149:5f4cb161cec3 315 delete = pico_tree_findNode(tree, key);
TASS Belgium NV 131:4758606c9316 316
tass picotcp@tass.be 149:5f4cb161cec3 317 /* this key isn't in the tree, bail out */
tass 152:a3d286bf94e5 318 if(!delete)
tass picotcp@tass.be 149:5f4cb161cec3 319 return NULL;
tass 152:a3d286bf94e5 320
tass picotcp@tass.be 149:5f4cb161cec3 321 lkey = delete->keyValue;
tass picotcp@tass.be 149:5f4cb161cec3 322 nodeColor = pico_tree_delete_check_switch(tree, delete, &temp);
tass 68:0847e35d08a6 323
tass 152:a3d286bf94e5 324 if_nodecolor_black_fix_collisions(tree, temp, nodeColor);
tass 68:0847e35d08a6 325
tass picotcp@tass.be 149:5f4cb161cec3 326 if(allocator == USE_PICO_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 327 PICO_FREE(delete);
tass 68:0847e35d08a6 328
tass picotcp@tass.be 149:5f4cb161cec3 329 #ifdef PICO_SUPPORT_MM
tass picotcp@tass.be 149:5f4cb161cec3 330 else
tass picotcp@tass.be 149:5f4cb161cec3 331 pico_mem_page0_free(delete);
tass picotcp@tass.be 149:5f4cb161cec3 332 #endif
TASS Belgium NV 131:4758606c9316 333 return lkey;
tass 68:0847e35d08a6 334 }
tass 68:0847e35d08a6 335
TASS Belgium NV 131:4758606c9316 336 int pico_tree_empty(struct pico_tree *tree)
tass 68:0847e35d08a6 337 {
TASS Belgium NV 131:4758606c9316 338 return (!tree->root || IS_LEAF(tree->root));
tass 68:0847e35d08a6 339 }
tass 68:0847e35d08a6 340
tass 68:0847e35d08a6 341 /*
tass 68:0847e35d08a6 342 * Private functions
tass 68:0847e35d08a6 343 */
TASS Belgium NV 131:4758606c9316 344 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node)
tass 68:0847e35d08a6 345 {
TASS Belgium NV 131:4758606c9316 346 struct pico_tree_node*temp;
tass 68:0847e35d08a6 347
TASS Belgium NV 131:4758606c9316 348 temp = node->rightChild;
tass 68:0847e35d08a6 349
TASS Belgium NV 131:4758606c9316 350 if(temp == &LEAF) return;
tass 68:0847e35d08a6 351
TASS Belgium NV 131:4758606c9316 352 node->rightChild = temp->leftChild;
tass 68:0847e35d08a6 353
TASS Belgium NV 131:4758606c9316 354 if(IS_NOT_LEAF(temp->leftChild))
TASS Belgium NV 131:4758606c9316 355 temp->leftChild->parent = node;
tass 68:0847e35d08a6 356
TASS Belgium NV 131:4758606c9316 357 temp->parent = node->parent;
tass 68:0847e35d08a6 358
TASS Belgium NV 131:4758606c9316 359 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 360 tree->root = temp;
TASS Belgium NV 131:4758606c9316 361 else
tass 68:0847e35d08a6 362 if(node == node->parent->leftChild)
TASS Belgium NV 131:4758606c9316 363 node->parent->leftChild = temp;
tass 68:0847e35d08a6 364 else
TASS Belgium NV 131:4758606c9316 365 node->parent->rightChild = temp;
tass 68:0847e35d08a6 366
TASS Belgium NV 131:4758606c9316 367 temp->leftChild = node;
TASS Belgium NV 131:4758606c9316 368 node->parent = temp;
tass 68:0847e35d08a6 369 }
tass 68:0847e35d08a6 370
tass 68:0847e35d08a6 371
TASS Belgium NV 131:4758606c9316 372 static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 373 {
TASS Belgium NV 131:4758606c9316 374 struct pico_tree_node*temp;
tass 68:0847e35d08a6 375
TASS Belgium NV 131:4758606c9316 376 temp = node->leftChild;
TASS Belgium NV 131:4758606c9316 377 node->leftChild = temp->rightChild;
tass 68:0847e35d08a6 378
TASS Belgium NV 131:4758606c9316 379 if(temp == &LEAF) return;
tass 68:0847e35d08a6 380
TASS Belgium NV 131:4758606c9316 381 if(IS_NOT_LEAF(temp->rightChild))
TASS Belgium NV 131:4758606c9316 382 temp->rightChild->parent = node;
tass 68:0847e35d08a6 383
TASS Belgium NV 131:4758606c9316 384 temp->parent = node->parent;
tass 68:0847e35d08a6 385
TASS Belgium NV 131:4758606c9316 386 if(IS_LEAF(node->parent))
TASS Belgium NV 131:4758606c9316 387 tree->root = temp;
TASS Belgium NV 131:4758606c9316 388 else
tass 68:0847e35d08a6 389 if(node == node->parent->rightChild)
TASS Belgium NV 131:4758606c9316 390 node->parent->rightChild = temp;
tass 68:0847e35d08a6 391 else
TASS Belgium NV 131:4758606c9316 392 node->parent->leftChild = temp;
tass 68:0847e35d08a6 393
TASS Belgium NV 131:4758606c9316 394 temp->rightChild = node;
TASS Belgium NV 131:4758606c9316 395 node->parent = temp;
TASS Belgium NV 131:4758606c9316 396 return;
tass 68:0847e35d08a6 397 }
tass 68:0847e35d08a6 398
tass picotcp@tass.be 149:5f4cb161cec3 399 static struct pico_tree_node *create_node(struct pico_tree *tree, void*key, uint8_t allocator)
tass 68:0847e35d08a6 400 {
tass picotcp@tass.be 149:5f4cb161cec3 401 struct pico_tree_node *temp = NULL;
TASS Belgium NV 131:4758606c9316 402 IGNORE_PARAMETER(tree);
tass picotcp@tass.be 149:5f4cb161cec3 403 if(allocator == USE_PICO_ZALLOC)
tass picotcp@tass.be 149:5f4cb161cec3 404 temp = (struct pico_tree_node *)PICO_ZALLOC(sizeof(struct pico_tree_node));
tass picotcp@tass.be 149:5f4cb161cec3 405
tass picotcp@tass.be 149:5f4cb161cec3 406 #ifdef PICO_SUPPORT_MM
tass picotcp@tass.be 149:5f4cb161cec3 407 else
tass picotcp@tass.be 149:5f4cb161cec3 408 temp = (struct pico_tree_node *)pico_mem_page0_zalloc(sizeof(struct pico_tree_node));
tass picotcp@tass.be 149:5f4cb161cec3 409 #endif
tass 68:0847e35d08a6 410
TASS Belgium NV 131:4758606c9316 411 if(!temp)
TASS Belgium NV 131:4758606c9316 412 return NULL;
tass 68:0847e35d08a6 413
TASS Belgium NV 131:4758606c9316 414 temp->keyValue = key;
TASS Belgium NV 131:4758606c9316 415 temp->parent = &LEAF;
TASS Belgium NV 131:4758606c9316 416 temp->leftChild = &LEAF;
TASS Belgium NV 131:4758606c9316 417 temp->rightChild = &LEAF;
TASS Belgium NV 131:4758606c9316 418 /* by default every new node is red */
TASS Belgium NV 131:4758606c9316 419 temp->color = RED;
TASS Belgium NV 131:4758606c9316 420 return temp;
tass 68:0847e35d08a6 421 }
tass 68:0847e35d08a6 422
tass 68:0847e35d08a6 423 /*
tass 68:0847e35d08a6 424 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 425 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 426 */
TASS Belgium NV 131:4758606c9316 427 static void fix_insert_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->parent->color == RED && IS_NOT_LEAF(GRANPA(node)))
TASS Belgium NV 131:4758606c9316 432 {
TASS Belgium NV 131:4758606c9316 433 if(AM_I_RIGHT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 434 {
TASS Belgium NV 131:4758606c9316 435 temp = GRANPA(node)->leftChild;
TASS Belgium NV 131:4758606c9316 436 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 437 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 438 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 439 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 440 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 441 }
TASS Belgium NV 131:4758606c9316 442 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 443 if(node == node->parent->leftChild) {
TASS Belgium NV 131:4758606c9316 444 node = node->parent;
TASS Belgium NV 131:4758606c9316 445 rotateToRight(tree, node);
TASS Belgium NV 131:4758606c9316 446 }
tass 68:0847e35d08a6 447
TASS Belgium NV 131:4758606c9316 448 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 449 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 450 rotateToLeft(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 451 }
TASS Belgium NV 131:4758606c9316 452 }
TASS Belgium NV 131:4758606c9316 453 else if(AM_I_LEFT_CHILD(node->parent))
TASS Belgium NV 131:4758606c9316 454 {
TASS Belgium NV 131:4758606c9316 455 temp = GRANPA(node)->rightChild;
TASS Belgium NV 131:4758606c9316 456 if(temp->color == RED) {
TASS Belgium NV 131:4758606c9316 457 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 458 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 459 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 460 node = GRANPA(node);
TASS Belgium NV 131:4758606c9316 461 }
TASS Belgium NV 131:4758606c9316 462 else if(temp->color == BLACK) {
TASS Belgium NV 131:4758606c9316 463 if(AM_I_RIGHT_CHILD(node)) {
TASS Belgium NV 131:4758606c9316 464 node = node->parent;
TASS Belgium NV 131:4758606c9316 465 rotateToLeft(tree, node);
TASS Belgium NV 131:4758606c9316 466 }
TASS Belgium NV 131:4758606c9316 467
TASS Belgium NV 131:4758606c9316 468 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 469 GRANPA(node)->color = RED;
TASS Belgium NV 131:4758606c9316 470 rotateToRight(tree, GRANPA(node));
TASS Belgium NV 131:4758606c9316 471 }
TASS Belgium NV 131:4758606c9316 472 }
tass 68:0847e35d08a6 473 }
TASS Belgium NV 131:4758606c9316 474 /* make sure that the root of the tree stays black */
TASS Belgium NV 131:4758606c9316 475 tree->root->color = BLACK;
tass 68:0847e35d08a6 476 }
tass 68:0847e35d08a6 477
TASS Belgium NV 131:4758606c9316 478 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB)
tass 68:0847e35d08a6 479 {
tass 68:0847e35d08a6 480
TASS Belgium NV 131:4758606c9316 481 if(IS_LEAF(nodeA->parent))
TASS Belgium NV 131:4758606c9316 482 tree->root = nodeB;
tass 68:0847e35d08a6 483 else
TASS Belgium NV 131:4758606c9316 484 if(IS_NOT_LEAF(nodeA))
TASS Belgium NV 131:4758606c9316 485 {
TASS Belgium NV 131:4758606c9316 486 if(AM_I_LEFT_CHILD(nodeA))
TASS Belgium NV 131:4758606c9316 487 nodeA->parent->leftChild = nodeB;
TASS Belgium NV 131:4758606c9316 488 else
TASS Belgium NV 131:4758606c9316 489 nodeA->parent->rightChild = nodeB;
TASS Belgium NV 131:4758606c9316 490 }
tass 68:0847e35d08a6 491
TASS Belgium NV 131:4758606c9316 492 if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent;
tass 68:0847e35d08a6 493
tass 68:0847e35d08a6 494 }
tass 68:0847e35d08a6 495
tass 68:0847e35d08a6 496 /*
tass 68:0847e35d08a6 497 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 498 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 499 * In this case the function fixes the constant black path property.
tass 68:0847e35d08a6 500 */
TASS Belgium NV 131:4758606c9316 501 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node)
tass 68:0847e35d08a6 502 {
TASS Belgium NV 131:4758606c9316 503 struct pico_tree_node*temp;
TASS Belgium NV 131:4758606c9316 504
TASS Belgium NV 131:4758606c9316 505 while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
TASS Belgium NV 131:4758606c9316 506 {
TASS Belgium NV 131:4758606c9316 507 if(AM_I_LEFT_CHILD(node)) {
tass 68:0847e35d08a6 508
TASS Belgium NV 131:4758606c9316 509 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 510 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 511 {
TASS Belgium NV 131:4758606c9316 512 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 513 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 514 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 515 temp = node->parent->rightChild;
TASS Belgium NV 131:4758606c9316 516 }
TASS Belgium NV 131:4758606c9316 517
TASS Belgium NV 131:4758606c9316 518 if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 519 {
TASS Belgium NV 131:4758606c9316 520 temp->color = RED;
TASS Belgium NV 131:4758606c9316 521 node = node->parent;
TASS Belgium NV 131:4758606c9316 522 }
TASS Belgium NV 131:4758606c9316 523 else
TASS Belgium NV 131:4758606c9316 524 {
TASS Belgium NV 131:4758606c9316 525 if(temp->rightChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 526 {
TASS Belgium NV 131:4758606c9316 527 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 528 temp->color = RED;
TASS Belgium NV 131:4758606c9316 529 rotateToRight(tree, temp);
TASS Belgium NV 131:4758606c9316 530 temp = temp->parent->rightChild;
TASS Belgium NV 131:4758606c9316 531 }
tass 68:0847e35d08a6 532
TASS Belgium NV 131:4758606c9316 533 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 534 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 535 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 536 rotateToLeft(tree, node->parent);
TASS Belgium NV 131:4758606c9316 537 node = tree->root;
TASS Belgium NV 131:4758606c9316 538 }
TASS Belgium NV 131:4758606c9316 539 }
TASS Belgium NV 131:4758606c9316 540 else{
TASS Belgium NV 131:4758606c9316 541 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 542 if(temp->color == RED)
TASS Belgium NV 131:4758606c9316 543 {
TASS Belgium NV 131:4758606c9316 544 temp->color = BLACK;
TASS Belgium NV 131:4758606c9316 545 node->parent->color = RED;
TASS Belgium NV 131:4758606c9316 546 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 547 temp = node->parent->leftChild;
TASS Belgium NV 131:4758606c9316 548 }
TASS Belgium NV 131:4758606c9316 549
TASS Belgium NV 131:4758606c9316 550 if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 551 {
TASS Belgium NV 131:4758606c9316 552 temp->color = RED;
TASS Belgium NV 131:4758606c9316 553 node = node->parent;
TASS Belgium NV 131:4758606c9316 554 }
TASS Belgium NV 131:4758606c9316 555 else{
TASS Belgium NV 131:4758606c9316 556 if(temp->leftChild->color == BLACK)
TASS Belgium NV 131:4758606c9316 557 {
TASS Belgium NV 131:4758606c9316 558 temp->rightChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 559 temp->color = RED;
TASS Belgium NV 131:4758606c9316 560 rotateToLeft(tree, temp);
TASS Belgium NV 131:4758606c9316 561 temp = temp->parent->leftChild;
TASS Belgium NV 131:4758606c9316 562 }
TASS Belgium NV 131:4758606c9316 563
TASS Belgium NV 131:4758606c9316 564 temp->color = node->parent->color;
TASS Belgium NV 131:4758606c9316 565 node->parent->color = BLACK;
TASS Belgium NV 131:4758606c9316 566 temp->leftChild->color = BLACK;
TASS Belgium NV 131:4758606c9316 567 rotateToRight(tree, node->parent);
TASS Belgium NV 131:4758606c9316 568 node = tree->root;
TASS Belgium NV 131:4758606c9316 569 }
TASS Belgium NV 131:4758606c9316 570 }
tass 68:0847e35d08a6 571 }
TASS Belgium NV 131:4758606c9316 572 node->color = BLACK;
tass 68:0847e35d08a6 573 }