Make it build on W32 again.
[gnupg.git] / dirmngr / cdblib.c
1 /* cdblib.c - all CDB library functions.
2  *
3  * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
4  * Public domain.
5  *
6  * Taken from tinycdb-0.73 and merged into one file for easier
7  * inclusion into Dirmngr.  By Werner Koch <wk@gnupg.org> 2003-12-12.
8  */
9
10 /* A cdb database is a single file used to map `keys' to `values',
11    having records of (key,value) pairs.  File consists of 3 parts: toc
12    (table of contents), data and index (hash tables).
13
14    Toc has fixed length of 2048 bytes, containing 256 pointers to hash
15    tables inside index sections.  Every pointer consists of position
16    of a hash table in bytes from the beginning of a file, and a size
17    of a hash table in entries, both are 4-bytes (32 bits) unsigned
18    integers in little-endian form.  Hash table length may have zero
19    length, meaning that corresponding hash table is empty.
20
21    Right after toc section, data section follows without any
22    alingment.  It consists of series of records, each is a key length,
23    value (data) length, key and value.  Again, key and value length
24    are 4-byte unsigned integers.  Each next record follows previous
25    without any special alignment.
26
27    After data section, index (hash tables) section follows.  It should
28    be looked to in conjunction with toc section, where each of max 256
29    hash tables are defined.  Index section consists of series of hash
30    tables, with starting position and length defined in toc section.
31    Every hash table is a sequence of records each holds two numbers:
32    key's hash value and record position inside data section (bytes
33    from the beginning of a file to first byte of key length starting
34    data record).  If record position is zero, then this is an empty
35    hash table slot, pointed to nowhere.
36
37    CDB hash function is
38      hv = ((hv << 5) + hv) ^ c
39    for every single c byte of a key, starting with hv = 5381.
40
41    Toc section indexed by (hv % 256), i.e. hash value modulo 256
42    (number of entries in toc section).
43
44    In order to find a record, one should: first, compute the hash
45    value (hv) of a key.  Second, look to hash table number hv modulo
46    256.  If it is empty, then there is no such key exists.  If it is
47    not empty, then third, loop by slots inside that hash table,
48    starting from slot with number hv divided by 256 modulo length of
49    that table, or ((hv / 256) % htlen), searching for this hv in hash
50    table.  Stop search on empty slot (if record position is zero) or
51    when all slots was probed (note cyclic search, jumping from end to
52    beginning of a table).  When hash value in question is found in
53    hash table, look to key of corresponding record, comparing it with
54    key in question.  If them of the same length and equals to each
55    other, then record is found, overwise, repeat with next hash table
56    slot.  Note that there may be several records with the same key.
57 */
58
59 #ifdef HAVE_CONFIG_H
60 #include <config.h>
61 #endif
62 #include <stdlib.h> 
63 #include <errno.h>
64 #include <string.h>
65 #include <unistd.h>
66 #include <sys/types.h>
67 #ifdef _WIN32
68 # include <windows.h>
69 #else
70 # include <sys/mman.h>
71 # ifndef MAP_FAILED
72 #  define MAP_FAILED ((void*)-1)
73 # endif
74 #endif
75 #include <sys/stat.h>
76 #include "cdb.h"
77
78 #ifndef EPROTO
79 # define EPROTO EINVAL
80 #endif
81 #ifndef SEEK_SET
82 # define SEEK_SET 0
83 #endif
84
85
86 struct cdb_rec {
87   cdbi_t hval;
88   cdbi_t rpos;
89 };
90   
91 struct cdb_rl {
92   struct cdb_rl *next;
93   cdbi_t cnt;
94   struct cdb_rec rec[254];
95 };
96
97 static int make_find(struct cdb_make *cdbmp,
98                    const void *key, cdbi_t klen, cdbi_t hval,
99                    struct cdb_rl **rlp);
100 static int make_write(struct cdb_make *cdbmp,
101                     const char *ptr, cdbi_t len);
102
103
104
105 /* Initializes structure given by CDBP pointer and associates it with
106    the open file descriptor FD.  Allocate memory for the structure
107    itself if needed and file open operation should be done by
108    application.  File FD should be opened at least read-only, and
109    should be seekable.  Routine returns 0 on success or negative value
110    on error. */
111 int
112 cdb_init(struct cdb *cdbp, int fd)
113 {
114   struct stat st;
115   unsigned char *mem;
116   unsigned fsize;
117 #ifdef _WIN32
118   HANDLE hFile, hMapping;
119 #endif
120
121   /* get file size */
122   if (fstat(fd, &st) < 0)
123     return -1;
124   /* trivial sanity check: at least toc should be here */
125   if (st.st_size < 2048) {
126     errno = EPROTO;
127     return -1;
128   }
129   fsize = (unsigned)(st.st_size & 0xffffffffu);
130   /* memory-map file */
131 #ifdef _WIN32
132   hFile = (HANDLE) _get_osfhandle(fd);
133   if (hFile == (HANDLE) -1)
134     return -1;
135   hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
136   if (!hMapping)
137     return -1;
138   mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
139   if (!mem)
140     return -1;
141 #else
142   mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0);
143   if (mem == MAP_FAILED)
144     return -1;
145 #endif /* _WIN32 */
146
147   cdbp->cdb_fd = fd;
148   cdbp->cdb_fsize = st.st_size;
149   cdbp->cdb_mem = mem;
150
151 #if 0
152   /* XXX don't know well about madvise syscall -- is it legal
153      to set different options for parts of one mmap() region?
154      There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc...
155   */
156 #ifdef MADV_RANDOM
157   /* set madvise() parameters. Ignore errors for now if system
158      doesn't support it */
159   madvise(mem, 2048, MADV_WILLNEED);
160   madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM);
161 #endif
162 #endif
163
164   cdbp->cdb_vpos = cdbp->cdb_vlen = 0;
165
166   return 0;
167 }
168
169
170 /* Frees the internal resources held by structure.  Note that this
171    routine does not close the file. */
172 void
173 cdb_free(struct cdb *cdbp)
174 {
175   if (cdbp->cdb_mem) {
176 #ifdef _WIN32
177     HANDLE hFile, hMapping;
178 #endif
179 #ifdef _WIN32
180     hFile = (HANDLE) _get_osfhandle(cdbp->cdb_fd);
181     hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
182     UnmapViewOfFile((void*) cdbp->cdb_mem);
183     CloseHandle(hMapping);
184 #else
185     munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize);
186 #endif /* _WIN32 */
187     cdbp->cdb_mem = NULL;
188   }
189   cdbp->cdb_fsize = 0;
190 }
191
192
193 /* Read data from cdb file, starting at position pos of length len,
194    placing result to buf.  This routine may be used to get actual
195    value found by cdb_find() or other routines that returns position
196    and length of a data.  Returns 0 on success or negative value on
197    error. */
198 int
199 cdb_read(const struct cdb *cdbp, void *buf, unsigned len, cdbi_t pos)
200 {
201   if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) {
202     errno = EPROTO;
203     return -1;
204   }
205   memcpy(buf, cdbp->cdb_mem + pos, len);
206   return 0;
207 }
208
209
210 /* Attempts to find a key given by (key,klen) parameters.  If key
211    exists in database, routine returns 1 and places position and
212    length of value associated with this key to internal fields inside
213    cdbp structure, to be accessible by cdb_datapos() and
214    cdb_datalen().  If key is not in database, routines returns 0.  On
215    error, negative value is returned.  Note that using cdb_find() it
216    is possible to lookup only first record with a given key. */
217 int
218 cdb_find(struct cdb *cdbp, const void *key, cdbi_t klen)
219 {
220   const unsigned char *htp;     /* hash table pointer */
221   const unsigned char *htab;    /* hash table */
222   const unsigned char *htend;   /* end of hash table */
223   cdbi_t httodo;                /* ht bytes left to look */
224   cdbi_t pos, n;
225
226   cdbi_t hval;
227
228   if (klen > cdbp->cdb_fsize)   /* if key size is larger than file */
229     return 0;
230
231   hval = cdb_hash(key, klen);
232
233   /* find (pos,n) hash table to use */
234   /* first 2048 bytes (toc) are always available */
235   /* (hval % 256) * 8 */
236   htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
237   n = cdb_unpack(htp + 4);      /* table size */
238   if (!n)                       /* empty table */
239     return 0;                   /* not found */
240   httodo = n << 3;              /* bytes of htab to lookup */
241   pos = cdb_unpack(htp);        /* htab position */
242   if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
243       || pos > cdbp->cdb_fsize /* htab start within file ? */
244       || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
245   {
246     errno = EPROTO;
247     return -1;
248   }
249
250   htab = cdbp->cdb_mem + pos;   /* htab pointer */
251   htend = htab + httodo;        /* after end of htab */
252   /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
253   htp = htab + (((hval >> 8) % n) << 3);
254
255   for(;;) {
256     pos = cdb_unpack(htp + 4);  /* record position */
257     if (!pos)
258       return 0;
259     if (cdb_unpack(htp) == hval) {
260       if (pos > cdbp->cdb_fsize - 8) { /* key+val lengths */
261         errno = EPROTO;
262         return -1;
263       }
264       if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
265         if (cdbp->cdb_fsize - klen < pos + 8) {
266           errno = EPROTO;
267           return -1;
268         }
269         if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
270           n = cdb_unpack(cdbp->cdb_mem + pos + 4);
271           pos += 8 + klen;
272           if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
273             errno = EPROTO;
274             return -1;
275           }
276           cdbp->cdb_vpos = pos;
277           cdbp->cdb_vlen = n;
278           return 1;
279         }
280       }
281     }
282     httodo -= 8;
283     if (!httodo)
284       return 0;
285     if ((htp += 8) >= htend)
286       htp = htab;
287   }
288
289 }
290
291
292
293 /* Sequential-find routines that used separate structure.  It is
294    possible to have many than one record with the same key in a
295    database, and these routines allows to enumerate all them.
296    cdb_findinit() initializes search structure pointed to by cdbfp.
297    It will return negative value on error or 0 on success.  cdb_findĀ­
298    next() attempts to find next matching key, setting value position
299    and length in cdbfp structure.  It will return positive value if
300    given key was found, 0 if there is no more such key(s), or negative
301    value on error.  To access value position and length after
302    successeful call to cdb_findnext() (when it returned positive
303    result), use cdb_datapos() and cdb_datalen() macros with cdbp
304    pointer.  It is error to use cdb_findnext() after it returned 0 or
305    error condition.  These routines is a bit slower than
306    cdb_find(). 
307
308    Setting KEY to NULL will start a sequential search through the
309    entire DB.
310 */
311 int
312 cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp,
313              const void *key, cdbi_t klen)
314 {
315   cdbi_t n, pos;
316
317   cdbfp->cdb_cdbp = cdbp;
318   cdbfp->cdb_key  = key;
319   cdbfp->cdb_klen = klen;
320   cdbfp->cdb_hval = key? cdb_hash(key, klen) : 0;
321
322   if (key)
323     {
324       cdbfp->cdb_htp = cdbp->cdb_mem + ((cdbfp->cdb_hval << 3) & 2047);
325       n = cdb_unpack(cdbfp->cdb_htp + 4);
326       cdbfp->cdb_httodo = n << 3; /* Set to size of hash table. */
327       if (!n)
328         return 0; /* The hash table is empry. */
329       pos = cdb_unpack(cdbfp->cdb_htp);
330       if (n > (cdbp->cdb_fsize >> 3)
331           || pos > cdbp->cdb_fsize
332           || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
333         {
334           errno = EPROTO;
335           return -1;
336         }
337
338       cdbfp->cdb_htab = cdbp->cdb_mem + pos;
339       cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
340       cdbfp->cdb_htp = cdbfp->cdb_htab + (((cdbfp->cdb_hval >> 8) % n) << 3);
341     }
342   else /* Walk over all entries. */
343     {
344       cdbfp->cdb_hval = 0; 
345       /* Force stepping in findnext. */
346       cdbfp->cdb_htp = cdbfp->cdb_htend = cdbp->cdb_mem;
347     }
348   return 0;
349 }
350
351
352 /* See cdb_findinit. */
353 int 
354 cdb_findnext(struct cdb_find *cdbfp)
355 {
356   cdbi_t pos, n;
357   struct cdb *cdbp = cdbfp->cdb_cdbp;
358
359   if (cdbfp->cdb_key)
360     {
361       while(cdbfp->cdb_httodo) {
362         pos = cdb_unpack(cdbfp->cdb_htp + 4);
363         if (!pos)
364           return 0;
365         n = cdb_unpack(cdbfp->cdb_htp) == cdbfp->cdb_hval;
366         if ((cdbfp->cdb_htp += 8) >= cdbfp->cdb_htend)
367           cdbfp->cdb_htp = cdbfp->cdb_htab;
368         cdbfp->cdb_httodo -= 8;
369         if (n) {
370           if (pos > cdbp->cdb_fsize - 8) {
371             errno = EPROTO;
372             return -1;
373           }
374           if (cdb_unpack(cdbp->cdb_mem + pos) == cdbfp->cdb_klen) {
375             if (cdbp->cdb_fsize - cdbfp->cdb_klen < pos + 8) {
376               errno = EPROTO;
377               return -1;
378             }
379             if (memcmp(cdbfp->cdb_key,
380                        cdbp->cdb_mem + pos + 8, cdbfp->cdb_klen) == 0) {
381               n = cdb_unpack(cdbp->cdb_mem + pos + 4);
382               pos += 8 + cdbfp->cdb_klen;
383               if (cdbp->cdb_fsize < n || cdbp->cdb_fsize - n < pos) {
384                 errno = EPROTO;
385                 return -1;
386               }
387               cdbp->cdb_vpos = pos;
388               cdbp->cdb_vlen = n;
389               return 1;
390             }
391           }
392         }
393       }
394     }
395   else /* Walk over all entries. */
396     {
397       do
398         {
399           while (cdbfp->cdb_htp >= cdbfp->cdb_htend)
400             {
401               if (cdbfp->cdb_hval > 255)
402                 return 0; /* No more items. */
403               
404               cdbfp->cdb_htp = cdbp->cdb_mem + cdbfp->cdb_hval * 8;
405               cdbfp->cdb_hval++; /* Advance for next round. */
406               pos = cdb_unpack (cdbfp->cdb_htp);     /* Offset of table. */
407               n   = cdb_unpack (cdbfp->cdb_htp + 4); /* Number of entries. */
408               cdbfp->cdb_httodo = n * 8;             /* Size of table. */
409               if (n > (cdbp->cdb_fsize / 8)
410                   || pos > cdbp->cdb_fsize
411                   || cdbfp->cdb_httodo > cdbp->cdb_fsize - pos)
412                 {
413                   errno = EPROTO;
414                   return -1;
415                 }
416               
417               cdbfp->cdb_htab  = cdbp->cdb_mem + pos;
418               cdbfp->cdb_htend = cdbfp->cdb_htab + cdbfp->cdb_httodo;
419               cdbfp->cdb_htp   = cdbfp->cdb_htab;
420             }
421           
422           pos = cdb_unpack (cdbfp->cdb_htp + 4); /* Offset of record. */
423           cdbfp->cdb_htp += 8;
424         } 
425       while (!pos);
426       if (pos > cdbp->cdb_fsize - 8)
427         {
428           errno = EPROTO;
429           return -1;
430         }
431       
432       cdbp->cdb_kpos = pos + 8;
433       cdbp->cdb_klen = cdb_unpack(cdbp->cdb_mem + pos);
434       cdbp->cdb_vpos = pos + 8 + cdbp->cdb_klen;
435       cdbp->cdb_vlen = cdb_unpack(cdbp->cdb_mem + pos + 4);
436       n = 8 + cdbp->cdb_klen + cdbp->cdb_vlen;
437       if ( pos > cdbp->cdb_fsize || pos > cdbp->cdb_fsize - n)
438         {
439           errno = EPROTO;
440           return -1;
441         }
442       return 1; /* Found. */
443     }
444   return 0;
445 }
446
447 /* Read a chunk from file, ignoring interrupts (EINTR) */
448 int
449 cdb_bread(int fd, void *buf, int len)
450 {
451   int l;
452   while(len > 0) {
453     do l = read(fd, buf, len);
454     while(l < 0 && errno == EINTR);
455     if (l <= 0) {
456       if (!l)
457         errno = EIO;
458       return -1;
459     }
460     buf = (char*)buf + l;
461     len -= l;
462   }
463   return 0;
464 }
465
466 /* Find a given key in cdb file, seek a file pointer to it's value and
467    place data length to *dlenp. */
468 int
469 cdb_seek(int fd, const void *key, unsigned klen, cdbi_t *dlenp)
470 {
471   cdbi_t htstart;               /* hash table start position */
472   cdbi_t htsize;                /* number of elements in a hash table */
473   cdbi_t httodo;                /* hash table elements left to look */
474   cdbi_t hti;                   /* hash table index */
475   cdbi_t pos;                   /* position in a file */
476   cdbi_t hval;                  /* key's hash value */
477   unsigned char rbuf[64];       /* read buffer */
478   int needseek = 1;             /* if we should seek to a hash slot */
479
480   hval = cdb_hash(key, klen);
481   pos = (hval & 0xff) << 3; /* position in TOC */
482   /* read the hash table parameters */
483   if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
484     return -1;
485   if ((htsize = cdb_unpack(rbuf + 4)) == 0)
486     return 0;
487   hti = (hval >> 8) % htsize;   /* start position in hash table */
488   httodo = htsize;
489   htstart = cdb_unpack(rbuf);
490
491   for(;;) {
492     if (needseek && lseek(fd, htstart + (hti << 3), SEEK_SET) < 0)
493       return -1;
494     if (cdb_bread(fd, rbuf, 8) < 0)
495       return -1;
496     if ((pos = cdb_unpack(rbuf + 4)) == 0) /* not found */
497       return 0;
498
499     if (cdb_unpack(rbuf) != hval) /* hash value not matched */
500       needseek = 0;
501     else { /* hash value matched */
502       if (lseek(fd, pos, SEEK_SET) < 0 || cdb_bread(fd, rbuf, 8) < 0)
503         return -1;
504       if (cdb_unpack(rbuf) == klen) { /* key length matches */
505         /* read the key from file and compare with wanted */
506         cdbi_t l = klen, c;
507         const char *k = (const char*)key;
508         if (*dlenp)
509           *dlenp = cdb_unpack(rbuf + 4); /* save value length */
510         for(;;) {
511           if (!l) /* the whole key read and matches, return */
512             return 1;
513           c = l > sizeof(rbuf) ? sizeof(rbuf) : l;
514           if (cdb_bread(fd, rbuf, c) < 0)
515             return -1;
516           if (memcmp(rbuf, k, c) != 0) /* no, it differs, stop here */
517             break;
518           k += c; l -= c;
519         }
520       }
521       needseek = 1; /* we're looked to other place, should seek back */
522     }
523     if (!--httodo)
524       return 0;
525     if (++hti == htsize) {
526       hti = htstart;
527       needseek = 1;
528     }
529   }
530 }
531
532 cdbi_t
533 cdb_unpack(const unsigned char buf[4])
534 {
535   cdbi_t n = buf[3];
536   n <<= 8; n |= buf[2];
537   n <<= 8; n |= buf[1];
538   n <<= 8; n |= buf[0];
539   return n;
540 }
541
542 /* Add record with key (KEY,KLEN) and value (VAL,VLEN) to a database.
543    Returns 0 on success or negative value on error.  Note that this
544    routine does not checks if given key already exists, but cdb_find()
545    will not see second record with the same key.  It is not possible
546    to continue building a database if cdb_make_add() returned an error
547    indicator. */
548 int
549 cdb_make_add(struct cdb_make *cdbmp,
550              const void *key, cdbi_t klen,
551              const void *val, cdbi_t vlen)
552 {
553   unsigned char rlen[8];
554   cdbi_t hval;
555   struct cdb_rl *rl;
556   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
557       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
558     errno = ENOMEM;
559     return -1;
560   }
561   hval = cdb_hash(key, klen);
562   rl = cdbmp->cdb_rec[hval&255];
563   if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
564     rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
565     if (!rl) {
566       errno = ENOMEM;
567       return -1;
568     }
569     rl->cnt = 0;
570     rl->next = cdbmp->cdb_rec[hval&255];
571     cdbmp->cdb_rec[hval&255] = rl;
572   }
573   rl->rec[rl->cnt].hval = hval;
574   rl->rec[rl->cnt].rpos = cdbmp->cdb_dpos;
575   ++rl->cnt;
576   ++cdbmp->cdb_rcnt;
577   cdb_pack(klen, rlen);
578   cdb_pack(vlen, rlen + 4);
579   if (make_write(cdbmp, rlen, 8) < 0 ||
580       make_write(cdbmp, key, klen) < 0 ||
581       make_write(cdbmp, val, vlen) < 0)
582     return -1;
583   return 0;
584 }
585
586 int
587 cdb_make_put(struct cdb_make *cdbmp,
588              const void *key, cdbi_t klen,
589              const void *val, cdbi_t vlen,
590              int flags)
591 {
592   unsigned char rlen[8];
593   cdbi_t hval = cdb_hash(key, klen);
594   struct cdb_rl *rl;
595   int c, r;
596
597   switch(flags) {
598     case CDB_PUT_REPLACE:
599     case CDB_PUT_INSERT:
600     case CDB_PUT_WARN:
601       c = make_find(cdbmp, key, klen, hval, &rl);
602       if (c < 0)
603         return -1;
604       if (c) {
605         if (flags == CDB_PUT_INSERT) {
606           errno = EEXIST;
607           return 1;
608         }
609         else if (flags == CDB_PUT_REPLACE) {
610           --c;
611           r = 1;
612           break;
613         }
614         else
615           r = 1;
616       }
617       /* fall */
618
619     case CDB_PUT_ADD:
620       rl = cdbmp->cdb_rec[hval&255];
621       if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) {
622         rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl));
623         if (!rl) {
624           errno = ENOMEM;
625           return -1;
626         }
627         rl->cnt = 0;
628         rl->next = cdbmp->cdb_rec[hval&255];
629         cdbmp->cdb_rec[hval&255] = rl;
630       }
631       c = rl->cnt;
632       r = 0;
633       break;
634
635     default:
636       errno = EINVAL;
637       return -1;
638   }
639
640   if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) ||
641       vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) {
642     errno = ENOMEM;
643     return -1;
644   }
645   rl->rec[c].hval = hval;
646   rl->rec[c].rpos = cdbmp->cdb_dpos;
647   if (c == rl->cnt) {
648     ++rl->cnt;
649     ++cdbmp->cdb_rcnt;
650   }
651   cdb_pack(klen, rlen);
652   cdb_pack(vlen, rlen + 4);
653   if (make_write(cdbmp, rlen, 8) < 0 ||
654       make_write(cdbmp, key, klen) < 0 ||
655       make_write(cdbmp, val, vlen) < 0)
656     return -1;
657   return r;
658 }
659
660
661 static int
662 match(int fd, cdbi_t pos, const char *key, cdbi_t klen)
663 {
664   unsigned char buf[64]; /*XXX cdb_buf may be used here instead */
665   if (lseek(fd, pos, SEEK_SET) < 0 || read(fd, buf, 8) != 8)
666     return -1;
667   if (cdb_unpack(buf) != klen)
668     return 0;
669
670   while(klen > sizeof(buf)) {
671     if (read(fd, buf, sizeof(buf)) != sizeof(buf))
672       return -1;
673     if (memcmp(buf, key, sizeof(buf)) != 0)
674       return 0;
675     key += sizeof(buf);
676     klen -= sizeof(buf);
677   }
678   if (klen) {
679     if (read(fd, buf, klen) != klen)
680       return -1;
681     if (memcmp(buf, key, klen) != 0)
682       return 0;
683   }
684   return 1;
685 }
686
687
688 static int
689 make_find (struct cdb_make *cdbmp,
690            const void *key, cdbi_t klen, cdbi_t hval,
691            struct cdb_rl **rlp)
692 {
693   struct cdb_rl *rl = cdbmp->cdb_rec[hval&255];
694   int r, i;
695   int seeked = 0;
696   while(rl) {
697     for(i = rl->cnt - 1; i >= 0; --i) { /* search backward */
698       if (rl->rec[i].hval != hval)
699         continue;
700       /*XXX this explicit flush may be unnecessary having
701        * smarter match() that looks to cdb_buf too, but
702        * most of a time here spent in finding hash values
703        * (above), not keys */
704       if (cdbmp->cdb_bpos != cdbmp->cdb_buf) {
705         if (write(cdbmp->cdb_fd, cdbmp->cdb_buf,
706                   cdbmp->cdb_bpos - cdbmp->cdb_buf) < 0)
707           return -1;
708         cdbmp->cdb_bpos = cdbmp->cdb_buf;
709       }
710       seeked = 1;
711       r = match(cdbmp->cdb_fd, rl->rec[i].rpos, key, klen);
712       if (!r)
713         continue;
714       if (r < 0)
715         return -1;
716       if (lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
717         return -1;
718       if (rlp)
719         *rlp = rl;
720       return i + 1;
721     }
722     rl = rl->next;
723   }
724   if (seeked && lseek(cdbmp->cdb_fd, cdbmp->cdb_dpos, SEEK_SET) < 0)
725     return -1;
726   return 0;
727 }
728
729 int
730 cdb_make_exists(struct cdb_make *cdbmp,
731                 const void *key, cdbi_t klen)
732 {
733   return make_find(cdbmp, key, klen, cdb_hash(key, klen), NULL);
734 }
735
736
737 void
738 cdb_pack(cdbi_t num, unsigned char buf[4])
739 {
740   buf[0] = num & 255; num >>= 8;
741   buf[1] = num & 255; num >>= 8;
742   buf[2] = num & 255;
743   buf[3] = num >> 8;
744 }
745
746
747 /* Initializes structure to create a database.  File FD should be
748    opened read-write and should be seekable.  Returns 0 on success or
749    negative value on error. */
750 int
751 cdb_make_start(struct cdb_make *cdbmp, int fd)
752 {
753   memset (cdbmp, 0, sizeof *cdbmp);
754   cdbmp->cdb_fd = fd;
755   cdbmp->cdb_dpos = 2048;
756   cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
757   return 0;
758 }
759
760
761 static int
762 ewrite(int fd, const char *buf, int len)
763 {
764   while(len) {
765     int l = write(fd, buf, len);
766     if (l < 0 && errno != EINTR)
767       return -1;
768     if (l > 0)
769       {
770         len -= l;
771         buf += l;
772       }
773   }
774   return 0;
775 }
776
777 static int
778 make_write(struct cdb_make *cdbmp, const char *ptr, cdbi_t len)
779 {
780   cdbi_t l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
781   cdbmp->cdb_dpos += len;
782   if (len > l) {
783     memcpy(cdbmp->cdb_bpos, ptr, l);
784     if (ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf, sizeof(cdbmp->cdb_buf)) < 0)
785       return -1;
786     ptr += l; len -= l;
787     l = len / sizeof(cdbmp->cdb_buf);
788     if (l) {
789       l *= sizeof(cdbmp->cdb_buf);
790       if (ewrite(cdbmp->cdb_fd, ptr, l) < 0)
791         return -1;
792       ptr += l; len -= l;
793     }
794     cdbmp->cdb_bpos = cdbmp->cdb_buf;
795   }
796   if (len) {
797     memcpy(cdbmp->cdb_bpos, ptr, len);
798     cdbmp->cdb_bpos += len;
799   }
800   return 0;
801 }
802
803 static int
804 cdb_make_finish_internal(struct cdb_make *cdbmp)
805 {
806   cdbi_t hcnt[256];             /* hash table counts */
807   cdbi_t hpos[256];             /* hash table positions */
808   struct cdb_rec *htab;
809   unsigned char *p;
810   struct cdb_rl *rl;
811   cdbi_t hsize;
812   unsigned t, i;
813
814   if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) {
815     errno = ENOMEM;
816     return -1;
817   }
818
819   /* count htab sizes and reorder reclists */
820   hsize = 0;
821   for (t = 0; t < 256; ++t) {
822     struct cdb_rl *rlt = NULL;
823     i = 0;
824     rl = cdbmp->cdb_rec[t];
825     while(rl) {
826       struct cdb_rl *rln = rl->next;
827       rl->next = rlt;
828       rlt = rl;
829       i += rl->cnt;
830       rl = rln;
831     }
832     cdbmp->cdb_rec[t] = rlt;
833     if (hsize < (hcnt[t] = i << 1))
834       hsize = hcnt[t];
835   }
836
837   /* allocate memory to hold max htable */
838   htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
839   if (!htab) {
840     errno = ENOENT;
841     return -1;
842   }
843   p = (unsigned char *)htab;
844   htab += 2;
845
846   /* build hash tables */
847   for (t = 0; t < 256; ++t) {
848     cdbi_t len, hi;
849     hpos[t] = cdbmp->cdb_dpos;
850     if ((len = hcnt[t]) == 0)
851       continue;
852     for (i = 0; i < len; ++i)
853       htab[i].hval = htab[i].rpos = 0;
854     for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
855       for (i = 0; i < rl->cnt; ++i) {
856         hi = (rl->rec[i].hval >> 8) % len;
857         while(htab[hi].rpos)
858           if (++hi == len)
859             hi = 0;
860         htab[hi] = rl->rec[i];
861       }
862     for (i = 0; i < len; ++i) {
863       cdb_pack(htab[i].hval, p + (i << 3));
864       cdb_pack(htab[i].rpos, p + (i << 3) + 4);
865     }
866     if (make_write(cdbmp, p, len << 3) < 0) {
867       free(p);
868       return -1;
869     }
870   }
871   free(p);
872   if (cdbmp->cdb_bpos != cdbmp->cdb_buf &&
873       ewrite(cdbmp->cdb_fd, cdbmp->cdb_buf,
874              cdbmp->cdb_bpos - cdbmp->cdb_buf) != 0)
875       return -1;
876   p = cdbmp->cdb_buf;
877   for (t = 0; t < 256; ++t) {
878     cdb_pack(hpos[t], p + (t << 3));
879     cdb_pack(hcnt[t], p + (t << 3) + 4);
880   }
881   if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
882       ewrite(cdbmp->cdb_fd, p, 2048) != 0)
883     return -1;
884
885   return 0;
886 }
887
888 static void
889 cdb_make_free(struct cdb_make *cdbmp)
890 {
891   unsigned t;
892   for(t = 0; t < 256; ++t) {
893     struct cdb_rl *rl = cdbmp->cdb_rec[t];
894     while(rl) {
895       struct cdb_rl *tm = rl;
896       rl = rl->next;
897       free(tm);
898     }
899   }
900 }
901
902
903
904 /* Finalizes database file, constructing all needed indexes, and frees
905    memory structures.  It does not close the file descriptor.  Returns
906    0 on success or a negative value on error. */
907 int
908 cdb_make_finish(struct cdb_make *cdbmp)
909 {
910   int r = cdb_make_finish_internal(cdbmp);
911   cdb_make_free(cdbmp);
912   return r;
913 }
914
915
916 cdbi_t
917 cdb_hash(const void *buf, cdbi_t len)
918 {
919   register const unsigned char *p = (const unsigned char *)buf;
920   register const unsigned char *end = p + len;
921   register cdbi_t hash = 5381;  /* start value */
922   while (p < end)
923     hash = (hash + (hash << 5)) ^ *p++;
924   return hash;
925 }