Systemnahe Programmierung in C: Binäre Patricia-Bäume
| Systemnahe Programmierung in C: Binäre Patricia-Bäume |
|
|
|
1/* Macros and functions for bitstring processing */
2
3/* these are the basic operations for
4 implementing "big-endian patricia trees"
5 for efficient maps with unsigned int's as keys
6*/
7
8#include <limits.h>
9
10typedef unsigned long int BitString;
11
12/* a Prefix of a BitString is represented
13 by a BitString where the least significant
14 bits are cleared
15*/
16typedef BitString Prefix;
17
18/* a Mask (in this context) is a BitString
19 with a single bit set. A Mask will be used
20 to specify the length of a Prefix. The bit
21 position of the mask determined the 1. bit
22 not included in the prefix
23*/
24typedef BitString Mask;
25
26#define LEN_BITSTRING (CHAR_BIT * sizeof (BitString))
27
28
29#define check(i) ( (BitString)(i) < LEN_BITSTRING )
30
31#define emptyBitString ( (BitString)0 )
32
33#define singleton(i) ( ((BitString)1) << (i) )
34
35/* in a Mask a single bit is set */
36
37#define invMask(m) ( (m) != emptyBitString \
38 && \
39 ((m) ^ ((m) & (~(m) + 1))) \
40 == emptyBitString \
41 )
42
43/*----------------------------------------*/
44
45extern void printBitString (BitString bs);
46
47extern void printPrefix(Prefix p, Mask m);
48
49/* mask for longest 0-prefix
50 basic operation, needed by commonPrefixMask
51 */
52extern Mask zeroPrefix(BitString bs);
53
54/* faster version of zeroPrefix */
55extern Mask zeroPrefixFast(BitString bs);
56
57/* compute common prefix length represented by a mask*/
58extern Mask commonPrefixMask(BitString bs1, BitString bs2);
59
60/* get a prefix of a given length (represented by a mask) */
61extern Prefix getPrefix(BitString bs, Mask m);
62
63/* compare a prefix of a bitstring with a given prefix */
64extern int matchPrefix(BitString bs, Prefix p, Mask m);
65
|
|
1#include <stdio.h>
2#include <assert.h>
3
4#include "BitString.h"
5
6/*----------------------------------------*/
7
8void
9printBitString (BitString bs) {
10 int i = LEN_BITSTRING;
11 int blank = 0;
12 while (i > 0) {
13 if (blank) printf(" ");
14 --i;
15 printf ("%c", (char)(((bs >> i) & 0x1) + '0'));
16 blank = i % 8 == 0;
17 }
18}
19
20void
21printPrefix(Prefix p, Mask m) {
22 int i = LEN_BITSTRING;
23 int blank = 0;
24 while ((singleton(i - 1) & m) == 0) {
25 if (blank) printf(" ");
26 --i;
27 printf ("%c", (char)(((p >> i) & 0x1) + '0'));
28 blank = i % 8 == 0;
29 }
30}
31
32/*----------------------------------------*/
33
34Mask zeroPrefix(BitString bs) {
35 int i = 1;
36 while (i < LEN_BITSTRING) {
37 bs = bs | (bs >> i);
38 i *= 2;
39 }
40 return bs ^ (bs >> 1);
41}
42
43/* optimization: loop unrolling (here for 64-bit architecture)*/
44Mask zeroPrefixFast(BitString bs) {
45 register BitString bs1 = bs;
46
47 bs1 |= bs1 >> 1;
48 bs1 |= bs1 >> 2;
49 bs1 |= bs1 >> 4;
50 bs1 |= bs1 >> 8;
51 bs1 |= bs1 >> 16;
52 bs1 |= bs1 >> 32;
53
54 return bs1 ^ (bs1 >> 1);
55}
56
57Mask commonPrefixMask(BitString bs1, BitString bs2) {
58 return
59 zeroPrefixFast(bs1 ^ bs2);
60}
61
62Prefix getPrefix(BitString bs, Mask m) {
63 assert(invMask(m));
64 return
65 bs & (~(m - 1) ^ m);
66}
67
68int matchPrefix(BitString bs, Prefix p, Mask m) {
69 return
70 getPrefix(bs, m) == p;
71}
|
|
1#include "BitString.h"
2
3typedef BitString Key;
4typedef long int Attr; /* or something else */
5
6typedef enum {Empty, Leaf, Fork} TreeKind;
7
8typedef struct Node * Tree;
9
10struct Node {
11 TreeKind Kind;
12 union {
13 /* data for leaf nodes */
14 struct {
15 Key k;
16 Attr a;
17 } leaf;
18
19 /* data for inner nodes */
20 struct {
21 Prefix p;
22 Mask m;
23 Tree l;
24 Tree r;
25 } fork;
26
27 /* data for empty tree */
28 /* not there */
29
30 } data;
31};
32
33typedef Tree IntMap;
34
35typedef void (*ProcessKeyAttr)(Key k, Attr a);
36
37extern Tree empty;
38
39extern int isInMap(Key k, Tree t, Attr * res);
40extern Tree insert(Key k, Attr a, Tree t);
41extern Tree remov(Key k, Tree t); /* remove is in stdio.h */
42extern void foreach(ProcessKeyAttr p, Tree t);
43
44extern void showTree(Tree t);
45extern void showTree0(char * txt, Tree t);
46
47#if TRACE
48#define trace(x) x
49#else
50#define trace(x)
51#endif
|
|
1#include <stdio.h>
2#include <stdlib.h>
3#include <assert.h>
4
5#include "IntMap.h"
6
7static struct Node emptyNode = {Empty};
8
9Tree empty = & emptyNode;
10
11/* selector macros */
12
13#define kind(t) ((t)->Kind)
14#define isEmpty(t) (kind(t) == Empty)
15#define isLeaf(t) (kind(t) == Leaf)
16#define isFork(t) (kind(t) == Fork)
17
18#define key(t) ((t)->data.leaf.k)
19#define attr(t) ((t)->data.leaf.a)
20#define prefix(t) ((t)->data.fork.p)
21#define mask(t) ((t)->data.fork.m)
22#define left(t) ((t)->data.fork.l)
23#define right(t) ((t)->data.fork.r)
24
25/*----------------------------------------*/
26/* constructors */
27
28static
29Tree mkLeaf(Key k, Attr a) {
30 Tree res = malloc(sizeof(* res));
31 if (! res) {
32 perror("mkLeaf: heap overflow");
33 exit(1);
34 }
35 kind(res) = Leaf;
36 key (res) = k;
37 attr(res) = a;
38
39 trace(showTree0("mkLeaf", res));
40
41 return res;
42}
43
44static
45Tree mkFork(Prefix p, Mask m, Tree l, Tree r) {
46 Tree res = malloc(sizeof(* res));
47 if (! res) {
48 perror("mkFork: heap overflow");
49 exit(1);
50 }
51 kind (res) = Fork;
52 prefix(res) = p;
53 mask (res) = m;
54 left (res) = l;
55 right (res) = r;
56
57 trace(showTree0("mkFork", res));
58
59 return res;
60}
61
62/*----------------------------------------------*/
63/* destructors */
64/* helper for profiling and counting free calls */
65
66static
67void freeFork(Tree t) {
68 assert(isFork(t));
69 free(t);
70}
71
72static
73void freeLeaf(Tree t) {
74 assert(isLeaf(t));
75 free(t);
76}
77
78/*----------------------------------------*/
79
80int isInMap(Key k, Tree t, Attr * res) {
81 switch ( kind(t) ) {
82 case Empty:
83 return 0;
84
85 case Leaf:
86 { int found = key(t) == k;
87 if (found)
88 *res = attr(t);
89 return found;
90 }
91
92 case Fork:
93 { Tree t1;
94 if (! matchPrefix(k, prefix(t), mask(t)))
95 return 0;
96
97 t1 = (k & mask(t)) ? right(t) : left(t);
98
99 return isInMap(k, t1, res);
100 }
101
102 default:
103 assert(0);
104 return 0;
105 }
106}
107
108/* join 2 none empty trees together */
109/* intervall of elements don't overlap */
110
111static
112Tree join(Prefix p1, Tree t1,
113 Prefix p2, Tree t2) {
114
115 Mask m = commonPrefixMask(p1, p2);
116 Prefix p = getPrefix(p1, m);
117
118 trace(showTree0("join t1", t1));
119 trace(showTree0("join t2", t2));
120
121 if (p1 & m) {
122 return
123 mkFork(p, m, t2, t1);
124 } else {
125 return
126 mkFork(p, m, t1, t2);
127 }
128}
129
130Tree insert(Key k, Attr a, Tree t) {
131 trace(printf("insert %ld %ld\n", k, a));
132 trace(showTree0("insert", t));
133
134 switch ( kind(t) ) {
135 case Empty:
136 return
137 mkLeaf(k, a);
138
139 case Leaf:
140 { Key k1 = key(t);
141
142 if (k == k1) {
143 /* destructive update */
144 attr(t) = a;
145 return t;
146 } else {
147 return
148 join(k, mkLeaf(k, a),
149 k1, t);
150 }
151 }
152
153 case Fork:
154 { Prefix p = prefix(t);
155 Mask m = mask(t);
156
157 if (! matchPrefix(k, p, m)) {
158 return join(k, mkLeaf(k, a),
159 p, t);
160 }
161
162 /* destructive updates */
163 if (k & m) {
164 right(t) = insert(k, a, right(t));
165 } else {
166 left(t) = insert(k, a, left(t));
167 }
168 trace(showTree0("insert: Fork return", t));
169 return t;
170 }
171
172 default:
173 assert(0);
174 return 0;
175 }
176}
177
178Tree remov(Key k, Tree t) {
179 switch ( kind(t) ) {
180 case Empty:
181 return t;
182
183 case Leaf:
184 { Key k1 = key(t);
185
186 if (k == k1) {
187 freeLeaf(t);
188 return empty;
189 } else {
190 return t;
191 }
192 }
193
194 case Fork:
195 { Prefix p = prefix(t);
196 Mask m = mask(t);
197
198 if (! matchPrefix(k, p, m)) {
199 /* entry not there */
200
201 return t;
202 } else {
203 if (k & m) {
204 /* remove entry in right subtree */
205
206 Tree r = remov(k, right(t));
207 if (isEmpty(r)) {
208 Tree res = left(t);
209 freeFork(t);
210 return res;
211 } else {
212 right(t) = r;
213 return t;
214 }
215 } else {
216 /* remove entry in left subtree */
217
218 Tree l = remov(k, left(t));
219 if (isEmpty(l)) {
220 Tree res = right(t);
221 freeFork(t);
222 return res;
223 } else {
224 left(t) = l;
225 return t;
226 }
227 }
228 return t;
229 }
230 }
231
232 default:
233 assert(0);
234 return 0;
235 }
236}
237
238
239void foreach(ProcessKeyAttr p, Tree t) {
240 switch ( kind(t) ) {
241 case Empty:
242 break;
243 case Leaf:
244 p(key(t), attr(t));
245 break;
246 case Fork:
247 foreach(p, left(t));
248 foreach(p, right(t));
249 break;
250 }
251}
252
253static
254void indent(int level) {
255 int i;
256 for (i = 0; i < level; ++i)
257 printf(" ");
258}
259
260static
261void showTree1(int level, Tree t) {
262 indent(level);
263 switch ( kind(t) ) {
264 case Empty:
265 printf("Empty\n");
266 break;
267 case Leaf:
268 printf("\"");
269 printBitString(key(t));
270 printf("\"\t%ld\n", attr(t));
271 break;
272 case Fork:
273 /* printf("%lu,%lu,",prefix(t),mask(t)); */
274 printf("\"");
275 printPrefix(prefix(t), mask(t));
276 printf("\"\n");
277 showTree1(level + 2, left(t));
278 showTree1(level + 2, right(t));
279 break;
280 }
281 return;
282}
283
284void showTree(Tree t) {
285 showTree0("", t);
286}
287
288void showTree0(char * txt, Tree t) {
289 printf("%s\t%p\n", txt, (void *)t);
290 showTree1(0, t);
291 printf("\n");
292}
293
|
|
1#include <stdio.h>
2#include <stdlib.h>
3#include <assert.h>
4
5#include "IntMap.h"
6
7#if QUIET
8#define show(x,y)
9#define printTree1(x)
10/* depth of tree is 23 */
11#define MAX (8 * 1024 * 1024)
12#else
13#define show(x,y) showTree0(x,y)
14#define printTree1(x) printTree(x)
15#define MAX 128
16#endif
17
18void printKeyAttr(Key k, Attr a) {
19 printf("%ld :-> %ld\n", k, a);
20}
21
22void printTree(Tree t) {
23 foreach(printKeyAttr,t);
24}
25
26int main(void) {
27#if ! QUIET
28 {
29 IntMap t1 = empty;
30 show("{}", t1);
31 t1 = insert(1, 1, t1);
32 show("1", t1);
33 t1 = insert(1024, 1024, t1);
34 show("1,1024", t1);
35 t1 = insert(2,2, t1);
36 show("1,2,1024", t1);
37 t1 = insert(1025,1025, t1);
38 show("1,2,1024,1025", t1);
39 t1 = insert(1023,1023, t1);
40 show("1,2,1023,1024,1025", t1);
41 printTree1(t1);
42 }
43 printf("\n");
44#endif
45
46 {
47 Key i;
48 IntMap m;
49 for (i = 0, m = empty; i < MAX; ++i) {
50 m = insert(i, i, m);
51 }
52
53 printTree1(m);
54 show("filled tree", m);
55
56 { int found = 1;
57 Attr res;
58
59 for (i = 0; i < MAX; ++i) {
60 int b = isInMap(i, m, &res);
61 b = b && res == i;
62 if ( ! b ) {
63 printf("isIn: %ld not found in tree\n", i);
64 }
65 found = found && b;
66 }
67 if ( ! found ) {
68 printf("isIn: some elements not found\n");
69 }
70 }
71
72 for (i = 0; i < MAX; ++i) {
73 m = remov(i, m);
74 }
75 show("empty tree", m);
76 }
77
78 return 0;
79}
|
SRC = IntMap.c BitString.c IntMapTest.c
time = /usr/bin/time --format="runtime was %U sec"
include ../rules.mk
##all
## make all targets
## for normal version: all1
## without debug: ndebug
## and for iterative versions: iterative
all :
$(MAKE) ndebug prof
ndebug :
$(MAKE) CCFLAGS='$(CCFLAGS) -O2 \
-DNDEBUG=1 -DTRACE=0 -DQUIET=0' IntMapTest
prof :
$(MAKE) CCFLAGS='$(CCFLAGS) -pg \
-DNDEBUG=1 -DTRACE=0 -DQUIET=1' IntMapProfTest
run : ./IntMapTest
@$(time) ./IntMapTest
profrun : ./IntMapProfTest
rm -f gmon.out
./IntMapProfTest
gprof --brief IntMapProfTest gmon.out
distclean :
$(MAKE) clean
rm -f ./IntMapProfTest ./IntMapTest gmon.out
IntMap.o : IntMap.h BitString.h
BitString.o : BitString.h
IntMapTest : IntMap.h
IntMapTest : $(OBJ)
$(CC) -o $@ $(OBJ) $(CCFLAGS)
IntMapProfTest : $(SRC) IntMap.h BitString.h
$(CC) -o $@ $(SRC) $(CCFLAGS)
.PHONY : all ndebug run clean distclean indent profrun
|
| Letzte Änderung: 09.01.2015 | © Prof. Dr. Uwe Schmidt |
