src/findkey.c

   1 /* findkey.c - The routine that finds a key entry in the file. */
   2
   3 /* This file is part of GDBM, the GNU data base manager.
   4    Copyright (C) 1990, 1991, 1993, 2007, 2011, 2013 Free Software Foundation,
   5    Inc.
   6
   7    GDBM is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GDBM is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GDBM. If not, see <http://www.gnu.org/licenses/>.    */
  19
  20 /* Include system configuration before all else. */
  21 #include "autoconf.h"
  22
  23 #include "gdbmdefs.h"
  24
  25
  26 /* Read the data found in bucket entry ELEM_LOC in file DBF and
  27    return a pointer to it.  Also, cache the read value. */
  28
  29 char *
  30 _gdbm_read_entry (GDBM_FILE dbf, int elem_loc)
  31 {
  32   int rc;
  33   int key_size;
  34   int data_size;
  35   off_t file_pos;
  36   data_cache_elem *data_ca;
  37
  38   /* Is it already in the cache? */
  39   if (dbf->cache_entry->ca_data.elem_loc == elem_loc)
  40     return dbf->cache_entry->ca_data.dptr;
  41
  42   /* Set sizes and pointers. */
  43   key_size = dbf->bucket->h_table[elem_loc].key_size;
  44   data_size = dbf->bucket->h_table[elem_loc].data_size;
  45   data_ca = &dbf->cache_entry->ca_data;
  46
  47   /* Set up the cache. */
  48   if (data_ca->dptr != NULL) free (data_ca->dptr);
  49   data_ca->key_size = key_size;
  50   data_ca->data_size = data_size;
  51   data_ca->elem_loc = elem_loc;
  52   data_ca->hash_val = dbf->bucket->h_table[elem_loc].hash_value;
  53   if (key_size+data_size == 0)
  54     data_ca->dptr = (char *) malloc (1);
  55   else
  56     data_ca->dptr = (char *) malloc (key_size+data_size);
  57   if (data_ca->dptr == NULL) _gdbm_fatal (dbf, _("malloc error"));
  58
  59
  60   /* Read into the cache. */
  61   file_pos = __lseek (dbf, dbf->bucket->h_table[elem_loc].data_pointer,
  62                       SEEK_SET);
  63   if (file_pos != dbf->bucket->h_table[elem_loc].data_pointer)
  64     _gdbm_fatal (dbf, _("lseek error"));
  65   rc = _gdbm_full_read (dbf, data_ca->dptr, key_size+data_size);
  66   if (rc)
  67     _gdbm_fatal (dbf, gdbm_strerror (rc));
  68
  69   return data_ca->dptr;
  70 }
  71
  72
  73
  74 /* Find the KEY in the file and get ready to read the associated data.  The
  75    return value is the location in the current hash bucket of the KEY's
  76    entry.  If it is found, a pointer to the data and the key are returned
  77    in DPTR.  If it is not found, the value -1 is returned.  Since find
  78    key computes the hash value of key, that value */
  79 int
  80 _gdbm_findkey (GDBM_FILE dbf, datum key, char **dptr, int *new_hash_val)
  81 {
  82   int    bucket_hash_val;       /* The hash value from the bucket. */
  83   char  *file_key;              /* The complete key as stored in the file. */
  84   int    elem_loc;              /* The location in the bucket. */
  85   int    home_loc;              /* The home location in the bucket. */
  86   int    key_size;              /* Size of the key on the file.  */
  87
  88   /* Compute hash value and load proper bucket.  */
  89   *new_hash_val = _gdbm_hash (key);
  90   _gdbm_get_bucket (dbf, *new_hash_val>> (31-dbf->header->dir_bits));
  91
  92   /* Is the element the last one found for this bucket? */
  93   if (dbf->cache_entry->ca_data.elem_loc != -1
  94       && *new_hash_val == dbf->cache_entry->ca_data.hash_val
  95       && dbf->cache_entry->ca_data.key_size == key.dsize
  96       && dbf->cache_entry->ca_data.dptr != NULL
  97       && memcmp (dbf->cache_entry->ca_data.dptr, key.dptr, key.dsize) == 0)
  98     {
  99       /* This is it. Return the cache pointer. */
 100       *dptr = dbf->cache_entry->ca_data.dptr+key.dsize;
 101       return dbf->cache_entry->ca_data.elem_loc;
 102     }
 103
 104   /* It is not the cached value, search for element in the bucket. */
 105   elem_loc = *new_hash_val % dbf->header->bucket_elems;
 106   home_loc = elem_loc;
 107   bucket_hash_val = dbf->bucket->h_table[elem_loc].hash_value;
 108   while (bucket_hash_val != -1)
 109     {
 110       key_size = dbf->bucket->h_table[elem_loc].key_size;
 111       if (bucket_hash_val != *new_hash_val
 112          || key_size != key.dsize
 113          || memcmp (dbf->bucket->h_table[elem_loc].key_start, key.dptr,
 114                         (SMALL < key_size ? SMALL : key_size)) != 0)
 115         {
 116           /* Current elem_loc is not the item, go to next item. */
 117           elem_loc = (elem_loc + 1) % dbf->header->bucket_elems;
 118           if (elem_loc == home_loc) return -1;
 119           bucket_hash_val = dbf->bucket->h_table[elem_loc].hash_value;
 120         }
 121       else
 122         {
 123           /* This may be the one we want.
 124              The only way to tell is to read it. */
 125           file_key = _gdbm_read_entry (dbf, elem_loc);
 126           if (memcmp (file_key, key.dptr, key_size) == 0)
 127             {
 128               /* This is the item. */
 129               *dptr = file_key+key.dsize;
 130               return elem_loc;
 131             }
 132           else
 133             {
 134               /* Not the item, try the next one.  Return if not found. */
 135               elem_loc = (elem_loc + 1) % dbf->header->bucket_elems;
 136               if (elem_loc == home_loc) return -1;
 137               bucket_hash_val = dbf->bucket->h_table[elem_loc].hash_value;
 138             }
 139         }
 140     }
 141
 142   /* If we get here, we never found the key. */
 143   return -1;
 144
 145 }