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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
2007-12-17 Neal H. Walfield <neal@gnu.org>
* btree.h (BTREE_(check_tree_internal)): Take additional
parameter, the btree. Update users.
(BTREE_check_tree_internal_): Take additional parameter, the
btree. Update users.
(BTREE_(find_internal)): Take additional parameter, may_overlap.
If true, then don't break out when a matching node is found.
Update users.
(BTREE_(insert)): Take additional parameter, may_overlap.
If true, don't require that nodes have a unique key.
(BTREE_CLASS): Take additional parameter, may_overlap. Generate
stubs appropriate.
* btree.c (BTREE_): New function.
(check_tree_recurse): Take additional parameter, btree. Update
users. Add additional tests.
(BTREE_(check_tree_internal)): Take additional parameter, btree.
Update users.
* btree-test.c: Add tests for checking trees with overlapping keys.
2007-12-17 Neal H. Walfield <neal@gnu.org>
* btree.c (DEBUGGING): Don't define. Use !NDEBUG instead.
(BTREE_(check_tree_internal) [NDEBUG]): Define.
* btree.h (BTREE_check_tree_internal_): Define. Update users to
use it instead of BTREE_(check_tree_internal).
2007-12-17 Neal H. Walfield <neal@gnu.org>
* btree.h (struct BTREE_(node_ptr)): New structure.
(struct BTREE_(node_pptr)): Likewise.
(struct BTREE_(node)): Make parent a struct BTREE_(node_pptr).
left a struct BTREE_(node_ptr). Likewise for right. Fold red
into the parent field. Update all users.
(BTREE_NP): New macro.
(BTREE_NP_SET): Likewise.
(BTREE_NP_THREAD_P): Likewise.
(BTREE_NP_THREAD_P_SET): Likewise.
(BTREE_NP_THREAD): Likewise.
(BTREE_NP_THREAD_SET): Likewise.
(BTREE_NP_CHILD): Likewise.
(BTREE_NP_CHILD_SET): Likewise.
(BTREE_NODE_RED_P): Likewise.
(BTREE_NODE_RED_SET): Likewise.
(struct BTREE_(t)): Make root a struct BTREE_(node_ptr).
(BTREE_(link_internal)): Remove function.
(BTREE_(check_tree_internal)): New declaration.
(BTREE_(insert)): Make NEWNODE->LEFT a thread. Call
BTREE_(check_tree_internal).
(BTREE_(prev_hard)): New declaration.
(BTREE_(prev)): New function.
(BTREE_CLASS:detach): Call BTREE_(check_tree_internal).
* btree.c (BTREE_): Take additional parameter, check_colors.
Update callers. If COMPARE is NULL, don't compare values. Check
if the threads are correct.
(BTREE_(check_tree_internal)): Take additional parameter,
check_colors.
(BTREE_(next_hard)): Remove static qualifier.
(BTREE_(prev)): Rename from this...
(BTREE_(prev_hard)): ... to this. If
(selfp): Change return type to a struct BTREE_(node_ptr) *.
Update users.
(BTREE_(detach)): Also adjust the left thread as appropriate.
2007-12-17 Neal H. Walfield <neal@gnu.org>
* Makefile.am (AM_CPPFLAGS): Add -D_GNU_SOURCE.
(TESTS): New variable.
(check_PROGRAMS): Likewise.
(btree_test_SOURCES): Likewise.
(btree_test_LDADD): Likewise.
* btree-test.c (program_name): New variable.
(print_nodes): Update to insert API change.
2007-11-14 Neal H. Walfield <neal@gnu.org>
* btree.h: Include <stddef.h>.
(BTREE_CLASS): Cast the return of the insert template
appropriately.
2007-11-05 Neal H. Walfield <neal@gnu.org>
* btree.h (insert): Don't return an error code. Return the node
with the overlapping key.
(BTREE_CLASS): Update insert template.
2007-10-17 Neal H. Walfield <neal@gnu.org>
* btree.h: Don't include <stdlib.h>.
2007-07-31 Neal H. Walfield <neal@gnu.org>
* btree.h: Fix comment.
2007-07-30 Neal H. Walfield <neal@gnu.org>
* btree.h (offsetof) [! offsetof]: Define.
(tree_init): Add prototype.
(maybe_split_internal): Likewise.
(find_internal): Likewise.
(find): Likewise.
(insert): Likewise.
(first): Likewise.
(next): Likewise.
2004-12-25 Neal H. Walfield <neal@gnu.org>
* btree.h (BTREE_CLASS): Rename from BTREE_NODE_CLASS.
If the function returns a returns a NODE_TYPE and it fails, simply
return NULL.
(btree_detach): Fix comment.
* btree-test.c: Use BTREE_CLASS, BTREE_NODE_CLASS.
2004-12-25 Neal H. Walfield <neal@gnu.org>
* Makefile.am: New file.
* headers.m4: Likewise.
* btree.c: Likewise.
* btree.h: Likewise.
* btree-test.c: Likewise.
|
