1 /* Adapted from public domain sources written by D. J. Bernstein */
2
3 #include <errno.h>
4 #include <string.h>
5 #include <unistd.h>
6 #include "cdb.h"
7 #include "uint32.h"
8
cdb_read(struct cdb * c,unsigned char * buf,unsigned int len,uint32 pos)9 int cdb_read(struct cdb *c,unsigned char *buf,unsigned int len,uint32 pos)
10 {
11 if (c->map) {
12 if ((pos > c->size) || (c->size - pos < len)) goto FORMAT;
13 memcpy(buf, c->map + pos, len);
14 }
15 else {
16 if (lseek(c->fd, pos, SEEK_SET) == -1) return -1;
17 while (len > 0) {
18 int r;
19 do
20 r = read(c->fd,buf,len);
21 while ((r == -1) && (errno == EINTR));
22 if (r == -1) return -1;
23 if (r == 0) goto FORMAT;
24 buf += r;
25 len -= r;
26 }
27 }
28 return 0;
29
30 FORMAT:
31 #ifdef EPROTO
32 errno = EPROTO;
33 #else
34 errno = EINTR;
35 #endif
36 return -1;
37 }
38
match(struct cdb * c,const char * key,unsigned int len,uint32 pos)39 static int match(struct cdb *c,const char *key,unsigned int len,uint32 pos)
40 {
41 unsigned char buf[32];
42 unsigned int n;
43
44 while (len > 0) {
45 n = sizeof buf;
46 if (n > len) n = len;
47 if (cdb_read(c,buf,n,pos) == -1) return -1;
48 if (memcmp(buf, key, n) != 0) return 0;
49 pos += n;
50 key += n;
51 len -= n;
52 }
53 return 1;
54 }
55
cdb_findnext(struct cdb * c,const char * key,unsigned int len)56 int cdb_findnext(struct cdb *c,const char *key,unsigned int len)
57 {
58 unsigned char buf[8];
59 uint32 pos;
60 uint32 u;
61
62 if (!c->loop) {
63 u = cdb_hash(key,len);
64 if (cdb_read(c,buf,8,(u << 3) & 2047) == -1) return -1;
65 c->hslots = uint32_get(buf + 4);
66 if (!c->hslots) return 0;
67 c->hpos = uint32_get(buf);
68 c->khash = u;
69 u >>= 8;
70 u %= c->hslots;
71 u <<= 3;
72 c->kpos = c->hpos + u;
73 }
74
75 while (c->loop < c->hslots) {
76 if (cdb_read(c,buf,8,c->kpos) == -1) return -1;
77 pos = uint32_get(buf + 4);
78 if (!pos) return 0;
79 c->loop += 1;
80 c->kpos += 8;
81 if (c->kpos == c->hpos + (c->hslots << 3)) c->kpos = c->hpos;
82 u = uint32_get(buf);
83 if (u == c->khash) {
84 if (cdb_read(c,buf,8,pos) == -1) return -1;
85 u = uint32_get(buf);
86 if (u == len)
87 switch(match(c,key,len,pos + 8)) {
88 case -1:
89 return -1;
90 case 1:
91 c->dlen = uint32_get(buf + 4);
92 c->dpos = pos + 8 + len;
93 return 1;
94 }
95 }
96 }
97
98 return 0;
99 }
100
cdb_find(struct cdb * c,const char * key,unsigned int len)101 int cdb_find(struct cdb *c,const char *key,unsigned int len)
102 {
103 cdb_findstart(c);
104 return cdb_findnext(c,key,len);
105 }
106