1 /* hdb_find.c
2 ** wcm, 2010.05.29 - 2010.12.14
3 ** ===
4 */
5
6 #include <errno.h>
7
8 /* lasagna: */
9 #include "buf.h"
10 #include "uchar.h"
11 #include "upak.h"
12
13 /* libhdb: */
14 #include "hdb.h"
15
16 /* subroutines in scope: */
17 static int hdb_key_match(struct hdb *H, const uchar_t *key, uint32_t klen, uint32_t kpos);
18 static int hdb_hash_probe(struct hdb *H, uint32_t target);
19
20
21 /* hdb_key_match()
22 ** compare record key of klen at kpos
23 ** to search key initialized in hdb_find()
24 */
25 static
26 int
hdb_key_match(struct hdb * H,const uchar_t * key,uint32_t klen,uint32_t kpos)27 hdb_key_match(struct hdb *H, const uchar_t *key, uint32_t klen, uint32_t kpos)
28 {
29 uchar_t kbuf[80]; /* compare upto 80 bytes of key at a time */
30 uint32_t n;
31
32 while(klen > 0){
33 n = sizeof kbuf;
34 if(n > klen) n = klen;
35 if(hdb_read(H, kbuf, n, kpos) == -1){
36 /* io error: */
37 return -1;
38 }
39 if(buf_cmp(key, kbuf, n) != 0){
40 /* no match: */
41 return 0;
42 }
43 kpos += n;
44 klen -= n;
45 }
46
47 /* match! */
48 return 1;
49 }
50
51
52 /* hdb_hash_probe()
53 ** after hdb_find() initialization,
54 ** probe for match in hash table beginning at target
55 ** return:
56 ** 1: key match found, cursors setup accordingly
57 ** 0: key match not found
58 ** -1: error
59 */
60 static
61 int
hdb_hash_probe(struct hdb * H,uint32_t target)62 hdb_hash_probe(struct hdb *H, uint32_t target)
63 {
64 /* initialized by hdb_find(): */
65 uint32_t hash = H->h;
66 uint32_t klen = H->klen;
67 uint32_t tbase = H->tbase;
68 uint32_t tslots = H->tslots;
69 /* etc: */
70 uint32_t fp;
71 uchar_t nbuf[8];
72 uint32_t rpos;
73 uint32_t slot_hash;
74 uint32_t u;
75
76 /* probe for matching key starting at target: */
77 while(target < tslots){
78 fp = tbase + (target * 8);
79 if(hdb_read(H, nbuf, sizeof nbuf, fp) == -1){
80 return -1;
81 }
82 rpos = upak32_UNPACK(nbuf + 4);
83 if(rpos == 0){
84 /* slot empty, key not found: */
85 return 0;
86 }
87 /* else, check hash: */
88 slot_hash = upak32_UNPACK(nbuf);
89 if(slot_hash == hash){
90 /* hash match; test record key match: */
91 if(hdb_read(H, nbuf, 6, rpos) == -1){
92 return -1;
93 }
94 u = upak24_UNPACK(nbuf);
95 if(u == klen){
96 switch(hdb_key_match(H, H->key, klen, rpos + 6)){
97 case -1:
98 /* io error: */
99 return -1; break;
100 case 1:
101 /* match! */
102 H->sN = target;
103 H->rpos = rpos;
104 H->dlen = upak24_UNPACK(nbuf + 3);
105 return 1;
106 break;
107 default:
108 /* no match; continue probe... */
109 break;
110 }
111 }
112 }
113
114 /* advance target: */
115 ++target;
116 if(target == tslots) target = 0;
117 if(target == H->s0){
118 /* back at original target; key not found: */
119 break;
120 }
121 }
122
123 /* not found: */
124 return 0;
125 }
126
127
128 int
hdb_find(struct hdb * H,const uchar_t * key,uint32_t klen)129 hdb_find(struct hdb *H, const uchar_t *key, uint32_t klen)
130 {
131 uint32_t hash, ntab, tslots, target;
132
133 /* constrain klen to 24-bit length: */
134 if(klen > HDB_U24MAX){
135 errno = ERANGE;
136 return -1;
137 }
138
139 /* search initialization: */
140 H->key = (uchar_t *)key;
141 H->klen = klen;
142 H->h = hash = hdb_hash(key, klen);
143
144 /* subtable: */
145 ntab = hdb_NTAB(hash);
146
147 /* subtable offet: */
148 H->tbase = H->tndx[ntab].offset;
149 /* slots in subtable: */
150 H->tslots = tslots = H->tndx[ntab].value;
151
152 if(tslots == 0){
153 /* no slots in this table; key not found: */
154 return 0;
155 }
156
157 /* target slot for this key: */
158 H->s0 = target = hdb_SLOT(hash, tslots);
159
160 /* probe: */
161 return hdb_hash_probe(H, target);
162 }
163
164
165 int
hdb_findnext(struct hdb * H)166 hdb_findnext(struct hdb *H)
167 {
168 uint32_t target = H->sN;
169
170 /* advance target from last succesful find: */
171 ++target;
172 if(target == H->tslots) target = 0;
173 if(target == H->s0){
174 /* back at original target; key not found: */
175 return 0;
176 }
177
178 /* probe: */
179 return hdb_hash_probe(H, target);
180 }
181
182
183 /* eof (hdb_find.c) */
184