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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
# Mulklib: purely functional integer maps for C
## Summary
This library implements [Patricia Trees][] in C, providing fast,
purely functional maps keyed by integers.
## Motivation
1. Patricia trees are very amenable to structure sharing.
2. Furthermore, big-endian Patricia trees are especially efficient
when indices are allocated sequentially.
3. Finally, bitmapping improves the performance of copying because
copying an array is much cheaper than copying an equivalent branch
in a tree.
## Preparation
Build with something like the following:
```sh
make CC=gcc LIB_PREFIX=lib LIB_SUFFIX=.so
```
The defaults are `CC=clang LIB_PREFIX=lib LIB_SUFFIX=.dylib`, which is
all right for Mac OS X but not so great on other systems. They are
also subject to change, since they depend on my development
environment. (Of course, if you feel the urge to make the build system
a little smarter, patches are always welcome.)
If building and installing a library consisting of a single object
file seems like overkill to you (it sure does to me), you may prefer
simply integrating the source files (`bitmapped_patricia_tree.c`,
`bitmapped_patricia_tree.h`) into your own project directly.
## Usage
### Main Concepts
A Bitmapped Patricia Tree (**BPT**) maps integer keys to `void*` values.
BPTs provide a functional, Lisp-like interface. All modifying
operations (`bpt_assoc` and `bpt_dissoc`, which add and remove
entries, respectively) return a new BPT with the requested changes
applied, although by default, they **may destructively modify** the
original BPT for improved performance.
Destructive modification can be prohibited by **sealing** the original
BPT using the `bpt_seal` procedure. Note that there is practically no
performance overhead in sealing (the seal being just a boolean flag),
so there is nothing wrong with using bitmapped Patricia Trees in a
purely functional manner by calling `bpt_seal` after every operation.
An **empty BPT** is represented as `NULL`.
### Example
```c
//
// This is a very basic example of using BPTs that blissfully neglects memory
// management in favor of didactic simplicity.
//
// For a more complete example, see bpt_test.c in the source distribution.
//
#include "stdio.h"
#include "stdlib.h"
#include "bitmapped_patricia_tree.h"
void print_tree(bpt_t b) {
int i;
for (i = 0; i < 10; i++) {
if (bpt_has_key(b, i)) {
printf(" %d -> %s\n", i, bpt_get(b, i));
}
}
}
int main() {
bpt_t b1, b2;
// Create b1.
b1 = bpt_assoc(NULL, 0, "zero"); //functional (obviously)
b1 = bpt_assoc(b1, 1, "one"); //|
b1 = bpt_assoc(b1, 2, "two"); //|destructive!
b1 = bpt_assoc(b1, 3, "three"); //|
b1 = bpt_assoc(b1, 4, "four"); //|
// Make b1 functional.
bpt_seal(b1);
// Make b2 a structure-sharing copy of b1.
b2 = bpt_assoc(b1, 0, "null"); //functional, as b1 is sealed
b2 = bpt_assoc(b2, 3, "a triple"); //destructive
// Modifying b1 does not affect b2.
b1 = bpt_assoc(b1, 5, "five"); //destructive
printf("Map 1:\n");
print_tree(b1);
printf("\nMap 2:\n");
print_tree(b2);
return EXIT_SUCCESS;
}
```
Output:
```
Map 1:
0 -> zero
1 -> one
2 -> two
3 -> three
4 -> four
5 -> five
Map 2:
0 -> null
1 -> one
2 -> two
3 -> a triple
4 -> four
```
### API
```c
typedef int32_t bpt_key_t;
// Querying
void *bpt_get(bpt_t bpt, bpt_key_t key);
bool bpt_has_key(bpt_t bpt, bpt_key_t key);
// Adding and Removing Entries
bpt_t bpt_assoc(bpt_t bpt, bpt_key_t key, void *item);
bpt_t bpt_dissoc(bpt_t bpt, bpt_key_t key);
// Managing Memory
void bpt_retain(bpt_t bpt);
void bpt_release(bpt_t bpt);
void bpt_dealloc(bpt_t bpt);
void bpt_set_dealloc_hook(bpt_t bpt, bpt_key_t key, void (*hook)(bpt_key_t key, void* value));
// Making Maps Functional
void bpt_seal(bpt_t bpt);
```
[Patricia Trees]: http://citeseer.ist.psu.edu/okasaki98fast.html
|
