1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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.04.06 $
$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__*/
|
