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

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;
       }
     }
   }