https://github.com/vollero/openCAPWAP
Tip revision: 04b6c7203e73cce604e8359cfef85359eb44fad2 authored by elenago on 08 November 2017, 17:55:51 UTC
README update
README update
Tip revision: 04b6c72
CWAVL.c
#include "CWCommon.h"
int compareEthAddr(unsigned char * staAddr, unsigned char * AVLaddr) {
int index=0;
for(index=0; index<ETH_ALEN; index++)
{
if((int)staAddr[index] > (int)AVLaddr[index])
return 1;
if((int)staAddr[index] < (int)AVLaddr[index])
return -1;
}
//Gli indirizzi sono uguali
return 0;
}
/*
remove all nodes of an AVL tree
*/
void AVLdispose(nodeAVL* t)
{
if( t != NULL )
{
AVLdispose( t->left );
AVLdispose( t->right );
free( t );
}
}
/*
find a specific nodeAVL's key in the tree
*/
nodeAVL* AVLfind(unsigned char * staAddr, nodeAVL* t )
{
if(staAddr == NULL || t == NULL )
return NULL;
if(compareEthAddr(staAddr, t->staAddr) < 0)
return AVLfind(staAddr, t->left );
else if(compareEthAddr(staAddr, t->staAddr) > 0)
return AVLfind(staAddr, t->right );
else
return t;
}
nodeAVL* AVLfindWTPNode(nodeAVL* t, int index)
{
if(t == NULL)
return NULL;
if(t->index == index)
return t;
AVLfindWTPNode(t->left, index);
AVLfindWTPNode(t->right, index);
/*
else if(compareEthAddr(staAddr, t->staAddr) < 0)
return AVLfindWTPNode(staAddr, t->left, index);
else if(compareEthAddr(staAddr, t->staAddr) > 0)
return AVLfindWTPNode(staAddr, t->right, index);
else
return NULL;
*/
}
/*
find minimum nodeAVL's key
*/
nodeAVL* AVLfind_min( nodeAVL* t )
{
if( t == NULL )
return NULL;
else if( t->left == NULL )
return t;
else
return AVLfind_min( t->left );
}
/*
find maximum nodeAVL's key
*/
nodeAVL* AVLfind_max( nodeAVL* t )
{
if( t != NULL )
while( t->right != NULL )
t = t->right;
return t;
}
/*
get the height of a nodeAVL
*/
int AVLheight( nodeAVL* n )
{
if( n == NULL )
return -1;
else
return n->height;
}
/*
get maximum value of two integers
*/
int AVLmax( int l, int r)
{
return l > r ? l: r;
}
/*
perform a rotation between a k2 nodeAVL and its left child
note: call single_rotate_with_left only if k2 nodeAVL has a left child
*/
nodeAVL* AVLsingle_rotate_with_left( nodeAVL* k2 )
{
nodeAVL* k1 = NULL;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = AVLmax( AVLheight( k2->left ), AVLheight( k2->right ) ) + 1;
k1->height = AVLmax( AVLheight( k1->left ), k2->height ) + 1;
return k1; /* new root */
}
/*
perform a rotation between a nodeAVL (k1) and its right child
note: call single_rotate_with_right only if
the k1 nodeAVL has a right child
*/
nodeAVL* AVLsingle_rotate_with_right( nodeAVL* k1 )
{
nodeAVL* k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = AVLmax( AVLheight( k1->left ), AVLheight( k1->right ) ) + 1;
k2->height = AVLmax( AVLheight( k2->right ), k1->height ) + 1;
return k2; /* New root */
}
/*
perform the left-right double rotation,
note: call double_rotate_with_left only if k3 nodeAVL has
a left child and k3's left child has a right child
*/
nodeAVL* AVLdouble_rotate_with_left( nodeAVL* k3 )
{
/* Rotate between k1 and k2 */
k3->left = AVLsingle_rotate_with_right( k3->left );
/* Rotate between K3 and k2 */
return AVLsingle_rotate_with_left( k3 );
}
/*
perform the right-left double rotation
notes: call double_rotate_with_right only if k1 has a
right child and k1's right child has a left child
*/
nodeAVL* AVLdouble_rotate_with_right( nodeAVL* k1 )
{
/* rotate between K3 and k2 */
k1->right = AVLsingle_rotate_with_left( k1->right );
/* rotate between k1 and k2 */
return AVLsingle_rotate_with_right( k1 );
}
/*
insert a new nodeAVL into the tree
*/
nodeAVL* AVLinsert(int index, unsigned char * staAddr, unsigned char * BSSID, int radioID, nodeAVL* t )
{
if(staAddr == NULL)
return NULL;
if( t == NULL )
{
/* Create and return a one-nodeAVL tree */
t = (nodeAVL*)malloc(sizeof(nodeAVL));
if( t == NULL )
{
CWErrorRaise(CW_ERROR_OUT_OF_MEMORY, NULL);
return NULL;
}
t->index = index;
t->radioID = radioID;
CW_COPY_MEMORY(t->staAddr, staAddr,ETH_ALEN);
if(BSSID != NULL)
CW_COPY_MEMORY(t->BSSID, BSSID,ETH_ALEN);
t->height = 0;
t->left = t->right = NULL;
}
else if(compareEthAddr(staAddr, t->staAddr) < 0)
{
t->left = AVLinsert(index, staAddr, BSSID, radioID, t->left );
if( AVLheight( t->left ) - AVLheight( t->right ) == 2 )
if( compareEthAddr(staAddr, t->left->staAddr) < 0 )
t = AVLsingle_rotate_with_left( t );
else
t = AVLdouble_rotate_with_left( t );
}
else if(compareEthAddr(staAddr, t->staAddr) > 0)
{
t->right = AVLinsert(index, staAddr, BSSID, radioID, t->right );
if( AVLheight( t->right ) - AVLheight( t->left ) == 2 )
if( compareEthAddr(staAddr, t->right->staAddr) > 0)
t = AVLsingle_rotate_with_right( t );
else
t = AVLdouble_rotate_with_right( t );
}
/* Else X is in the tree already; we'll do nothing */
t->height = AVLmax( AVLheight( t->left ), AVLheight( t->right ) ) + 1;
return t;
}
/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
struct nodeAVL * AVLminValueNode(struct nodeAVL* node)
{
struct nodeAVL* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
struct nodeAVL* AVLdeleteNode(struct nodeAVL* root, unsigned char * staAddr, int radioID)
{
if(staAddr == NULL)
return NULL;
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if ( compareEthAddr(staAddr, root->staAddr) < 0 )
root->left = AVLdeleteNode(root->left, staAddr, radioID);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if( compareEthAddr(staAddr, root->staAddr) > 0 )
root->right = AVLdeleteNode(root->right, staAddr, radioID);
// if key is same as root's key, then This is the node
// to be deleted. If radioID is the same
else
{
if(root->radioID == radioID)
{
// node with only one child or no child
if(
((root->left == NULL) || (root->right == NULL)) &&
(root->radioID == radioID)
)
{
struct nodeAVL *temp = root->left ? root->left : root->right;
// No child case
if(temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
CWPrintEthernetAddress(staAddr, "STA deleted from AVL");
}
else
{
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct nodeAVL* temp = AVLminValueNode(root->right);
// Copy the inorder successor's data to this node
root->index = temp->index;
root->radioID = temp->radioID;
CW_COPY_MEMORY(root->staAddr, temp->staAddr, ETH_ALEN);
CW_COPY_MEMORY(root->BSSID, temp->BSSID, ETH_ALEN);
// Delete the inorder successor
root->right = AVLdeleteNode(root->right, temp->staAddr, temp->radioID);
}
}
else
{
CWLog("AVL find STA[%02x:%02x:%02x:%02x:%02x:%02x] node to delete, but radioID value (%d) is different from input radioID(%d). So AVL doesn't delete node", (int)staAddr[0], (int)staAddr[1], (int)staAddr[2], (int)staAddr[3], (int)staAddr[4], (int)staAddr[5],
root->radioID, radioID);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = AVLmax(AVLheight(root->left), AVLheight(root->right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = AVLgetBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && AVLgetBalance(root->left) >= 0)
return AVLsingle_rotate_with_right(root);
// Left Right Case
if (balance > 1 && AVLgetBalance(root->left) < 0)
{
root->left = AVLsingle_rotate_with_left(root->left);
return AVLsingle_rotate_with_right(root);
}
// Right Right Case
if (balance < -1 && AVLgetBalance(root->right) <= 0)
return AVLsingle_rotate_with_left(root);
// Right Left Case
if (balance < -1 && AVLgetBalance(root->right) > 0)
{
root->right = AVLsingle_rotate_with_right(root->right);
return AVLsingle_rotate_with_left(root);
}
return root;
}
struct nodeAVL* AVLdeleteNodeWithoutRadioID(struct nodeAVL* root, struct nodeAVL* nodeToDelete)
{
if(nodeToDelete->staAddr == NULL)
return NULL;
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if ( compareEthAddr(nodeToDelete->staAddr, root->staAddr) < 0 )
root->left = AVLdeleteNodeWithoutRadioID(root->left, nodeToDelete);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if( compareEthAddr(nodeToDelete->staAddr, root->staAddr) > 0 )
root->right = AVLdeleteNodeWithoutRadioID(root->right, nodeToDelete);
// if key is same as root's key, then This is the node
// to be deleted. If radioID is the same
else
{
// node with only one child or no child
if((root->left == NULL) || (root->right == NULL))
{
struct nodeAVL *temp = root->left ? root->left : root->right;
CWPrintEthernetAddress(root->staAddr, "Delete STA from AVL");
// No child case
if(temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
{
*root = *temp; // Copy the contents of the non-empty child
}
free(temp);
temp = NULL;
}
else
{
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct nodeAVL* temp = AVLminValueNode(root->right);
CWPrintEthernetAddress(root->staAddr, "Removing STA from AVL");
// Copy the inorder successor's data to this node
root->index = temp->index;
root->radioID = temp->radioID;
CW_COPY_MEMORY(root->staAddr, temp->staAddr, ETH_ALEN);
CW_COPY_MEMORY(root->BSSID, temp->BSSID, ETH_ALEN);
CWPrintEthernetAddress(temp->staAddr, "Node to move");
// Delete the inorder successor
root->right = AVLdeleteNodeWithoutRadioID(root->right, temp);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
CWLog("root != NULL");
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = AVLmax(AVLheight(root->left), AVLheight(root->right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = AVLgetBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && AVLgetBalance(root->left) >= 0)
return AVLsingle_rotate_with_right(root);
// Left Right Case
if (balance > 1 && AVLgetBalance(root->left) < 0)
{
root->left = AVLsingle_rotate_with_left(root->left);
return AVLsingle_rotate_with_right(root);
}
// Right Right Case
if (balance < -1 && AVLgetBalance(root->right) <= 0)
return AVLsingle_rotate_with_left(root);
// Right Left Case
if (balance < -1 && AVLgetBalance(root->right) > 0)
{
root->right = AVLsingle_rotate_with_right(root->right);
return AVLsingle_rotate_with_left(root);
}
return root;
}
/*
data data of a nodeAVL
*/
/*
int get(nodeAVL* n)
{
return n->data;
}
*/
// Get Balance factor of node N
int AVLgetBalance(struct nodeAVL *N)
{
if (N == NULL)
return 0;
return AVLheight(N->left) - AVLheight(N->right);
}
/*
Recursively display AVL tree or subtree
*/
void AVLdisplay_avl(nodeAVL* t)
{
if (t == NULL)
return;
CWLog("[%d] - %02x:%02x:%02x:%02x:%02x:%02x",t->index, (int)t->staAddr[0], (int)t->staAddr[1], (int)t->staAddr[2], (int)t->staAddr[3], (int)t->staAddr[4], (int)t->staAddr[5]);
if(t->left != NULL)
CWLog("[L: %d] - %02x:%02x:%02x:%02x:%02x:%02x",t->left->index, (int)t->left->staAddr[0], (int)t->left->staAddr[1], (int)t->left->staAddr[2], (int)t->left->staAddr[3], (int)t->left->staAddr[4], (int)t->left->staAddr[5]);
if(t->right != NULL)
CWLog("[R: %d] - %02x:%02x:%02x:%02x:%02x:%02x",t->right->index, (int)t->right->staAddr[0], (int)t->right->staAddr[1], (int)t->right->staAddr[2], (int)t->right->staAddr[3], (int)t->right->staAddr[4], (int)t->right->staAddr[5]);
CWLog("\n");
AVLdisplay_avl(t->left);
AVLdisplay_avl(t->right);
}
/*
nodeAVL * AVLremoveWTP(nodeAVL* root, int WTPIndex)
{
if (root == NULL)
return NULL;
while(root != NULL)
{
if(root->index == WTPIndex)
AVLdeleteNode(struct nodeAVL* root, unsigned char * staAddr, int radioID)
}
CWLog("[%d] - %02x:%02x:%02x:%02x:%02x:%02x",t->index, (int)t->staAddr[0], (int)t->staAddr[1], (int)t->staAddr[2], (int)t->staAddr[3], (int)t->staAddr[4], (int)t->staAddr[5]);
if(t->left != NULL)
CWLog("[L: %d] - %02x:%02x:%02x:%02x:%02x:%02x",t->left->index, (int)t->left->staAddr[0], (int)t->left->staAddr[1], (int)t->left->staAddr[2], (int)t->left->staAddr[3], (int)t->left->staAddr[4], (int)t->left->staAddr[5]);
if(t->right != NULL)
CWLog("[R: %d] - %02x:%02x:%02x:%02x:%02x:%02x",t->right->index, (int)t->right->staAddr[0], (int)t->right->staAddr[1], (int)t->right->staAddr[2], (int)t->right->staAddr[3], (int)t->right->staAddr[4], (int)t->right->staAddr[5]);
CWLog("\n");
AVLdisplay_avl(t->left);
AVLdisplay_avl(t->right);
}
*/