| 1 |
/*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\ |
| 2 |
|
| 3 |
File: octapi_bt0_private.h |
| 4 |
|
| 5 |
Copyright (c) 2001 Octasic Inc. All rights reserved. |
| 6 |
|
| 7 |
Description: |
| 8 |
|
| 9 |
Library used to manage a binary tree of variable max size. Library is |
| 10 |
made to use one block of contiguous memory to manage the tree. |
| 11 |
|
| 12 |
This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is |
| 13 |
free software; you can redistribute it and/or modify it under the terms of |
| 14 |
the GNU General Public License as published by the Free Software Foundation; |
| 15 |
either version 2 of the License, or (at your option) any later version. |
| 16 |
|
| 17 |
The OCT6100 GPL API is distributed in the hope that it will be useful, but |
| 18 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
| 19 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 20 |
for more details. |
| 21 |
|
| 22 |
You should have received a copy of the GNU General Public License |
| 23 |
along with the OCT6100 GPL API; if not, write to the Free Software |
| 24 |
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 25 |
|
| 26 |
$Octasic_Release: OCT612xAPI-01.00-PR49 $ |
| 27 |
|
| 28 |
$Octasic_Revision: 11 $ |
| 29 |
|
| 30 |
\*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/ |
| 31 |
#ifndef __OCTAPI_BT0_PRIVATE_H__ |
| 32 |
#define __OCTAPI_BT0_PRIVATE_H__ |
| 33 |
|
| 34 |
|
| 35 |
|
| 36 |
#include "octdef.h" |
| 37 |
|
| 38 |
#define OCTAPI_BT0_LKEY_LARGER 0x0 |
| 39 |
#define OCTAPI_BT0_LKEY_SMALLER 0x1 |
| 40 |
#define OCTAPI_BT0_LKEY_EQUAL 0x2 |
| 41 |
|
| 42 |
typedef struct __OCTAPI_BT0_LINK__ |
| 43 |
{ |
| 44 |
UINT32 node_number; |
| 45 |
UINT32 depth; |
| 46 |
} OCTAPI_BT0_LINK; |
| 47 |
|
| 48 |
typedef struct __OCTAPI_BT0_NODE__ |
| 49 |
{ |
| 50 |
UINT32 next_free_node; /* Number of the next node in the free node link-list.*/ |
| 51 |
OCTAPI_BT0_LINK l[2]; /* 0 = left link; 1 = right link.*/ |
| 52 |
} OCTAPI_BT0_NODE; |
| 53 |
|
| 54 |
|
| 55 |
typedef struct __OCTAPI_BT0__ |
| 56 |
{ |
| 57 |
UINT32 number_of_items; /* Number of items on total that can be allocated in the tree.*/ |
| 58 |
UINT32 key_size; /* Size is in UINT32s*/ |
| 59 |
UINT32 data_size; /* Size is in UINT32s*/ |
| 60 |
|
| 61 |
/* Empty node linked-list:*/ |
| 62 |
UINT32 next_free_node; /* 0xFFFFFFFF means that no nodes are free.*/ |
| 63 |
|
| 64 |
/* Tree as such:*/ |
| 65 |
OCTAPI_BT0_NODE * node; /* Array of nodes (number_of_items in size).*/ |
| 66 |
|
| 67 |
/* Tree root:*/ |
| 68 |
OCTAPI_BT0_LINK root_link; |
| 69 |
|
| 70 |
/* Associated key structure*/ |
| 71 |
UINT32 * key; /* Array of keys associated to NODEs.*/ |
| 72 |
|
| 73 |
/* Associated data structure.*/ |
| 74 |
UINT32 * data; /* Array of data associated to NODEs.*/ |
| 75 |
|
| 76 |
UINT32 invalid_value; |
| 77 |
UINT32 no_smaller_key; |
| 78 |
|
| 79 |
} OCTAPI_BT0; |
| 80 |
|
| 81 |
void OctApiBt0CorrectPointers( OCTAPI_BT0 * bb ); |
| 82 |
UINT32 OctApiBt0AddNode2( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey, UINT32 new_node_number ); |
| 83 |
UINT32 OctApiBt0AddNode3( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey, UINT32 *p_new_node_number ); |
| 84 |
UINT32 OctApiBt0AddNode4(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number, UINT32 *p_prev_node_number, UINT32 state ); |
| 85 |
UINT32 OctApiBt0KeyCompare( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link, UINT32 * lkey ); |
| 86 |
void OctApiBt0UpdateLinkDepth( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * link ); |
| 87 |
void OctApiBt0Rebalance( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * root_link ); |
| 88 |
void OctApiBt0ExternalHeavy( OCTAPI_BT0 * bb, OCTAPI_BT0_LINK * root_link ); |
| 89 |
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 ); |
| 90 |
|
| 91 |
|
| 92 |
|
| 93 |
#endif /*__OCTAPI_BT0_PRIVATE_H__*/ |