Commit | Line | Data |
---|---|---|
8d5530c4 MW |
1 | #include "cdbmake.h" |
2 | ||
3 | void cdbmake_init(cdbm) | |
4 | struct cdbmake *cdbm; | |
5 | { | |
6 | cdbm->head = 0; | |
7 | cdbm->split = 0; | |
8 | cdbm->hash = 0; | |
9 | cdbm->numentries = 0; | |
10 | } | |
11 | ||
12 | int cdbmake_add(cdbm,h,p,alloc) | |
13 | struct cdbmake *cdbm; | |
14 | uint32 h; | |
15 | uint32 p; | |
16 | char *(*alloc)(); | |
17 | { | |
18 | struct cdbmake_hplist *head; | |
19 | ||
20 | head = cdbm->head; | |
21 | if (!head || (head->num >= CDBMAKE_HPLIST)) { | |
22 | head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist)); | |
23 | if (!head) return 0; | |
24 | head->num = 0; | |
25 | head->next = cdbm->head; | |
26 | cdbm->head = head; | |
27 | } | |
28 | head->hp[head->num].h = h; | |
29 | head->hp[head->num].p = p; | |
30 | ++head->num; | |
31 | ++cdbm->numentries; | |
32 | return 1; | |
33 | } | |
34 | ||
35 | int cdbmake_split(cdbm,alloc) | |
36 | struct cdbmake *cdbm; | |
37 | char *(*alloc)(); | |
38 | { | |
39 | int i; | |
40 | uint32 u; | |
41 | uint32 memsize; | |
42 | struct cdbmake_hplist *x; | |
43 | ||
44 | for (i = 0;i < 256;++i) | |
45 | cdbm->count[i] = 0; | |
46 | ||
47 | for (x = cdbm->head;x;x = x->next) { | |
48 | i = x->num; | |
49 | while (i--) | |
50 | ++cdbm->count[255 & x->hp[i].h]; | |
51 | } | |
52 | ||
53 | memsize = 1; | |
54 | for (i = 0;i < 256;++i) { | |
55 | u = cdbm->count[i] * 2; | |
56 | if (u > memsize) | |
57 | memsize = u; | |
58 | } | |
59 | ||
60 | memsize += cdbm->numentries; /* no overflow possible up to now */ | |
61 | u = (uint32) 0 - (uint32) 1; | |
62 | u /= sizeof(struct cdbmake_hp); | |
63 | if (memsize > u) return 0; | |
64 | ||
65 | cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp)); | |
66 | if (!cdbm->split) return 0; | |
67 | ||
68 | cdbm->hash = cdbm->split + cdbm->numentries; | |
69 | ||
70 | u = 0; | |
71 | for (i = 0;i < 256;++i) { | |
72 | u += cdbm->count[i]; /* bounded by numentries, so no overflow */ | |
73 | cdbm->start[i] = u; | |
74 | } | |
75 | ||
76 | for (x = cdbm->head;x;x = x->next) { | |
77 | i = x->num; | |
78 | while (i--) | |
79 | cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i]; | |
80 | } | |
81 | ||
82 | return 1; | |
83 | } | |
84 | ||
85 | uint32 cdbmake_throw(cdbm,pos,b) | |
86 | struct cdbmake *cdbm; | |
87 | uint32 pos; | |
88 | int b; | |
89 | { | |
90 | uint32 len; | |
91 | uint32 j; | |
92 | uint32 count; | |
93 | struct cdbmake_hp *hp; | |
94 | uint32 where; | |
95 | ||
96 | count = cdbm->count[b]; | |
97 | ||
98 | len = count + count; /* no overflow possible */ | |
99 | cdbmake_pack(cdbm->final + 8 * b,pos); | |
100 | cdbmake_pack(cdbm->final + 8 * b + 4,len); | |
101 | ||
102 | if (len) { | |
103 | for (j = 0;j < len;++j) | |
104 | cdbm->hash[j].h = cdbm->hash[j].p = 0; | |
105 | ||
106 | hp = cdbm->split + cdbm->start[b]; | |
107 | for (j = 0;j < count;++j) { | |
108 | where = (hp->h >> 8) % len; | |
109 | while (cdbm->hash[where].p) | |
110 | if (++where == len) | |
111 | where = 0; | |
112 | cdbm->hash[where] = *hp++; | |
113 | } | |
114 | } | |
115 | ||
116 | return len; | |
117 | } |