3 void cdbmake_init(cdbm
)
12 int cdbmake_add(cdbm
,h
,p
,alloc
)
18 struct cdbmake_hplist
*head
;
21 if (!head
|| (head
->num
>= CDBMAKE_HPLIST
)) {
22 head
= (struct cdbmake_hplist
*) alloc(sizeof(struct cdbmake_hplist
));
25 head
->next
= cdbm
->head
;
28 head
->hp
[head
->num
].h
= h
;
29 head
->hp
[head
->num
].p
= p
;
35 int cdbmake_split(cdbm
,alloc
)
42 struct cdbmake_hplist
*x
;
44 for (i
= 0;i
< 256;++i
)
47 for (x
= cdbm
->head
;x
;x
= x
->next
) {
50 ++cdbm
->count
[255 & x
->hp
[i
].h
];
54 for (i
= 0;i
< 256;++i
) {
55 u
= cdbm
->count
[i
] * 2;
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;
65 cdbm
->split
= (struct cdbmake_hp
*) alloc(memsize
* sizeof(struct cdbmake_hp
));
66 if (!cdbm
->split
) return 0;
68 cdbm
->hash
= cdbm
->split
+ cdbm
->numentries
;
71 for (i
= 0;i
< 256;++i
) {
72 u
+= cdbm
->count
[i
]; /* bounded by numentries, so no overflow */
76 for (x
= cdbm
->head
;x
;x
= x
->next
) {
79 cdbm
->split
[--cdbm
->start
[255 & x
->hp
[i
].h
]] = x
->hp
[i
];
85 uint32
cdbmake_throw(cdbm
,pos
,b
)
93 struct cdbmake_hp
*hp
;
96 count
= cdbm
->count
[b
];
98 len
= count
+ count
; /* no overflow possible */
99 cdbmake_pack(cdbm
->final
+ 8 * b
,pos
);
100 cdbmake_pack(cdbm
->final
+ 8 * b
+ 4,len
);
103 for (j
= 0;j
< len
;++j
)
104 cdbm
->hash
[j
].h
= cdbm
->hash
[j
].p
= 0;
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
)
112 cdbm
->hash
[where
] = *hp
++;