1 /* gdbmseq.c - Routines to visit all keys. Not in sorted order. */
2
3 /* This file is part of GDBM, the GNU data base manager.
4 Copyright (C) 1990-2021 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 3, 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. If not, see <http://www.gnu.org/licenses/>. */
18
19 /* Include system configuration before all else. */
20 #include "autoconf.h"
21
22 #include "gdbmdefs.h"
23
24 static inline int
gdbm_valid_key_p(GDBM_FILE dbf,char * key_ptr,int key_size,int elem_loc)25 gdbm_valid_key_p (GDBM_FILE dbf, char *key_ptr, int key_size, int elem_loc)
26 {
27 datum key;
28 int hash, bucket, offset;
29
30 key.dptr = key_ptr;
31 key.dsize = key_size;
32 _gdbm_hash_key (dbf, key, &hash, &bucket, &offset);
33 if (gdbm_dir_entry_valid_p (dbf, bucket) &&
34 dbf->dir[bucket] == dbf->dir[dbf->bucket_dir] &&
35 hash == dbf->bucket->h_table[elem_loc].hash_value)
36 return 1;
37 GDBM_SET_ERRNO (dbf, GDBM_BAD_HASH_ENTRY, TRUE);
38 return 0;
39 }
40
41 /* Find and read the next entry in the hash structure for DBF starting
42 at ELEM_LOC of the current bucket and using RETURN_VAL as the place to
43 put the data that is found.
44
45 If no next key is found, gdbm_errno is set to GDBM_ITEM_NOT_FOUND
46 and RETURN_VAL remains unmodified.
47
48 On error, gdbm_errno is set.
49 */
50
51 static void
get_next_key(GDBM_FILE dbf,int elem_loc,datum * return_val)52 get_next_key (GDBM_FILE dbf, int elem_loc, datum *return_val)
53 {
54 int found; /* Have we found the next key. */
55 char *find_data; /* Data pointer returned by find_key. */
56
57 /* Find the next key. */
58 found = FALSE;
59 while (!found)
60 {
61 /* Advance to the next location in the bucket. */
62 elem_loc++;
63 if (elem_loc == dbf->header->bucket_elems)
64 {
65 /* We have finished the current bucket, get the next bucket. */
66 elem_loc = 0;
67
68 /* Find the next bucket. It is possible several entries in
69 the bucket directory point to the same bucket. */
70 while (dbf->bucket_dir < GDBM_DIR_COUNT (dbf)
71 && dbf->cache_entry->ca_adr == dbf->dir[dbf->bucket_dir])
72 dbf->bucket_dir++;
73
74 /* Check to see if there was a next bucket. */
75 if (dbf->bucket_dir < GDBM_DIR_COUNT (dbf))
76 {
77 if (_gdbm_get_bucket (dbf, dbf->bucket_dir))
78 return;
79 }
80 else
81 {
82 /* No next key, just return. */
83 GDBM_SET_ERRNO2 (dbf, GDBM_ITEM_NOT_FOUND, FALSE,
84 GDBM_DEBUG_LOOKUP);
85 return;
86 }
87 }
88 found = dbf->bucket->h_table[elem_loc].hash_value != -1;
89 }
90
91 /* Found the next key, read it into return_val. */
92 find_data = _gdbm_read_entry (dbf, elem_loc);
93 if (!find_data)
94 return;
95 /* Verify if computed hash and bucket address for the key match the
96 actual ones. Bail out if not. */
97 if (!gdbm_valid_key_p (dbf, find_data,
98 dbf->bucket->h_table[elem_loc].key_size, elem_loc))
99 return;
100 return_val->dsize = dbf->bucket->h_table[elem_loc].key_size;
101 if (return_val->dsize == 0)
102 return_val->dptr = (char *) malloc (1);
103 else
104 return_val->dptr = (char *) malloc (return_val->dsize);
105 if (return_val->dptr == NULL)
106 {
107 return_val->dsize = 0;
108 GDBM_SET_ERRNO2 (dbf, GDBM_MALLOC_ERROR, FALSE, GDBM_DEBUG_LOOKUP);
109 }
110 else
111 memcpy (return_val->dptr, find_data, return_val->dsize);
112 }
113
114
115 /* Start the visit of all keys in the database. This produces something in
116 hash order, not in any sorted order. */
117
118 datum
gdbm_firstkey(GDBM_FILE dbf)119 gdbm_firstkey (GDBM_FILE dbf)
120 {
121 datum return_val; /* To return the first key. */
122
123 /* Set the default return value for not finding a first entry. */
124 return_val.dptr = NULL;
125 return_val.dsize = 0;
126
127 GDBM_DEBUG (GDBM_DEBUG_READ, "%s: getting first key", dbf->name);
128
129 /* Return immediately if the database needs recovery */
130 GDBM_ASSERT_CONSISTENCY (dbf, return_val);
131
132 /* Initialize the gdbm_errno variable. */
133 gdbm_set_errno (dbf, GDBM_NO_ERROR, FALSE);
134
135 /* Get the first bucket. */
136 if (_gdbm_get_bucket (dbf, 0) == 0)
137 {
138 /* Look for first entry. */
139 get_next_key (dbf, -1, &return_val);
140
141 if (return_val.dptr)
142 GDBM_DEBUG_DATUM (GDBM_DEBUG_READ, return_val, "%s: found", dbf->name);
143 else
144 GDBM_DEBUG (GDBM_DEBUG_READ, "%s: key not found", dbf->name);
145 }
146
147 return return_val;
148 }
149
150
151 /* Continue visiting all keys. The next key following KEY is returned. */
152
153 datum
gdbm_nextkey(GDBM_FILE dbf,datum key)154 gdbm_nextkey (GDBM_FILE dbf, datum key)
155 {
156 datum return_val; /* The return value. */
157 int elem_loc; /* The location in the bucket. */
158
159 /* Set the default return value for no next entry. */
160 return_val.dptr = NULL;
161
162 GDBM_DEBUG_DATUM (GDBM_DEBUG_READ, key, "%s: getting next key", dbf->name);
163
164 /* Return immediately if the database needs recovery */
165 GDBM_ASSERT_CONSISTENCY (dbf, return_val);
166
167 /* Initialize the gdbm_errno variable. */
168 gdbm_set_errno (dbf, GDBM_NO_ERROR, FALSE);
169
170 /* Do we have a valid key? */
171 if (key.dptr == NULL)
172 {
173 GDBM_DEBUG (GDBM_DEBUG_READ, "%s: key not found", dbf->name);
174 GDBM_SET_ERRNO2 (dbf, GDBM_ITEM_NOT_FOUND, /* FIXME: special error code perhaps */
175 FALSE,
176 GDBM_DEBUG_LOOKUP);
177 return return_val;
178 }
179
180 /* Find the key. */
181 elem_loc = _gdbm_findkey (dbf, key, NULL, NULL);
182 if (elem_loc == -1) return return_val;
183
184 /* Find the next key. */
185 get_next_key (dbf, elem_loc, &return_val);
186
187 if (return_val.dptr)
188 GDBM_DEBUG_DATUM (GDBM_DEBUG_READ, return_val, "%s: found", dbf->name);
189 else
190 GDBM_DEBUG (GDBM_DEBUG_READ, "%s: key not found", dbf->name);
191
192 return return_val;
193 }
194