diff options
Diffstat (limited to 'Core/EM/usb/tree.c')
| -rw-r--r-- | Core/EM/usb/tree.c | 374 |
1 files changed, 374 insertions, 0 deletions
diff --git a/Core/EM/usb/tree.c b/Core/EM/usb/tree.c new file mode 100644 index 0000000..bb4c275 --- /dev/null +++ b/Core/EM/usb/tree.c @@ -0,0 +1,374 @@ +//**************************************************************************** +//**************************************************************************** +//** ** +//** (C)Copyright 1985-2008, American Megatrends, Inc. ** +//** ** +//** All Rights Reserved. ** +//** ** +//** 5555 Oakbrook Pkwy, Norcross, GA 30093 ** +//** ** +//** Phone (770)-246-8600 ** +//** ** +//**************************************************************************** +//**************************************************************************** + +//**************************************************************************** +// $Header: /Alaska/SOURCE/Modules/USB/ALASKA/tree.c 10 12/16/08 10:51a Olegi $ +// +// $Revision: 10 $ +// +// $Date: 12/16/08 10:51a $ +// +//**************************************************************************** +// Revision History +// ---------------- +// $Log: /Alaska/SOURCE/Modules/USB/ALASKA/tree.c $ +// +// 10 12/16/08 10:51a Olegi +// Correction in the return values: 0 changed to NULL. EIP#17767. +// +// 8 5/16/08 12:02p Olegi +// Compliance with AMI coding standard. +// +// 7 3/20/07 1:29p Olegi +// +// 5 3/20/06 3:37p Olegi +// Version 8.5 - x64 compatible. +// +// 4 6/15/05 1:59p Andriyn +// Comments were changed +//**************************************************************************** + +//<AMI_FHDR_START> +//----------------------------------------------------------------------------- +// +// Name: TREE.C +// +// Description: USB tree manipulation routines +// +//----------------------------------------------------------------------------- +//<AMI_FHDR_END> + + +#include "Efi.h" +#include "amidef.h" +#include "usbdef.h" +#include "uhcd.h" + +#include "tree.h" + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeCreate +// +// Description: initializes TREENODE_T structure +// +// Input: +// n - pointer to TREENODE_T structure +// d - pointer to data structure specific to +// the type of tree node +// +// Output: Pointer to TREENODE_T structure that was passed in as parrameter +// +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +TREENODE_T* TreeCreate( TREENODE_T* n, VOID* d ) +{ + n->data = d; + n->child = 0; + n->right = 0; + n->left = 0; + n->parent = 0; + return n; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeAddChild +// +// Description: add a child node to the TREENODE_T structure +// +// Input: +// p - pointer to parent TREENODE_T structure +// c - pointer to child TREENODE_T structure +// +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID TreeAddChild( TREENODE_T* p, TREENODE_T* c ) +{ + TREENODE_T* n = p->child; + //for( n = p->child; n != NULL; n = n->right ); + p->child = c; + c->right = n; + if(n!=0) + n->left = c; + c->left = 0; + c->parent = p; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeRemove +// +// Description: removes a node from the tree +// +// Input: +// n - pointer to TREENODE_T structure +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID TreeRemove( TREENODE_T* n ) +{ + if( n->right != 0){ + n->right->left = n->left; + } + if( n->left != 0){ + n->left->right = n->right; + } + if( n->parent && n->parent->child == n ) + n->parent->child = n->right; + n->left = 0; + n->right = 0; + n->parent = 0; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeSearchSibling +// +// Description: Enumerates nodes of the tree which are direct children of +// the same parent +// +// Input: +// n - pointer to TREENODE_T structure +// pr - predicate function that is called for each node +// and controll whether enumeration should continue +// once predicate returns TRUE the enumeration will +// data - pointer that is passed to predicate to maintain +// the context of the enumeration +// +// Output: the node that cause enumeration to stop +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +TREENODE_T* TreeSearchSibling( TREENODE_T* n, TREE_PREDICATE1_T pr, VOID* data ) +{ + TREENODE_T *r; + for(;n;n=r){ + r = n->right; + if(pr(n->data,data))return n; + } + return NULL; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeSearchDeep +// +// Description: Enumerates nodes of the tree which are direct and indirect +// children of the same parent +// +// Input: +// n - pointer to TREENODE_T structure +// pr - predicate function that is called for each node; +// controlls whether enumeration should continue +// once predicate returns TRUE the enumeration will +// data - pointer that is passed to predicate to maintain +// the context of the enumeration +// +// Output: the node that cause enumeration to stop +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +TREENODE_T* TreeSearchDeep( TREENODE_T* n, TREE_PREDICATE1_T pr, VOID* data ) +{ + TREENODE_T *r; + TREENODE_T *c; + for(;n;n=r){ + r = n->right; + c = n->child; + if(pr(n->data,data))return n; + if(c){ + TREENODE_T* c1 = TreeSearchDeep(n->child,pr,data); + if(c1) + return c1; + } + } + return 0; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: TreeForEachSibling +// +// Description: Enumerates nodes of the tree which are direct children of +// the same parent; In contrust to TreeSearchSibling this +// function ignores the result returned from call-back routine +// and always enumerates all sibling nodes +// +// Input: +// n - pointer to TREENODE_T structure +// pr - call-back function that is called for each node +// data - pointer that is passed to call-back to maintain +// the context of the enumeration +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID TreeForEachSibling( TREENODE_T* n, TREE_CALLBACK_T pr, VOID* data ) +{ + for(;n;n=n->right) + pr(n->data,data); +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: QueueGet +// +// Description: retrieves data stored at the tail of the queue and +// removes the tail item +// +// Input: +// q - pointer to QUEUE_T structure +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID* QueueGet( QUEUE_T* q) +{ + VOID* d; + if( q->tail == q->head ) return NULL; + d = q->data[q->tail++]; + if( q->tail == q->maxsize ) q->tail -= q->maxsize; + return d; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: QueueSize +// +// Description: retrieves number of items stored in the queue +// +// Input: +// q - pointer to QUEUE_T structure +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +int QueueSize(QUEUE_T* q) +{ + return (q->head >= q->tail)? q->head - q->tail: + q->head + q->maxsize - q->tail; +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: QueuePut +// +// Description: add a new item in front of the head of the queue +// +// Input: +// q - pointer to QUEUE_T structure +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID QueuePut( QUEUE_T* q, VOID * d) +{ + ASSERT(QueueSize(q) < q->maxsize ); + q->data[q->head++] = d; + if(q->head==q->maxsize) q->head -= q->maxsize; + if(q->head==q->tail){ + //Drop data from queue + q->tail++; + if( q->tail == q->maxsize ) q->tail -= q->maxsize; + } +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: QueuePutMsg +// +// Description: add a variable size item to the queue +// +// Input: +// q - pointer to QUEUE_T structure +// sz - number of dwords to add to the queue +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID QueuePutMsg( QUEUE_T* q, VOID * d, int sz ) +{ + ASSERT(QueueSize(q) < q->maxsize ); + ASSERT(sz<q->maxsize); + if(q->head + sz > q->maxsize ) + q->head = 0; + EfiCopyMem( (char*)q->data + q->head, d, sz ); + q->head += sz; + if(q->head==q->maxsize) q->head = 0; + if(q->head==q->tail){ + //Drop data from queue + q->tail+=sz; + if( q->tail >= q->maxsize ) q->tail = 0; + } +} + + +//<AMI_PHDR_START> +//--------------------------------------------------------------------------- +// +// Name: QueueRemoveMsg +// +// Description: retrieves a variable size item from the queue +// +// Input: +// q - pointer to QUEUE_T structure +// sz - number of dwords to remove from the queue +//--------------------------------------------------------------------------- +//<AMI_PHDR_END> + +VOID* QueueRemoveMsg( QUEUE_T* q, int sz) +{ + VOID* d; + if( q->tail == q->head ) return NULL; + d = (char*)q->data + q->tail; + q->tail += sz; + if( q->tail > q->maxsize ){ + d = q->data; + q->tail = sz; + } else if(q->tail == q->maxsize ){ + q->tail = 0; + } + return d; +} + +//**************************************************************************** +//**************************************************************************** +//** ** +//** (C)Copyright 1985-2008, American Megatrends, Inc. ** +//** ** +//** All Rights Reserved. ** +//** ** +//** 5555 Oakbrook Pkwy, Norcross, GA 30093 ** +//** ** +//** Phone (770)-246-8600 ** +//** ** +//**************************************************************************** +//**************************************************************************** |