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 RTOSgeneric mbed Ethernet driverhigh performance NXP LPC1768 specific Ethernet driverMulti-threading support for mbed RTOSBerkeley sockets and integration with the New Socket APIFork of the apps running on top of the New Socket APIScheduling 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.
Diff: stack/pico_tree.c
- Revision:
- 51:ab4529a384a6
- Parent:
- 48:40fc4462265c
- Child:
- 63:97f481e33cb2
--- a/stack/pico_tree.c Tue Aug 06 08:04:03 2013 +0000 +++ b/stack/pico_tree.c Mon Sep 02 08:02:21 2013 +0000 @@ -7,8 +7,9 @@ #include "pico_tree.h" #include "pico_config.h" +#include "pico_protocol.h" -#define RED 0 +#define RED 0 #define BLACK 1 // By default the null leafs are black @@ -44,81 +45,89 @@ struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node * node) { - while(IS_NOT_LEAF(node->leftChild)) - node = node->leftChild; - return node; + while(IS_NOT_LEAF(node->leftChild)) + node = node->leftChild; + return node; } struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node) { - while(IS_NOT_LEAF(node->rightChild)) - node = node->rightChild; - return node; + while(IS_NOT_LEAF(node->rightChild)) + node = node->rightChild; + return node; } struct pico_tree_node * pico_tree_next(struct pico_tree_node * node) { - if(IS_NOT_LEAF(node->rightChild)) - { - node = node->rightChild; - while(IS_NOT_LEAF(node->leftChild)) - node = node->leftChild; - } - else - { - if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node)) - node = node->parent; - else { - while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) - node = node->parent; + if(IS_NOT_LEAF(node->rightChild)) + { + node = node->rightChild; + while(IS_NOT_LEAF(node->leftChild)) + node = node->leftChild; + } + else + { + if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node)) + node = node->parent; + else { + while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) + node = node->parent; - node = node->parent; - } - } - return node; + node = node->parent; + } + } + return node; } struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node) { - if (IS_NOT_LEAF(node->leftChild)) { - node = node->leftChild; - while (IS_NOT_LEAF(node->rightChild)) - node = node->rightChild; + if (IS_NOT_LEAF(node->leftChild)) { + node = node->leftChild; + while (IS_NOT_LEAF(node->rightChild)) + node = node->rightChild; } else { - if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) - node = node->parent; - else { - while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node)) - node = node->parent; + if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) + node = node->parent; + else { + while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node)) + node = node->parent; - node = node->parent; - } + node = node->parent; + } } - return node; + return node; } void * pico_tree_insert(struct pico_tree* tree, void * key){ - struct pico_tree_node * last_node = INIT_LEAF; + struct pico_tree_node * last_node = INIT_LEAF; struct pico_tree_node * temp = tree->root; struct pico_tree_node * insert; void * LocalKey; int result = 0; - LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL); - // if node already in, bail out + LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL); + // if node already in, bail out if(LocalKey) - return LocalKey; + return LocalKey; else - insert = create_node(tree,key); + { + insert = create_node(tree,key); + if(!insert) + { + pico_err = PICO_ERR_ENOMEM; + // to let the user know that it couldn't insert + return (void *)&LEAF; + } + } // search for the place to insert the new node while(IS_NOT_LEAF(temp)) { - last_node = temp; - result = tree->compare(insert->keyValue,temp->keyValue); + last_node = temp; + result = tree->compare(insert->keyValue,temp->keyValue); - temp = (result < 0 ? temp->leftChild : temp->rightChild); + temp = (result < 0 ? temp->leftChild : temp->rightChild); } // make the needed connections @@ -127,7 +136,7 @@ if(IS_LEAF(last_node)) tree->root = insert; else{ - result = tree->compare(insert->keyValue,last_node->keyValue); + result = tree->compare(insert->keyValue,last_node->keyValue); if(result < 0) last_node->leftChild = insert; else @@ -137,32 +146,32 @@ // fix colour issues fix_insert_collisions(tree, insert); - return NULL; + return NULL; } struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key) { - struct pico_tree_node *found; + struct pico_tree_node *found; - found = tree->root; + found = tree->root; - while(IS_NOT_LEAF(found)) - { - int result; - result = tree->compare(found->keyValue, key); - if(result == 0) - { - return found; - } - else if(result < 0) - found = found->rightChild; - else - found = found->leftChild; - } + while(IS_NOT_LEAF(found)) + { + int result; + result = tree->compare(found->keyValue, key); + if(result == 0) + { + return found; + } + else if(result < 0) + found = found->rightChild; + else + found = found->leftChild; + } - return NULL; + return NULL; } void * pico_tree_findKey(struct pico_tree * tree, void * key) @@ -174,12 +183,12 @@ while(IS_NOT_LEAF(found)) { - int result; + int result; - result = tree->compare(found->keyValue, key); - if(result == 0) - return found->keyValue; - else if(result < 0) + result = tree->compare(found->keyValue, key); + if(result == 0) + return found->keyValue; + else if(result < 0) found = found->rightChild; else found = found->leftChild; @@ -191,24 +200,24 @@ void * pico_tree_first(struct pico_tree * tree) { - return pico_tree_firstNode(tree->root)->keyValue; + return pico_tree_firstNode(tree->root)->keyValue; } void * pico_tree_last(struct pico_tree * tree) { - return pico_tree_lastNode(tree->root)->keyValue; + return pico_tree_lastNode(tree->root)->keyValue; } void * pico_tree_delete(struct pico_tree * tree, void * key){ - uint8_t nodeColor; // keeps the color of the node to be deleted + uint8_t nodeColor; // keeps the color of the node to be deleted void * lkey; // keeps a copy of the key which will be removed - struct pico_tree_node * delete; // keeps a copy of the node to be extracted - struct pico_tree_node * temp; // temporary - struct pico_tree_node * ltemp; // used for switching nodes, as a copy + struct pico_tree_node * delete; // keeps a copy of the node to be extracted + struct pico_tree_node * temp; // temporary + struct pico_tree_node * ltemp; // used for switching nodes, as a copy - delete = pico_tree_findNode(tree, key); - ltemp = delete; + delete = pico_tree_findNode(tree, key); + ltemp = delete; // this key isn't in the tree, bail out if(!delete) @@ -225,22 +234,22 @@ else if(IS_LEAF(delete->rightChild)) { - struct pico_tree_node * ltemp = delete; - temp = ltemp->leftChild; - switchNodes(tree, ltemp, ltemp->leftChild); + struct pico_tree_node * _ltemp = delete; + temp = _ltemp->leftChild; + switchNodes(tree, _ltemp, _ltemp->leftChild); } else{ - struct pico_tree_node * min; - min = pico_tree_firstNode(delete->rightChild); + struct pico_tree_node * min; + min = pico_tree_firstNode(delete->rightChild); nodeColor = min->color; temp = min->rightChild; if(min->parent == ltemp && IS_NOT_LEAF(temp)) - temp->parent = min; + temp->parent = min; else{ - switchNodes(tree, min, min->rightChild); - min->rightChild = ltemp->rightChild; - if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min; + switchNodes(tree, min, min->rightChild); + min->rightChild = ltemp->rightChild; + if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min; } switchNodes(tree, ltemp, min); min->leftChild = ltemp->leftChild; @@ -259,7 +268,7 @@ int pico_tree_empty(struct pico_tree * tree) { - return (!tree->root || IS_LEAF(tree->root)); + return (!tree->root || IS_LEAF(tree->root)); } /* @@ -284,9 +293,9 @@ tree->root = temp; else if(node == node->parent->leftChild) - node->parent->leftChild = temp; + node->parent->leftChild = temp; else - node->parent->rightChild = temp; + node->parent->rightChild = temp; temp->leftChild = node; node->parent = temp; @@ -323,10 +332,11 @@ static struct pico_tree_node * create_node(struct pico_tree * tree, void* key) { struct pico_tree_node *temp; + IGNORE_PARAMETER(tree); temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node)); if(!temp) - return NULL; + return NULL; temp->keyValue = key; temp->parent = &LEAF; @@ -347,43 +357,43 @@ while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)) ) { - if(AM_I_RIGHT_CHILD(node->parent)) - { - temp = GRANPA(node)->leftChild; - if(temp->color == RED){ - node->parent->color = BLACK; - temp->color = BLACK; - GRANPA(node)->color = RED; - node = GRANPA(node); - } - else if(temp->color == BLACK){ - if(node == node->parent->leftChild){ - node = node->parent; - rotateToRight(tree, node); - } - node->parent->color = BLACK; - GRANPA(node)->color = RED; - rotateToLeft(tree, GRANPA(node)); - } - } - else if(AM_I_LEFT_CHILD(node->parent)) + if(AM_I_RIGHT_CHILD(node->parent)) + { + temp = GRANPA(node)->leftChild; + if(temp->color == RED){ + node->parent->color = BLACK; + temp->color = BLACK; + GRANPA(node)->color = RED; + node = GRANPA(node); + } + else if(temp->color == BLACK){ + if(node == node->parent->leftChild){ + node = node->parent; + rotateToRight(tree, node); + } + node->parent->color = BLACK; + GRANPA(node)->color = RED; + rotateToLeft(tree, GRANPA(node)); + } + } + else if(AM_I_LEFT_CHILD(node->parent)) { temp = GRANPA(node)->rightChild; if(temp->color == RED){ - node->parent->color = BLACK; - temp->color = BLACK; - GRANPA(node)->color = RED; - node = GRANPA(node); + node->parent->color = BLACK; + temp->color = BLACK; + GRANPA(node)->color = RED; + node = GRANPA(node); } else if(temp->color == BLACK){ - if(AM_I_RIGHT_CHILD(node)){ - node = node->parent; - rotateToLeft(tree, node); - } - node->parent->color = BLACK; - GRANPA(node)->color = RED; - rotateToRight(tree, GRANPA(node)); - } + if(AM_I_RIGHT_CHILD(node)){ + node = node->parent; + rotateToLeft(tree, node); + } + node->parent->color = BLACK; + GRANPA(node)->color = RED; + rotateToRight(tree, GRANPA(node)); + } } } @@ -394,11 +404,11 @@ static void switchNodes(struct pico_tree* tree, struct pico_tree_node* nodeA, struct pico_tree_node* nodeB) { - if(IS_LEAF(nodeA->parent)) + if(IS_LEAF(nodeA->parent)) tree->root = nodeB; else if(IS_NOT_LEAF(nodeA)) - { + { if(AM_I_LEFT_CHILD(nodeA)) nodeA->parent->leftChild = nodeB; else @@ -420,64 +430,64 @@ while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node)) { - if(AM_I_LEFT_CHILD(node)){ + if(AM_I_LEFT_CHILD(node)){ temp = node->parent->rightChild; if(temp->color == RED) { - temp->color = BLACK; - node->parent->color = RED; - rotateToLeft(tree, node->parent); - temp = node->parent->rightChild; + temp->color = BLACK; + node->parent->color = RED; + rotateToLeft(tree, node->parent); + temp = node->parent->rightChild; } if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK) { - temp->color = RED; - node = node->parent; + temp->color = RED; + node = node->parent; } else { - if(temp->rightChild->color == BLACK) - { - temp->leftChild->color = BLACK; - temp->color = RED; - rotateToRight(tree, temp); - temp = temp->parent->rightChild; - } - temp->color = node->parent->color; - node->parent->color = BLACK; - temp->rightChild->color = BLACK; - rotateToLeft(tree, node->parent); - node = tree->root; + if(temp->rightChild->color == BLACK) + { + temp->leftChild->color = BLACK; + temp->color = RED; + rotateToRight(tree, temp); + temp = temp->parent->rightChild; + } + temp->color = node->parent->color; + node->parent->color = BLACK; + temp->rightChild->color = BLACK; + rotateToLeft(tree, node->parent); + node = tree->root; } } else{ temp = node->parent->leftChild; if(temp->color == RED) { - temp->color = BLACK; - node->parent->color = RED; - rotateToRight(tree, node->parent); - temp = node->parent->leftChild; + temp->color = BLACK; + node->parent->color = RED; + rotateToRight(tree, node->parent); + temp = node->parent->leftChild; } if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK) { - temp->color = RED; - node = node->parent; + temp->color = RED; + node = node->parent; } else{ - if(temp->leftChild->color == BLACK) - { - temp->rightChild->color = BLACK; - temp->color = RED; - rotateToLeft(tree, temp); - temp = temp->parent->leftChild; - } - temp->color = node->parent->color; - node->parent->color = BLACK; - temp->leftChild->color = BLACK; - rotateToRight(tree, node->parent); - node = tree->root; + if(temp->leftChild->color == BLACK) + { + temp->rightChild->color = BLACK; + temp->color = RED; + rotateToLeft(tree, temp); + temp = temp->parent->leftChild; + } + temp->color = node->parent->color; + node->parent->color = BLACK; + temp->leftChild->color = BLACK; + rotateToRight(tree, node->parent); + node = tree->root; } } }