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