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
|
/* $Id: cdb_init.c,v 1.12 2008-11-06 18:07:04 mjt Exp $
* cdb_init, cdb_free and cdb_read routines
*
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
* Public domain.
*/
#include "cdb.h"
int
cdb_find(struct cdb *cdbp, const void *key, unsigned klen)
{
const unsigned char *htp; /* hash table pointer */
const unsigned char *htab; /* hash table */
const unsigned char *htend; /* end of hash table */
unsigned httodo; /* ht bytes left to look */
unsigned pos, n;
unsigned hval;
if (klen >= cdbp->cdb_dend) /* if key size is too large */
return 0;
hval = cdb_hash (key, klen);
/* find (pos,n) hash table to use */
/* first 2048 bytes (toc) are always available */
/* (hval % 256) * 8 */
htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
n = cdb_unpack (htp + 4); /* table size */
if (!n) /* empty table */
return 0; /* not found */
httodo = n << 3; /* bytes of htab to lookup */
pos = cdb_unpack (htp); /* htab position */
if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
|| pos < cdbp->cdb_dend /* is htab inside data section ? */
|| pos > cdbp->cdb_fsize /* htab start within file ? */
|| httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
return errno = EPROTO, -1;
htab = cdbp->cdb_mem + pos; /* htab pointer */
htend = htab + httodo; /* after end of htab */
/* htab starting position: rest of hval modulo htsize, 8bytes per elt */
htp = htab + (((hval >> 8) % n) << 3);
for (;;) {
pos = cdb_unpack (htp + 4); /* record position */
if (!pos)
return 0;
if (cdb_unpack (htp) == hval) {
if (pos > cdbp->cdb_dend - 8) /* key+val lengths */
return errno = EPROTO, -1;
if (cdb_unpack (cdbp->cdb_mem + pos) == klen) {
if (cdbp->cdb_dend - klen < pos + 8)
return errno = EPROTO, -1;
if (memcmp (key, cdbp->cdb_mem + pos + 8, klen) == 0) {
n = cdb_unpack (cdbp->cdb_mem + pos + 4);
pos += 8;
if (cdbp->cdb_dend < n || cdbp->cdb_dend - n < pos + klen)
return errno = EPROTO, -1;
cdbp->cdb_kpos = pos;
cdbp->cdb_klen = klen;
cdbp->cdb_vpos = pos + klen;
cdbp->cdb_vlen = n;
return 1;
}
}
}
httodo -= 8;
if (!httodo)
return 0;
if ((htp += 8) >= htend)
htp = htab;
}
}
int
cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
const void *key, unsigned klen)
{
unsigned n, pos;
cdbfp->cdb_cdbp = cdbp;
cdbfp->cdb_key = key;
cdbfp->cdb_klen = klen;
cdbfp->cdb_hval = cdb_hash(key, klen);
cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
n = cdb_unpack(cdbfp->cdb_htp + 4);
cdbfp->cdb_httodo = n << 3;
if (!n)
return 0;
pos = cdb_unpack(cdbfp->cdb_htp);
if (n > (cdbp->cdb_fsize >> 3)
|| pos < cdbp->cdb_dend
|| pos > cdbp->cdb_fsize
|| cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
return errno = EPROTO, -1;
cdbfp->cdb_htab = cdbp->cdb_mem + pos;
cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
return 1;
}
int
cdb_findnext(struct cdb_find *cdbfp) {
struct cdb *cdbp = cdbfp->cdb_cdbp;
unsigned pos, n;
unsigned klen = cdbfp->cdb_klen;
while(cdbfp->cdb_httodo) {
pos = cdb_unpack(cdbfp->cdb_htp + 4);
if (!pos)
return 0;
n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
cdbfp->cdb_htp = cdbfp->cdb_htab;
cdbfp->cdb_httodo -= 8;
if (n) {
if (pos > cdbp->cdb_fsize - 8)
return errno = EPROTO, -1;
if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
if (cdbp->cdb_fsize - klen < pos + 8)
return errno = EPROTO, -1;
if (memcmp(cdbfp->cdb_key,
cdbp->cdb_mem + pos + 8, klen) == 0) {
n = cdb_unpack(cdbp->cdb_mem + pos + 4);
pos += 8;
if (cdbp->cdb_fsize < n ||
cdbp->cdb_fsize - n < pos + klen)
return errno = EPROTO, -1;
cdbp->cdb_kpos = pos;
cdbp->cdb_klen = klen;
cdbp->cdb_vpos = pos + klen;
cdbp->cdb_vlen = n;
return 1;
}
}
}
}
return 0;
}
|
