OLD | NEW |
1 /*- | 1 /*- |
2 * Copyright (c) 1990, 1993, 1994 | 2 * Copyright (c) 1990, 1993, 1994 |
3 * The Regents of the University of California. All rights reserved. | 3 * The Regents of the University of California. All rights reserved. |
4 * | 4 * |
5 * This code is derived from software contributed to Berkeley by | 5 * This code is derived from software contributed to Berkeley by |
6 * Margo Seltzer. | 6 * Margo Seltzer. |
7 * | 7 * |
8 * Redistribution and use in source and binary forms, with or without | 8 * Redistribution and use in source and binary forms, with or without |
9 * modification, are permitted provided that the following conditions | 9 * modification, are permitted provided that the following conditions |
10 * are met: | 10 * are met: |
11 * 1. Redistributions of source code must retain the above copyright | 11 * 1. Redistributions of source code must retain the above copyright |
12 * notice, this list of conditions and the following disclaimer. | 12 * notice, this list of conditions and the following disclaimer. |
13 * 2. Redistributions in binary form must reproduce the above copyright | 13 * 2. Redistributions in binary form must reproduce the above copyright |
14 * notice, this list of conditions and the following disclaimer in the | 14 * notice, this list of conditions and the following disclaimer in the |
15 * documentation and/or other materials provided with the distribution. | 15 * documentation and/or other materials provided with the distribution. |
16 * 3. ***REMOVED*** - see | 16 * 3. ***REMOVED*** - see |
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change | 17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change |
18 * 4. Neither the name of the University nor the names of its contributors | 18 * 4. Neither the name of the University nor the names of its contributors |
19 * may be used to endorse or promote products derived from this software | 19 * may be used to endorse or promote products derived from this software |
20 * without specific prior written permission. | 20 * without specific prior written permission. |
21 * | 21 * |
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
(...skipping 27 matching lines...) Expand all Loading... |
54 | 54 |
55 #include <errno.h> | 55 #include <errno.h> |
56 #include <fcntl.h> | 56 #include <fcntl.h> |
57 #include <stdio.h> | 57 #include <stdio.h> |
58 #include <stdlib.h> | 58 #include <stdlib.h> |
59 #include <string.h> | 59 #include <string.h> |
60 | 60 |
61 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) | 61 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) |
62 #include <unistd.h> | 62 #include <unistd.h> |
63 #endif | 63 #endif |
64 #if defined(_WIN32) || defined(_WINDOWS) | 64 #if defined(_WIN32) || defined(_WINDOWS) |
65 #include <windows.h> | 65 #include <windows.h> |
66 #endif | 66 #endif |
67 | 67 |
68 #include <assert.h> | 68 #include <assert.h> |
69 | 69 |
70 #include "mcom_db.h" | 70 #include "mcom_db.h" |
71 #include "hash.h" | 71 #include "hash.h" |
72 #include "page.h" | 72 #include "page.h" |
73 | 73 |
74 /* | 74 /* |
75 #include "extern.h" | 75 #include "extern.h" |
76 */ | 76 */ |
77 static int alloc_segs __P((HTAB *, int)); | 77 static int alloc_segs __P((HTAB *, int)); |
78 static int flush_meta __P((HTAB *)); | 78 static int flush_meta __P((HTAB *)); |
79 static int hash_access __P((HTAB *, ACTION, DBT *, DBT *)); | 79 static int hash_access __P((HTAB *, ACTION, DBT *, DBT *)); |
80 static int hash_close __P((DB *)); | 80 static int hash_close __P((DB *)); |
81 static int hash_delete __P((const DB *, const DBT *, uint)); | 81 static int hash_delete __P((const DB *, const DBT *, uint)); |
82 static int hash_fd __P((const DB *)); | 82 static int hash_fd __P((const DB *)); |
83 static int hash_get __P((const DB *, const DBT *, DBT *, uint)); | 83 static int hash_get __P((const DB *, const DBT *, DBT *, uint)); |
84 static int hash_put __P((const DB *, DBT *, const DBT *, uint)); | 84 static int hash_put __P((const DB *, DBT *, const DBT *, uint)); |
85 static void *hash_realloc __P((SEGMENT **, size_t, size_t)); | 85 static void *hash_realloc __P((SEGMENT **, size_t, size_t)); |
86 static int hash_seq __P((const DB *, DBT *, DBT *, uint)); | 86 static int hash_seq __P((const DB *, DBT *, DBT *, uint)); |
87 static int hash_sync __P((const DB *, uint)); | 87 static int hash_sync __P((const DB *, uint)); |
88 static int hdestroy __P((HTAB *)); | 88 static int hdestroy __P((HTAB *)); |
89 static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *)); | 89 static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *)); |
90 static int init_htab __P((HTAB *, int)); | 90 static int init_htab __P((HTAB *, int)); |
91 #if BYTE_ORDER == LITTLE_ENDIAN | 91 #if BYTE_ORDER == LITTLE_ENDIAN |
92 static void swap_header __P((HTAB *)); | 92 static void swap_header __P((HTAB *)); |
93 static void swap_header_copy __P((HASHHDR *, HASHHDR *)); | 93 static void swap_header_copy __P((HASHHDR *, HASHHDR *)); |
94 #endif | 94 #endif |
95 | 95 |
96 /* Fast arithmetic, relying on powers of 2, */ | 96 /* Fast arithmetic, relying on powers of 2, */ |
97 #define MOD(x, y)» » ((x) & ((y) - 1)) | 97 #define MOD(x, y) ((x) & ((y) - 1)) |
98 | 98 |
99 #define RETURN_ERROR(ERR, LOC)» { save_errno = ERR; goto LOC; } | 99 #define RETURN_ERROR(ERR, LOC) \ |
| 100 { \ |
| 101 save_errno = ERR; \ |
| 102 goto LOC; \ |
| 103 } |
100 | 104 |
101 /* Return values */ | 105 /* Return values */ |
102 #define»SUCCESS» (0) | 106 #define SUCCESS (0) |
103 #define»DBM_ERROR» (-1) | 107 #define DBM_ERROR (-1) |
104 #define»ABNORMAL (1) | 108 #define ABNORMAL (1) |
105 | 109 |
106 #ifdef HASH_STATISTICS | 110 #ifdef HASH_STATISTICS |
107 int hash_accesses, hash_collisions, hash_expansions, hash_overflows; | 111 int hash_accesses, hash_collisions, hash_expansions, hash_overflows; |
108 #endif | 112 #endif |
109 | 113 |
110 /* A new Lou (montulli@mozilla.com) routine. | 114 /* A new Lou (montulli@mozilla.com) routine. |
111 * | 115 * |
112 * The database is screwed. | 116 * The database is screwed. |
113 * | 117 * |
114 * This closes the file, flushing buffers as appropriate. | 118 * This closes the file, flushing buffers as appropriate. |
115 */ | 119 */ |
116 static void | 120 static void __remove_database(DB *dbp) { |
117 __remove_database(DB *dbp) | 121 HTAB *hashp = (HTAB *)dbp->internal; |
118 { | 122 |
119 » HTAB *hashp = (HTAB *)dbp->internal; | 123 assert(0); |
120 | 124 |
121 » assert(0); | 125 if (!hashp) return; |
122 | 126 hdestroy(hashp); |
123 » if (!hashp) | 127 dbp->internal = NULL; |
124 » » return; | |
125 » hdestroy(hashp); | |
126 » dbp->internal = NULL; | |
127 } | 128 } |
128 | 129 |
129 /************************** INTERFACE ROUTINES ***************************/ | 130 /************************** INTERFACE ROUTINES ***************************/ |
130 /* OPEN/CLOSE */ | 131 /* OPEN/CLOSE */ |
131 | 132 |
132 | 133 extern DB *__hash_open(const char *file, int flags, int mode, |
133 extern DB * | 134 const HASHINFO *info, int dflags) { |
134 __hash_open(const char *file, int flags, int mode, const HASHINFO *info, int dfl
ags) | 135 HTAB *hashp = NULL; |
135 { | 136 struct stat statbuf; |
136 » HTAB *hashp=NULL; | 137 DB *dbp; |
137 » struct stat statbuf; | 138 int bpages, hdrsize, new_table, nsegs, save_errno; |
138 » DB *dbp; | 139 |
139 » int bpages, hdrsize, new_table, nsegs, save_errno; | 140 if ((flags & O_ACCMODE) == O_WRONLY) { |
140 | 141 errno = EINVAL; |
141 » if ((flags & O_ACCMODE) == O_WRONLY) { | 142 return NULL; |
142 » » errno = EINVAL; | 143 } |
143 » » return NULL; | 144 |
144 » } | 145 /* zero the statbuffer so that |
145 | 146 * we can check it for a non-zero |
146 » /* zero the statbuffer so that | 147 * date to see if stat succeeded |
147 » * we can check it for a non-zero | 148 */ |
148 » * date to see if stat succeeded | 149 memset(&statbuf, 0, sizeof(struct stat)); |
149 » */ | 150 |
150 » memset(&statbuf, 0, sizeof(struct stat)); | 151 if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) { |
151 | 152 errno = ENOMEM; |
152 » if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) { | 153 return NULL; |
153 » » errno = ENOMEM; | 154 } |
154 » » return NULL; | 155 hashp->fp = NO_FILE; |
155 » } | 156 if (file) hashp->filename = strdup(file); |
156 » hashp->fp = NO_FILE; | 157 |
157 » if(file) | 158 /* |
158 » » hashp->filename = strdup(file); | 159 * Even if user wants write only, we need to be able to read |
159 | 160 * the actual file, so we need to open it read/write. But, the |
160 » /* | 161 * field in the hashp structure needs to be accurate so that |
161 » * Even if user wants write only, we need to be able to read | 162 * we can check accesses. |
162 » * the actual file, so we need to open it read/write. But, the | 163 */ |
163 » * field in the hashp structure needs to be accurate so that | 164 hashp->flags = flags; |
164 » * we can check accesses. | 165 |
165 » */ | 166 new_table = 0; |
166 » hashp->flags = flags; | 167 if (!file || (flags & O_TRUNC) || |
167 | 168 (stat(file, &statbuf) && (errno == ENOENT))) { |
168 » new_table = 0; | 169 if (errno == ENOENT) errno = 0; /* Just in case someone looks at errno */ |
169 » if (!file || (flags & O_TRUNC) »|| (stat(file, &statbuf) && (errno == E
NOENT))) | 170 new_table = 1; |
170 » { | 171 } else if (statbuf.st_mtime && statbuf.st_size == 0) { |
171 » » if (errno == ENOENT) | 172 /* check for a zero length file and delete it |
172 » » » errno = 0; /* Just in case someone looks at errno */ | 173 * if it exists |
173 » » new_table = 1; | 174 */ |
174 » } | 175 new_table = 1; |
175 » else if(statbuf.st_mtime && statbuf.st_size == 0) | 176 } |
176 » { | 177 hashp->file_size = statbuf.st_size; |
177 » » /* check for a zero length file and delete it | 178 |
178 » » * if it exists | 179 if (file) { |
179 » » */ | 180 #if defined(_WIN32) || defined(_WINDOWS) || defined(macintosh) || \ |
180 » » new_table = 1; | 181 defined(XP_OS2) |
181 » } | 182 if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) |
182 » hashp->file_size = statbuf.st_size; | 183 RETURN_ERROR(errno, error1); |
183 | |
184 » if (file) {» » » » | |
185 #if defined(_WIN32) || defined(_WINDOWS) || defined (macintosh) || defined(XP_O
S2) | |
186 » » if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -
1) | |
187 » » » RETURN_ERROR(errno, error1); | |
188 #else | 184 #else |
189 » » if ((hashp->fp = open(file, flags, mode)) == -1) | 185 if ((hashp->fp = open(file, flags, mode)) == -1) |
190 » » » RETURN_ERROR(errno, error1); | 186 RETURN_ERROR(errno, error1); |
191 » » (void)fcntl(hashp->fp, F_SETFD, 1); | 187 (void)fcntl(hashp->fp, F_SETFD, 1); |
192 #endif | 188 #endif |
193 » } | 189 } |
194 » if (new_table) { | 190 if (new_table) { |
195 » » if (!init_hash(hashp, file, (HASHINFO *)info)) | 191 if (!init_hash(hashp, file, (HASHINFO *)info)) RETURN_ERROR(errno, error1); |
196 » » » RETURN_ERROR(errno, error1); | 192 } else { |
197 » } else { | 193 /* Table already exists */ |
198 » » /* Table already exists */ | 194 if (info && info->hash) |
199 » » if (info && info->hash) | 195 hashp->hash = info->hash; |
200 » » » hashp->hash = info->hash; | 196 else |
201 » » else | 197 hashp->hash = __default_hash; |
202 » » » hashp->hash = __default_hash; | 198 |
203 | 199 hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR)); |
204 » » hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR)); | 200 if (hdrsize == -1) RETURN_ERROR(errno, error1); |
205 » » if (hdrsize == -1) | 201 if (hdrsize != sizeof(HASHHDR)) RETURN_ERROR(EFTYPE, error1); |
206 » » » RETURN_ERROR(errno, error1); | |
207 » » if (hdrsize != sizeof(HASHHDR)) | |
208 » » » RETURN_ERROR(EFTYPE, error1); | |
209 #if BYTE_ORDER == LITTLE_ENDIAN | 202 #if BYTE_ORDER == LITTLE_ENDIAN |
210 » » swap_header(hashp); | 203 swap_header(hashp); |
211 #endif | 204 #endif |
212 » » /* Verify file type, versions and hash function */ | 205 /* Verify file type, versions and hash function */ |
213 » » if (hashp->MAGIC != HASHMAGIC) | 206 if (hashp->MAGIC != HASHMAGIC) RETURN_ERROR(EFTYPE, error1); |
214 » » » RETURN_ERROR(EFTYPE, error1); | 207 #define OLDHASHVERSION 1 |
215 #define»OLDHASHVERSION» 1 | 208 if (hashp->VERSION != HASHVERSION && hashp->VERSION != OLDHASHVERSION) |
216 » » if (hashp->VERSION != HASHVERSION && | 209 RETURN_ERROR(EFTYPE, error1); |
217 » » hashp->VERSION != OLDHASHVERSION) | 210 if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) |
218 » » » RETURN_ERROR(EFTYPE, error1); | 211 RETURN_ERROR(EFTYPE, error1); |
219 » » if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) | 212 if (hashp->NKEYS < 0) /* Old bad database. */ |
220 » » » RETURN_ERROR(EFTYPE, error1); | 213 RETURN_ERROR(EFTYPE, error1); |
221 » » if (hashp->NKEYS < 0) /* Old bad database. */ | 214 |
222 » » » RETURN_ERROR(EFTYPE, error1); | 215 /* |
223 | 216 * Figure out how many segments we need. Max_Bucket is the |
224 » » /* | 217 * maximum bucket number, so the number of buckets is |
225 » » * Figure out how many segments we need. Max_Bucket is the | 218 * max_bucket + 1. |
226 » » * maximum bucket number, so the number of buckets is | 219 */ |
227 » » * max_bucket + 1. | 220 nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / hashp->SGSIZE; |
228 » » */ | 221 hashp->nsegs = 0; |
229 » » nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / | 222 if (alloc_segs(hashp, nsegs)) |
230 » » » hashp->SGSIZE; | 223 /* If alloc_segs fails, errno will have been set. */ |
231 » » hashp->nsegs = 0; | 224 RETURN_ERROR(errno, error1); |
232 » » if (alloc_segs(hashp, nsegs)) | 225 /* Read in bitmaps */ |
233 » » » /* If alloc_segs fails, errno will have been set. */ | 226 bpages = |
234 » » » RETURN_ERROR(errno, error1); | 227 (hashp->SPARES[hashp->OVFL_POINT] + (hashp->BSIZE << BYTE_SHIFT) - 1) >> |
235 » » /* Read in bitmaps */ | 228 (hashp->BSHIFT + BYTE_SHIFT); |
236 » » bpages = (hashp->SPARES[hashp->OVFL_POINT] + | 229 |
237 » » (hashp->BSIZE << BYTE_SHIFT) - 1) >> | 230 hashp->nmaps = bpages; |
238 » » (hashp->BSHIFT + BYTE_SHIFT); | 231 (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *)); |
239 | 232 } |
240 » » hashp->nmaps = bpages; | 233 |
241 » » (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *)); | 234 /* Initialize Buffer Manager */ |
242 » } | 235 if (info && info->cachesize) |
243 | 236 __buf_init(hashp, (int32)info->cachesize); |
244 » /* Initialize Buffer Manager */ | 237 else |
245 » if (info && info->cachesize) | 238 __buf_init(hashp, DEF_BUFSIZE); |
246 » » __buf_init(hashp, (int32) info->cachesize); | 239 |
247 » else | 240 hashp->new_file = new_table; |
248 » » __buf_init(hashp, DEF_BUFSIZE); | |
249 | |
250 » hashp->new_file = new_table; | |
251 #ifdef macintosh | 241 #ifdef macintosh |
252 » hashp->save_file = file && !(hashp->flags & O_RDONLY); | 242 hashp->save_file = file && !(hashp->flags & O_RDONLY); |
253 #else | 243 #else |
254 » hashp->save_file = file && (hashp->flags & O_RDWR); | 244 hashp->save_file = file && (hashp->flags & O_RDWR); |
255 #endif | 245 #endif |
256 » hashp->cbucket = -1; | 246 hashp->cbucket = -1; |
257 » if (!(dbp = (DB *)malloc(sizeof(DB)))) { | 247 if (!(dbp = (DB *)malloc(sizeof(DB)))) { |
258 » » RETURN_ERROR(ENOMEM, error1); | 248 RETURN_ERROR(ENOMEM, error1); |
259 » } | 249 } |
260 » dbp->internal = hashp; | 250 dbp->internal = hashp; |
261 » dbp->close = hash_close; | 251 dbp->close = hash_close; |
262 » dbp->del = hash_delete; | 252 dbp->del = hash_delete; |
263 » dbp->fd = hash_fd; | 253 dbp->fd = hash_fd; |
264 » dbp->get = hash_get; | 254 dbp->get = hash_get; |
265 » dbp->put = hash_put; | 255 dbp->put = hash_put; |
266 » dbp->seq = hash_seq; | 256 dbp->seq = hash_seq; |
267 » dbp->sync = hash_sync; | 257 dbp->sync = hash_sync; |
268 » dbp->type = DB_HASH; | 258 dbp->type = DB_HASH; |
269 | 259 |
270 #ifdef HASH_STATISTICS | 260 #ifdef HASH_STATISTICS |
271 » hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; | 261 hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; |
272 #endif | 262 #endif |
273 » return (dbp); | 263 return (dbp); |
274 | 264 |
275 error1: | 265 error1: |
276 » hdestroy(hashp); | 266 hdestroy(hashp); |
277 » errno = save_errno; | 267 errno = save_errno; |
278 » return (NULL); | 268 return (NULL); |
279 } | 269 } |
280 | 270 |
281 static int | 271 static int hash_close(DB *dbp) { |
282 hash_close(DB *dbp) | 272 HTAB *hashp; |
283 { | 273 int retval; |
284 » HTAB *hashp; | 274 |
285 » int retval; | 275 if (!dbp) return (DBM_ERROR); |
286 | 276 |
287 » if (!dbp) | 277 hashp = (HTAB *)dbp->internal; |
288 » » return (DBM_ERROR); | 278 if (!hashp) return (DBM_ERROR); |
289 | 279 |
290 » hashp = (HTAB *)dbp->internal; | 280 retval = hdestroy(hashp); |
291 » if(!hashp) | 281 free(dbp); |
292 » » return (DBM_ERROR); | 282 return (retval); |
293 | 283 } |
294 » retval = hdestroy(hashp); | 284 |
295 » free(dbp); | 285 static int hash_fd(const DB *dbp) { |
296 » return (retval); | 286 HTAB *hashp; |
297 } | 287 |
298 | 288 if (!dbp) return (DBM_ERROR); |
299 static int hash_fd(const DB *dbp) | 289 |
300 { | 290 hashp = (HTAB *)dbp->internal; |
301 » HTAB *hashp; | 291 if (!hashp) return (DBM_ERROR); |
302 | 292 |
303 » if (!dbp) | 293 if (hashp->fp == -1) { |
304 » » return (DBM_ERROR); | 294 errno = ENOENT; |
305 | 295 return (-1); |
306 » hashp = (HTAB *)dbp->internal; | 296 } |
307 » if(!hashp) | 297 return (hashp->fp); |
308 » » return (DBM_ERROR); | |
309 | |
310 » if (hashp->fp == -1) { | |
311 » » errno = ENOENT; | |
312 » » return (-1); | |
313 » } | |
314 » return (hashp->fp); | |
315 } | 298 } |
316 | 299 |
317 /************************** LOCAL CREATION ROUTINES **********************/ | 300 /************************** LOCAL CREATION ROUTINES **********************/ |
318 static HTAB * | 301 static HTAB *init_hash(HTAB *hashp, const char *file, HASHINFO *info) { |
319 init_hash(HTAB *hashp, const char *file, HASHINFO *info) | 302 struct stat statbuf; |
320 { | 303 int nelem; |
321 » struct stat statbuf; | 304 |
322 » int nelem; | 305 nelem = 1; |
323 | 306 hashp->NKEYS = 0; |
324 » nelem = 1; | 307 hashp->LORDER = BYTE_ORDER; |
325 » hashp->NKEYS = 0; | 308 hashp->BSIZE = DEF_BUCKET_SIZE; |
326 » hashp->LORDER = BYTE_ORDER; | 309 hashp->BSHIFT = DEF_BUCKET_SHIFT; |
327 » hashp->BSIZE = DEF_BUCKET_SIZE; | 310 hashp->SGSIZE = DEF_SEGSIZE; |
328 » hashp->BSHIFT = DEF_BUCKET_SHIFT; | 311 hashp->SSHIFT = DEF_SEGSIZE_SHIFT; |
329 » hashp->SGSIZE = DEF_SEGSIZE; | 312 hashp->DSIZE = DEF_DIRSIZE; |
330 » hashp->SSHIFT = DEF_SEGSIZE_SHIFT; | 313 hashp->FFACTOR = DEF_FFACTOR; |
331 » hashp->DSIZE = DEF_DIRSIZE; | 314 hashp->hash = __default_hash; |
332 » hashp->FFACTOR = DEF_FFACTOR; | 315 memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); |
333 » hashp->hash = __default_hash; | 316 memset(hashp->BITMAPS, 0, sizeof(hashp->BITMAPS)); |
334 » memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); | 317 |
335 » memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS)); | 318 /* Fix bucket size to be optimal for file system */ |
336 | 319 if (file != NULL) { |
337 » /* Fix bucket size to be optimal for file system */ | 320 if (stat(file, &statbuf)) return (NULL); |
338 » if (file != NULL) { | 321 |
339 » » if (stat(file, &statbuf)) | 322 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && \ |
340 » » » return (NULL); | 323 !defined(XP_OS2) |
341 | |
342 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP
_OS2) | |
343 #if defined(__QNX__) && !defined(__QNXNTO__) | 324 #if defined(__QNX__) && !defined(__QNXNTO__) |
344 » » hashp->BSIZE = 512; /* preferred blk size on qnx4 */ | 325 hashp->BSIZE = 512; /* preferred blk size on qnx4 */ |
345 #else | 326 #else |
346 » » hashp->BSIZE = statbuf.st_blksize; | 327 hashp->BSIZE = statbuf.st_blksize; |
347 #endif | 328 #endif |
348 | 329 |
349 » » /* new code added by Lou to reduce block | 330 /* new code added by Lou to reduce block |
350 » » * size down below MAX_BSIZE | 331 * size down below MAX_BSIZE |
351 » » */ | 332 */ |
352 » » if (hashp->BSIZE > MAX_BSIZE) | 333 if (hashp->BSIZE > MAX_BSIZE) hashp->BSIZE = MAX_BSIZE; |
353 » » » hashp->BSIZE = MAX_BSIZE; | 334 #endif |
354 #endif | 335 hashp->BSHIFT = __log2((uint32)hashp->BSIZE); |
355 » » hashp->BSHIFT = __log2((uint32)hashp->BSIZE); | 336 } |
356 » } | 337 |
357 | 338 if (info) { |
358 » if (info) { | 339 if (info->bsize) { |
359 » » if (info->bsize) { | 340 /* Round pagesize up to power of 2 */ |
360 » » » /* Round pagesize up to power of 2 */ | 341 hashp->BSHIFT = __log2(info->bsize); |
361 » » » hashp->BSHIFT = __log2(info->bsize); | 342 hashp->BSIZE = 1 << hashp->BSHIFT; |
362 » » » hashp->BSIZE = 1 << hashp->BSHIFT; | 343 if (hashp->BSIZE > MAX_BSIZE) { |
363 » » » if (hashp->BSIZE > MAX_BSIZE) { | 344 errno = EINVAL; |
364 » » » » errno = EINVAL; | 345 return (NULL); |
365 » » » » return (NULL); | 346 } |
366 » » » } | 347 } |
367 » » } | 348 if (info->ffactor) hashp->FFACTOR = info->ffactor; |
368 » » if (info->ffactor) | 349 if (info->hash) hashp->hash = info->hash; |
369 » » » hashp->FFACTOR = info->ffactor; | 350 if (info->nelem) nelem = info->nelem; |
370 » » if (info->hash) | 351 if (info->lorder) { |
371 » » » hashp->hash = info->hash; | 352 if (info->lorder != BIG_ENDIAN && info->lorder != LITTLE_ENDIAN) { |
372 » » if (info->nelem) | 353 errno = EINVAL; |
373 » » » nelem = info->nelem; | 354 return (NULL); |
374 » » if (info->lorder) { | 355 } |
375 » » » if (info->lorder != BIG_ENDIAN && | 356 hashp->LORDER = info->lorder; |
376 » » » info->lorder != LITTLE_ENDIAN) { | 357 } |
377 » » » » errno = EINVAL; | 358 } |
378 » » » » return (NULL); | 359 /* init_htab sets errno if it fails */ |
379 » » » } | 360 if (init_htab(hashp, nelem)) |
380 » » » hashp->LORDER = info->lorder; | 361 return (NULL); |
381 » » } | 362 else |
382 » } | 363 return (hashp); |
383 » /* init_htab sets errno if it fails */ | 364 } |
384 » if (init_htab(hashp, nelem)) | 365 /* |
385 » » return (NULL); | 366 * This calls alloc_segs which may run out of memory. Alloc_segs will |
386 » else | |
387 » » return (hashp); | |
388 } | |
389 /* | |
390 * This calls alloc_segs which may run out of memory. Alloc_segs will· | |
391 * set errno, so we just pass the error information along. | 367 * set errno, so we just pass the error information along. |
392 * | 368 * |
393 * Returns 0 on No Error | 369 * Returns 0 on No Error |
394 */ | 370 */ |
395 static int | 371 static int init_htab(HTAB *hashp, int nelem) { |
396 init_htab(HTAB *hashp, int nelem) | 372 register int nbuckets, nsegs; |
397 { | 373 int l2; |
398 » register int nbuckets, nsegs; | 374 |
399 » int l2; | 375 /* |
400 | 376 * Divide number of elements by the fill factor and determine a |
401 » /* | 377 * desired number of buckets. Allocate space for the next greater |
402 » * Divide number of elements by the fill factor and determine a | 378 * power of two number of buckets. |
403 » * desired number of buckets. Allocate space for the next greater | 379 */ |
404 » * power of two number of buckets. | 380 nelem = (nelem - 1) / hashp->FFACTOR + 1; |
405 » */ | 381 |
406 » nelem = (nelem - 1) / hashp->FFACTOR + 1; | 382 l2 = __log2((uint32)PR_MAX(nelem, 2)); |
407 | 383 nbuckets = 1 << l2; |
408 » l2 = __log2((uint32)PR_MAX(nelem, 2)); | 384 |
409 » nbuckets = 1 << l2; | 385 hashp->SPARES[l2] = l2 + 1; |
410 | 386 hashp->SPARES[l2 + 1] = l2 + 1; |
411 » hashp->SPARES[l2] = l2 + 1; | 387 hashp->OVFL_POINT = l2; |
412 » hashp->SPARES[l2 + 1] = l2 + 1; | 388 hashp->LAST_FREED = 2; |
413 » hashp->OVFL_POINT = l2; | 389 |
414 » hashp->LAST_FREED = 2; | 390 /* First bitmap page is at: splitpoint l2 page offset 1 */ |
415 | 391 if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0)) return (-1); |
416 » /* First bitmap page is at: splitpoint l2 page offset 1 */ | 392 |
417 » if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0)) | 393 hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; |
418 » » return (-1); | 394 hashp->HIGH_MASK = (nbuckets << 1) - 1; |
419 | 395 hashp->HDRPAGES = |
420 » hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; | 396 ((PR_MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> hashp->BSHIFT) + 1; |
421 » hashp->HIGH_MASK = (nbuckets << 1) - 1; | 397 |
422 » hashp->HDRPAGES = ((PR_MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> | 398 nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; |
423 » hashp->BSHIFT) + 1; | 399 nsegs = 1 << __log2((uint32)nsegs); |
424 | 400 |
425 » nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; | 401 if (nsegs > hashp->DSIZE) hashp->DSIZE = nsegs; |
426 » nsegs = 1 << __log2((uint32)nsegs); | 402 return (alloc_segs(hashp, nsegs)); |
427 | |
428 » if (nsegs > hashp->DSIZE) | |
429 » » hashp->DSIZE = nsegs; | |
430 » return (alloc_segs(hashp, nsegs)); | |
431 } | 403 } |
432 | 404 |
433 /********************** DESTROY/CLOSE ROUTINES ************************/ | 405 /********************** DESTROY/CLOSE ROUTINES ************************/ |
434 | 406 |
435 /* | 407 /* |
436 * Flushes any changes to the file if necessary and destroys the hashp | 408 * Flushes any changes to the file if necessary and destroys the hashp |
437 * structure, freeing all allocated space. | 409 * structure, freeing all allocated space. |
438 */ | 410 */ |
439 static int | 411 static int hdestroy(HTAB *hashp) { |
440 hdestroy(HTAB *hashp) | 412 int i, save_errno; |
441 { | 413 |
442 » int i, save_errno; | 414 save_errno = 0; |
443 | |
444 » save_errno = 0; | |
445 | 415 |
446 #ifdef HASH_STATISTICS | 416 #ifdef HASH_STATISTICS |
447 » (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", | 417 (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", |
448 » hash_accesses, hash_collisions); | 418 hash_accesses, hash_collisions); |
449 » (void)fprintf(stderr, "hdestroy: expansions %ld\n", | 419 (void)fprintf(stderr, "hdestroy: expansions %ld\n", hash_expansions); |
450 » hash_expansions); | 420 (void)fprintf(stderr, "hdestroy: overflows %ld\n", hash_overflows); |
451 » (void)fprintf(stderr, "hdestroy: overflows %ld\n", | 421 (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", hashp->NKEYS, |
452 » hash_overflows); | 422 hashp->MAX_BUCKET, hashp->nsegs); |
453 » (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", | 423 |
454 » hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); | 424 for (i = 0; i < NCACHED; i++) |
455 | 425 (void)fprintf(stderr, "spares[%d] = %d\n", i, hashp->SPARES[i]); |
456 » for (i = 0; i < NCACHED; i++) | 426 #endif |
457 » » (void)fprintf(stderr, | 427 /* |
458 » » "spares[%d] = %d\n", i, hashp->SPARES[i]); | 428 * Call on buffer manager to free buffers, and if required, |
459 #endif | 429 * write them to disk. |
460 » /* | 430 */ |
461 » * Call on buffer manager to free buffers, and if required, | 431 if (__buf_free(hashp, 1, hashp->save_file)) save_errno = errno; |
462 » * write them to disk. | 432 if (hashp->dir) { |
463 » */ | 433 free(*hashp->dir); /* Free initial segments */ |
464 » if (__buf_free(hashp, 1, hashp->save_file)) | 434 /* Free extra segments */ |
465 » » save_errno = errno; | 435 while (hashp->exsegs--) free(hashp->dir[--hashp->nsegs]); |
466 » if (hashp->dir) { | 436 free(hashp->dir); |
467 » » free(*hashp->dir);» /* Free initial segments */ | 437 } |
468 » » /* Free extra segments */ | 438 if (flush_meta(hashp) && !save_errno) save_errno = errno; |
469 » » while (hashp->exsegs--) | 439 /* Free Bigmaps */ |
470 » » » free(hashp->dir[--hashp->nsegs]); | 440 for (i = 0; i < hashp->nmaps; i++) |
471 » » free(hashp->dir); | 441 if (hashp->mapp[i]) free(hashp->mapp[i]); |
472 » } | 442 |
473 » if (flush_meta(hashp) && !save_errno) | 443 if (hashp->fp != -1) (void)close(hashp->fp); |
474 » » save_errno = errno; | 444 |
475 » /* Free Bigmaps */ | 445 if (hashp->filename) { |
476 » for (i = 0; i < hashp->nmaps; i++) | |
477 » » if (hashp->mapp[i]) | |
478 » » » free(hashp->mapp[i]); | |
479 | |
480 » if (hashp->fp != -1) | |
481 » » (void)close(hashp->fp); | |
482 | |
483 » if(hashp->filename) { | |
484 #if defined(_WIN32) || defined(_WINDOWS) || defined(XP_OS2) | 446 #if defined(_WIN32) || defined(_WINDOWS) || defined(XP_OS2) |
485 » » if (hashp->is_temp) | 447 if (hashp->is_temp) (void)unlink(hashp->filename); |
486 » » » (void)unlink(hashp->filename); | 448 #endif |
487 #endif | 449 free(hashp->filename); |
488 » » free(hashp->filename); | 450 } |
489 » } | 451 if (hashp->tmp_buf) free(hashp->tmp_buf); |
490 » if (hashp->tmp_buf) | 452 if (hashp->tmp_key) free(hashp->tmp_key); |
491 » free(hashp->tmp_buf); | 453 free(hashp); |
492 » if (hashp->tmp_key) | 454 if (save_errno) { |
493 » free(hashp->tmp_key); | 455 errno = save_errno; |
494 » free(hashp); | 456 return (DBM_ERROR); |
495 » if (save_errno) { | 457 } |
496 » » errno = save_errno; | 458 return (SUCCESS); |
497 » » return (DBM_ERROR); | 459 } |
498 » } | 460 |
499 » return (SUCCESS); | 461 #if defined(_WIN32) || defined(_WINDOWS) |
500 } | 462 /* |
501 | 463 * Close and reopen file to force file length update on windows. |
502 #if defined(_WIN32) || defined(_WINDOWS) | |
503 /* | |
504 * Close and reopen file to force file length update on windows.· | |
505 * | 464 * |
506 * Returns: | 465 * Returns: |
507 * 0 == OK | 466 * 0 == OK |
508 * -1 DBM_ERROR | 467 * -1 DBM_ERROR |
509 */ | 468 */ |
510 static int | 469 static int update_EOF(HTAB *hashp) { |
511 update_EOF(HTAB *hashp) | |
512 { | |
513 #if defined(DBM_REOPEN_ON_FLUSH) | 470 #if defined(DBM_REOPEN_ON_FLUSH) |
514 » char * file = hashp->filename; | 471 char *file = hashp->filename; |
515 » off_t file_size; | 472 off_t file_size; |
516 » int flags; | 473 int flags; |
517 » int mode = -1; | 474 int mode = -1; |
518 » struct stat statbuf; | 475 struct stat statbuf; |
519 | 476 |
520 » memset(&statbuf, 0, sizeof statbuf); | 477 memset(&statbuf, 0, sizeof statbuf); |
521 | 478 |
522 » /* make sure we won't lose the file by closing it. */ | 479 /* make sure we won't lose the file by closing it. */ |
523 » if (!file || (stat(file, &statbuf) && (errno == ENOENT))) { | 480 if (!file || (stat(file, &statbuf) && (errno == ENOENT))) { |
524 » » /* pretend we did it. */ | 481 /* pretend we did it. */ |
525 » » return 0; | 482 return 0; |
526 » } | 483 } |
527 | 484 |
528 » (void)close(hashp->fp); | 485 (void)close(hashp->fp); |
529 | 486 |
530 » flags = hashp->flags & ~(O_TRUNC | O_CREAT | O_EXCL); | 487 flags = hashp->flags & ~(O_TRUNC | O_CREAT | O_EXCL); |
531 | 488 |
532 » if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) | 489 if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1) return -1; |
533 » » return -1; | 490 file_size = lseek(hashp->fp, (off_t)0, SEEK_END); |
534 » file_size = lseek(hashp->fp, (off_t)0, SEEK_END); | 491 if (file_size == -1) return -1; |
535 » if (file_size == -1) | 492 hashp->file_size = file_size; |
536 » » return -1; | 493 return 0; |
537 » hashp->file_size = file_size; | |
538 » return 0; | |
539 #else | 494 #else |
540 » int fd = hashp->fp; | 495 int fd = hashp->fp; |
541 » off_t file_size = lseek(fd, (off_t)0, SEEK_END); | 496 off_t file_size = lseek(fd, (off_t)0, SEEK_END); |
542 » HANDLE handle = (HANDLE)_get_osfhandle(fd); | 497 HANDLE handle = (HANDLE)_get_osfhandle(fd); |
543 » BOOL cool = FlushFileBuffers(handle); | 498 BOOL cool = FlushFileBuffers(handle); |
544 #ifdef DEBUG3 | 499 #ifdef DEBUG3 |
545 » if (!cool) { | 500 if (!cool) { |
546 » » DWORD err = GetLastError(); | 501 DWORD err = GetLastError(); |
547 » » (void)fprintf(stderr, | 502 (void)fprintf(stderr, "FlushFileBuffers failed, last error = %d, 0x%08x\n", |
548 » » » "FlushFileBuffers failed, last error = %d, 0x%08x\n", | 503 err, err); |
549 » » » err, err); | 504 } |
550 » } | 505 #endif |
551 #endif | 506 if (file_size == -1) return -1; |
552 » if (file_size == -1) | 507 hashp->file_size = file_size; |
553 » » return -1; | 508 return cool ? 0 : -1; |
554 » hashp->file_size = file_size; | |
555 » return cool ? 0 : -1; | |
556 #endif | 509 #endif |
557 } | 510 } |
558 #endif | 511 #endif |
559 | 512 |
560 /* | 513 /* |
561 * Write modified pages to disk | 514 * Write modified pages to disk |
562 * | 515 * |
563 * Returns: | 516 * Returns: |
564 * 0 == OK | 517 * 0 == OK |
565 * -1 DBM_ERROR | 518 * -1 DBM_ERROR |
566 */ | 519 */ |
567 static int | 520 static int hash_sync(const DB *dbp, uint flags) { |
568 hash_sync(const DB *dbp, uint flags) | 521 HTAB *hashp; |
569 { | 522 |
570 » HTAB *hashp; | 523 if (flags != 0) { |
571 | 524 errno = EINVAL; |
572 » if (flags != 0) { | 525 return (DBM_ERROR); |
573 » » errno = EINVAL; | 526 } |
574 » » return (DBM_ERROR); | 527 |
575 » } | 528 if (!dbp) return (DBM_ERROR); |
576 | 529 |
577 » if (!dbp) | 530 hashp = (HTAB *)dbp->internal; |
578 » » return (DBM_ERROR); | 531 if (!hashp) return (DBM_ERROR); |
579 | 532 |
580 » hashp = (HTAB *)dbp->internal; | 533 if (!hashp->save_file) return (0); |
581 » if(!hashp) | 534 if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) return (DBM_ERROR); |
582 » » return (DBM_ERROR); | 535 #if defined(_WIN32) || defined(_WINDOWS) |
583 | 536 if (hashp->updateEOF && hashp->filename && !hashp->is_temp) { |
584 » if (!hashp->save_file) | 537 int status = update_EOF(hashp); |
585 » » return (0); | 538 hashp->updateEOF = 0; |
586 » if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) | 539 if (status) return status; |
587 » » return (DBM_ERROR); | 540 } |
588 #if defined(_WIN32) || defined(_WINDOWS)· | 541 #endif |
589 » if (hashp->updateEOF && hashp->filename && !hashp->is_temp) { | 542 hashp->new_file = 0; |
590 » » int status = update_EOF(hashp); | 543 return (0); |
591 » » hashp->updateEOF = 0; | |
592 » » if (status) | |
593 » » » return status; | |
594 » } | |
595 #endif | |
596 » hashp->new_file = 0; | |
597 » return (0); | |
598 } | 544 } |
599 | 545 |
600 /* | 546 /* |
601 * Returns: | 547 * Returns: |
602 * 0 == OK | 548 * 0 == OK |
603 * -1 indicates that errno should be set | 549 * -1 indicates that errno should be set |
604 */ | 550 */ |
605 static int | 551 static int flush_meta(HTAB *hashp) { |
606 flush_meta(HTAB *hashp) | 552 HASHHDR *whdrp; |
607 { | |
608 » HASHHDR *whdrp; | |
609 #if BYTE_ORDER == LITTLE_ENDIAN | 553 #if BYTE_ORDER == LITTLE_ENDIAN |
610 » HASHHDR whdr; | 554 HASHHDR whdr; |
611 #endif | 555 #endif |
612 » int fp, i, wsize; | 556 int fp, i, wsize; |
613 | 557 |
614 » if (!hashp->save_file) | 558 if (!hashp->save_file) return (0); |
615 » » return (0); | 559 hashp->MAGIC = HASHMAGIC; |
616 » hashp->MAGIC = HASHMAGIC; | 560 hashp->VERSION = HASHVERSION; |
617 » hashp->VERSION = HASHVERSION; | 561 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); |
618 » hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); | 562 |
619 | 563 fp = hashp->fp; |
620 » fp = hashp->fp; | 564 whdrp = &hashp->hdr; |
621 » whdrp = &hashp->hdr; | |
622 #if BYTE_ORDER == LITTLE_ENDIAN | 565 #if BYTE_ORDER == LITTLE_ENDIAN |
623 » whdrp = &whdr; | 566 whdrp = &whdr; |
624 » swap_header_copy(&hashp->hdr, whdrp); | 567 swap_header_copy(&hashp->hdr, whdrp); |
625 #endif | 568 #endif |
626 » if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || | 569 if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || |
627 » ((wsize = write(fp, (char*)whdrp, sizeof(HASHHDR))) == -1)) | 570 ((wsize = write(fp, (char *)whdrp, sizeof(HASHHDR))) == -1)) |
628 » » return (-1); | 571 return (-1); |
629 » else | 572 else if (wsize != sizeof(HASHHDR)) { |
630 » » if (wsize != sizeof(HASHHDR)) { | 573 errno = EFTYPE; |
631 » » » errno = EFTYPE; | 574 hashp->dbmerrno = errno; |
632 » » » hashp->dbmerrno = errno; | 575 return (-1); |
633 » » » return (-1); | 576 } |
634 » » } | 577 for (i = 0; i < NCACHED; i++) |
635 » for (i = 0; i < NCACHED; i++) | 578 if (hashp->mapp[i]) |
636 » » if (hashp->mapp[i]) | 579 if (__put_page(hashp, (char *)hashp->mapp[i], hashp->BITMAPS[i], 0, 1)) |
637 » » » if (__put_page(hashp, (char *)hashp->mapp[i], | 580 return (-1); |
638 » » » » hashp->BITMAPS[i], 0, 1)) | 581 return (0); |
639 » » » » return (-1); | |
640 » return (0); | |
641 } | 582 } |
642 | 583 |
643 /*******************************SEARCH ROUTINES *****************************/ | 584 /*******************************SEARCH ROUTINES *****************************/ |
644 /* | 585 /* |
645 * All the access routines return | 586 * All the access routines return |
646 * | 587 * |
647 * Returns: | 588 * Returns: |
648 * 0 on SUCCESS | 589 * 0 on SUCCESS |
649 * 1 to indicate an external DBM_ERROR (i.e. key not found, etc) | 590 * 1 to indicate an external DBM_ERROR (i.e. key not found, etc) |
650 * -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc) | 591 * -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc) |
651 */ | 592 */ |
652 static int | 593 static int hash_get(const DB *dbp, const DBT *key, DBT *data, uint flag) { |
653 hash_get( | 594 HTAB *hashp; |
654 » const DB *dbp, | 595 int rv; |
655 » const DBT *key, | 596 |
656 » DBT *data, | 597 hashp = (HTAB *)dbp->internal; |
657 » uint flag) | 598 if (!hashp) return (DBM_ERROR); |
| 599 |
| 600 if (flag) { |
| 601 hashp->dbmerrno = errno = EINVAL; |
| 602 return (DBM_ERROR); |
| 603 } |
| 604 |
| 605 rv = hash_access(hashp, HASH_GET, (DBT *)key, data); |
| 606 |
| 607 if (rv == DATABASE_CORRUPTED_ERROR) { |
| 608 #if defined(unix) && defined(DEBUG) |
| 609 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); |
| 610 #endif |
| 611 __remove_database((DB *)dbp); |
| 612 } |
| 613 |
| 614 return (rv); |
| 615 } |
| 616 |
| 617 static int hash_put(const DB *dbp, DBT *key, const DBT *data, uint flag) { |
| 618 HTAB *hashp; |
| 619 int rv; |
| 620 |
| 621 hashp = (HTAB *)dbp->internal; |
| 622 if (!hashp) return (DBM_ERROR); |
| 623 |
| 624 if (flag && flag != R_NOOVERWRITE) { |
| 625 hashp->dbmerrno = errno = EINVAL; |
| 626 return (DBM_ERROR); |
| 627 } |
| 628 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { |
| 629 hashp->dbmerrno = errno = EPERM; |
| 630 return (DBM_ERROR); |
| 631 } |
| 632 |
| 633 rv = hash_access(hashp, flag == R_NOOVERWRITE ? HASH_PUTNEW : HASH_PUT, |
| 634 (DBT *)key, (DBT *)data); |
| 635 |
| 636 if (rv == DATABASE_CORRUPTED_ERROR) { |
| 637 #if defined(unix) && defined(DEBUG) |
| 638 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); |
| 639 #endif |
| 640 __remove_database((DB *)dbp); |
| 641 } |
| 642 |
| 643 return (rv); |
| 644 } |
| 645 |
| 646 static int hash_delete(const DB *dbp, const DBT *key, uint flag) /* Ignored */ |
658 { | 647 { |
659 » HTAB *hashp; | 648 HTAB *hashp; |
660 » int rv; | 649 int rv; |
661 | 650 |
662 » hashp = (HTAB *)dbp->internal; | 651 hashp = (HTAB *)dbp->internal; |
663 » if (!hashp) | 652 if (!hashp) return (DBM_ERROR); |
664 » » return (DBM_ERROR); | 653 |
665 | 654 if (flag && flag != R_CURSOR) { |
666 » if (flag) { | 655 hashp->dbmerrno = errno = EINVAL; |
667 » » hashp->dbmerrno = errno = EINVAL; | 656 return (DBM_ERROR); |
668 » » return (DBM_ERROR); | 657 } |
669 » } | 658 if ((hashp->flags & O_ACCMODE) == O_RDONLY) { |
670 | 659 hashp->dbmerrno = errno = EPERM; |
671 » rv = hash_access(hashp, HASH_GET, (DBT *)key, data); | 660 return (DBM_ERROR); |
672 | 661 } |
673 » if(rv == DATABASE_CORRUPTED_ERROR) | 662 rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL); |
674 » { | 663 |
| 664 if (rv == DATABASE_CORRUPTED_ERROR) { |
675 #if defined(unix) && defined(DEBUG) | 665 #if defined(unix) && defined(DEBUG) |
676 » » printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); | 666 printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); |
677 #endif | 667 #endif |
678 » » __remove_database((DB *)dbp); | 668 __remove_database((DB *)dbp); |
679 » } | 669 } |
680 | 670 |
681 » return(rv); | 671 return (rv); |
682 } | |
683 | |
684 static int | |
685 hash_put( | |
686 » const DB *dbp, | |
687 » DBT *key, | |
688 » const DBT *data, | |
689 » uint flag) | |
690 { | |
691 » HTAB *hashp; | |
692 » int rv; | |
693 | |
694 » hashp = (HTAB *)dbp->internal; | |
695 » if (!hashp) | |
696 » » return (DBM_ERROR); | |
697 | |
698 » if (flag && flag != R_NOOVERWRITE) { | |
699 » » hashp->dbmerrno = errno = EINVAL; | |
700 » » return (DBM_ERROR); | |
701 » } | |
702 » if ((hashp->flags & O_ACCMODE) == O_RDONLY) { | |
703 » » hashp->dbmerrno = errno = EPERM; | |
704 » » return (DBM_ERROR); | |
705 » } | |
706 | |
707 » rv = hash_access(hashp, flag == R_NOOVERWRITE ? | |
708 » HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data); | |
709 | |
710 » if(rv == DATABASE_CORRUPTED_ERROR) | |
711 » { | |
712 #if defined(unix) && defined(DEBUG) | |
713 » » printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); | |
714 #endif | |
715 » » __remove_database((DB *)dbp); | |
716 » } | |
717 | |
718 » return(rv); | |
719 } | |
720 | |
721 static int | |
722 hash_delete( | |
723 » const DB *dbp, | |
724 » const DBT *key, | |
725 » uint flag)» » /* Ignored */ | |
726 { | |
727 » HTAB *hashp; | |
728 » int rv; | |
729 | |
730 » hashp = (HTAB *)dbp->internal; | |
731 » if (!hashp) | |
732 » » return (DBM_ERROR); | |
733 | |
734 » if (flag && flag != R_CURSOR) { | |
735 » » hashp->dbmerrno = errno = EINVAL; | |
736 » » return (DBM_ERROR); | |
737 » } | |
738 » if ((hashp->flags & O_ACCMODE) == O_RDONLY) { | |
739 » » hashp->dbmerrno = errno = EPERM; | |
740 » » return (DBM_ERROR); | |
741 » } | |
742 » rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL); | |
743 | |
744 » if(rv == DATABASE_CORRUPTED_ERROR) | |
745 » { | |
746 #if defined(unix) && defined(DEBUG) | |
747 » » printf("\n\nDBM Database has been corrupted, tell Lou...\n\n"); | |
748 #endif | |
749 » » __remove_database((DB *)dbp); | |
750 » } | |
751 | |
752 » return(rv); | |
753 } | 672 } |
754 | 673 |
755 #define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000 | 674 #define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000 |
756 /* | 675 /* |
757 * Assume that hashp has been set in wrapper routine. | 676 * Assume that hashp has been set in wrapper routine. |
758 */ | 677 */ |
759 static int | 678 static int hash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val) { |
760 hash_access( | 679 register BUFHEAD *rbufp; |
761 » HTAB *hashp, | 680 BUFHEAD *bufp, *save_bufp; |
762 » ACTION action, | 681 register uint16 *bp; |
763 » DBT *key, DBT *val) | 682 register long n, ndx, off; |
764 { | 683 register size_t size; |
765 » register BUFHEAD *rbufp; | 684 register char *kp; |
766 » BUFHEAD *bufp, *save_bufp; | 685 uint16 pageno; |
767 » register uint16 *bp; | 686 uint32 ovfl_loop_count = 0; |
768 » register long n, ndx, off; | 687 int32 last_overflow_page_no = -1; |
769 » register size_t size; | |
770 » register char *kp; | |
771 » uint16 pageno; | |
772 » uint32 ovfl_loop_count=0; | |
773 int32 last_overflow_page_no = -1; | |
774 | 688 |
775 #ifdef HASH_STATISTICS | 689 #ifdef HASH_STATISTICS |
776 » hash_accesses++; | 690 hash_accesses++; |
777 #endif | 691 #endif |
778 | 692 |
779 » off = hashp->BSIZE; | 693 off = hashp->BSIZE; |
780 » size = key->size; | 694 size = key->size; |
781 » kp = (char *)key->data; | 695 kp = (char *)key->data; |
782 » rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); | 696 rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); |
783 » if (!rbufp) | 697 if (!rbufp) return (DATABASE_CORRUPTED_ERROR); |
784 » » return (DATABASE_CORRUPTED_ERROR); | 698 save_bufp = rbufp; |
785 » save_bufp = rbufp; | 699 |
786 | 700 /* Pin the bucket chain */ |
787 » /* Pin the bucket chain */ | 701 rbufp->flags |= BUF_PIN; |
788 » rbufp->flags |= BUF_PIN; | 702 for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) { |
789 » for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) | 703 |
790 » { | 704 if (bp[1] >= REAL_KEY) { |
791 | 705 /* Real key/data pair */ |
792 » » if (bp[1] >= REAL_KEY) { | 706 if (size == (unsigned long)(off - *bp) && |
793 » » » /* Real key/data pair */ | 707 memcmp(kp, rbufp->page + *bp, size) == 0) |
794 » » » if (size == (unsigned long)(off - *bp) && | 708 goto found; |
795 » » » memcmp(kp, rbufp->page + *bp, size) == 0) | 709 off = bp[1]; |
796 » » » » goto found; | |
797 » » » off = bp[1]; | |
798 #ifdef HASH_STATISTICS | 710 #ifdef HASH_STATISTICS |
799 » » » hash_collisions++; | 711 hash_collisions++; |
800 #endif | 712 #endif |
801 » » » bp += 2; | 713 bp += 2; |
802 » » » ndx += 2; | 714 ndx += 2; |
803 » » } else if (bp[1] == OVFLPAGE) { | 715 } else if (bp[1] == OVFLPAGE) { |
804 | 716 |
805 /* database corruption: overflow loop detection */ | 717 /* database corruption: overflow loop detection */ |
806 if(last_overflow_page_no == (int32)*bp) | 718 if (last_overflow_page_no == (int32) * bp) |
807 » » » return (DATABASE_CORRUPTED_ERROR); | 719 return (DATABASE_CORRUPTED_ERROR); |
808 | 720 |
809 last_overflow_page_no = *bp; | 721 last_overflow_page_no = *bp; |
810 | 722 |
811 » » » rbufp = __get_buf(hashp, *bp, rbufp, 0); | 723 rbufp = __get_buf(hashp, *bp, rbufp, 0); |
812 » » » if (!rbufp) { | 724 if (!rbufp) { |
813 » » » » save_bufp->flags &= ~BUF_PIN; | 725 save_bufp->flags &= ~BUF_PIN; |
814 » » » » return (DBM_ERROR); | 726 return (DBM_ERROR); |
815 » » » } | 727 } |
816 | 728 |
817 ovfl_loop_count++; | 729 ovfl_loop_count++; |
818 if(ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS) | 730 if (ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS) |
819 » » » return (DATABASE_CORRUPTED_ERROR); | 731 return (DATABASE_CORRUPTED_ERROR); |
820 | 732 |
821 » » » /* FOR LOOP INIT */ | 733 /* FOR LOOP INIT */ |
822 » » » bp = (uint16 *)rbufp->page; | 734 bp = (uint16 *)rbufp->page; |
823 » » » n = *bp++; | 735 n = *bp++; |
824 » » » ndx = 1; | 736 ndx = 1; |
825 » » » off = hashp->BSIZE; | 737 off = hashp->BSIZE; |
826 » » } else if (bp[1] < REAL_KEY) { | 738 } else if (bp[1] < REAL_KEY) { |
827 » » » if ((ndx = | 739 if ((ndx = __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0) |
828 » » » __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) >
0) | 740 goto found; |
829 » » » » goto found; | 741 if (ndx == -2) { |
830 » » » if (ndx == -2) { | 742 bufp = rbufp; |
831 » » » » bufp = rbufp; | 743 if (!(pageno = __find_last_page(hashp, &bufp))) { |
832 » » » » if (!(pageno = | 744 ndx = 0; |
833 » » » » __find_last_page(hashp, &bufp))) { | 745 rbufp = bufp; |
834 » » » » » ndx = 0; | 746 break; /* FOR */ |
835 » » » » » rbufp = bufp; | 747 } |
836 » » » » » break;» /* FOR */ | 748 rbufp = __get_buf(hashp, pageno, bufp, 0); |
837 » » » » } | 749 if (!rbufp) { |
838 » » » » rbufp = __get_buf(hashp, pageno, bufp, 0); | 750 save_bufp->flags &= ~BUF_PIN; |
839 » » » » if (!rbufp) { | 751 return (DBM_ERROR); |
840 » » » » » save_bufp->flags &= ~BUF_PIN; | 752 } |
841 » » » » » return (DBM_ERROR); | 753 /* FOR LOOP INIT */ |
842 » » » » } | 754 bp = (uint16 *)rbufp->page; |
843 » » » » /* FOR LOOP INIT */ | 755 n = *bp++; |
844 » » » » bp = (uint16 *)rbufp->page; | 756 ndx = 1; |
845 » » » » n = *bp++; | 757 off = hashp->BSIZE; |
846 » » » » ndx = 1; | 758 } else { |
847 » » » » off = hashp->BSIZE; | 759 save_bufp->flags &= ~BUF_PIN; |
848 » » » } else { | 760 return (DBM_ERROR); |
849 » » » » save_bufp->flags &= ~BUF_PIN; | 761 } |
850 » » » » return (DBM_ERROR); | 762 } |
851 | 763 } |
852 » » » } | 764 |
853 » » } | 765 /* Not found */ |
854 » } | 766 switch (action) { |
855 | 767 case HASH_PUT: |
856 » /* Not found */ | 768 case HASH_PUTNEW: |
857 » switch (action) { | 769 if (__addel(hashp, rbufp, key, val)) { |
858 » case HASH_PUT: | 770 save_bufp->flags &= ~BUF_PIN; |
859 » case HASH_PUTNEW: | 771 return (DBM_ERROR); |
860 » » if (__addel(hashp, rbufp, key, val)) { | 772 } else { |
861 » » » save_bufp->flags &= ~BUF_PIN; | 773 save_bufp->flags &= ~BUF_PIN; |
862 » » » return (DBM_ERROR); | 774 return (SUCCESS); |
863 » » } else { | 775 } |
864 » » » save_bufp->flags &= ~BUF_PIN; | 776 case HASH_GET: |
865 » » » return (SUCCESS); | 777 case HASH_DELETE: |
866 » » } | 778 default: |
867 » case HASH_GET: | 779 save_bufp->flags &= ~BUF_PIN; |
868 » case HASH_DELETE: | 780 return (ABNORMAL); |
869 » default: | 781 } |
870 » » save_bufp->flags &= ~BUF_PIN; | |
871 » » return (ABNORMAL); | |
872 » } | |
873 | 782 |
874 found: | 783 found: |
875 » switch (action) { | 784 switch (action) { |
876 » case HASH_PUTNEW: | 785 case HASH_PUTNEW: |
877 » » save_bufp->flags &= ~BUF_PIN; | 786 save_bufp->flags &= ~BUF_PIN; |
878 » » return (ABNORMAL); | 787 return (ABNORMAL); |
879 » case HASH_GET: | 788 case HASH_GET: |
880 » » bp = (uint16 *)rbufp->page; | 789 bp = (uint16 *)rbufp->page; |
881 » » if (bp[ndx + 1] < REAL_KEY) { | 790 if (bp[ndx + 1] < REAL_KEY) { |
882 » » » if (__big_return(hashp, rbufp, ndx, val, 0)) | 791 if (__big_return(hashp, rbufp, ndx, val, 0)) return (DBM_ERROR); |
883 » » » » return (DBM_ERROR); | 792 } else { |
884 » » } else { | 793 val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1]; |
885 » » » val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1]; | 794 val->size = bp[ndx] - bp[ndx + 1]; |
886 » » » val->size = bp[ndx] - bp[ndx + 1]; | 795 } |
887 » » } | 796 break; |
888 » » break; | 797 case HASH_PUT: |
889 » case HASH_PUT: | 798 if ((__delpair(hashp, rbufp, ndx)) || (__addel(hashp, rbufp, key, val))) { |
890 » » if ((__delpair(hashp, rbufp, ndx)) || | 799 save_bufp->flags &= ~BUF_PIN; |
891 » » (__addel(hashp, rbufp, key, val))) { | 800 return (DBM_ERROR); |
892 » » » save_bufp->flags &= ~BUF_PIN; | 801 } |
893 » » » return (DBM_ERROR); | 802 break; |
894 » » } | 803 case HASH_DELETE: |
895 » » break; | 804 if (__delpair(hashp, rbufp, ndx)) return (DBM_ERROR); |
896 » case HASH_DELETE: | 805 break; |
897 » » if (__delpair(hashp, rbufp, ndx)) | 806 default: |
898 » » » return (DBM_ERROR); | 807 abort(); |
899 » » break; | 808 } |
900 » default: | 809 save_bufp->flags &= ~BUF_PIN; |
901 » » abort(); | 810 return (SUCCESS); |
902 » } | 811 } |
903 » save_bufp->flags &= ~BUF_PIN; | 812 |
904 » return (SUCCESS); | 813 static int hash_seq(const DB *dbp, DBT *key, DBT *data, uint flag) { |
905 } | 814 register uint32 bucket; |
906 | 815 register BUFHEAD *bufp; |
907 static int | 816 HTAB *hashp; |
908 hash_seq( | 817 uint16 *bp, ndx; |
909 » const DB *dbp, | 818 |
910 » DBT *key, DBT *data, | 819 hashp = (HTAB *)dbp->internal; |
911 » uint flag) | 820 if (!hashp) return (DBM_ERROR); |
912 { | 821 |
913 » register uint32 bucket; | 822 if (flag && flag != R_FIRST && flag != R_NEXT) { |
914 » register BUFHEAD *bufp; | 823 hashp->dbmerrno = errno = EINVAL; |
915 » HTAB *hashp; | 824 return (DBM_ERROR); |
916 » uint16 *bp, ndx; | 825 } |
917 | |
918 » hashp = (HTAB *)dbp->internal; | |
919 » if (!hashp) | |
920 » » return (DBM_ERROR); | |
921 | |
922 » if (flag && flag != R_FIRST && flag != R_NEXT) { | |
923 » » hashp->dbmerrno = errno = EINVAL; | |
924 » » return (DBM_ERROR); | |
925 » } | |
926 #ifdef HASH_STATISTICS | 826 #ifdef HASH_STATISTICS |
927 » hash_accesses++; | 827 hash_accesses++; |
928 #endif | 828 #endif |
929 » if ((hashp->cbucket < 0) || (flag == R_FIRST)) { | 829 if ((hashp->cbucket < 0) || (flag == R_FIRST)) { |
930 » » hashp->cbucket = 0; | 830 hashp->cbucket = 0; |
931 » » hashp->cndx = 1; | 831 hashp->cndx = 1; |
932 » » hashp->cpage = NULL; | 832 hashp->cpage = NULL; |
933 » } | 833 } |
934 | 834 |
935 » for (bp = NULL; !bp || !bp[0]; ) { | 835 for (bp = NULL; !bp || !bp[0];) { |
936 » » if (!(bufp = hashp->cpage)) { | 836 if (!(bufp = hashp->cpage)) { |
937 » » » for (bucket = hashp->cbucket; | 837 for (bucket = hashp->cbucket; bucket <= (uint32)hashp->MAX_BUCKET; |
938 » » » bucket <= (uint32)hashp->MAX_BUCKET; | 838 bucket++, hashp->cndx = 1) { |
939 » » » bucket++, hashp->cndx = 1) { | 839 bufp = __get_buf(hashp, bucket, NULL, 0); |
940 » » » » bufp = __get_buf(hashp, bucket, NULL, 0); | 840 if (!bufp) return (DBM_ERROR); |
941 » » » » if (!bufp) | 841 hashp->cpage = bufp; |
942 » » » » » return (DBM_ERROR); | 842 bp = (uint16 *)bufp->page; |
943 » » » » hashp->cpage = bufp; | 843 if (bp[0]) break; |
944 » » » » bp = (uint16 *)bufp->page; | 844 } |
945 » » » » if (bp[0]) | 845 hashp->cbucket = bucket; |
946 » » » » » break; | 846 if (hashp->cbucket > hashp->MAX_BUCKET) { |
947 » » » } | 847 hashp->cbucket = -1; |
948 » » » hashp->cbucket = bucket; | 848 return (ABNORMAL); |
949 » » » if (hashp->cbucket > hashp->MAX_BUCKET) { | 849 } |
950 » » » » hashp->cbucket = -1; | 850 } else |
951 » » » » return (ABNORMAL); | 851 bp = (uint16 *)hashp->cpage->page; |
952 » » » } | |
953 » » } else | |
954 » » » bp = (uint16 *)hashp->cpage->page; | |
955 | 852 |
956 #ifdef DEBUG | 853 #ifdef DEBUG |
957 » » assert(bp); | 854 assert(bp); |
958 » » assert(bufp); | 855 assert(bufp); |
959 #endif | 856 #endif |
960 » » while (bp[hashp->cndx + 1] == OVFLPAGE) { | 857 while (bp[hashp->cndx + 1] == OVFLPAGE) { |
961 » » » bufp = hashp->cpage = | 858 bufp = hashp->cpage = __get_buf(hashp, bp[hashp->cndx], bufp, 0); |
962 » » » __get_buf(hashp, bp[hashp->cndx], bufp, 0); | 859 if (!bufp) return (DBM_ERROR); |
963 » » » if (!bufp) | 860 bp = (uint16 *)(bufp->page); |
964 » » » » return (DBM_ERROR); | 861 hashp->cndx = 1; |
965 » » » bp = (uint16 *)(bufp->page); | 862 } |
966 » » » hashp->cndx = 1; | 863 if (!bp[0]) { |
967 » » } | 864 hashp->cpage = NULL; |
968 » » if (!bp[0]) { | 865 ++hashp->cbucket; |
969 » » » hashp->cpage = NULL; | 866 } |
970 » » » ++hashp->cbucket; | 867 } |
971 » » } | 868 ndx = hashp->cndx; |
972 » } | 869 if (bp[ndx + 1] < REAL_KEY) { |
973 » ndx = hashp->cndx; | 870 if (__big_keydata(hashp, bufp, key, data, 1)) return (DBM_ERROR); |
974 » if (bp[ndx + 1] < REAL_KEY) { | 871 } else { |
975 » » if (__big_keydata(hashp, bufp, key, data, 1)) | 872 key->data = (uint8 *)hashp->cpage->page + bp[ndx]; |
976 » » » return (DBM_ERROR); | 873 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; |
977 » } else { | 874 data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1]; |
978 » » key->data = (uint8 *)hashp->cpage->page + bp[ndx]; | 875 data->size = bp[ndx] - bp[ndx + 1]; |
979 » » key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; | 876 ndx += 2; |
980 » » data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1]; | 877 if (ndx > bp[0]) { |
981 » » data->size = bp[ndx] - bp[ndx + 1]; | 878 hashp->cpage = NULL; |
982 » » ndx += 2; | 879 hashp->cbucket++; |
983 » » if (ndx > bp[0]) { | 880 hashp->cndx = 1; |
984 » » » hashp->cpage = NULL; | 881 } else |
985 » » » hashp->cbucket++; | 882 hashp->cndx = ndx; |
986 » » » hashp->cndx = 1; | 883 } |
987 » » } else | 884 return (SUCCESS); |
988 » » » hashp->cndx = ndx; | |
989 » } | |
990 » return (SUCCESS); | |
991 } | 885 } |
992 | 886 |
993 /********************************* UTILITIES ************************/ | 887 /********************************* UTILITIES ************************/ |
994 | 888 |
995 /* | 889 /* |
996 * Returns: | 890 * Returns: |
997 * 0 ==> OK | 891 * 0 ==> OK |
998 * -1 ==> Error | 892 * -1 ==> Error |
999 */ | 893 */ |
1000 extern int | 894 extern int __expand_table(HTAB *hashp) { |
1001 __expand_table(HTAB *hashp) | 895 uint32 old_bucket, new_bucket; |
1002 { | 896 int new_segnum, spare_ndx; |
1003 » uint32 old_bucket, new_bucket; | 897 size_t dirsize; |
1004 » int new_segnum, spare_ndx; | |
1005 » size_t dirsize; | |
1006 | 898 |
1007 #ifdef HASH_STATISTICS | 899 #ifdef HASH_STATISTICS |
1008 » hash_expansions++; | 900 hash_expansions++; |
1009 #endif | 901 #endif |
1010 » new_bucket = ++hashp->MAX_BUCKET; | 902 new_bucket = ++hashp->MAX_BUCKET; |
1011 » old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); | 903 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); |
1012 | 904 |
1013 » new_segnum = new_bucket >> hashp->SSHIFT; | 905 new_segnum = new_bucket >> hashp->SSHIFT; |
1014 | 906 |
1015 » /* Check if we need a new segment */ | 907 /* Check if we need a new segment */ |
1016 » if (new_segnum >= hashp->nsegs) { | 908 if (new_segnum >= hashp->nsegs) { |
1017 » » /* Check if we need to expand directory */ | 909 /* Check if we need to expand directory */ |
1018 » » if (new_segnum >= hashp->DSIZE) { | 910 if (new_segnum >= hashp->DSIZE) { |
1019 » » » /* Reallocate directory */ | 911 /* Reallocate directory */ |
1020 » » » dirsize = hashp->DSIZE * sizeof(SEGMENT *); | 912 dirsize = hashp->DSIZE * sizeof(SEGMENT *); |
1021 » » » if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) | 913 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) return (-1); |
1022 » » » » return (-1); | 914 hashp->DSIZE = dirsize << 1; |
1023 » » » hashp->DSIZE = dirsize << 1; | 915 } |
1024 » » } | 916 if ((hashp->dir[new_segnum] = |
1025 » » if ((hashp->dir[new_segnum] = | 917 (SEGMENT)calloc((size_t)hashp->SGSIZE, sizeof(SEGMENT))) == NULL) |
1026 » » (SEGMENT)calloc((size_t)hashp->SGSIZE, sizeof(SEGMENT))) ==
NULL) | 918 return (-1); |
1027 » » » return (-1); | 919 hashp->exsegs++; |
1028 » » hashp->exsegs++; | 920 hashp->nsegs++; |
1029 » » hashp->nsegs++; | 921 } |
1030 » } | 922 /* |
1031 » /* | 923 * If the split point is increasing (MAX_BUCKET's log base 2 |
1032 » * If the split point is increasing (MAX_BUCKET's log base 2 | 924 * * increases), we need to copy the current contents of the spare |
1033 » * * increases), we need to copy the current contents of the spare | 925 * split bucket to the next bucket. |
1034 » * split bucket to the next bucket. | 926 */ |
1035 » */ | 927 spare_ndx = __log2((uint32)(hashp->MAX_BUCKET + 1)); |
1036 » spare_ndx = __log2((uint32)(hashp->MAX_BUCKET + 1)); | 928 if (spare_ndx > hashp->OVFL_POINT) { |
1037 » if (spare_ndx > hashp->OVFL_POINT) { | 929 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; |
1038 » » hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; | 930 hashp->OVFL_POINT = spare_ndx; |
1039 » » hashp->OVFL_POINT = spare_ndx; | 931 } |
1040 » } | 932 |
1041 | 933 if (new_bucket > (uint32)hashp->HIGH_MASK) { |
1042 » if (new_bucket > (uint32)hashp->HIGH_MASK) { | 934 /* Starting a new doubling */ |
1043 » » /* Starting a new doubling */ | 935 hashp->LOW_MASK = hashp->HIGH_MASK; |
1044 » » hashp->LOW_MASK = hashp->HIGH_MASK; | 936 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; |
1045 » » hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; | 937 } |
1046 » } | 938 /* Relocate records to the new bucket */ |
1047 » /* Relocate records to the new bucket */ | 939 return (__split_page(hashp, old_bucket, new_bucket)); |
1048 » return (__split_page(hashp, old_bucket, new_bucket)); | |
1049 } | 940 } |
1050 | 941 |
1051 /* | 942 /* |
1052 * If realloc guarantees that the pointer is not destroyed if the realloc | 943 * If realloc guarantees that the pointer is not destroyed if the realloc |
1053 * fails, then this routine can go away. | 944 * fails, then this routine can go away. |
1054 */ | 945 */ |
1055 static void * | 946 static void *hash_realloc(SEGMENT **p_ptr, size_t oldsize, size_t newsize) { |
1056 hash_realloc( | 947 register void *p; |
1057 » SEGMENT **p_ptr, | 948 |
1058 » size_t oldsize, size_t newsize) | 949 if ((p = malloc(newsize))) { |
1059 { | 950 memmove(p, *p_ptr, oldsize); |
1060 » register void *p; | 951 memset((char *)p + oldsize, 0, newsize - oldsize); |
1061 | 952 free(*p_ptr); |
1062 » if ((p = malloc(newsize))) { | 953 *p_ptr = (SEGMENT *)p; |
1063 » » memmove(p, *p_ptr, oldsize); | 954 } |
1064 » » memset((char *)p + oldsize, 0, newsize - oldsize); | 955 return (p); |
1065 » » free(*p_ptr); | 956 } |
1066 » » *p_ptr = (SEGMENT *)p; | 957 |
1067 » } | 958 extern uint32 __call_hash(HTAB *hashp, char *k, size_t len) { |
1068 » return (p); | 959 uint32 n, bucket; |
1069 } | 960 |
1070 | 961 n = hashp->hash(k, len); |
1071 extern uint32 | 962 bucket = n & hashp->HIGH_MASK; |
1072 __call_hash(HTAB *hashp, char *k, size_t len) | 963 if (bucket > (uint32)hashp->MAX_BUCKET) bucket = bucket & hashp->LOW_MASK; |
1073 { | 964 return (bucket); |
1074 » uint32 n, bucket; | |
1075 | |
1076 » n = hashp->hash(k, len); | |
1077 » bucket = n & hashp->HIGH_MASK; | |
1078 » if (bucket > (uint32)hashp->MAX_BUCKET) | |
1079 » » bucket = bucket & hashp->LOW_MASK; | |
1080 » return (bucket); | |
1081 } | 965 } |
1082 | 966 |
1083 /* | 967 /* |
1084 * Allocate segment table. On error, set errno. | 968 * Allocate segment table. On error, set errno. |
1085 * | 969 * |
1086 * Returns 0 on success | 970 * Returns 0 on success |
1087 */ | 971 */ |
1088 static int | 972 static int alloc_segs(HTAB *hashp, int nsegs) { |
1089 alloc_segs( | 973 register int i; |
1090 » HTAB *hashp, | 974 register SEGMENT store; |
1091 » int nsegs) | 975 |
1092 { | 976 if ((hashp->dir = (SEGMENT *)calloc((size_t)hashp->DSIZE, |
1093 » register int i; | 977 sizeof(SEGMENT *))) == NULL) { |
1094 » register SEGMENT store; | 978 errno = ENOMEM; |
1095 | 979 return (-1); |
1096 » if ((hashp->dir = | 980 } |
1097 » (SEGMENT *)calloc((size_t)hashp->DSIZE, sizeof(SEGMENT *))) == NULL)
{ | 981 /* Allocate segments */ |
1098 » » errno = ENOMEM; | 982 if ((store = (SEGMENT)calloc((size_t)nsegs << hashp->SSHIFT, |
1099 » » return (-1); | 983 sizeof(SEGMENT))) == NULL) { |
1100 » } | 984 errno = ENOMEM; |
1101 » /* Allocate segments */ | 985 return (-1); |
1102 » if ((store = | 986 } |
1103 » (SEGMENT)calloc((size_t)nsegs << hashp->SSHIFT, sizeof(SEGMENT))) ==
NULL) { | 987 for (i = 0; i < nsegs; i++, hashp->nsegs++) |
1104 » » errno = ENOMEM; | 988 hashp->dir[i] = &store[i << hashp->SSHIFT]; |
1105 » » return (-1); | 989 return (0); |
1106 » } | |
1107 » for (i = 0; i < nsegs; i++, hashp->nsegs++) | |
1108 » » hashp->dir[i] = &store[i << hashp->SSHIFT]; | |
1109 » return (0); | |
1110 } | 990 } |
1111 | 991 |
1112 #if BYTE_ORDER == LITTLE_ENDIAN | 992 #if BYTE_ORDER == LITTLE_ENDIAN |
1113 /* | 993 /* |
1114 * Hashp->hdr needs to be byteswapped. | 994 * Hashp->hdr needs to be byteswapped. |
1115 */ | 995 */ |
1116 static void | 996 static void swap_header_copy(HASHHDR *srcp, HASHHDR *destp) { |
1117 swap_header_copy( | 997 int i; |
1118 » HASHHDR *srcp, HASHHDR *destp) | 998 |
1119 { | 999 P_32_COPY(srcp->magic, destp->magic); |
1120 » int i; | 1000 P_32_COPY(srcp->version, destp->version); |
1121 | 1001 P_32_COPY(srcp->lorder, destp->lorder); |
1122 » P_32_COPY(srcp->magic, destp->magic); | 1002 P_32_COPY(srcp->bsize, destp->bsize); |
1123 » P_32_COPY(srcp->version, destp->version); | 1003 P_32_COPY(srcp->bshift, destp->bshift); |
1124 » P_32_COPY(srcp->lorder, destp->lorder); | 1004 P_32_COPY(srcp->dsize, destp->dsize); |
1125 » P_32_COPY(srcp->bsize, destp->bsize); | 1005 P_32_COPY(srcp->ssize, destp->ssize); |
1126 » P_32_COPY(srcp->bshift, destp->bshift); | 1006 P_32_COPY(srcp->sshift, destp->sshift); |
1127 » P_32_COPY(srcp->dsize, destp->dsize); | 1007 P_32_COPY(srcp->ovfl_point, destp->ovfl_point); |
1128 » P_32_COPY(srcp->ssize, destp->ssize); | 1008 P_32_COPY(srcp->last_freed, destp->last_freed); |
1129 » P_32_COPY(srcp->sshift, destp->sshift); | 1009 P_32_COPY(srcp->max_bucket, destp->max_bucket); |
1130 » P_32_COPY(srcp->ovfl_point, destp->ovfl_point); | 1010 P_32_COPY(srcp->high_mask, destp->high_mask); |
1131 » P_32_COPY(srcp->last_freed, destp->last_freed); | 1011 P_32_COPY(srcp->low_mask, destp->low_mask); |
1132 » P_32_COPY(srcp->max_bucket, destp->max_bucket); | 1012 P_32_COPY(srcp->ffactor, destp->ffactor); |
1133 » P_32_COPY(srcp->high_mask, destp->high_mask); | 1013 P_32_COPY(srcp->nkeys, destp->nkeys); |
1134 » P_32_COPY(srcp->low_mask, destp->low_mask); | 1014 P_32_COPY(srcp->hdrpages, destp->hdrpages); |
1135 » P_32_COPY(srcp->ffactor, destp->ffactor); | 1015 P_32_COPY(srcp->h_charkey, destp->h_charkey); |
1136 » P_32_COPY(srcp->nkeys, destp->nkeys); | 1016 for (i = 0; i < NCACHED; i++) { |
1137 » P_32_COPY(srcp->hdrpages, destp->hdrpages); | 1017 P_32_COPY(srcp->spares[i], destp->spares[i]); |
1138 » P_32_COPY(srcp->h_charkey, destp->h_charkey); | 1018 P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); |
1139 » for (i = 0; i < NCACHED; i++) { | 1019 } |
1140 » » P_32_COPY(srcp->spares[i], destp->spares[i]); | 1020 } |
1141 » » P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); | 1021 |
1142 » } | 1022 static void swap_header(HTAB *hashp) { |
1143 } | 1023 HASHHDR *hdrp; |
1144 | 1024 int i; |
1145 static void | 1025 |
1146 swap_header(HTAB *hashp) | 1026 hdrp = &hashp->hdr; |
1147 { | 1027 |
1148 » HASHHDR *hdrp; | 1028 M_32_SWAP(hdrp->magic); |
1149 » int i; | 1029 M_32_SWAP(hdrp->version); |
1150 | 1030 M_32_SWAP(hdrp->lorder); |
1151 » hdrp = &hashp->hdr; | 1031 M_32_SWAP(hdrp->bsize); |
1152 | 1032 M_32_SWAP(hdrp->bshift); |
1153 » M_32_SWAP(hdrp->magic); | 1033 M_32_SWAP(hdrp->dsize); |
1154 » M_32_SWAP(hdrp->version); | 1034 M_32_SWAP(hdrp->ssize); |
1155 » M_32_SWAP(hdrp->lorder); | 1035 M_32_SWAP(hdrp->sshift); |
1156 » M_32_SWAP(hdrp->bsize); | 1036 M_32_SWAP(hdrp->ovfl_point); |
1157 » M_32_SWAP(hdrp->bshift); | 1037 M_32_SWAP(hdrp->last_freed); |
1158 » M_32_SWAP(hdrp->dsize); | 1038 M_32_SWAP(hdrp->max_bucket); |
1159 » M_32_SWAP(hdrp->ssize); | 1039 M_32_SWAP(hdrp->high_mask); |
1160 » M_32_SWAP(hdrp->sshift); | 1040 M_32_SWAP(hdrp->low_mask); |
1161 » M_32_SWAP(hdrp->ovfl_point); | 1041 M_32_SWAP(hdrp->ffactor); |
1162 » M_32_SWAP(hdrp->last_freed); | 1042 M_32_SWAP(hdrp->nkeys); |
1163 » M_32_SWAP(hdrp->max_bucket); | 1043 M_32_SWAP(hdrp->hdrpages); |
1164 » M_32_SWAP(hdrp->high_mask); | 1044 M_32_SWAP(hdrp->h_charkey); |
1165 » M_32_SWAP(hdrp->low_mask); | 1045 for (i = 0; i < NCACHED; i++) { |
1166 » M_32_SWAP(hdrp->ffactor); | 1046 M_32_SWAP(hdrp->spares[i]); |
1167 » M_32_SWAP(hdrp->nkeys); | 1047 M_16_SWAP(hdrp->bitmaps[i]); |
1168 » M_32_SWAP(hdrp->hdrpages); | 1048 } |
1169 » M_32_SWAP(hdrp->h_charkey); | 1049 } |
1170 » for (i = 0; i < NCACHED; i++) { | 1050 #endif |
1171 » » M_32_SWAP(hdrp->spares[i]); | |
1172 » » M_16_SWAP(hdrp->bitmaps[i]); | |
1173 » } | |
1174 } | |
1175 #endif | |
OLD | NEW |