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