xapian-applications/omega/cdb_find.cc

   1 /* $Id: cdb_find.c,v 1.8 2003/11/03 16:42:41 mjt Exp $
   2  * cdb_find routine
   3  *
   4  * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
   5  * Public domain.
   6  */
   7
   8 #include <config.h>
   9
  10 #include "cdb_int.h"
  11
  12 #include <cstring>
  13
  14 using namespace std;
  15
  16 int
  17 cdb_find(struct cdb *cdbp, const void *key, unsigned klen)
  18 {
  19   const unsigned char *htp;     /* hash table pointer */
  20   const unsigned char *htab;    /* hash table */
  21   const unsigned char *htend;   /* end of hash table */
  22   unsigned httodo;              /* ht bytes left to look */
  23   unsigned pos, n;
  24
  25   unsigned hval;
  26
  27   if (klen >= cdbp->cdb_dend)   /* if key size is too large */
  28     return 0;
  29
  30   hval = cdb_hash(key, klen);
  31
  32   /* find (pos,n) hash table to use */
  33   /* first 2048 bytes (toc) are always available */
  34   /* (hval % 256) * 8 */
  35   htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */
  36   n = cdb_unpack(htp + 4);      /* table size */
  37   if (!n)                       /* empty table */
  38     return 0;                   /* not found */
  39   httodo = n << 3;              /* bytes of htab to lookup */
  40   pos = cdb_unpack(htp);        /* htab position */
  41   if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */
  42       || pos < cdbp->cdb_dend /* is htab inside data section ? */
  43       || pos > cdbp->cdb_fsize /* htab start within file ? */
  44       || httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */
  45     return errno = EPROTO, -1;
  46
  47   htab = cdbp->cdb_mem + pos;   /* htab pointer */
  48   htend = htab + httodo;        /* after end of htab */
  49   /* htab starting position: rest of hval modulo htsize, 8bytes per elt */
  50   htp = htab + (((hval >> 8) % n) << 3);
  51
  52   for(;;) {
  53     pos = cdb_unpack(htp + 4);  /* record position */
  54     if (!pos)
  55       return 0;
  56     if (cdb_unpack(htp) == hval) {
  57       if (pos > cdbp->cdb_dend - 8) /* key+val lengths */
  58         return errno = EPROTO, -1;
  59       if (cdb_unpack(cdbp->cdb_mem + pos) == klen) {
  60         if (cdbp->cdb_dend - klen < pos + 8)
  61           return errno = EPROTO, -1;
  62         if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) {
  63           n = cdb_unpack(cdbp->cdb_mem + pos + 4);
  64           pos += 8;
  65           if (cdbp->cdb_dend < n || cdbp->cdb_dend - n < pos + klen)
  66             return errno = EPROTO, -1;
  67           cdbp->cdb_kpos = pos;
  68           cdbp->cdb_klen = klen;
  69           cdbp->cdb_vpos = pos + klen;
  70           cdbp->cdb_vlen = n;
  71           return 1;
  72         }
  73       }
  74     }
  75     httodo -= 8;
  76     if (!httodo)
  77       return 0;
  78     if ((htp += 8) >= htend)
  79       htp = htab;
  80   }
  81
  82 }