| 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 | } |