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