diff options
Diffstat (limited to 'software/apilib')
| -rw-r--r-- | software/apilib/bt/octapi_bt0.c | 1179 | ||||
| -rw-r--r-- | software/apilib/bt/octapi_bt0_private.h | 93 | ||||
| -rw-r--r-- | software/apilib/largmath/octapi_largmath.c | 612 | ||||
| -rw-r--r-- | software/apilib/llman/octapi_llman.c | 2715 | ||||
| -rw-r--r-- | software/apilib/llman/octapi_llman_private.h | 206 |
5 files changed, 4805 insertions, 0 deletions
diff --git a/software/apilib/bt/octapi_bt0.c b/software/apilib/bt/octapi_bt0.c new file mode 100644 index 0000000..600eaac --- /dev/null +++ b/software/apilib/bt/octapi_bt0.c @@ -0,0 +1,1179 @@ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ + +File: octapi_bt0.c + + Copyright (c) 2001-2005 Octasic Inc. + +Description: + + Library used to manage a binary tree of variable max size. Library is + made to use one block of contiguous memory to manage the tree. + +This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is +free software; you can redistribute it and/or modify it under the terms of +the GNU General Public License as published by the Free Software Foundation; +either version 2 of the License, or (at your option) any later version. + +The OCT6100 GPL API is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with the OCT6100 GPL API; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + +$Octasic_Release: OCT612xAPI-01.00-PR38 $ + +$Octasic_Revision: 18 $ + +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +#include "apilib/octapi_bt0.h" +#include "octapi_bt0_private.h" + + + +UINT32 OctApiBt0GetSize(UINT32 number_of_items,UINT32 key_size, UINT32 data_size, UINT32 * b_size) +{ + if ((key_size % 4) != 0) return(OCTAPI_BT0_KEY_SIZE_NOT_MUTLIPLE_OF_UINT32); + if ((data_size % 4) != 0) return(OCTAPI_BT0_DATA_SIZE_NOT_MUTLIPLE_OF_UINT32); + + *b_size = 0; + *b_size += sizeof(OCTAPI_BT0); + *b_size += sizeof(OCTAPI_BT0_NODE) * number_of_items; + *b_size += key_size * number_of_items; + *b_size += data_size * number_of_items; + + return(GENERIC_OK); +} + +UINT32 OctApiBt0Init(void ** b,UINT32 number_of_items,UINT32 key_size, UINT32 data_size) +{ + UINT32 i; + OCTAPI_BT0 * bb; + + /* Check input parameters.*/ + if ((key_size % 4) != 0) return(OCTAPI_BT0_KEY_SIZE_NOT_MUTLIPLE_OF_UINT32); + if ((data_size % 4) != 0) return(OCTAPI_BT0_DATA_SIZE_NOT_MUTLIPLE_OF_UINT32); + + /* If b is not already allocated.*/ + if (*b == NULL) return(OCTAPI_BT0_MALLOC_FAILED); + + bb = (OCTAPI_BT0 *)(*b); + + /* Initialize the tree to an empty one!*/ + bb->root_link.node_number = 0xFFFFFFFF; + bb->root_link.depth = 0; + + /* Initialize tree parameters.*/ + bb->number_of_items = number_of_items; + bb->key_size = key_size / 4; + bb->data_size = data_size / 4; + + /* Initialize the next free node pointer.*/ + if (number_of_items != 0) + bb->next_free_node = 0; + else + bb->next_free_node = 0xFFFFFFFF; + + /* Setup the arrays.*/ + OctApiBt0CorrectPointers(bb); + + /* Initialize the Nodes to unused!*/ + for(i=0;i<number_of_items;i++) + { + bb->node[i].next_free_node = i + 1; + } + + /* Last empty node points to invalid node.*/ + bb->node[number_of_items-1].next_free_node = 0xFFFFFFFF; + + bb->invalid_value = 0xFFFFFFFF; + bb->no_smaller_key = OCTAPI_BT0_NO_SMALLER_KEY; + + return(GENERIC_OK); +} + + +void OctApiBt0CorrectPointers(OCTAPI_BT0 * bb) +{ + bb->node = (OCTAPI_BT0_NODE *)(((BYTE *)bb) + sizeof(OCTAPI_BT0)); + bb->key = (UINT32 *)(((BYTE *)bb->node) + (sizeof(OCTAPI_BT0_NODE) * bb->number_of_items)); + bb->data = (UINT32 *)(((BYTE *)bb->key) + (sizeof(UINT32) * bb->number_of_items * bb->key_size)); +} + + +UINT32 OctApiBt0AddNode(void * b,void * key,void ** data) +{ + OCTAPI_BT0 * bb; + OCTAPI_BT0_NODE * new_node; + UINT32 * lkey; + UINT32 * nkey; + UINT32 i; + UINT32 new_node_number; + UINT32 result; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Check that there is at least one block left.*/ + if (bb->next_free_node == 0xFFFFFFFF) return(OCTAPI_BT0_NO_NODES_AVAILABLE); + + /* Seize the node!*/ + new_node_number = bb->next_free_node; + new_node = &(bb->node[new_node_number]); + bb->next_free_node = new_node->next_free_node; + + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Find the first UINT32 of the key.*/ + nkey = &(bb->key[bb->key_size * new_node_number]); + + /* Copy the key.*/ + for(i=0;i<bb->key_size;i++) + nkey[i] = lkey[i]; + + /* Attempt to place the node. Only a "multiple hit" will cause an error.*/ + result = OctApiBt0AddNode2(bb,&(bb->root_link), lkey, new_node_number); + if (result != GENERIC_OK) + { + /* This attempt failed. Refree the node!*/ + bb->next_free_node = new_node_number; + + /* Return the error code.*/ + return(result); + } + + /* Return the address of the data to the user.*/ + if ( bb->data_size > 0 ) + *data = (void *)(&(bb->data[bb->data_size * new_node_number])); + + return(GENERIC_OK); +} + +UINT32 OctApiBt0AddNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 new_node_number) +{ + UINT32 result; + + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/ + { + bb->node[new_node_number].l[0].node_number = 0xFFFFFFFF; + bb->node[new_node_number].l[0].depth = 0; + bb->node[new_node_number].l[1].node_number = 0xFFFFFFFF; + bb->node[new_node_number].l[1].depth = 0; + + /* OCTAPI_BT0_LINK to parent!*/ + link->node_number = new_node_number; + link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/ + + return(GENERIC_OK); + } + else /* Current node is used, check for a match and a direction.*/ + { + OCTAPI_BT0_NODE * this_node; + UINT32 compare; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + result = OctApiBt0AddNode2(bb,&(this_node->l[0]), lkey, new_node_number); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + result = OctApiBt0AddNode2(bb,&(this_node->l[1]), lkey, new_node_number); + if (result != GENERIC_OK) return(result); + } + else + { + return(OCTAPI_BT0_KEY_ALREADY_IN_TREE); + } + + /* Check if this node is unbalanced by 2. If so, rebalance it:*/ + if (this_node->l[0].depth > (this_node->l[1].depth + 1) || + this_node->l[1].depth > (this_node->l[0].depth + 1)) + { + OctApiBt0Rebalance(bb,link); + } + + /* Always update the OCTAPI_BT0_LINK depth before exiting.*/ + OctApiBt0UpdateLinkDepth(bb,link); + + return(GENERIC_OK); + } +} + + +UINT32 OctApiBt0AddNode3(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number) +{ + UINT32 result; + + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/ + { + if ( *p_new_node_number == 0xFFFFFFFF ) + return(OCTAPI_BT0_NO_NODES_AVAILABLE); + + bb->node[*p_new_node_number].l[0].node_number = 0xFFFFFFFF; + bb->node[*p_new_node_number].l[0].depth = 0; + bb->node[*p_new_node_number].l[1].node_number = 0xFFFFFFFF; + bb->node[*p_new_node_number].l[1].depth = 0; + + /* OCTAPI_BT0_LINK to parent!*/ + link->node_number = *p_new_node_number; + link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/ + + return(GENERIC_OK); + } + else /* Current node is used, check for a match and a direction.*/ + { + OCTAPI_BT0_NODE * this_node; + UINT32 compare; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + result = OctApiBt0AddNode3(bb,&(this_node->l[0]), lkey, p_new_node_number); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + result = OctApiBt0AddNode3(bb,&(this_node->l[1]), lkey, p_new_node_number); + if (result != GENERIC_OK) return(result); + } + else + { + *p_new_node_number = link->node_number; + return(OCTAPI_BT0_KEY_ALREADY_IN_TREE); + } + + /* Check if this node is unbalanced by 2. If so, rebalance it:*/ + if (this_node->l[0].depth > (this_node->l[1].depth + 1) || + this_node->l[1].depth > (this_node->l[0].depth + 1)) + { + OctApiBt0Rebalance(bb,link); + } + + /* Always update the OCTAPI_BT0_LINK depth before exiting.*/ + OctApiBt0UpdateLinkDepth(bb,link); + + return(GENERIC_OK); + } +} + +/* state +0 -> first call to the function. +1 -> recursive call.*/ +UINT32 OctApiBt0AddNode4(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number, UINT32 *p_prev_node_number, UINT32 state ) +{ + UINT32 result; + UINT32 *nkey; + UINT32 *okey; + + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/ + { + bb->node[*p_new_node_number].l[0].node_number = 0xFFFFFFFF; + bb->node[*p_new_node_number].l[0].depth = 0; + bb->node[*p_new_node_number].l[1].node_number = 0xFFFFFFFF; + bb->node[*p_new_node_number].l[1].depth = 0; + + /* OCTAPI_BT0_LINK to parent!*/ + link->node_number = *p_new_node_number; + link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/ + + if ( state == 0 ) + *p_prev_node_number = 0xFFFFFFFF; + + return(GENERIC_OK); + } + else /* Current node is used, check for a match and a direction.*/ + { + OCTAPI_BT0_NODE * this_node; + UINT32 compare; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + if ( state == 0 ) + *p_prev_node_number = OCTAPI_BT0_NO_SMALLER_KEY; + + if ( *p_prev_node_number != OCTAPI_BT0_NO_SMALLER_KEY ) + { + /* Check if the key is the smallest one encountered yet.*/ + okey = &(bb->key[bb->key_size * (*p_prev_node_number)]); + nkey = &(bb->key[bb->key_size * link->node_number]); + /* If the node is key smaller then the old small one, change the value.*/ + if ( *nkey > *okey ) + { + if ( *nkey < *lkey ) + *p_prev_node_number = link->node_number; + } + } + + result = OctApiBt0AddNode4(bb,&(this_node->l[0]), lkey, p_new_node_number, p_prev_node_number, 1); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + if ( state == 0 ) + *p_prev_node_number = link->node_number; + else + { + if ( *p_prev_node_number == OCTAPI_BT0_NO_SMALLER_KEY ) + *p_prev_node_number = link->node_number; + else + { + /* Check if the key is the smallest one encountered yet.*/ + okey = &(bb->key[bb->key_size * (*p_prev_node_number)]); + nkey = &(bb->key[bb->key_size * link->node_number]); + /* If the node is key smaller then the old small one, change the value.*/ + if ( *nkey > *okey ) + { + if ( *nkey < *lkey ) + *p_prev_node_number = link->node_number; + } + } + } + + result = OctApiBt0AddNode4(bb,&(this_node->l[1]), lkey, p_new_node_number, p_prev_node_number, 1); + if (result != GENERIC_OK) return(result); + } + else + { + *p_new_node_number = link->node_number; + return(OCTAPI_BT0_KEY_ALREADY_IN_TREE); + } + + /* Check if this node is unbalanced by 2. If so, rebalance it:*/ + if (this_node->l[0].depth > (this_node->l[1].depth + 1) || + this_node->l[1].depth > (this_node->l[0].depth + 1)) + { + OctApiBt0Rebalance(bb,link); + } + + /* Always update the OCTAPI_BT0_LINK depth before exiting.*/ + OctApiBt0UpdateLinkDepth(bb,link); + + return(GENERIC_OK); + } +} + +UINT32 OctApiBt0KeyCompare(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey) +{ + UINT32 * nkey; + UINT32 i; + + /* Find the first UINT32 of the key.*/ + nkey = &(bb->key[bb->key_size * link->node_number]); + + for(i=0;i<bb->key_size;i++) + { + if (lkey[i] < nkey[i]) + return(OCTAPI_BT0_LKEY_SMALLER); + else if (lkey[i] > nkey[i]) + return(OCTAPI_BT0_LKEY_LARGER); + } + + return(OCTAPI_BT0_LKEY_EQUAL); +} + + +void OctApiBt0UpdateLinkDepth(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link) +{ + OCTAPI_BT0_NODE * this_node; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + if (this_node->l[0].depth > this_node->l[1].depth) + link->depth = this_node->l[0].depth + 1; + else + link->depth = this_node->l[1].depth + 1; +} + +void OctApiBt0Rebalance(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * root_link) +{ + if (bb->node[root_link->node_number].l[0].depth > (bb->node[root_link->node_number].l[1].depth + 1)) /* Heavy to the left.*/ + { + /* Check if the right child of the heavy child node is causing a problem.*/ + /* If so, do a left rotate in order to make the left most child the longer one.*/ + { + OCTAPI_BT0_LINK * heavy_link; + heavy_link = &(bb->node[root_link->node_number].l[0]); + + if (bb->node[heavy_link->node_number].l[1].depth > bb->node[heavy_link->node_number].l[0].depth) + { + OctApiBt0ExternalHeavy(bb,heavy_link); + } + } + + /* Ready to do super rotation!*/ + { + OCTAPI_BT0_LINK init_root_link; + OCTAPI_BT0_LINK init_heavy_link; + OCTAPI_BT0_LINK init_leaf_tree[3]; + + /* Save pertinent initial OCTAPI_BT0_LINK information.*/ + init_root_link = *root_link; + init_heavy_link = bb->node[root_link->node_number].l[0]; + init_leaf_tree[2] = bb->node[root_link->node_number].l[1]; + init_leaf_tree[0] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[0]; + init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[1]; + + /* Restructure the tree.*/ + *root_link = init_heavy_link; + bb->node[init_heavy_link.node_number].l[1] = init_root_link; + bb->node[init_root_link.node_number].l[0] = init_leaf_tree[1]; + + /* Reconstruct the depth of the branches.*/ + OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[1])); + OctApiBt0UpdateLinkDepth(bb,root_link); + } + } + else if (bb->node[root_link->node_number].l[1].depth > (bb->node[root_link->node_number].l[0].depth + 1)) /* Heavy to the right.*/ + { + /* Check if the right child of the heavy child node is causing a problem.*/ + /* If so, do a left rotate in order to make the left most child the longer one.*/ + { + OCTAPI_BT0_LINK * heavy_link; + heavy_link = &(bb->node[root_link->node_number].l[1]); + + if (bb->node[heavy_link->node_number].l[0].depth > bb->node[heavy_link->node_number].l[1].depth) + { + OctApiBt0ExternalHeavy(bb,heavy_link); + } + } + + /* Ready to do super rotation!*/ + { + OCTAPI_BT0_LINK init_root_link; + OCTAPI_BT0_LINK init_heavy_link; + OCTAPI_BT0_LINK init_leaf_tree[3]; + + /* Save pertinent initial OCTAPI_BT0_LINK information.*/ + init_root_link = *root_link; + init_heavy_link = bb->node[root_link->node_number].l[1]; + init_leaf_tree[2] = bb->node[root_link->node_number].l[0]; + init_leaf_tree[0] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[1]; + init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[0]; + + /* Restructure the tree.*/ + *root_link = init_heavy_link; + bb->node[init_heavy_link.node_number].l[0] = init_root_link; + bb->node[init_root_link.node_number].l[1] = init_leaf_tree[1]; + + /* Reconstruct the depth of the branches.*/ + OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[0])); + OctApiBt0UpdateLinkDepth(bb,root_link); + } + } +} + +/* This function does a rotation towards the outside of the tree*/ +/* in order to keep the heavy branches towards the outside.*/ +void OctApiBt0ExternalHeavy(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * root_link) +{ + if (bb->node[root_link->node_number].l[1].depth > bb->node[root_link->node_number].l[0].depth) /* Exterior of tree is towards the left.*/ + { + OCTAPI_BT0_LINK init_root_link; + OCTAPI_BT0_LINK init_heavy_link; + OCTAPI_BT0_LINK init_leaf_tree[3]; + + /* Save pertinent initial OCTAPI_BT0_LINK information.*/ + init_root_link = *root_link; + init_leaf_tree[0] = bb->node[root_link->node_number].l[0]; + init_heavy_link = bb->node[root_link->node_number].l[1]; + init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[0]; + init_leaf_tree[2] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[1]; + + /* Restructure the tree.*/ + *root_link = init_heavy_link; + bb->node[init_heavy_link.node_number].l[0] = init_root_link; + bb->node[init_root_link.node_number].l[1] = init_leaf_tree[1]; + + /* Reconstruct the depth of the branches.*/ + OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[0])); + OctApiBt0UpdateLinkDepth(bb,root_link); + } + else if (bb->node[root_link->node_number].l[0].depth > bb->node[root_link->node_number].l[1].depth) /* Exterior of tree is towards the right.*/ + { + OCTAPI_BT0_LINK init_root_link; + OCTAPI_BT0_LINK init_heavy_link; + OCTAPI_BT0_LINK init_leaf_tree[3]; + + /* Save pertinent initial OCTAPI_BT0_LINK information.*/ + init_root_link = *root_link; + init_leaf_tree[0] = bb->node[root_link->node_number].l[1]; + init_heavy_link = bb->node[root_link->node_number].l[0]; + init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[1]; + init_leaf_tree[2] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[0]; + + /* Restructure the tree.*/ + *root_link = init_heavy_link; + bb->node[init_heavy_link.node_number].l[1] = init_root_link; + bb->node[init_root_link.node_number].l[0] = init_leaf_tree[1]; + + /* Reconstruct the depth of the branches.*/ + OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[1])); + OctApiBt0UpdateLinkDepth(bb,root_link); + } +} + + +/* State:*/ +/* 0 = seeking node to be removed.*/ +/* 1 = node found, left branch taken.*/ +/* 2 = node found, right branch taken.*/ +UINT32 OctApiBt0RemoveNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey, OCTAPI_BT0_LINK * link_to_removed_node, UINT32 state, OCTAPI_BT0_LINK * volatile_grandparent_link) +{ + UINT32 result; + OCTAPI_BT0_NODE * this_node; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + if (state == 0) + { + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/ + { + return(OCTAPI_BT0_KEY_NOT_IN_TREE); + } + else /* Current node is used, check for a match and a direction.*/ + { + UINT32 compare; + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, 0, NULL); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, 0, NULL); + if (result != GENERIC_OK) return(result); + } + else + { + link_to_removed_node = link; + + /* Keep on going down to find a replacement node.*/ + if (bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) + { + /* Doe! No tree left! WHAT TO DO? */ + /* Just delete the current node. That's it.*/ + + /* Release the current node (restore free node link-list)*/ + bb->node[link->node_number].next_free_node = bb->next_free_node; + bb->next_free_node = link->node_number; + + link->node_number = 0xFFFFFFFF; + link->depth = 0; + + return(GENERIC_OK); + } + else if (bb->node[link->node_number].l[0].node_number != 0xFFFFFFFF) /* Left node is present. Go left, then permanently right.*/ + { + OCTAPI_BT0_NODE * removed_node_pnt; + removed_node_pnt = &(bb->node[link->node_number]); + + result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[0]), lkey, link_to_removed_node, 1, link); + if (result != GENERIC_OK) return(result); + + /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/ + /* but is about to be discarded! Save it quickly!*/ + /* bb->node[link->node_number].l[0] = removed_node_pnt->l[0];*/ + } + else /* Right node is present. Go right, then permanently left.*/ + { + OCTAPI_BT0_NODE * removed_node_pnt; + removed_node_pnt = &(bb->node[link->node_number]); + + result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[1]), lkey, link_to_removed_node, 2, link); + if (result != GENERIC_OK) return(result); + + /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/ + /* but is about to be discarded! Save it quickly!*/ + /* bb->node[link->node_number].l[1] = removed_node_pnt->l[1];*/ + } + } + } + } + else + { + /* Left side, Right-most node found! OR*/ + /* Right side, Left-most node found!*/ + if ((state == 1 && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) || + (state == 2 && bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF)) + { + OCTAPI_BT0_LINK init_chosen_link; + + /* Release the current node (restore free node link-list)*/ + bb->node[link_to_removed_node->node_number].next_free_node = bb->next_free_node; + bb->next_free_node = link_to_removed_node->node_number; + + /* Save the link to the chosen node, because it is about to be deleted.*/ + init_chosen_link = *link; + + /* Remove this node, and allow the tree to go on:*/ + { + OCTAPI_BT0_LINK init_child_link[2]; + + init_child_link[0] = bb->node[link->node_number].l[0]; + init_child_link[1] = bb->node[link->node_number].l[1]; + + if (state == 1) + *link = init_child_link[0]; + else + *link = init_child_link[1]; + } + + /* Replace the removed node by this node.*/ + { + OCTAPI_BT0_LINK init_removed_child_link[2]; + + init_removed_child_link[0] = bb->node[link_to_removed_node->node_number].l[0]; + init_removed_child_link[1] = bb->node[link_to_removed_node->node_number].l[1]; + + *link_to_removed_node = init_chosen_link; + bb->node[init_chosen_link.node_number].l[0] = init_removed_child_link[0]; + bb->node[init_chosen_link.node_number].l[1] = init_removed_child_link[1]; + } + + return(GENERIC_OK); + } + else + { + /* Keep on going, we have not found the center most node yet!*/ + if (state == 1) + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, state, NULL); + if (result != GENERIC_OK) return(result); + + /* Refresh the link if our link is volatile.*/ + if (volatile_grandparent_link != NULL) + { + link = &(bb->node[volatile_grandparent_link->node_number].l[0]); + } + } + else + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, state, NULL); + if (result != GENERIC_OK) return(result); + + /* Refresh the link if our link is volatile.*/ + if (volatile_grandparent_link != NULL) + { + link = &(bb->node[volatile_grandparent_link->node_number].l[1]); + } + } + } + } + + /* We may have messed up the tree. So patch it!*/ + /* Check if this node is unbalanced by 2. If so, rebalance it:*/ + if (this_node->l[0].depth > (this_node->l[1].depth + 1) || + this_node->l[1].depth > (this_node->l[0].depth + 1)) + { + OctApiBt0Rebalance(bb,link); + } + + /* Always update the OCTAPI_BT0_LINK depth before exiting.*/ + OctApiBt0UpdateLinkDepth(bb,link); + + return(GENERIC_OK); +} + + +/* State:*/ +/* 0 = seeking node to be removed.*/ +/* 1 = node found, left branch taken.*/ +/* 2 = node found, right branch taken.*/ +UINT32 OctApiBt0RemoveNode3(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey, OCTAPI_BT0_LINK * link_to_removed_node, UINT32 state, OCTAPI_BT0_LINK * volatile_grandparent_link, UINT32 *p_prev_node_number ) +{ + UINT32 result; + UINT32 *nkey; + UINT32 *okey; + OCTAPI_BT0_NODE * this_node; + + /* Get a pointer to this node.*/ + this_node = &(bb->node[link->node_number]); + + if (state == 0) + { + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/ + { + return(OCTAPI_BT0_KEY_NOT_IN_TREE); + } + else /* Current node is used, check for a match and a direction.*/ + { + UINT32 compare; + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + /* Check if the key is the biggest one encountered yet.*/ + okey = &(bb->key[bb->key_size * (*p_prev_node_number)]); + nkey = &(bb->key[bb->key_size * link->node_number]); + /* If the node is key bigger then the old one, change the value.*/ + if ( *nkey > *okey ) + { + if ( *nkey < *lkey ) + *p_prev_node_number = link->node_number; + } + + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, 0, NULL); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + /* Check if the key is the biggest one encountered yet.*/ + okey = &(bb->key[bb->key_size * (*p_prev_node_number)]); + nkey = &(bb->key[bb->key_size * link->node_number]); + /* If the node is key bigger then the old one, change the value.*/ + if ( *nkey > *okey ) + { + if ( *nkey < *lkey ) + *p_prev_node_number = link->node_number; + } + + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, 0, NULL); + if (result != GENERIC_OK) return(result); + } + else + { + link_to_removed_node = link; + + /* Keep on going down to find a replacement node.*/ + if (bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) + { + /* Doe! No tree left! WHAT TO DO? */ + /* Just delete the current node. That's it.*/ + + /* Release the current node (restore free node link-list)*/ + bb->node[link->node_number].next_free_node = bb->next_free_node; + bb->next_free_node = link->node_number; + + link->node_number = 0xFFFFFFFF; + link->depth = 0; + + return(GENERIC_OK); + } + else if (bb->node[link->node_number].l[0].node_number != 0xFFFFFFFF) /* Left node is present. Go left, then permanently right.*/ + { + OCTAPI_BT0_NODE * removed_node_pnt; + removed_node_pnt = &(bb->node[link->node_number]); + + result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[0]), lkey, link_to_removed_node, 1, link); + if (result != GENERIC_OK) return(result); + + /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/ + /* but is about to be discarded! Save it quickly!*/ + /* bb->node[link->node_number].l[0] = removed_node_pnt->l[0];*/ + } + else /* Right node is present. Go right, then permanently left.*/ + { + OCTAPI_BT0_NODE * removed_node_pnt; + removed_node_pnt = &(bb->node[link->node_number]); + + result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[1]), lkey, link_to_removed_node, 2, link); + if (result != GENERIC_OK) return(result); + + /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/ + /* but is about to be discarded! Save it quickly!*/ + /* bb->node[link->node_number].l[1] = removed_node_pnt->l[1];*/ + } + } + } + } + else + { + /* Check if the key is the biggest one encountered yet.*/ + okey = &(bb->key[bb->key_size * (*p_prev_node_number)]); + nkey = &(bb->key[bb->key_size * link->node_number]); + /* If the node is key bigger then the old one, change the value.*/ + if ( *nkey > *okey ) + { + if ( *nkey < *lkey ) + *p_prev_node_number = link->node_number; + } + + /* Left side, Right-most node found! OR*/ + /* Right side, Left-most node found!*/ + if ((state == 1 && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) || + (state == 2 && bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF)) + { + OCTAPI_BT0_LINK init_chosen_link; + + /* Release the current node (restore free node link-list)*/ + bb->node[link_to_removed_node->node_number].next_free_node = bb->next_free_node; + bb->next_free_node = link_to_removed_node->node_number; + + /* Save the link to the chosen node, because it is about to be deleted.*/ + init_chosen_link = *link; + + /* Remove this node, and allow the tree to go on:*/ + { + OCTAPI_BT0_LINK init_child_link[2]; + + init_child_link[0] = bb->node[link->node_number].l[0]; + init_child_link[1] = bb->node[link->node_number].l[1]; + + if (state == 1) + *link = init_child_link[0]; + else + *link = init_child_link[1]; + } + + /* Replace the removed node by this node.*/ + { + OCTAPI_BT0_LINK init_removed_child_link[2]; + + init_removed_child_link[0] = bb->node[link_to_removed_node->node_number].l[0]; + init_removed_child_link[1] = bb->node[link_to_removed_node->node_number].l[1]; + + *link_to_removed_node = init_chosen_link; + bb->node[init_chosen_link.node_number].l[0] = init_removed_child_link[0]; + bb->node[init_chosen_link.node_number].l[1] = init_removed_child_link[1]; + } + + return(GENERIC_OK); + } + else + { + /* Keep on going, we have not found the center most node yet!*/ + if (state == 1) + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, state, NULL); + if (result != GENERIC_OK) return(result); + + /* Refresh the link if our link is volatile.*/ + if (volatile_grandparent_link != NULL) + { + link = &(bb->node[volatile_grandparent_link->node_number].l[0]); + } + } + else + { + result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, state, NULL); + if (result != GENERIC_OK) return(result); + + /* Refresh the link if our link is volatile.*/ + if (volatile_grandparent_link != NULL) + { + link = &(bb->node[volatile_grandparent_link->node_number].l[1]); + } + } + } + } + + /* We may have messed up the tree. So patch it!*/ + /* Check if this node is unbalanced by 2. If so, rebalance it:*/ + if (this_node->l[0].depth > (this_node->l[1].depth + 1) || + this_node->l[1].depth > (this_node->l[0].depth + 1)) + { + OctApiBt0Rebalance(bb,link); + } + + /* Always update the OCTAPI_BT0_LINK depth before exiting.*/ + OctApiBt0UpdateLinkDepth(bb,link); + + return(GENERIC_OK); +} + +UINT32 OctApiBt0RemoveNode(void * b,void * key) +{ + OCTAPI_BT0 * bb; + UINT32 result; + UINT32 * lkey; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Attempt to remove the node. Only a "no hit" will cause an error.*/ + result = OctApiBt0RemoveNode2(bb,&(bb->root_link), lkey, NULL, 0, NULL); + if (result != GENERIC_OK) return(result); + + return(GENERIC_OK); +} + +UINT32 OctApiBt0QueryNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 * node_number) +{ + UINT32 result; + + if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/ + { + return(OCTAPI_BT0_KEY_NOT_IN_TREE); + } + else /* Current node is used, check for a match and a direction.*/ + { + UINT32 compare; + + /* Compare this node to the lkey.*/ + compare = OctApiBt0KeyCompare(bb,link,lkey); + + if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/ + { + result = OctApiBt0QueryNode2(bb,&(bb->node[link->node_number].l[0]), lkey, node_number); + if (result != GENERIC_OK) return(result); + } + else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/ + { + result = OctApiBt0QueryNode2(bb,&(bb->node[link->node_number].l[1]), lkey, node_number); + if (result != GENERIC_OK) return(result); + } + else + { + /* A match!*/ + *node_number = link->node_number; + } + } + + return(GENERIC_OK); +} + + +UINT32 OctApiBt0QueryNode(void * b,void * key,void ** data) +{ + OCTAPI_BT0 * bb; + UINT32 node_number; + UINT32 result; + UINT32 * lkey; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Get the node number.*/ + result = OctApiBt0QueryNode2(bb,&(bb->root_link),lkey,&node_number); + if (result != GENERIC_OK) return(result); + + /* Return the address of the data to the user.*/ + if ( bb->data_size > 0 ) + *data = (void *)(&(bb->data[bb->data_size * node_number])); + + return(GENERIC_OK); +} + +UINT32 OctApiBt0GetFirstNode(void * b,void ** key, void ** data) +{ + OCTAPI_BT0 * bb; + OCTAPI_BT0_NODE * node; + UINT32 node_number; + UINT32 * lkey; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Check if there are any keys present in the tree. */ + if (bb->root_link.node_number == 0xFFFFFFFF) return OCTAPI_BT0_NO_NODES_AVAILABLE; + + node_number = bb->root_link.node_number; + node = &bb->node[node_number]; + + /* Make our way down to the left-most node. */ + while (node->l[0].node_number != 0xFFFFFFFF) + { + node_number = node->l[0].node_number; + node = &bb->node[node_number]; + } + + /* Return the address of the data to the user.*/ + if ( bb->key_size > 0 ) + *key = (void *)(&(bb->key[bb->key_size * node_number])); + + if ( bb->data_size > 0 ) + *data = (void *)(&(bb->data[bb->data_size * node_number])); + + return(GENERIC_OK); +} + +UINT32 OctApiBt0FindOrAddNode(void * b,void * key,void ** data, UINT32 *fnct_result) +{ + OCTAPI_BT0 * bb; + OCTAPI_BT0_NODE * new_node; + UINT32 * lkey; + UINT32 * nkey; + UINT32 i; + UINT32 new_node_number; + UINT32 temp_node_number = 0; + UINT32 result; + UINT32 tree_already_full = FALSE; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Seize the node!*/ + new_node_number = bb->next_free_node; + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Check that there is at least one block left.*/ + if (bb->next_free_node != 0xFFFFFFFF) + { + + temp_node_number = new_node_number; + new_node = &(bb->node[new_node_number]); + bb->next_free_node = new_node->next_free_node; + + /* Find the first UINT32 of the key.*/ + nkey = &(bb->key[bb->key_size * new_node_number]); + + /* Copy the key.*/ + for(i=0;i<bb->key_size;i++) + nkey[i] = lkey[i]; + } + else + tree_already_full = TRUE; /* Signal that the tree was already full when the function was called.*/ + + /* Attempt to place the node. Only a "multiple hit" will cause an error.*/ + result = OctApiBt0AddNode3(bb,&(bb->root_link), lkey, &new_node_number); + switch( result ) + { + case GENERIC_OK: + *fnct_result = OCTAPI0_BT0_NODE_ADDDED; + break; + case OCTAPI_BT0_KEY_ALREADY_IN_TREE: + *fnct_result = OCTAPI0_BT0_NODE_FOUND; + /* This attempt did not add a new node. Refree the node!*/ + if ( tree_already_full == FALSE ) + bb->next_free_node = temp_node_number; + result = GENERIC_OK; + break; + default: + break; + } + + if (result != GENERIC_OK) + { + /* This attempt failed. Refree the node!*/ + if ( tree_already_full == FALSE ) + bb->next_free_node = new_node_number; + + /* Return the error code.*/ + return(result); + } + + /* Return the address of the data to the user.*/ + if ( bb->data_size > 0 ) + *data = (void *)(&(bb->data[bb->data_size * new_node_number])); + + return(GENERIC_OK); +} + + +UINT32 OctApiBt0AddNodeReportPrevNodeData(void * b,void * key,void ** data, void ** prev_data, PUINT32 fnct_result ) +{ + OCTAPI_BT0 * bb; + OCTAPI_BT0_NODE * new_node; + UINT32 * lkey; + UINT32 * nkey; + UINT32 i; + UINT32 new_node_number; + UINT32 temp_node_number; + UINT32 prev_node_number; + UINT32 result; + + /* Load all!*/ + bb = (OCTAPI_BT0 *)(b); + OctApiBt0CorrectPointers(bb); + + /* Check that there is at least one block left.*/ + if (bb->next_free_node == 0xFFFFFFFF) return(OCTAPI_BT0_NO_NODES_AVAILABLE); + + /* Seize the node!*/ + new_node_number = bb->next_free_node; + temp_node_number = new_node_number; + new_node = &(bb->node[new_node_number]); + bb->next_free_node = new_node->next_free_node; + + /* Set the previous node value */ + prev_node_number = 0xFFFFFFFF; + + /* Register in the key and the data.*/ + lkey = ((UINT32 *)key); + + /* Find the first UINT32 of the key.*/ + nkey = &(bb->key[bb->key_size * new_node_number]); + + /* Copy the key.*/ + for(i=0;i<bb->key_size;i++) + nkey[i] = lkey[i]; + + /* Attempt to place the node. Only a "multiple hit" will cause an error.*/ + result = OctApiBt0AddNode4(bb,&(bb->root_link), lkey, &new_node_number, &prev_node_number, 0); + switch( result ) + { + case GENERIC_OK: + *fnct_result = OCTAPI0_BT0_NODE_ADDDED; + break; + case OCTAPI_BT0_KEY_ALREADY_IN_TREE: + *fnct_result = OCTAPI0_BT0_NODE_FOUND; + /* This attempt did not add a new node. Refree the node!*/ + bb->next_free_node = temp_node_number; + result = GENERIC_OK; + break; + default: + break; + } + + if (result != GENERIC_OK) + { + /* This attempt failed. Refree the node!*/ + bb->next_free_node = new_node_number; + + /* Return the error code.*/ + return(result); + } + + /* Return the address of the data to the user.*/ + if ( bb->data_size > 0 ) + *data = (void *)(&(bb->data[bb->data_size * new_node_number])); + + if ( bb->data_size > 0 ) + { + if ( (prev_node_number != 0xFFFFFFFF) && + (prev_node_number != OCTAPI_BT0_NO_SMALLER_KEY) && + (*fnct_result == OCTAPI0_BT0_NODE_ADDDED)) + *prev_data = ( void* )(&(bb->data[bb->data_size * prev_node_number])); + else if ( prev_node_number == 0xFFFFFFFF ) + *prev_data = ( void* )(&bb->invalid_value); + else if ( prev_node_number == OCTAPI_BT0_NO_SMALLER_KEY ) + *prev_data = ( void* )(&bb->no_smaller_key); + } + + return(GENERIC_OK); +} + diff --git a/software/apilib/bt/octapi_bt0_private.h b/software/apilib/bt/octapi_bt0_private.h new file mode 100644 index 0000000..feabb8e --- /dev/null +++ b/software/apilib/bt/octapi_bt0_private.h @@ -0,0 +1,93 @@ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ + +File: octapi_bt0_private.h + +Copyright (c) 2001 Octasic Inc. All rights reserved. + +Description: + + Library used to manage a binary tree of variable max size. Library is + made to use one block of contiguous memory to manage the tree. + +This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is +free software; you can redistribute it and/or modify it under the terms of +the GNU General Public License as published by the Free Software Foundation; +either version 2 of the License, or (at your option) any later version. + +The OCT6100 GPL API is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with the OCT6100 GPL API; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + +$Octasic_Release: OCT612xAPI-01.00-PR38 $ + +$Octasic_Revision: 11 $ + +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +#ifndef __OCTAPI_BT0_PRIVATE_H__ +#define __OCTAPI_BT0_PRIVATE_H__ + + + +#include "octdef.h" + +#define OCTAPI_BT0_LKEY_LARGER 0x0 +#define OCTAPI_BT0_LKEY_SMALLER 0x1 +#define OCTAPI_BT0_LKEY_EQUAL 0x2 + +typedef struct __OCTAPI_BT0_LINK__ +{ + UINT32 node_number; + UINT32 depth; +} OCTAPI_BT0_LINK; + +typedef struct __OCTAPI_BT0_NODE__ +{ + UINT32 next_free_node; /* Number of the next node in the free node link-list.*/ + OCTAPI_BT0_LINK l[2]; /* 0 = left link; 1 = right link.*/ +} OCTAPI_BT0_NODE; + + +typedef struct __OCTAPI_BT0__ +{ + UINT32 number_of_items; /* Number of items on total that can be allocated in the tree.*/ + UINT32 key_size; /* Size is in UINT32s*/ + UINT32 data_size; /* Size is in UINT32s*/ + + /* Empty node linked-list:*/ + UINT32 next_free_node; /* 0xFFFFFFFF means that no nodes are free.*/ + + /* Tree as such:*/ + OCTAPI_BT0_NODE * node; /* Array of nodes (number_of_items in size).*/ + + /* Tree root:*/ + OCTAPI_BT0_LINK root_link; + + /* Associated key structure*/ + UINT32 * key; /* Array of keys associated to NODEs.*/ + + /* Associated data structure.*/ + UINT32 * data; /* Array of data associated to NODEs.*/ + + UINT32 invalid_value; + UINT32 no_smaller_key; + +} OCTAPI_BT0; + +void OctApiBt0CorrectPointers( OCTAPI_BT0 * bb ); +UINT32 OctApiBt0AddNode2( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey, UINT32 new_node_number ); +UINT32 OctApiBt0AddNode3( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey, UINT32 *p_new_node_number ); +UINT32 OctApiBt0AddNode4(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number, UINT32 *p_prev_node_number, UINT32 state ); +UINT32 OctApiBt0KeyCompare( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey ); +void OctApiBt0UpdateLinkDepth( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link ); +void OctApiBt0Rebalance( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * root_link ); +void OctApiBt0ExternalHeavy( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * root_link ); +UINT32 OctApiBt0RemoveNode2( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey, OCTAPI_BT0_LINK * link_to_removed_node, UINT32 state, OCTAPI_BT0_LINK * volatile_grandparent_link ); + + + +#endif /*__OCTAPI_BT0_PRIVATE_H__*/ diff --git a/software/apilib/largmath/octapi_largmath.c b/software/apilib/largmath/octapi_largmath.c new file mode 100644 index 0000000..c2823a3 --- /dev/null +++ b/software/apilib/largmath/octapi_largmath.c @@ -0,0 +1,612 @@ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ + +File: octapi_largmath.h + + Copyright (c) 2001-2005 Octasic Inc. + +Description: + + Library used to perform arithmetic on integer values of an integer multiple + of 32-bits. + +This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is +free software; you can redistribute it and/or modify it under the terms of +the GNU General Public License as published by the Free Software Foundation; +either version 2 of the License, or (at your option) any later version. + +The OCT6100 GPL API is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with the OCT6100 GPL API; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + +$Octasic_Release: OCT612xAPI-01.00-PR38 $ + +$Octasic_Revision: 10 $ + +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +#include "apilib/octapi_largmath.h" + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmAdd. +| +| Description: This function adds 2 numbers, a and b. Number a is +| (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The +| result is (zlen + 1) * 32 bits long. It the function succeeds it returns +| GENERIC_OK, else GENERIC_ERROR. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *a UINT32 The array containing the first number. +| alen USHORT The length of array a, minus 1 (0 - 99). +| *b UINT32 The array containing the second number. +| blen USHORT The length of array b, minus 1 (0 - 99). +| *z UINT32 The array containing the resulting number. +| zlen USHORT The length of array z, minus 1 (0 - 99). +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmAdd(UINT32 * a,USHORT alen,UINT32 * b,USHORT blen,UINT32 * z, USHORT zlen) +{ + USHORT i; + UINT32 temp; + UINT32 carry=0; + UINT32 aprim; + UINT32 bprim; + + /* Check for array lengths.*/ + if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH); + + for(i=0;i<=zlen;i++) + { + if (i <= alen) aprim = *(a+i); else aprim = 0; + if (i <= blen) bprim = *(b+i); else bprim = 0; + temp = aprim + bprim + carry; + + /* Calculate carry for next time.*/ + if (carry == 0) + if (temp < aprim) carry = 1; else carry = 0; + else + if (temp <= aprim) carry = 1; else carry = 0; + + /* Write new value.*/ + *(z+i) = temp; + } + + /* Check for overflow.*/ + if (carry == 1) return(OCTAPI_LM_OVERFLOW); + + /* All is well.*/ + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmSubtract. +| +| Description: This function subtracts 2 numbers, a and b. Number a is +| (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The result +| is (zlen + 1) * 32 bits long. It the function succeeds it returns +| GENERIC_OK, else GENERIC_ERROR. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *a UINT32 The array containing the first number. +| alen USHORT The length of array a, minus 1 (0 - 99). +| *bneg UINT32 The array containing the second number. +| blen USHORT The length of array b, minus 1 (0 - 99). +| *z UINT32 The array containing the resulting number. +| zlen USHORT The length of array z, minus 1 (0 - 99). +| *neg USHORT Indicates if the result is negative +| (TRUE/FALSE). +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmSubtract(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,UINT32 * z,USHORT zlen,USHORT * neg) +{ + USHORT i; + UINT32 temp; + UINT32 carry=1; + UINT32 aprim; + UINT32 bprim; + + /* Check for array lengths.*/ + if (alen > zlen || blen > zlen) return(OCTAPI_LM_ARRAY_SIZE_MISMATCH); + + for(i=0;i<=zlen;i++) + { + if (i <= alen) aprim = *(a+i); else aprim = 0; + if (i <= blen) bprim = ~(*(bneg+i)); else bprim = 0xFFFFFFFF; + temp = aprim + bprim + carry; + + /* Calculate carry for next time.*/ + if (carry == 0) + if (temp < aprim) carry = 1; else carry = 0; + else + if (temp <= aprim) carry = 1; else carry = 0; + + /* Write new value.*/ + *(z+i) = temp; + } + + /* Check for overflow, which means negative number!*/ + if (carry == 0) + { + /* Number is not of right neg. Invert and add one to correct neg.*/ + for(i=0;i<=zlen;i++) + *(z+i) = ~(*(z+i)); + + temp = 1; + OctApiLmAdd(&temp,0,z,zlen,z,zlen); + + *neg = TRUE; + return(GENERIC_OK); + } + + /* Result is positive.*/ + *neg = FALSE; + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmCompare. +| +| Description: This function compares two numbers (arrays) of equal lengths. +| Number a is (alen + 1) * 32 bits long; b is (blen + 1) * 32 bits long. The result +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *a UINT32 The array containing the first number. +| alen USHORT The length of array a, minus 1 (0 - 99). +| *b UINT32 The array containing the second number. +| blen USHORT The length of array b, minus 1 (0 - 99). +| *neg USHORT Result of compare. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmCompare(UINT32 * a,USHORT alen,UINT32 * bneg,USHORT blen,USHORT * neg) +{ + USHORT i; + UINT32 temp; + UINT32 carry=1; + UINT32 aprim; + UINT32 bprim; + UINT32 zlen; + + /* Set zlen to alen or blen (which ever is longer)*/ + if (alen < blen) + zlen = blen; + else + zlen = alen; + + for(i=0;i<=zlen;i++) + { + if (i <= alen) aprim = *(a+i); else aprim = 0; + if (i <= blen) bprim = ~(*(bneg+i)); else bprim = 0xFFFFFFFF; + temp = aprim + bprim + carry; + + /* Calculate carry for next time.*/ + if (carry == 0) + if (temp < aprim) carry = 1; else carry = 0; + else + if (temp <= aprim) carry = 1; else carry = 0; + } + + /* Check for overflow, which means negative number!*/ + if (carry == 0) + { + *neg = TRUE; + return(GENERIC_OK); + } + + /* Result is positive.*/ + *neg = FALSE; + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmSubtract. +| +| Description: This function multiplies 2 numbers, a and b. Number a and +| b are both (ablen + 1) * 32 bits long. The result is twice as +| long. If the functions succeeds if returns GENERIC_OK, +| else GENERIC_ERROR. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *a UINT32 The array containing the first number. +| *b UINT32 The array containing the second number. +| ablen USHORT The length of arrays a and b, minus 1 (0 - 99). +| *z UINT32 The array containing the resulting number. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmMultiply(UINT32 * a,UINT32 * b,USHORT ablen,UINT32 * z) +{ + USHORT i,j,k; + USHORT nos; + UINT32 lownum; + UINT32 highnum; + USHORT longnumi; + USHORT longnumj; + USHORT indentw,indentl; + + + /* Caculate number of shorts in a and b.*/ + nos = (USHORT)((ablen+1) * 2); + + /* Clear answer word.*/ + for(i=0;i<nos;i++) + *(z+i) = 0; + + { + USHORT optimizea, optimizeb; + USHORT l; + optimizea = TRUE; + optimizeb = TRUE; + for(l = 1; l < ablen+1; l++) + { + if(*(a+l) != 0) + optimizea = FALSE; + if(*(b+l) != 0) + optimizeb = FALSE; + } + if(*a > OCTAPI_LM_MAX_OPTIMIZE_MUL) + optimizea = FALSE; + if(*b > OCTAPI_LM_MAX_OPTIMIZE_MUL) + optimizeb = FALSE; + + if(optimizea == TRUE) + { + for(l = 0; l < *a; l++) + OctApiLmAdd(z, (USHORT)(nos-1), b, ablen, z, (USHORT)(nos-1)); + return(GENERIC_OK); + } + + if(optimizeb == TRUE) + { + for(l = 0; l < *b; l++) + OctApiLmAdd(z, (USHORT)(nos-1), a, ablen, z, (USHORT)(nos-1)); + return(GENERIC_OK); + } + } + + for(i=0;i<nos;i++) + { + longnumi = (USHORT)( i/2 ); + /* One iteration per short in a.*/ + if ((i%2) == 0) + lownum = *(a+longnumi) & 0xFFFF; /* Even word. Lower part of long.*/ + else + lownum = *(a+longnumi)>>16; /* Odd word. Upper part of long.*/ + + for(j=0;j<nos;j++) + { + UINT32 product; + + longnumj = (USHORT)( j/2 ); + /* One iteration per short in a.*/ + if ((j%2) == 0) + highnum = *(b+longnumj) & 0xFFFF; /* Even word. Lower part of long.*/ + else + highnum = *(b+longnumj)>>16; /* Odd word. Upper part of long.*/ + + /* Find the word indent of the answer. 0 = no indent. 1 = one word indent.*/ + indentw = (USHORT)( j+i ); + indentl = (USHORT)( indentw / 2 ); + + /* Multiply both numbers.*/ + product = highnum * lownum; + + /* After multiplying both numbers, add result to end result.*/ + if ((indentw % 2) == 0) /* Even word boundary, addition in one shot!*/ + { + UINT32 carry=0; + UINT32 temp; + UINT32 addme; + + for(k=indentl;k<nos;k++) + { + if (k==indentl) addme = product; else addme = 0; + + temp = *(z+k) + addme + carry; + + /* Calculate carry for next time.*/ + if (carry == 0) + if (temp < addme) carry = 1; else carry = 0; + else + if (temp <= addme) carry = 1; else carry = 0; + + /* Set value.*/ + *(z+k) = temp; + } + + /* Carry should always be 0.*/ + if (carry == 1) return(GENERIC_ERROR); + } + else /* Odd word boundary, addition in two shots.*/ + { + UINT32 carry=0; + UINT32 temp; + UINT32 addme; + + for(k=indentl;k<nos;k++) + { + if (k==indentl) addme = product<<16; + else if (k==(indentl+1)) addme = product>>16; + else addme = 0; + + temp = *(z+k) + addme + carry; + + /* Calculate carry for next time.*/ + if (carry == 0) + if (temp < addme) carry = 1; else carry = 0; + else + if (temp <= addme) carry = 1; else carry = 0; + + /* Set value.*/ + *(z+k) = temp; + } + + /* Carry should always be 0.*/ + if (carry == 1) return(GENERIC_ERROR); + } + } + } + + return(GENERIC_OK); +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmDivide. +| +| Description: This function divides the number n by the number d. The +| quotient is placed in q and the remainder in r. The arrays +| n, d, q and r are all of the same length, namely (ndqrlen + 1). +| If the functions succeeds if returns GENERIC_OK, else +| GENERIC_ERROR. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *a UINT32 The array containing the first number. +| *b UINT32 The array containing the second number. +| ablen USHORT The length of arrays a and b, minus 1 (0 - 99). +| *z UINT32 The array containing the resulting number. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmDivide(UINT32 * n,UINT32 * d,UINT32 * q,UINT32 * r,USHORT ndqrlen) +{ + /* Proceedure for division:*/ + /* r = n*/ + /* q = 0*/ + /* shift = initial_denominator_shift (for upper '1's to be in same bit position).*/ + /* d <<= shift;*/ + /* Start loop:*/ + /* compare r and d*/ + /* if r > d then*/ + /* r -= d;*/ + /* write a '1' to bit "shift" of array q.*/ + /* end if;*/ + /* if shift == 0 then*/ + /* return;*/ + /* else*/ + /* shift--;*/ + /* d>>=1;*/ + /* goto "Start loop:"*/ + /* end if;*/ + + UINT32 i; + UINT32 result; + USHORT shift,n_msb,d_msb; + USHORT neg; + USHORT ConditionFlag = TRUE; + + /* r = n*/ + for(i=0;i<=ndqrlen;i++) + *(r+i) = *(n+i); + + /* q = 0*/ + for(i=0;i<=ndqrlen;i++) + *(q+i) = 0; + + /* shift = initial_denominator_shift (for upper '1's to be in same bit position).*/ + result = OctApiLmGetMsb(d,ndqrlen,&d_msb); + if (result != GENERIC_OK) return(result); + + result = OctApiLmGetMsb(n,ndqrlen,&n_msb); + if (result != GENERIC_OK) return(result); + + if (d_msb == 0xFFFF) /* Division by 0.*/ + return(OCTAPI_LM_DIVISION_BY_ZERO); + + if (n_msb == 0xFFFF) /* 0/n, returns 0 R 0.*/ + return(GENERIC_OK); + + if (n_msb < d_msb) /* x/y, where x is smaller than y, returns 0 R x.*/ + return(GENERIC_OK); + + shift = (USHORT)( n_msb - d_msb ); + + /* Shift d to match n highest bit position.*/ + result = OctApiLmShiftn(d,ndqrlen,TRUE,shift); + if (result != GENERIC_OK) return(result); + + /* Start loop:*/ + while( ConditionFlag == TRUE ) + { + /* compare r and d*/ + result = OctApiLmCompare(r,ndqrlen,d,ndqrlen,&neg); + if (result != GENERIC_OK) return(result); + + if (neg == FALSE) /* Subtraction can be done(do it).*/ + { + /* r -= d;*/ + result = OctApiLmSubtract(r,ndqrlen,d,ndqrlen,r,ndqrlen,&neg); + if (result != GENERIC_OK) return(result); + + /* write a '1' to bit "shift" of array q.*/ + *(q+(shift/32)) |= (UINT32)0x1 << (shift%32); + } + + /* if shift == 0 then*/ + /* return;*/ + if (shift == 0) return(GENERIC_OK); + + /* shift--;*/ + /* d>>=1;*/ + /* goto "Start loop:"*/ + shift--; + OctApiLmShiftRight1(d,ndqrlen); + } + + return(GENERIC_OK); +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: octapi_lm_shifright1. +| +| Description: The function is for internal use only. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| N/A. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmShiftRight1(UINT32 * a,USHORT alen) +{ + UINT32 i; + + /* Start with lower long and move up by one long each time,*/ + /* shifting each long to the right by one bit. The upper bit*/ + /* of the next long will have to be concatenated each time a*/ + /* loop is executed. For the last long, leave the highest bit*/ + /* intact.*/ + for(i=0;i<alen;i++) + { + *(a+i)>>=1; /* Shift long by one to the right.*/ + *(a+i)|=*(a+i+1)<<31; + } + *(a+alen)>>=1; /* Shift last long, leaving it's highest bit at 0.*/ + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmShiftn. +| +| Description: The function is for internal use only. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| N/A. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmShiftn(UINT32 * a,USHORT alen,USHORT shiftleft,USHORT shiftn) +{ + UINT32 i; + USHORT long_offset; + USHORT bit_offset; + + long_offset = (USHORT)( shiftn / 32 ); + bit_offset = (USHORT)( shiftn % 32 ); + + if (shiftleft == TRUE) /* Shift left.*/ + { + for(i=alen;i<=alen;i--) + { + /* Fill upper bits of long.*/ + if (i >= long_offset) + *(a+i) = *(a+i-long_offset) << bit_offset; + else + *(a+i) = 0; + + /* Fill lower bits of long.*/ + if (i > long_offset && bit_offset != 0) + *(a+i) |= *(a+i-long_offset-1) >> (32-bit_offset); + } + } + else /* Shift right.*/ + { + for(i=0;i<=alen;i++) + { + /* Fill lower bits of long.*/ + if ((alen-i) >= long_offset) + *(a+i) = *(a+i+long_offset) >> bit_offset; + else + *(a+i) = 0; + + /* Fill upper bits of long.*/ + if ((alen-i) > long_offset && bit_offset != 0) + *(a+i) |= *(a+i+long_offset+1) << (32-bit_offset); + + } + } + + return(GENERIC_OK); +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLmGetMsb. +| +| Description: The function is for internal use only. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| N/A. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLmGetMsb(UINT32 * a,USHORT alen,USHORT * msb_pos) +{ + UINT32 i,j; + UINT32 x; + + for(i=alen;i<=alen;i--) + { + if (*(a+i) == 0) continue; + + x = *(a+i); + for(j=31;j<=31;j--) + { + /* Test for bit being '1'.*/ + if ((x & 0x80000000) != 0) + { + *msb_pos=(USHORT)(j+(32*i)); + return(GENERIC_OK); + } + + /* Shift bit one bit position, and try again.*/ + x<<=1; + } + } + + /* MSB not found.*/ + *msb_pos = 0xFFFF; + + return(GENERIC_OK); +} diff --git a/software/apilib/llman/octapi_llman.c b/software/apilib/llman/octapi_llman.c new file mode 100644 index 0000000..13c68eb --- /dev/null +++ b/software/apilib/llman/octapi_llman.c @@ -0,0 +1,2715 @@ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ + +File: octapi_llman.c + + Copyright (c) 2001-2005 Octasic Inc. + +Description: + + Library used to manage allocation tables and linked lists. The library is + made such that only a block of contiguous memory is needed for the + management of the linked list/allocation table. + +This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is +free software; you can redistribute it and/or modify it under the terms of +the GNU General Public License as published by the Free Software Foundation; +either version 2 of the License, or (at your option) any later version. + +The OCT6100 GPL API is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with the OCT6100 GPL API; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + +$Octasic_Release: OCT612xAPI-01.00-PR38 $ + +$Octasic_Revision: 21 $ + +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +#include "octapi_llman_private.h" +#include "apilib/octapi_llman.h" +#include "apilib/octapi_largmath.h" + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctapiLlmAllocGetSize. +| +| Description: This function determines the amount of memory needed to +| manage the allocation of a fixed amount of resources. +| The memory is measured in bytes. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| number_of_items UINT32 The number of resources to be allocated. +| *l_size UINT32 UINT32 The amount of memory needed, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctapiLlmAllocGetSize(UINT32 number_of_items,UINT32 * l_size) +{ + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + + *l_size = (sizeof(LLM_ALLOC)) + (number_of_items * sizeof(UINT32)); + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctapiLlmAllocInit. +| +| Description: This function intializes the LLM_ALLOC structure. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| **l void The memory used by the LLM_ALLOC structure. +| number_of_items UINT32 The number of resources to be allocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctapiLlmAllocInit(void ** l,UINT32 number_of_items) +{ + LLM_ALLOC* ls; + UINT32 i; + + /* Check the number of items required.*/ + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + + /* If no memory has been allocated yet:*/ + if (*l == NULL) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Build the structure before starting.*/ + ls = (LLM_ALLOC *)(*l); + ls->linked_list = (UINT32 *)((BYTE *)ls + sizeof(LLM_ALLOC)); + + ls->number_of_items = number_of_items; + + /* Linked list links all structures in ascending order.*/ + for(i=0;i<number_of_items;i++) + { + ls->linked_list[i] = i+1; + } + + ls->linked_list[number_of_items - 1] = 0xFFFFFFFF; /* Invalid link.*/ + + /* Next avail is 0.*/ + ls->next_avail_num = 0; + + /* Number of allocated items is null.*/ + ls->allocated_items = 0; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctapiLlmAllocInfo. +| +| Description: This function returns the number of free and allocated +| block in the LLMAN list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| *allocated_items UINT32 Number of allocated items. +| *available_items UINT32 Number of available items. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctapiLlmAllocInfo(void * l,UINT32 * allocated_items,UINT32 * available_items) +{ + LLM_ALLOC* ls; + + /* Build the structure before starting.*/ + ls = (LLM_ALLOC *)l; + ls->linked_list = (UINT32 *)((BYTE *)ls + sizeof(LLM_ALLOC)); + + *allocated_items = ls->allocated_items; + *available_items = ls->number_of_items - ls->allocated_items; + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctapiLlmAllocInfo. +| +| Description: This function allocates the resource indicated by blocknum. +| If the resource can be allocated then GENERIC_OK is returned. +| Else an error. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| *block_num UINT32 The resource to be allocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctapiLlmAllocAlloc(void * l,UINT32 * blocknum) +{ + LLM_ALLOC* ls; + UINT32 allocated_block; + UINT32* node; + + /* Build the structure before starting.*/ + ls = (LLM_ALLOC *)l; + ls->linked_list = (UINT32 *)((BYTE *)ls + sizeof(LLM_ALLOC)); + + /* Get next available block number.*/ + allocated_block = ls->next_avail_num; + + /* Check if block is invalid.*/ + if (allocated_block == 0xFFFFFFFF) + { + /* Make blocknum NULL.*/ + *blocknum = 0xFFFFFFFF; + + return(OCTAPI_LLM_NO_STRUCTURES_LEFT); + } + + node = &ls->linked_list[allocated_block]; + + /* Copy next block number.*/ + ls->next_avail_num = *node; + + /* Tag as used the current block number.*/ + *node = 0xFFFFFFFE; + + /* Return proper block number.*/ + *blocknum = allocated_block; + + /* Update block usage number.*/ + ls->allocated_items++; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctapiLlmAllocDealloc. +| +| Description: This function deallocates the resource indicated by blocknum. +| If the resource is not already allocated an error is returned. +| Else GENERIC_OK is returned. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| block_num UINT32 The resource to be deallocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctapiLlmAllocDealloc(void * l,UINT32 blocknum) +{ + LLM_ALLOC* ls; + UINT32* node; + + /* Build the structure before starting.*/ + ls = (LLM_ALLOC *)l; + ls->linked_list = (UINT32 *)((BYTE *)ls + sizeof(LLM_ALLOC)); + + /* Check for null item pointer.*/ + if (blocknum == 0xFFFFFFFF) return(GENERIC_OK); + + /* Check if blocknum is within specified item range.*/ + if (blocknum >= ls->number_of_items) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + + node = &ls->linked_list[blocknum]; + + /* Check if block is really used as of now.*/ + if (*node != 0xFFFFFFFE) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Add link to list.*/ + *node = ls->next_avail_num; + + /* Point to returned block.*/ + ls->next_avail_num = blocknum; + + /* Update block usage number.*/ + ls->allocated_items--; + + return(GENERIC_OK); +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmAllocGetSize. +| +| Description: This function determines the amount of memory needed to +| manage the allocation of a fixed amount of resources. +| The memory is measured in bytes. +| +| This version is a time manage version of llman. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| number_of_items UINT32 The number of resources to be allocated. +| *l_size UINT32 UINT32 The amount of memory needed, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmAllocGetSize(UINT32 number_of_items,UINT32 * l_size) +{ + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + + *l_size = (sizeof(TLLM_ALLOC)) + (number_of_items * sizeof(TLLM_ALLOC_NODE)); + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmAllocInit. +| +| Description: This function intializes the TLLM_ALLOC structure. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| **l void The memory used by the LLM_ALLOC structure. +| number_of_items UINT32 The number of resources to be allocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmAllocInit(void ** l,UINT32 number_of_items) +{ + TLLM_ALLOC* ls; + UINT32 i; + + /* Check the number of items required.*/ + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + + /* If no memory has been allocated yet.*/ + if (*l == NULL) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Build the structure before starting.*/ + ls = (TLLM_ALLOC *)(*l); + ls->linked_list = (TLLM_ALLOC_NODE *)((BYTE *)ls + sizeof(TLLM_ALLOC)); + + ls->number_of_items = number_of_items; + + /* Linked list links all structures in ascending order.*/ + for(i=0;i<number_of_items;i++) + { + ls->linked_list[i].value = i+1; + } + + ls->linked_list[number_of_items - 1].value = 0xFFFFFFFF; /* Invalid link.*/ + + /* Next avail is 0.*/ + ls->next_avail_num = 0; + + /* Number of allocated items is null.*/ + ls->allocated_items = 0; + + /* Set the number of timeout entry.*/ + ls->number_of_timeout = 0; + + /* Next timeout is 0.*/ + ls->next_timeout_num = 0xFFFFFFFF; + ls->last_timeout_num = 0xFFFFFFFF; + + /* Set the known time to 0.*/ + ls->last_known_time[ 0 ] = 0; + ls->last_known_time[ 1 ] = 0; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmAllocInfo. +| +| Description: This function returns the number of free and allocated +| block in the TLLMAN list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| *allocated_items UINT32 Number of allocated items. +| *available_items UINT32 Number of available items. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmAllocInfo(void * l,UINT32 * allocated_items,UINT32 * available_items) +{ + TLLM_ALLOC* ls; + + /* Build the structure before starting.*/ + ls = (TLLM_ALLOC *)l; + *allocated_items = ls->allocated_items; + *available_items = ls->number_of_items - ls->allocated_items; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmAllocAlloc. +| +| Description: This function allocates the resource indicated by blocknum. +| If the resource can be allocated then GENERIC_OK is returned. +| Else an error. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| *block_num UINT32 The resource to be allocated. +| *current_time UINT32 +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmAllocAlloc(void * l,UINT32 * blocknum, UINT32 *current_time) +{ + TLLM_ALLOC* ls; + UINT32 allocated_block; + TLLM_ALLOC_NODE* node; + + /* Build the structure before starting.*/ + ls = (TLLM_ALLOC *)l; + ls->linked_list = (TLLM_ALLOC_NODE *)((BYTE *)ls + sizeof(TLLM_ALLOC)); + + if ( ls->allocated_items == ls->number_of_items && + ls->next_timeout_num != 0xFFFFFFFF ) + { + UINT32 l_ulResult; + l_ulResult = OctApiTllmCheckTimeoutList( ls, current_time ); + if ( l_ulResult != GENERIC_OK ) + return l_ulResult; + } + + /* Get next available block number.*/ + allocated_block = ls->next_avail_num; + + /* Check if block is invalid.*/ + if (allocated_block == 0xFFFFFFFF) + { + /* Make blocknum NULL.*/ + *blocknum = 0xFFFFFFFF; + + return(OCTAPI_LLM_NO_STRUCTURES_LEFT); + } + + node = &ls->linked_list[allocated_block]; + + /* Copy next block number.*/ + ls->next_avail_num = node->value; + + /* Tag as used the current block number.*/ + node->value = 0xFFFFFFFE; + + /* Return proper block number.*/ + *blocknum = allocated_block; + + /* Update block usage number.*/ + ls->allocated_items++; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmAllocDealloc. +| +| Description: This function deallocates the resource indicated by blocknum. +| If the resource is not already allocated an error is returned. +| Else GENERIC_OK is returned. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_ALLOC structure. +| block_num UINT32 The resource to be deallocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmAllocDealloc(void * l,UINT32 blocknum, UINT32 timeout_value, UINT32 current_time[2]) +{ + TLLM_ALLOC* ls; + TLLM_ALLOC_NODE* node; + UINT32 l_ulResult; + + /* Build the structure before starting.*/ + ls = (TLLM_ALLOC *)l; + ls->linked_list = (TLLM_ALLOC_NODE *)((BYTE *)ls + sizeof(TLLM_ALLOC)); + + /* Check for null item pointer.*/ + if (blocknum == 0xFFFFFFFF) return(GENERIC_OK); + + /* Check if blocknum is within specified item range.*/ + if (blocknum >= ls->number_of_items) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + + if ( ls->next_timeout_num != 0xFFFFFFFF ) + { + l_ulResult = OctApiTllmCheckTimeoutList( ls, current_time ); + if ( l_ulResult != GENERIC_OK ) + return l_ulResult; + } + + node = &ls->linked_list[blocknum]; + + /* Check if block is really used as of now.*/ + if (node->value != 0xFFFFFFFE) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Add link to timeout list.*/ + if ( ls->last_timeout_num != 0xFFFFFFFF ) + { + TLLM_ALLOC_NODE* last_node; + + /* insert the node at the end of the list.*/ + node->value = 0xFFFFFFFF; + last_node = &ls->linked_list[ ls->last_timeout_num ]; + last_node->value = blocknum; + } + else + { + /* The node is alone in the list.*/ + node->value = 0xFFFFFFFF; + ls->next_timeout_num = blocknum; + } + + ls->last_timeout_num = blocknum; + ls->number_of_timeout++; + + /* Set the timeout time of the node.*/ + l_ulResult = OctApiLmAdd( current_time, 1, &timeout_value, 0, node->timeout, 1 ); + if (l_ulResult != GENERIC_OK) + return(l_ulResult); + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiTllmCheckTimeoutList. +| +| Description: This function will verify if the timeout time +| of all the node present in the timeout list are bigger +| then the current time. If so the node will be returned +| ot the free node list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *ls TLLM_ALLOC The memory used by the TLLM_ALLOC structure. +| current_time UINT32[2] The current time in msec. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiTllmCheckTimeoutList(TLLM_ALLOC *ls, UINT32 current_time[2]) +{ + UINT32 result; + UINT32 fConditionFlag = TRUE; + + /* Free-up any pending memory before trying the allocation:*/ + if ((ls->last_known_time[0] != current_time[0] || + ls->last_known_time[1] != current_time[1]) && + (current_time[1] != 0 || current_time[0] != 0)) /* Time has changed.*/ + { + TLLM_ALLOC_NODE *pcurrent_node; + UINT32 current_num; + USHORT neg; + + /* Remember time for next time!*/ + ls->last_known_time[0] = current_time[0]; + ls->last_known_time[1] = current_time[1]; + + + while ( fConditionFlag == TRUE ) + { + /* Get a node from the timeout list.*/ + pcurrent_node = &ls->linked_list[ ls->next_timeout_num ]; + current_num = ls->next_timeout_num; + + /* Check if first node has timeout.*/ + result = OctApiLmCompare(current_time,1,pcurrent_node->timeout ,1,&neg); + if (result != GENERIC_OK) return(result); + + /* if the timeout tiem was exceeded, set the block as free.*/ + if ( neg == FALSE ) + { + /* set the next node pointer.*/ + ls->next_timeout_num = pcurrent_node->value; + ls->number_of_timeout--; + + /* reset the last pointer of the timeout list.*/ + if ( ls->number_of_timeout == 0 ) + ls->last_timeout_num = 0xFFFFFFFF; + + /* return the node the free list.*/ + pcurrent_node->value = ls->next_avail_num; + ls->next_avail_num = current_num; + ls->allocated_items--; + } + else /* node not in timeout */ + { + fConditionFlag = FALSE; + break; + } + + if ( ls->next_timeout_num == 0xFFFFFFFF ) + { + fConditionFlag = FALSE; + break; /* end of timeout list.*/ + } + } + } + + return(GENERIC_OK); +} +/**************************************** llm_alloc section **********************************************/ + + + + + + + +/**************************************** llm_list section **********************************************/ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListGetSize +| +| Description: This function determines the amount of memory needed by +| the LLM_LIST structure to manage the allocation of +| number_of_items number of resources. The memory is +| measured in bytes. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| number_of_items UINT32 The number of resources to be allocated +| amongst all linked-lists. +| number_of_lists UINT32 The maximum number of linked-lists that +| can be allocated. +| *l_size UINT32 UINT32 The amount of memory needed, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListGetSize(UINT32 number_of_items,UINT32 number_of_lists,UINT32 user_info_size,UINT32 * l_size) +{ + UINT32 head_alloc_size; + UINT32 result; + UINT32 user_info_size_roundup; + + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + if (number_of_lists == 0) return(GENERIC_BAD_PARAM); + if (user_info_size == 0) return(GENERIC_BAD_PARAM); + + user_info_size_roundup = ((user_info_size + 3) / 4) * 4; + + result = OctapiLlmAllocGetSize(number_of_lists,&head_alloc_size); + if(result != GENERIC_OK) return(result); + + *l_size = sizeof(LLM_LIST) + (number_of_lists * sizeof(LLM_LIST_HEAD)) + head_alloc_size + (number_of_items * (sizeof(LLM_LIST_ITEM) + user_info_size_roundup - 4)); + + return(GENERIC_OK); +} + +LLM_LIST_ITEM * OctApiLlmListGetItemPointer(LLM_LIST * ls, UINT32 item_number) +{ + return (LLM_LIST_ITEM *) (((BYTE *)ls->li) + (ls->item_size * item_number)) ; +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListInit. +| +| Description: This function intializes the LLM_TALLOC structure. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| number_of_items UINT32 The number of resources to be allocated +| amongst all linked-lists. +| number_of_lists UINT32 The maximum number of linked-lists that +| can be allocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListInit(void ** l,UINT32 number_of_items,UINT32 number_of_lists,UINT32 user_info_size) +{ + LLM_LIST* ls; + LLM_LIST_ITEM* item; + UINT32 i; + UINT32 head_alloc_size; + UINT32 result; + UINT32 user_info_size_roundup; + UINT32 total_lists; + BYTE* lsbyte; + + + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + if (number_of_lists == 0) return(GENERIC_BAD_PARAM); + if (user_info_size == 0) return(GENERIC_BAD_PARAM); + + user_info_size_roundup = ((user_info_size + 3) / 4) * 4; + + /* Get the size of the Alloc structure used to manage head of list structures.*/ + result = OctapiLlmAllocGetSize(number_of_lists,&head_alloc_size); + if(result != GENERIC_OK) return(result); + + if (*l == NULL) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)(*l); + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + /* Initialize parameters in the structure.*/ + ls->head_alloc_size = head_alloc_size; + ls->user_info_bytes = user_info_size; + ls->user_info_size = user_info_size_roundup; + ls->total_items = number_of_items; + ls->assigned_items = 0; + ls->total_lists = number_of_lists; + ls->assigned_lists = 0; + ls->next_empty_item = 0; + ls->item_size = sizeof(LLM_LIST_ITEM) + user_info_size_roundup - 4; + + /* Complete the build!*/ + ls = (LLM_LIST *)(*l); + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + /* Initialize the head of queue Alloc structure.*/ + result = OctapiLlmAllocInit(&(ls->list_head_alloc),number_of_lists); + if(result != GENERIC_OK) return(result); + + /* Initialize the linked list of the items:*/ + for(i=0; i<number_of_items; i++) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * i); + + if (i == (number_of_items - 1)) + item->forward_link = 0xFFFFFFFF; + else + item->forward_link = i + 1; + } + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListInfo. +| +| Description: This function returns the status of the LLM_LIST structure. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *allocated_lists UINT32 The number of linked_lists allocated. +| *free_lists UINT32 The number of linked_lists still free. +| *allocated_items UINT32 The number of items allocated to lists. +| *free_items UINT32 The number of items still free. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListInfo(void * l,UINT32 * allocated_lists,UINT32 * allocated_items, + UINT32 * free_lists,UINT32 * free_items) +{ + LLM_LIST* ls; + BYTE* lsbyte; + UINT32 total_lists; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + *allocated_items = ls->assigned_items; + *free_items = ls->total_items - ls->assigned_items; + + *allocated_lists = ls->assigned_lists; + *free_lists = ls->total_lists - ls->assigned_lists; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListCreate. +| +| Description: This function creates a linked list. The target which is +| allocated the newly created list can request additions +| or removals from the list later on. To target identifies +| its list with the returned list handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the new list, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListCreate(void * l,UINT32 * list_handle) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + UINT32 blocknum; + UINT32 total_lists; + UINT32 result; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + /* Get a list using the list head alloc structure.*/ + result = OctapiLlmAllocAlloc(ls->list_head_alloc, &blocknum); + if (result != GENERIC_OK) return(result); + + /* The handle is the block number.*/ + *list_handle = blocknum; + + /* Initialize the list head structure.*/ + lh = &ls->lh[blocknum]; + lh->list_length = 0; + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + lh->cache_item_number = 0xFFFFFFFF; + lh->cache_item_pointer = 0xFFFFFFFF; + + ls->assigned_lists++; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListDelete. +| +| Description: This function deletes the linked list indicated by the +| handle list_handle. Any items which are still allocated +| to the list are first deallocated. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the list. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListDelete(void * l,UINT32 list_handle) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + UINT32 total_lists; + UINT32 result; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (ls->lh[list_handle].list_length == 0xFFFFFFFF) return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + /* Release internal list header handle...*/ + result = OctapiLlmAllocDealloc(ls->list_head_alloc,list_handle); + if (result != GENERIC_OK) return(result); + + lh = &ls->lh[list_handle]; + + /* Deallocate all items in the list!*/ + if (lh->list_length != 0) + { + LLM_LIST_ITEM * item; + + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->tail_pointer); + + /* Release the items using only the links.*/ + item->forward_link = ls->next_empty_item; + ls->next_empty_item = lh->head_pointer; + + /* Remove items from item counter.*/ + ls->assigned_items -= lh->list_length; + } + + lh->list_length = 0xFFFFFFFF; + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + lh->cache_item_number = 0xFFFFFFFF; + lh->cache_item_pointer = 0xFFFFFFFF; + + ls->assigned_lists--; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListLength. +| +| Description: This function returns the number of items allocated to the +| list indicated by the handle list_handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| list_handle UINT32 The handle to the list. +| *number_of_items UINT32 The number of items in the list, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListLength(void * l,UINT32 list_handle, UINT32 * number_of_items_in_list) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + UINT32 total_lists; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + *number_of_items_in_list = lh->list_length; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListItemData +| +| Description: This function returns a pointer to the user data associated +| with an item. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| list_handle UINT32 The handle to the list. +| item_number UINT32 The number of the list node in question. +| **item_data_pnt void The pointer to the user data, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListItemData(void * l,UINT32 list_handle,UINT32 item_number,void ** item_data_pnt) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* item; + UINT32 cur_list_pnt; + UINT32 cur_list_num; + UINT32 total_lists; + UINT32 list_length; + BYTE* lsbyte; + UINT32 fConditionFlag = TRUE; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + list_length = lh->list_length; + + *item_data_pnt = NULL; + if (list_handle >= ls->total_lists) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (list_length == 0xFFFFFFFF) return(OCTAPI_LLM_INVALID_LIST_HANDLE); + if (list_length <= item_number) return(OCTAPI_LLM_ELEMENT_NOT_FOUND); + + /* Determine where the search will start.*/ + if (list_length == (item_number + 1)) /* Last item in list:*/ + { + cur_list_pnt = lh->tail_pointer; + cur_list_num = item_number; + } + else if (lh->cache_item_number <= item_number) /* Start at cache:*/ + { + cur_list_pnt = lh->cache_item_pointer; + cur_list_num = lh->cache_item_number; + } + else /* Start at beginning:*/ + { + cur_list_pnt = lh->head_pointer; + cur_list_num = 0; + } + + /* Start search from cur_list_pnt and cur_list_num.*/ + while ( fConditionFlag == TRUE ) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + + if (cur_list_num == item_number) /* Item number found.*/ + { + /* Write new cache entry.*/ + lh->cache_item_pointer = cur_list_pnt; + lh->cache_item_number = cur_list_num; + + /* Get item info.*/ + *item_data_pnt = (void *)item->user_info; + + return(GENERIC_OK); + } + else if(item->forward_link == 0xFFFFFFFF) /* End of list found?!?*/ + { + return(OCTAPI_LLM_INTERNAL_ERROR0); + } + else /* Item was not found, but continue searching.*/ + { + cur_list_pnt = item->forward_link; + } + + cur_list_num++; + } + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListInsertItem. +| +| Description: This function allocates a node to the linked list specified +| by the handle list_handle. The position of the new item +| can be specified. A position of 0xFFFFFFFF means append to the +| list( use the OCTAPI_LLM_LIST_APPEND define for clarity); +| a position of 0 mean insert at the begining of the list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the list. +| **item_data void Address of the user data space for this item. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListInsertItem(void * l,UINT32 list_handle,UINT32 item_number,void ** item_data_pnt) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* free_item; + UINT32 free_item_pnt; + UINT32 total_lists; + BYTE* lsbyte; + UINT32 fConditionFlag = TRUE; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + *item_data_pnt = NULL; + if (list_handle >= ls->total_lists) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM_INVALID_LIST_HANDLE); + if (lh->list_length < item_number && item_number != 0xFFFFFFFF) + return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (ls->next_empty_item == 0xFFFFFFFF) return(OCTAPI_LLM_NO_STRUCTURES_LEFT); + + /* Get a free item from the free item list!*/ + free_item_pnt = ls->next_empty_item; + free_item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * free_item_pnt); + ls->next_empty_item = free_item->forward_link; + + if (item_number == 0xFFFFFFFF) + item_number = lh->list_length; + + if (lh->list_length == 0) /* First item and only item:*/ + { + free_item->forward_link = 0xFFFFFFFF; + lh->tail_pointer = free_item_pnt; + lh->head_pointer = free_item_pnt; + } + else if (item_number == 0) /* First item and but list not empty:*/ + { + free_item->forward_link = lh->head_pointer; + lh->head_pointer = free_item_pnt; + } + else if (item_number == lh->list_length) /* Append:*/ + { + LLM_LIST_ITEM * last_item; + last_item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->tail_pointer); + + last_item->forward_link = free_item_pnt; + free_item->forward_link = 0xFFFFFFFF; + lh->tail_pointer = free_item_pnt; + } + else /* Insert:*/ + { + LLM_LIST_ITEM * last_item = NULL; + LLM_LIST_ITEM * item; + UINT32 last_list_pnt; + UINT32 cur_list_pnt; + UINT32 cur_list_num; + + if (lh->cache_item_number < item_number) /* Start at cache:*/ + { + cur_list_pnt = lh->cache_item_pointer; + cur_list_num = lh->cache_item_number; + } + else /* Start at beginning:*/ + { + cur_list_pnt = lh->head_pointer; + cur_list_num = 0; + } + + last_list_pnt = 0xFFFFFFFF; + + /* Start search from cur_list_pnt and cur_list_num.*/ + while ( fConditionFlag == TRUE ) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + + if (cur_list_num == item_number) /* Item number found.*/ + { + if (last_list_pnt == 0xFFFFFFFF) return(OCTAPI_LLM_INTERNAL_ERROR1); + + free_item->forward_link = cur_list_pnt; + last_item->forward_link = free_item_pnt; + + fConditionFlag = FALSE; + break; + } + else if (item->forward_link == 0xFFFFFFFF) /* End of list found?!?*/ + { + return(OCTAPI_LLM_INTERNAL_ERROR0); + } + else /* Item was not found, but continue searching.*/ + { + last_item = item; + last_list_pnt = cur_list_pnt; + cur_list_pnt = item->forward_link; + } + + cur_list_num++; + } + } + + /* Increase the list length.*/ + lh->list_length++; + ls->assigned_items++; + *item_data_pnt = (void *)free_item->user_info; + + /* Write new cache entry.*/ + lh->cache_item_pointer = free_item_pnt; + lh->cache_item_number = item_number; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListCreateFull. +| +| Description: This function allocates the desired number of nodes to +| the linked list specified by the handle list_handle. +| The position of the new item can be specified. A +| position of 0xFFFFFFFF means append to the list (use the +| OCTAPI_LLM_LIST_APPEND define for clarity); a position +| of 0 means insert at the begining of the list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the list. +| **item_data void Address of the user data space for this item. +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListCreateFull(void* l, UINT32 list_length, UINT32* plist_handle) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* free_item; + LLM_LIST_ITEM* last_item = NULL; + UINT32 free_item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + UINT32 list_handle; + UINT32 list_length_m1; + UINT32 next_empty_item; + UINT32 result; + UINT32 i; + BYTE* lsbyte; + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Build the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Make sure another list can be created.*/ + if (ls->assigned_lists == ls->total_lists) + return(OCTAPI_LLM_ELEMENT_ALREADY_ASSIGNED); + + /* Make sure there are enough free nodes to fill the new list.*/ + if (list_length > (ls->total_items - ls->assigned_items)) + return(OCTAPI_LLM_ELEMENT_ALREADY_ASSIGNED); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Create list (i.e. get a list using the list head alloc structure.*/ + result = OctapiLlmAllocAlloc(ls->list_head_alloc, &list_handle); + if (result != GENERIC_OK) return(result); + + /* Initialize the list head structure.*/ + lh = &ls->lh[list_handle]; + lh->list_length = 0; + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + lh->cache_item_number = 0xFFFFFFFF; + lh->cache_item_pointer = 0xFFFFFFFF; + + ls->assigned_lists++; + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Add the number of requested nodes to the list.*/ + lh = &ls->lh[list_handle]; + list_length_m1 = list_length - 1; + next_empty_item = ls->next_empty_item; + + for (i=0; i<list_length; i++) + { + /* Get a free item from the free item list!*/ + free_item_pnt = next_empty_item; + free_item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * free_item_pnt); + next_empty_item = free_item->forward_link; + + /* Branch according to whether the node is the first in list, last, or in + the middle.*/ + if (i == 0) + { + /* First item.*/ + free_item->forward_link = 0xFFFFFFFF; + lh->head_pointer = free_item_pnt; + lh->tail_pointer = free_item_pnt; + } + else if (i == list_length_m1) + { + /* Last item.*/ + last_item->forward_link = free_item_pnt; + free_item->forward_link = 0xFFFFFFFF; + lh->tail_pointer = free_item_pnt; + } + else + { + /* Node somewhere in the middle.*/ + last_item->forward_link = free_item_pnt; + } + + /* Store pointer to free item as pointer to last item (for next iteration).*/ + last_item = free_item; + } + + /* Store new value of next_empty_item.*/ + ls->next_empty_item = next_empty_item; + + /* Write new cache entry.*/ + lh->cache_item_pointer = free_item_pnt; + lh->cache_item_number = list_length_m1; + + /* Set the list length.*/ + lh->list_length = list_length; + ls->assigned_items += list_length; + + /* Return pointer to new list.*/ + *plist_handle = list_handle; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListAppendItems. +| +| Description: This function allocates the desired number of nodes to +| the linked list specified by the handle list_handle. +| The position of the new item can be specified. A +| position of 0xFFFFFFFF means append to the list (use the +| OCTAPI_LLM_LIST_APPEND define for clarity); a position +| of 0 means insert at the begining of the list. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the list. +| **item_data void Address of the user data space for this item. +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListAppendItems(void* l, UINT32 list_handle, UINT32 num_items) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* item_list; + LLM_LIST_ITEM* curr_item = NULL; + LLM_LIST_ITEM* free_item; + UINT32 curr_item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + UINT32 next_empty_item; + UINT32 item_size; + UINT32 i; + BYTE* lsbyte; + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Build the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Make sure list handle is valid.*/ + if (list_handle >= ls->total_lists) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + /* Make sure there is at least one item.*/ + if (num_items == 0) + return(OCTAPI_LLM_INVALID_PARAMETER); + + /* Make sure there are enough free nodes.*/ + if (num_items > (ls->total_items - ls->assigned_items)) + return(OCTAPI_LLM_NO_STRUCTURES_LEFT); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Get pointer to list structure.*/ + lh = &ls->lh[list_handle]; + if (lh->list_length == 0xFFFFFFFF) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Add the number of requested nodes to the list.*/ + item_list = ls->li; + item_size = ls->item_size; + next_empty_item = ls->next_empty_item; + + for (i=0; i<num_items; i++) + { + if (i == 0) + { + if (lh->head_pointer == 0xFFFFFFFF) + { + /* Current and next items are one and the same!*/ + curr_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Set new head and tail pointers.*/ + lh->head_pointer = next_empty_item; + lh->tail_pointer = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next item.*/ + next_empty_item = curr_item->forward_link; + + /* Set first item to be only item in list.*/ + curr_item->forward_link = 0xFFFFFFFF; + } + else + { + /* Get a free item from the free item list!*/ + curr_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * lh->tail_pointer); + free_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Have current item point to next empty item.*/ + curr_item->forward_link = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next_empty_item.*/ + next_empty_item = free_item->forward_link; + + /* Update pointers to current item and free item.*/ + curr_item = free_item; + } + } + else + { + /* Update pointers to current item and free item.*/ + free_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Have current item point to next empty item.*/ + curr_item->forward_link = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next_empty_item.*/ + next_empty_item = free_item->forward_link; + + /* Update pointers to current item and free item.*/ + curr_item = free_item; + } + } + + /* Terminate list.*/ + if ( curr_item != NULL ) + curr_item->forward_link = 0xFFFFFFFF; + + /* Update llman structure variables.*/ + ls->next_empty_item = next_empty_item; + ls->assigned_items += num_items; + + /* Update list variables.*/ + lh->list_length += num_items; + lh->cache_item_pointer = curr_item_pnt; + lh->cache_item_number = lh->list_length - 1; + lh->tail_pointer = curr_item_pnt; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListAppendAndSetItems. +| +| Description: +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListAppendAndSetItems(void* l, UINT32 list_handle, UINT32 num_items, void* data_list) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* item_list; + LLM_LIST_ITEM* curr_item = NULL; + LLM_LIST_ITEM* free_item; + UINT32 curr_item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + UINT32 next_empty_item; + UINT32 user_info_bytes; + UINT32 item_size; + UINT32 i; + BYTE* lsbyte; + void* data_item; + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Build the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Make sure list handle is valid.*/ + if (list_handle >= ls->total_lists) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + /* Make sure there is at least one item.*/ + if (num_items == 0) + return(OCTAPI_LLM_INVALID_PARAMETER); + + /* Make sure there are enough free nodes.*/ + if (num_items > (ls->total_items - ls->assigned_items)) + return(OCTAPI_LLM_NO_STRUCTURES_LEFT); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Get pointer to list structure.*/ + lh = &ls->lh[list_handle]; + if (lh->list_length == 0xFFFFFFFF) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Add the number of requested nodes to the list.*/ + item_list = ls->li; + user_info_bytes = ls->user_info_bytes; + item_size = ls->item_size; + next_empty_item = ls->next_empty_item; + data_item = data_list; + + for (i=0; i<num_items; i++) + { + if (i == 0) + { + if (lh->head_pointer == 0xFFFFFFFF) + { + /* Current and next items are one and the same!*/ + curr_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Set new head and tail pointers.*/ + lh->head_pointer = next_empty_item; + lh->tail_pointer = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next item.*/ + next_empty_item = curr_item->forward_link; + + /* Set first item to be only item in list.*/ + curr_item->forward_link = 0xFFFFFFFF; + } + else + { + /* Get a free item from the free item list!*/ + curr_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * lh->tail_pointer); + free_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Have current item point to next empty item.*/ + curr_item->forward_link = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next_empty_item.*/ + next_empty_item = free_item->forward_link; + + /* Update pointers to current item and free item.*/ + curr_item = free_item; + } + } + else + { + /* Update pointers to current item and free item.*/ + free_item = (LLM_LIST_ITEM *)((BYTE *)item_list + item_size * next_empty_item); + + /* Have current item point to next empty item.*/ + curr_item->forward_link = next_empty_item; + + /* Update current item pnt.*/ + curr_item_pnt = next_empty_item; + + /* Update next_empty_item.*/ + next_empty_item = free_item->forward_link; + + /* Update pointers to current item and free item.*/ + curr_item = free_item; + } + + /* Copy data to new item.*/ + OctApiLlmMemCpy(curr_item->user_info, data_item, user_info_bytes); + + /* Update data_item pointer for next iteration (item).*/ + data_item = (void *)((BYTE *)data_item + user_info_bytes); + } + + + /* Terminate list.*/ + if ( curr_item != NULL ) + curr_item->forward_link = 0xFFFFFFFF; + + /* Update llman structure variables.*/ + ls->next_empty_item = next_empty_item; + ls->assigned_items += num_items; + + /* Update list variables.*/ + lh->list_length += num_items; + lh->cache_item_pointer = curr_item_pnt; + lh->cache_item_number = lh->list_length - 1; + lh->tail_pointer = curr_item_pnt; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListSetItems. +| +| Description: This function takes a start entry (0 to length - 1), +| a pointer to a list of data (each item of list is the +| size of one data unit, specified at init), and the +| length of the data list. From this, the data will be +| copied from the data list to the linked list, from +| entry start_entry to (start_entry + data_length - 1). +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListSetItems(void* l, UINT32 list_handle, UINT32 start_item, UINT32 data_length, void* pdata_list) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* item = NULL; + UINT32 total_lists; + UINT32 item_pnt = 0xFFFFFFFF; + UINT32 i, j; + BYTE* lsbyte; + void* pdata_item = NULL; + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Build the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Make sure list handle is valid.*/ + if (list_handle >= ls->total_lists) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + lh = &ls->lh[list_handle]; + if (lh->list_length == 0xFFFFFFFF) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + /* Make sure the start_entry is within limits.*/ + if (start_item >= lh->list_length) + return(OCTAPI_LLM_INVALID_PARAMETER); + + /* Make sure the end_entry is within limits.*/ + lh = &ls->lh[list_handle]; + if ((start_item + data_length) > lh->list_length) + return(OCTAPI_LLM_INVALID_PARAMETER); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Set the data of each node.*/ + for (i=0; i<data_length; i++) + { + /* Obtain pointer to current item.*/ + if (i == 0) + { + /* Check if location of start item is already cached. If not, must search + for it manually.*/ + if (start_item == (lh->cache_item_number + 1)) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->cache_item_pointer); + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + } + else + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->head_pointer); + item_pnt = lh->head_pointer; + for (j=0; j<start_item; j++) + { + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + } + } + + pdata_item = (void *)((BYTE *)pdata_list + (i * ls->user_info_bytes)); + } + else + { + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + + pdata_item = (void *)((BYTE *)pdata_item + ls->user_info_bytes); + } + + /* Set the value of the item's user data.*/ + OctApiLlmMemCpy(item->user_info, pdata_item, ls->user_info_bytes); + } + + /* Write new cache entry.*/ + lh->cache_item_pointer = item_pnt; + lh->cache_item_number = start_item + data_length - 1; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListCopyData. +| +| Description: This function takes a start entry (0 to length - 1), +| a pointer to a list of data (each item of list is the +| size of one data unit, specified at init), and the +| length of the data list. From this, the data will be +| copied from the linked list to the data list, from +| entry start_entry of the linked list to +| (start_entry + data_length - 1). +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListCopyData(void* l, UINT32 list_handle, UINT32 start_item, UINT32 data_length, void* pdata_list) +{ + LLM_LIST* ls; + LLM_LIST_HEAD* lh; + LLM_LIST_ITEM* item = NULL; + UINT32 item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + UINT32 i, j; + BYTE* lsbyte; + void* pdata_item = NULL; + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Build the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Make sure list handle is valid.*/ + if (list_handle >= ls->total_lists) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + lh = &ls->lh[list_handle]; + if (lh->list_length == 0xFFFFFFFF) + return(OCTAPI_LLM_INVALID_LIST_HANDLE); + + /* Make sure the start_entry is within limits.*/ + if (start_item >= lh->list_length) + return(OCTAPI_LLM_INVALID_PARAMETER); + + /* Make sure the end_entry is within limits.*/ + lh = &ls->lh[list_handle]; + if ((start_item + data_length) > lh->list_length) + return(OCTAPI_LLM_INVALID_PARAMETER); + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + + + + /*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/ + /* Set the data of each node.*/ + for (i=0; i<data_length; i++) + { + /* Obtain pointer to current item.*/ + if (i == 0) + { + /* Check if location of start item is already cached. If not, must search + for it manually.*/ + if (start_item == (lh->cache_item_number + 1)) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->cache_item_pointer); + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + } + else + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->head_pointer); + for (j=0; j<start_item; j++) + { + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + } + } + + pdata_item = (void *)((BYTE *)pdata_list + (i * ls->user_info_bytes)); + } + else + { + item_pnt = item->forward_link; + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * item_pnt); + + pdata_item = (void *)((BYTE *)pdata_item + ls->user_info_bytes); + } + + /* Set the value of the item's user data.*/ + OctApiLlmMemCpy(pdata_item, item->user_info, ls->user_info_bytes); + } + + /* Write new cache entry.*/ + lh->cache_item_pointer = item_pnt; + lh->cache_item_number = start_item + data_length - 1; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListRemoveItem. +| +| Description: This function deallocates a node of the linked list specified +| by the handle list_handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| list_handle UINT32 The handle to the list. +| item_number UINT32 The number of the item to be removed. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlmListRemoveItem(void * l,UINT32 list_handle,UINT32 item_number) +{ + LLM_LIST* ls; + LLM_LIST_ITEM* freed_item = NULL; + LLM_LIST_HEAD* lh; + UINT32 freed_item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + BYTE* lsbyte; + UINT32 fConditionFlag = TRUE; + + /* Built the structure based on the base address:*/ + ls = (LLM_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM_LIST_HEAD *)(lsbyte + sizeof(LLM_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD))); + ls->li = (LLM_LIST_ITEM *)(lsbyte + sizeof(LLM_LIST) + (total_lists * sizeof(LLM_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM_INVALID_LIST_HANDLE); + if (lh->list_length <= item_number) return(OCTAPI_LLM_BLOCKNUM_OUT_OF_RANGE); + + if (item_number == 0 && lh->list_length == 1)/* First item and only item:*/ + { + freed_item_pnt = lh->head_pointer; + freed_item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * freed_item_pnt); + + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + + lh->cache_item_number = 0xFFFFFFFF; + lh->cache_item_pointer = 0xFFFFFFFF; + } + else if (item_number == 0) /* First item and but list not empty:*/ + { + freed_item_pnt = ls->lh[list_handle].head_pointer; + freed_item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * freed_item_pnt); + + lh->head_pointer = freed_item->forward_link; + + lh->cache_item_number = 0; + lh->cache_item_pointer = freed_item->forward_link; + } + else /* Discard non-first item! (Caution: this could be the last item!)*/ + { + LLM_LIST_ITEM * last_item = NULL; + LLM_LIST_ITEM * item; + UINT32 last_list_pnt; + UINT32 cur_list_pnt; + UINT32 cur_list_num; + + if (lh->cache_item_number < item_number) /* Start at cache:*/ + { + cur_list_pnt = lh->cache_item_pointer; + cur_list_num = lh->cache_item_number; + } + else /* Start at beginning:*/ + { + cur_list_pnt = lh->head_pointer; + cur_list_num = 0; + } + + last_list_pnt = 0xFFFFFFFF; + + /* Start search from cur_list_pnt and cur_list_num.*/ + while( fConditionFlag == TRUE ) + { + item = (LLM_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + + if (cur_list_num == item_number) /* Item number found.*/ + { + if (last_list_pnt == 0xFFFFFFFF) return(OCTAPI_LLM_INTERNAL_ERROR1); + + if ((item_number + 1) == lh->list_length) + { + lh->tail_pointer = last_list_pnt; + last_item->forward_link = 0xFFFFFFFF; + } + else + { + last_item->forward_link = item->forward_link; + } + freed_item_pnt = cur_list_pnt; + freed_item = item; + + /* Reset cache entry.*/ + lh->cache_item_pointer = last_list_pnt; + lh->cache_item_number = cur_list_num - 1; + + fConditionFlag = FALSE; + break; + } + else if (item->forward_link == 0xFFFFFFFF) /* End of list found?!?*/ + { + return(OCTAPI_LLM_INTERNAL_ERROR0); + } + else /* Item was not found, but continue searching.*/ + { + last_item = item; + last_list_pnt = cur_list_pnt; + cur_list_pnt = item->forward_link; + } + + cur_list_num++; + } + } + + /* Decrease the list length.*/ + lh->list_length--; + ls->assigned_items--; + + /* Return free block to free block list:*/ + freed_item->forward_link = ls->next_empty_item; + ls->next_empty_item = freed_item_pnt; + + return(GENERIC_OK); +} + +/**************************************** llm2 function section *****************************************/ + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListGetSize +| +| Description: This function determines the amount of memory needed by +| the LLM2_LIST structure to manage the allocation of +| number_of_items number of resources. The memory is +| measured in bytes. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| number_of_items UINT32 The number of resources to be allocated +| amongst all linked-lists. +| number_of_lists UINT32 The maximum number of linked-lists that +| can be allocated. +| *l_size UINT32 UINT32 The amount of memory needed, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListGetSize(UINT32 number_of_items,UINT32 number_of_lists,UINT32 user_info_size,UINT32 * l_size) +{ + UINT32 head_alloc_size; + UINT32 result; + UINT32 user_info_size_roundup; + + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + if (number_of_lists == 0) return(GENERIC_BAD_PARAM); + if (user_info_size == 0) return(GENERIC_BAD_PARAM); + + user_info_size_roundup = ((user_info_size + 3) / 4) * 4; + + result = OctapiLlmAllocGetSize(number_of_lists,&head_alloc_size); + if(result != GENERIC_OK) return(result); + + *l_size = sizeof(LLM2_LIST) + (number_of_lists * sizeof(LLM2_LIST_HEAD)) + head_alloc_size + (number_of_items * (sizeof(LLM2_LIST_ITEM) + user_info_size_roundup - 4)); + + return(GENERIC_OK); +} + +LLM2_LIST_ITEM * OctApiLlm2ListGetItemPointer(LLM2_LIST * ls, UINT32 item_number) +{ + return (LLM2_LIST_ITEM *) (((BYTE *)ls->li) + (ls->item_size * item_number)) ; +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListInit. +| +| Description: This function intializes the LLM2_TALLOC structure. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| number_of_items UINT32 The number of resources to be allocated +| amongst all linked-lists. +| number_of_lists UINT32 The maximum number of linked-lists that +| can be allocated. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListInit(void ** l,UINT32 number_of_items,UINT32 number_of_lists,UINT32 user_info_size) +{ + LLM2_LIST* ls; + LLM2_LIST_ITEM* item; + UINT32 i; + UINT32 head_alloc_size; + UINT32 result; + UINT32 user_info_size_roundup; + UINT32 total_lists; + BYTE* lsbyte; + + + if (number_of_items == 0) return(GENERIC_BAD_PARAM); + if (number_of_lists == 0) return(GENERIC_BAD_PARAM); + if (user_info_size == 0) return(GENERIC_BAD_PARAM); + + user_info_size_roundup = ((user_info_size + 3) / 4) * 4; + + /* Get the size of the Alloc structure used to manage head of list structures.*/ + result = OctapiLlmAllocGetSize(number_of_lists,&head_alloc_size); + if(result != GENERIC_OK) return(result); + + if (*l == NULL) return(OCTAPI_LLM_MEMORY_NOT_ALLOCATED); + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)(*l); + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + /* Initialize parameters in the structure.*/ + ls->head_alloc_size = head_alloc_size; + ls->user_info_bytes = user_info_size; + ls->user_info_size = user_info_size_roundup; + ls->total_items = number_of_items; + ls->assigned_items = 0; + ls->total_lists = number_of_lists; + ls->assigned_lists = 0; + ls->next_empty_item = 0; + ls->item_size = sizeof(LLM2_LIST_ITEM) + user_info_size_roundup - 4; + + /* Complete the build!*/ + ls = (LLM2_LIST *)(*l); + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + /* Initialize the head of queue Alloc structure.*/ + result = OctapiLlmAllocInit(&(ls->list_head_alloc),number_of_lists); + if(result != GENERIC_OK) return(result); + + /* Initialize the linked list of the items:*/ + for(i=0; i<number_of_items; i++) + { + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * i); + + if (i == (number_of_items - 1)) + item->forward_link = 0xFFFFFFFF; + else + item->forward_link = i + 1; + } + + return(GENERIC_OK); +} + + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListCreate. +| +| Description: This function creates a linked list. The target which is +| allocated the newly created list can request additions +| or removals from the list later on. To target identifies +| its list with the returned list handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM_LIST structure. +| *list_handle UINT32 The handle to the new list, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListCreate(void * l,UINT32 * list_handle) +{ + LLM2_LIST* ls; + LLM2_LIST_HEAD* lh; + UINT32 blocknum; + UINT32 total_lists; + UINT32 result; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + /* Get a list using the list head alloc structure.*/ + result = OctapiLlmAllocAlloc(ls->list_head_alloc, &blocknum); + if (result != GENERIC_OK) return(result); + + /* The handle is the block number.*/ + *list_handle = blocknum; + + /* Initialize the list head structure.*/ + lh = &ls->lh[blocknum]; + lh->list_length = 0; + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + + ls->assigned_lists++; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListDelete. +| +| Description: This function deletes the linked list indicated by the +| handle list_handle. Any items which are still allocated +| to the list are first deallocated. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| *list_handle UINT32 The handle to the list. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListDelete(void * l,UINT32 list_handle) +{ + LLM2_LIST* ls; + LLM2_LIST_HEAD* lh; + UINT32 total_lists; + UINT32 result; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM2_BLOCKNUM_OUT_OF_RANGE); + if (ls->lh[list_handle].list_length == 0xFFFFFFFF) return(OCTAPI_LLM2_INVALID_LIST_HANDLE); + + /* Release internal list header handle...*/ + result = OctapiLlmAllocDealloc(ls->list_head_alloc,list_handle); + if (result != GENERIC_OK) return(result); + + lh = &ls->lh[list_handle]; + + /* Deallocate all items in the list!*/ + if (lh->list_length != 0) + { + LLM2_LIST_ITEM * item; + + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * lh->tail_pointer); + + /* Release the items using only the links.*/ + item->forward_link = ls->next_empty_item; + ls->next_empty_item = lh->head_pointer; + + /* Remove items from item counter.*/ + ls->assigned_items -= lh->list_length; + } + + lh->list_length = 0xFFFFFFFF; + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + + ls->assigned_lists--; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmListLength. +| +| Description: This function returns the number of items allocated to the +| list indicated by the handle list_handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| list_handle UINT32 The handle to the list. +| *number_of_items UINT32 The number of items in the list, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListLength(void * l,UINT32 list_handle, UINT32 * number_of_items_in_list) +{ + LLM2_LIST* ls; + LLM2_LIST_HEAD* lh; + UINT32 total_lists; + BYTE* lsbyte; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM2_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM2_INVALID_LIST_HANDLE); + + *number_of_items_in_list = lh->list_length; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListItemData +| +| Description: This function returns a pointer to the user data associated +| with an item. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| list_handle UINT32 The handle to the list. +| item_number UINT32 The number of the list node in question. +| **item_data_pnt void The pointer to the user data, returned. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListItemData(void * l,UINT32 list_handle,UINT32 item_key,void ** item_data_pnt, PUINT32 item_number_pnt) +{ + LLM2_LIST* ls; + LLM2_LIST_HEAD* lh; + LLM2_LIST_ITEM* item; + UINT32 cur_list_pnt; + UINT32 cur_list_key = 0xFFFFFFFF; + UINT32 total_lists; + UINT32 list_length; + BYTE* lsbyte; + UINT32 fConditionFlag = TRUE; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + list_length = lh->list_length; + + *item_data_pnt = NULL; + *item_number_pnt = 0; + if (list_handle >= ls->total_lists) return(OCTAPI_LLM2_BLOCKNUM_OUT_OF_RANGE); + if (list_length == 0xFFFFFFFF) return(OCTAPI_LLM2_INVALID_LIST_HANDLE); + + /* Determine where the search will start.*/ + /* Start at beginning:*/ + cur_list_pnt = lh->head_pointer; + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + + /* Start search from cur_list_pnt and cur_list_num.*/ + while ( fConditionFlag == TRUE ) + { + if (cur_list_key == item_key) /* Item key found.*/ + { + /* Get item info.*/ + *item_data_pnt = (void *)item->user_info; + + return(GENERIC_OK); + } + else if(item->forward_link == 0xFFFFFFFF) /* End of list found?!?*/ + { + return(OCTAPI_LLM2_INTERNAL_ERROR0); + } + else /* Item was not found, but continue searching.*/ + { + cur_list_pnt = item->forward_link; + } + + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + (*item_number_pnt)++; + } + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListInsertItem. +| +| Description: This function allocates a node to the linked list specified +| by the handle list_handle. The position of the new item +| will be defined based on the key value. All entry are inserted +| in the list in incremental Key value. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| *list_handle UINT32 The handle to the list. +| **item_data void Address of the user data space for this item. +| **prev_item_data void Address of the user data space for the previous item. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListInsertItem(void * l,UINT32 list_handle,UINT32 item_key,void ** item_data_pnt, void ** prev_item_data_pnt, void ** prev_prev_item_data_pnt, PUINT32 insert_status_pnt ) +{ + LLM2_LIST* ls; + LLM2_LIST_HEAD* lh; + LLM2_LIST_ITEM* free_item; + UINT32 free_item_pnt; + UINT32 total_lists; + BYTE* lsbyte; + UINT32 ulPassCount = 0; + UINT32 fConditionFlag = TRUE; + + /* Set the status of the insertion.*/ + *insert_status_pnt = OCTAPI_LLM2_INSERT_ERROR; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + *item_data_pnt = NULL; + if (list_handle >= ls->total_lists) return(OCTAPI_LLM2_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM2_INVALID_LIST_HANDLE); + if (ls->next_empty_item == 0xFFFFFFFF) return(OCTAPI_LLM2_NO_STRUCTURES_LEFT); + + /* Get a free item from the free item list!*/ + free_item_pnt = ls->next_empty_item; + free_item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * free_item_pnt); + free_item->key = item_key; + ls->next_empty_item = free_item->forward_link; + + if (lh->list_length == 0) /* First item and only item:*/ + { + free_item->forward_link = 0xFFFFFFFF; + lh->tail_pointer = free_item_pnt; + lh->head_pointer = free_item_pnt; + *insert_status_pnt = OCTAPI_LLM2_INSERT_FIRST_NODE; + + /* There is no previous node information to return.*/ + *prev_item_data_pnt = NULL; + *prev_prev_item_data_pnt = NULL; + } + else /* Insert:*/ + { + LLM2_LIST_ITEM * last_last_item = NULL; + LLM2_LIST_ITEM * last_item = NULL; + LLM2_LIST_ITEM * item; + UINT32 last_list_pnt; + UINT32 cur_list_pnt; + UINT32 cur_list_key = 0xFFFFFFFF; + + /* Start at beginning:*/ + cur_list_pnt = lh->head_pointer; + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + + last_list_pnt = 0xFFFFFFFF; + + /* Start search from cur_list_pnt and cur_list_num.*/ + while ( fConditionFlag == TRUE ) + { + /* Increment the pass count to determine if the addition will happen next to last.*/ + ulPassCount++; + + if (cur_list_key >= item_key) /* Item new node between the last and the curent. */ + { + if (last_list_pnt == 0xFFFFFFFF) /* Must insert at the head of the list.*/ + { + free_item->forward_link = cur_list_pnt; + lh->head_pointer = free_item_pnt; + } + else /* Standard insertion.*/ + { + free_item->forward_link = cur_list_pnt; + last_item->forward_link = free_item_pnt; + } + + /* Check if the entry was made before the last one.*/ + if ( ulPassCount == lh->list_length ) + *insert_status_pnt = OCTAPI_LLM2_INSERT_BEFORE_LAST_NODE; + else + *insert_status_pnt = OCTAPI_LLM2_INSERT_LIST_NODE; + + fConditionFlag = FALSE; + break; + } + else if (item->forward_link == 0xFFFFFFFF) /* End of list found, must insert at the end.*/ + { + free_item->forward_link = 0xFFFFFFFF; + item->forward_link = free_item_pnt; + lh->tail_pointer = free_item_pnt; + + *insert_status_pnt = OCTAPI_LLM2_INSERT_LAST_NODE; + + fConditionFlag = FALSE; + break; + } + else /* Item was not found, but continue searching.*/ + { + last_last_item = last_item; + last_item = item; + last_list_pnt = cur_list_pnt; + cur_list_pnt = item->forward_link; + } + + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + + } + + /* Return the previous node if possible.*/ + if ( *insert_status_pnt == OCTAPI_LLM2_INSERT_LIST_NODE || + *insert_status_pnt == OCTAPI_LLM2_INSERT_BEFORE_LAST_NODE ) + { + if ( last_item != NULL ) + *prev_item_data_pnt = (void *)last_item->user_info; + + if ( last_last_item != NULL ) + *prev_prev_item_data_pnt = (void *)last_last_item->user_info; + else + *prev_prev_item_data_pnt = NULL; + } + else + { + *prev_item_data_pnt = (void *)item->user_info; + + if ( ( last_last_item != NULL ) && ( last_item != NULL ) ) + *prev_prev_item_data_pnt = (void *)last_item->user_info; + else + *prev_prev_item_data_pnt = NULL; + } + } + + /* Increase the list length.*/ + lh->list_length++; + ls->assigned_items++; + *item_data_pnt = (void *)free_item->user_info; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlm2ListRemoveItem. +| +| Description: This function deallocates a node of the linked list specified +| by the handle list_handle. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *l void The memory used by the LLM2_LIST structure. +| list_handle UINT32 The handle to the list. +| item_key UINT32 The key of the item to be removed. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +UINT32 OctApiLlm2ListRemoveItem(void * l,UINT32 list_handle,UINT32 item_key, PUINT32 prev_item_key_pnt, PUINT32 prev_prev_item_key_pnt, PUINT32 remove_status_pnt ) +{ + LLM2_LIST* ls; + LLM2_LIST_ITEM* freed_item = NULL; + LLM2_LIST_HEAD* lh; + UINT32 freed_item_pnt = 0xFFFFFFFF; + UINT32 total_lists; + BYTE* lsbyte; + UINT32 fConditionFlag = TRUE; + UINT32 ulPassCount = 0; + + /* Built the structure based on the base address:*/ + ls = (LLM2_LIST *)l; + lsbyte = (BYTE *)ls; + total_lists = ls->total_lists; + + /* Set the status of the removal to error as a default value.*/ + *remove_status_pnt = OCTAPI_LLM2_REMOVE_ERROR; + + ls->lh = (LLM2_LIST_HEAD *)(lsbyte + sizeof(LLM2_LIST)); + ls->list_head_alloc = (void *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD))); + ls->li = (LLM2_LIST_ITEM *)(lsbyte + sizeof(LLM2_LIST) + (total_lists * sizeof(LLM2_LIST_HEAD)) + ls->head_alloc_size); + + lh = &ls->lh[list_handle]; + + if (list_handle >= ls->total_lists) return(OCTAPI_LLM2_BLOCKNUM_OUT_OF_RANGE); + if (lh->list_length == 0xFFFFFFFF) return(OCTAPI_LLM2_INVALID_LIST_HANDLE); + + if (lh->list_length == 1)/* First item and only item if he matches.*/ + { + freed_item_pnt = lh->head_pointer; + freed_item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * freed_item_pnt); + + if ( freed_item->key == item_key ) + { + lh->head_pointer = 0xFFFFFFFF; + lh->tail_pointer = 0xFFFFFFFF; + } + else + return(OCTAPI_LLM2_INTERNAL_ERROR1); + + /* Indicate that there was no node prior to the one removed.*/ + *prev_item_key_pnt = 0xFFFFFFFF; + *prev_prev_item_key_pnt = 0xFFFFFFFF; + *remove_status_pnt = OCTAPI_LLM2_REMOVE_FIRST_NODE; + } + else /* Discard non-first item! (Caution: this could be the last item!)*/ + { + LLM2_LIST_ITEM * last_last_item = NULL; + LLM2_LIST_ITEM * last_item = NULL; + LLM2_LIST_ITEM * item; + UINT32 last_list_pnt; + UINT32 cur_list_pnt; + UINT32 cur_list_key; + + /* Start at beginning:*/ + cur_list_pnt = lh->head_pointer; + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + + last_list_pnt = 0xFFFFFFFF; + + /* Start search from cur_list_pnt and cur_list_num.*/ + while( fConditionFlag == TRUE ) + { + ulPassCount++; + if (cur_list_key == item_key) /* Item number found.*/ + { + if (last_list_pnt == 0xFFFFFFFF) /* First item in the list.*/ + { + lh->head_pointer = item->forward_link; + *remove_status_pnt = OCTAPI_LLM2_REMOVE_FIRST_NODE; + } + else if ( item->forward_link == 0xFFFFFFFF) /* Last item of the list.*/ + { + last_item->forward_link = 0xFFFFFFFF; + lh->tail_pointer = last_list_pnt; + *remove_status_pnt = OCTAPI_LLM2_REMOVE_LAST_NODE; + } + else + { + last_item->forward_link = item->forward_link; + + if ( ulPassCount == ( lh->list_length - 1 ) ) + *remove_status_pnt = OCTAPI_LLM2_REMOVE_BEFORE_LAST_NODE; + else + *remove_status_pnt = OCTAPI_LLM2_REMOVE_LIST_NODE; + } + + freed_item_pnt = cur_list_pnt; + freed_item = item; + + fConditionFlag = FALSE; + break; + } + else if (item->forward_link == 0xFFFFFFFF) /* End of list found?!?*/ + { + return(OCTAPI_LLM2_INTERNAL_ERROR0); + } + else /* Item was not found, but continue searching.*/ + { + last_last_item = last_item; + last_item = item; + last_list_pnt = cur_list_pnt; + cur_list_pnt = item->forward_link; + } + + item = (LLM2_LIST_ITEM *)((BYTE *)ls->li + ls->item_size * cur_list_pnt); + cur_list_key = item->key; + } + + /* Return the key of the node before the node removed if possible.*/ + if ( last_list_pnt == 0xFFFFFFFF ) + *prev_item_key_pnt = 0xFFFFFFFF; + else if ( last_item != NULL ) + *prev_item_key_pnt = last_item->key; + + /* Return the key of the node before before the node removed if possible.*/ + if ( last_last_item == NULL ) + *prev_prev_item_key_pnt = 0xFFFFFFFF; + else + *prev_prev_item_key_pnt = last_last_item->key; + + } + + /* Decrease the list length.*/ + lh->list_length--; + ls->assigned_items--; + + /* Return free block to free block list:*/ + freed_item->forward_link = ls->next_empty_item; + ls->next_empty_item = freed_item_pnt; + + return(GENERIC_OK); +} + +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ +| API UTILITIES +| +| Function: OctApiLlmMemCpy. +| +| Description: This function copies data from a source to a destination. +| +| ----------------------------------------------------------------------- +| | Variable | Type | Description +| ----------------------------------------------------------------------- +| *f_pvDestination VOID The destination where to copy the data. +| *f_pvSource VOID The source where to copy the data from. +| f_ulSize UINT32 The number of bytes to copy. +| +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +VOID * OctApiLlmMemCpy( VOID *f_pvDestination, const VOID * f_pvSource, UINT32 f_ulSize ) +{ + CHAR * pbyDst; + const CHAR * pbySrc; + UINT32 * f_pulAlignedDst; + const UINT32 * f_pulAlignedSrc; + + pbyDst = (CHAR *)f_pvDestination; + pbySrc = (const CHAR *)f_pvSource; + + /* + * If the size is small, or either SRC or DST is unaligned, + * then punt into the byte copy loop. This should be rare. + */ + if ( ( f_ulSize < sizeof(UINT32) ) + || ( ( (UINT32)( pbySrc ) & ( sizeof(UINT32) - 1 ) ) | ( (UINT32)( pbyDst ) & ( sizeof(UINT32) - 1 ) ) ) ) + { + while ( f_ulSize-- ) + *pbyDst++ = *pbySrc++; + return f_pvDestination; + } + + f_pulAlignedDst = (UINT32 *)pbyDst; + f_pulAlignedSrc = (const UINT32 *)pbySrc; + + /* Copy 4X long words at a time if possible. */ + while ( f_ulSize >= 4 * sizeof(UINT32) ) + { + *f_pulAlignedDst++ = *f_pulAlignedSrc++; + *f_pulAlignedDst++ = *f_pulAlignedSrc++; + *f_pulAlignedDst++ = *f_pulAlignedSrc++; + *f_pulAlignedDst++ = *f_pulAlignedSrc++; + f_ulSize -= 4 * sizeof(UINT32); + } + + /* Copy one long word at a time if possible. */ + while ( f_ulSize >= sizeof(UINT32) ) + { + *f_pulAlignedDst++ = *f_pulAlignedSrc++; + f_ulSize -= sizeof(UINT32); + } + + /* Pick up any residual with a byte copier. */ + pbyDst = (CHAR *)f_pulAlignedDst; + pbySrc = (const CHAR *)f_pulAlignedSrc; + while ( f_ulSize-- ) + *pbyDst++ = *pbySrc++; + + return f_pvDestination; +} + +/**************************************** llm_list section **********************************************/ + diff --git a/software/apilib/llman/octapi_llman_private.h b/software/apilib/llman/octapi_llman_private.h new file mode 100644 index 0000000..f182cf1 --- /dev/null +++ b/software/apilib/llman/octapi_llman_private.h @@ -0,0 +1,206 @@ +/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ + +File: octapi_llman_private.h + +Copyright (c) 2001 Octasic Inc. All rights reserved. + +Description: + + Library used to manage allocation tables and linked lists. The library is + made such that only a block of contiguous memory is needed for the + management of the linked list/allocation table. + + +This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is +free software; you can redistribute it and/or modify it under the terms of +the GNU General Public License as published by the Free Software Foundation; +either version 2 of the License, or (at your option) any later version. + +The OCT6100 GPL API is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with the OCT6100 GPL API; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + +$Octasic_Release: OCT612xAPI-01.00-PR38 $ + +$Octasic_Revision: 13 $ + +\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ +#ifndef __OCTAPI_LLMAN_PRIVATE_H__ +#define __OCTAPI_LLMAN_PRIVATE_H__ + +#include "octdef.h" + + +/**************************************** llm_alloc section **********************************************/ + + +/* Most basic linked list model. + LLM_STR contains a list of "number_of_items" that + are each "unassigned" or "assigned". When requesting + a new element, llm_alloc must choose an "unassigned" + element. An element that is deallocated will be last + to be allocated. +*/ + +typedef struct _LLM_ALLOC +{ + UINT32 *linked_list; /* Each item is either used (0xFFFFFFFE)*/ + /* or unused (pointer to next unused item, 0xFFFFFFFF means last item reached).*/ + UINT32 next_avail_num; /* Points to the next available item in linked list. (0xFFFFFFFF means none available)*/ + UINT32 number_of_items; /* Total number of items in linked list.*/ + UINT32 allocated_items; /* Allocated items in linked list.*/ + +} LLM_ALLOC; + +typedef struct _TLLM_ALLOC_NODE_ +{ + UINT32 value; /* Each item is either used (0xFFFFFFFE)*/ + /* or unused (pointer to next unused item, 0xFFFFFFFF means last item reached).*/ + UINT32 timeout[2]; /* Timeout value that must be exceeded for the node to be considered free again.*/ + +} TLLM_ALLOC_NODE; + + +typedef struct _TLLM_ALLOC_ +{ + TLLM_ALLOC_NODE *linked_list; /* List of nodes used by the link list.*/ + + UINT32 next_avail_num; /* Points to the next available item in linked list. (0xFFFFFFFF means none available)*/ + UINT32 number_of_items; /* Total number of items in linked list.*/ + UINT32 allocated_items; /* Allocated items in linked list.*/ + + UINT32 number_of_timeout; /* Number of block currently in timeout.*/ + UINT32 next_timeout_num; /* Points to the next block currently in timeout.*/ + UINT32 last_timeout_num; /* Last node of the timeout list.*/ + + UINT32 last_known_time[2]; /* last known time.*/ + +} TLLM_ALLOC; + +/* +void octapi_llm_alloc_build_structure(void *l, LLM_ALLOC ** ls); +*/ +/**************************************** llm_alloc section **********************************************/ + + + +/**************************************** llm_list section **********************************************/ +/* This section contains memory structures and functions used + to maintain a variable number of lists (FIFOs) that each + have a variable amount of items. A total amount of items + can be assigned through-out all the lists. Each item in + each list contains a UINT32 specified by the software using + the lists. Each used item in the list is accessible through + it's position in the list. */ + +typedef struct _LLM_LIST_HEAD +{ + UINT32 list_length; /* Current number of items in the list.*/ + /* 0xFFFFFFFF means that the list is not used.*/ + UINT32 head_pointer; /* Number of the item in the item pool that is the first of this list.*/ + /* 0xFFFFFFFF indicates end-of-list link.*/ + UINT32 tail_pointer; /* Number of the item in the item pool that is the last of this list.*/ + + /* Item cache (pointer within the list of the last accessed item):*/ + UINT32 cache_item_number; /* Number of the last accessed item in the list. 0xFFFFFFFF indicates invalid cache.*/ + UINT32 cache_item_pointer; /* Number of the last accessed item in the item pool.*/ +} LLM_LIST_HEAD; + +typedef struct _LLM_LIST_ITEM +{ + UINT32 forward_link; /* Number of the item in the item pool that is next in this list.*/ + /* 0xFFFFFFFF indicates end-of-list link.*/ + + /* User item info (variable size)*/ + UINT32 user_info[1]; +} LLM_LIST_ITEM; + +typedef struct _LLM_LIST +{ + UINT32 user_info_bytes; /* In bytes, size of the user info in a single item.*/ + UINT32 user_info_size; /* In bytes, size of the user info in a single item.*/ + UINT32 item_size; + + UINT32 head_alloc_size; + UINT32 total_items; + UINT32 assigned_items; + + UINT32 total_lists; + UINT32 assigned_lists; + + UINT32 next_empty_item; /* Contains a pointer to the next empty item in the*/ + /* item pool.*/ + + /* Table of all the possible list heads:*/ + LLM_LIST_HEAD * lh; + void * list_head_alloc; /* LLM_ALLOC structure used for list head allocation!*/ + + /* Table of the list items:*/ + LLM_LIST_ITEM * li; +} LLM_LIST; + + +/**********************************************************************************/ +/* These structures are are used by the Llm2 functions to creates lists of ordered + items based on a key given by the user when a new node is inserted in a list. */ +typedef struct _LLM2_LIST_HEAD +{ + UINT32 list_length; /* Current number of items in the list.*/ + /* 0xFFFFFFFF means that the list is not used.*/ + UINT32 head_pointer; /* Number of the item in the item pool that is the first of this list.*/ + /* 0xFFFFFFFF indicates end-of-list link.*/ + UINT32 tail_pointer; /* Number of the item in the item pool that is the last of this list.*/ + +} LLM2_LIST_HEAD; + +typedef struct _LLM2_LIST_ITEM +{ + UINT32 forward_link; /* Number of the item in the item pool that is next in this list.*/ + /* 0xFFFFFFFF indicates end-of-list link.*/ + UINT32 key; /* Key used to order the entries.*/ + + /* User item info (variable size)*/ + UINT32 user_info[1]; +} LLM2_LIST_ITEM; + +typedef struct _LLM2_LIST +{ + UINT32 user_info_bytes; /* In bytes, size of the user info in a single item.*/ + UINT32 user_info_size; /* In bytes, size of the user info in a single item.*/ + UINT32 item_size; + + UINT32 head_alloc_size; + UINT32 total_items; + UINT32 assigned_items; + + UINT32 total_lists; + UINT32 assigned_lists; + + UINT32 next_empty_item; /* Contains a pointer to the next empty item in the*/ + /* item pool.*/ + + /* Table of all the possible list heads:*/ + LLM2_LIST_HEAD * lh; + void * list_head_alloc; /* LLM_ALLOC structure used for list head allocation!*/ + + /* Table of the list items:*/ + LLM2_LIST_ITEM * li; +} LLM2_LIST; + +/*void octapi_llm_list_build_structure(void *l, LLM_LIST ** ls);*/ +LLM_LIST_ITEM * OctApiLlmListGetItemPointer( LLM_LIST * ls, UINT32 item_number ); +LLM2_LIST_ITEM * OctApiLlm2ListGetItemPointer( LLM2_LIST * ls, UINT32 item_number ); +UINT32 OctApiTllmCheckTimeoutList( TLLM_ALLOC *ls, UINT32 current_time[2] ); +VOID * OctApiLlmMemCpy( VOID *f_pvDestination, const VOID * f_pvSource, UINT32 f_ulSize ); +/**************************************** llm_list section **********************************************/ + + + + + +#endif /*__OCTAPI_LLMAN_PRIVATE_H__*/ |