Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

hash.c @ 620

Last change on this file since 620 was 444, checked in by satin@…, 6 years ago
add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc
File size: 24.3 KB

Line
1	/*-
2	* Copyright (c) 1990, 1993, 1994
3	* The Regents of the University of California. All rights reserved.
4	*
5	* This code is derived from software contributed to Berkeley by
6	* Margo Seltzer.
7	*
8	* Redistribution and use in source and binary forms, with or without
9	* modification, are permitted provided that the following conditions
10	* are met:
11	* 1. Redistributions of source code must retain the above copyright
12	* notice, this list of conditions and the following disclaimer.
13	* 2. Redistributions in binary form must reproduce the above copyright
14	* notice, this list of conditions and the following disclaimer in the
15	* documentation and/or other materials provided with the distribution.
16	* 3. All advertising materials mentioning features or use of this software
17	* must display the following acknowledgement:
18	* This product includes software developed by the University of
19	* California, Berkeley and its contributors.
20	* 4. Neither the name of the University nor the names of its contributors
21	* may be used to endorse or promote products derived from this software
22	* without specific prior written permission.
23	*
24	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34	* SUCH DAMAGE.
35	*/
36
37	#include <sys/param.h>
38	#if defined(LIBC_SCCS) && !defined(lint)
39	static char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94";
40	#endif /* LIBC_SCCS and not lint */
41	#include <sys/cdefs.h>
42	#include <sys/types.h>
43
44	#include <sys/stat.h>
45
46	#include <errno.h>
47	#include <fcntl.h>
48	#include <stdio.h>
49	#include <stdlib.h>
50	#include <string.h>
51	#include <unistd.h>
52	#ifdef DEBUG
53	#include <assert.h>
54	#endif
55
56	#define __DBINTERFACE_PRIVATE /* activate prototypes from db_local.h */
57	#include "db_local.h"
58	#include "hash.h"
59	#include "page.h"
60	#include "extern.h"
61
62	static int alloc_segs(HTAB *, int);
63	static int flush_meta(HTAB *);
64	static int hash_access(HTAB , ACTION, DBT , DBT *);
65	static int hash_close(DB *);
66	static int hash_delete(const DB , const DBT , u_int);
67	static int hash_fd(const DB *);
68	static int hash_get(const DB , const DBT , DBT *, u_int);
69	static int hash_put(const DB , DBT , const DBT *, u_int);
70	static void hash_realloc(SEGMENT *, int, int);
71	static int hash_seq(const DB , DBT , DBT *, u_int);
72	static int hash_sync(const DB *, u_int);
73	static int hdestroy(HTAB *);
74	static HTAB init_hash(HTAB , const char , const HASHINFO );
75	static int init_htab(HTAB *, int);
76	#if (BYTE_ORDER == LITTLE_ENDIAN)
77	static void swap_header(HTAB *);
78	static void swap_header_copy(HASHHDR , HASHHDR );
79	#endif
80
81	/* Macros for min/max. */
82	#ifndef MIN
83	#define MIN(a,b) (((a)<(b))?(a):(b))
84	#endif
85	#ifndef MAX
86	#define MAX(a,b) (((a)>(b))?(a):(b))
87	#endif
88
89	/* Fast arithmetic, relying on powers of 2, */
90	#define MOD(x, y) ((x) & ((y) - 1))
91
92	#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; }
93
94	/* Return values */
95	#define SUCCESS (0)
96	#define ERROR (-1)
97	#define ABNORMAL (1)
98
99	#ifdef HASH_STATISTICS
100	int hash_accesses, hash_collisions, hash_expansions, hash_overflows;
101	#endif
102
103	/************************ INTERFACE ROUTINES *************************/
104	/* OPEN/CLOSE */
105
106	extern DB *
107	__hash_open (const char *file,
108	int flags,
109	int mode,
110	int dflags,
111	const HASHINFO info) / Special directives for create */
112	{
113	HTAB *hashp;
114
115	#ifdef __USE_INTERNAL_STAT64
116	struct stat64 statbuf;
117	#else
118	struct stat statbuf;
119	#endif
120	DB *dbp;
121	int bpages, hdrsize, new_table, nsegs, save_errno;
122
123	if ((flags & O_ACCMODE) == O_WRONLY) {
124	errno = EINVAL;
125	return (NULL);
126	}
127
128	if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))
129	return (NULL);
130	hashp->fp = -1;
131
132	/*
133	* Even if user wants write only, we need to be able to read
134	* the actual file, so we need to open it read/write. But, the
135	* field in the hashp structure needs to be accurate so that
136	* we can check accesses.
137	*/
138	hashp->flags = flags;
139
140	new_table = 0;
141	if (!file \|\| (flags & O_TRUNC) \|\|
142	#ifdef __USE_INTERNAL_STAT64
143	(_stat64(file, &statbuf) && (errno == ENOENT))) {
144	#else
145	(stat(file, &statbuf) && (errno == ENOENT))) {
146	#endif
147	if (errno == ENOENT)
148	errno = 0; /* Just in case someone looks at errno */
149	new_table = 1;
150	}
151	if (file) {
152	if ((hashp->fp = open(file, flags, mode)) == -1)
153	RETURN_ERROR(errno, error0);
154
155	/* if the .db file is empty, and we had permission to create
156	a new .db file, then reinitialize the database */
157	if ((flags & O_CREAT) &&
158	#ifdef __USE_INTERNAL_STAT64
159	_fstat64(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0)
160	#else
161	fstat(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0)
162	#endif
163	new_table = 1;
164
165	#ifdef HAVE_FCNTL
166	(void)fcntl(hashp->fp, F_SETFD, 1);
167	#endif
168	}
169	if (new_table) {
170	if (!(hashp = init_hash(hashp, file, (HASHINFO *)info)))
171	RETURN_ERROR(errno, error1);
172	} else {
173	/* Table already exists */
174	if (info && info->hash)
175	hashp->hash = info->hash;
176	else
177	hashp->hash = __default_hash;
178
179	hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));
180	#if (BYTE_ORDER == LITTLE_ENDIAN)
181	swap_header(hashp);
182	#endif
183	if (hdrsize == -1)
184	RETURN_ERROR(errno, error1);
185	if (hdrsize != sizeof(HASHHDR))
186	RETURN_ERROR(EFTYPE, error1);
187	/* Verify file type, versions and hash function */
188	if (hashp->MAGIC != HASHMAGIC)
189	RETURN_ERROR(EFTYPE, error1);
190	#define OLDHASHVERSION 1
191	if (hashp->HASH_VERSION != HASHVERSION &&
192	hashp->HASH_VERSION != OLDHASHVERSION)
193	RETURN_ERROR(EFTYPE, error1);
194	if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
195	RETURN_ERROR(EFTYPE, error1);
196	/*
197	* Figure out how many segments we need. Max_Bucket is the
198	* maximum bucket number, so the number of buckets is
199	* max_bucket + 1.
200	*/
201	nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
202	hashp->SGSIZE;
203	hashp->nsegs = 0;
204	if (alloc_segs(hashp, nsegs))
205	/*
206	* If alloc_segs fails, table will have been destroyed
207	* and errno will have been set.
208	*/
209	return (NULL);
210	/* Read in bitmaps */
211	bpages = (hashp->SPARES[hashp->OVFL_POINT] +
212	(hashp->BSIZE << BYTE_SHIFT) - 1) >>
213	(hashp->BSHIFT + BYTE_SHIFT);
214
215	hashp->nmaps = bpages;
216	(void)memset(&hashp->mapp[0], 0, bpages * sizeof(__uint32_t *));
217	}
218
219	/* Initialize Buffer Manager */
220	if (info && info->cachesize)
221	__buf_init(hashp, info->cachesize);
222	else
223	__buf_init(hashp, DEF_BUFSIZE);
224
225	hashp->new_file = new_table;
226	hashp->save_file = file && (hashp->flags & O_RDWR);
227	hashp->cbucket = -1;
228	if (!(dbp = (DB *)malloc(sizeof(DB)))) {
229	save_errno = errno;
230	hdestroy(hashp);
231	errno = save_errno;
232	return (NULL);
233	}
234	dbp->internal = hashp;
235	dbp->close = hash_close;
236	dbp->del = hash_delete;
237	dbp->fd = hash_fd;
238	dbp->get = hash_get;
239	dbp->put = hash_put;
240	dbp->seq = hash_seq;
241	dbp->sync = hash_sync;
242	dbp->type = DB_HASH;
243
244	#ifdef DEBUG
245	(void)fprintf(stderr,
246	"%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
247	"init_htab:",
248	"TABLE POINTER ", hashp,
249	"BUCKET SIZE ", hashp->BSIZE,
250	"BUCKET SHIFT ", hashp->BSHIFT,
251	"DIRECTORY SIZE ", hashp->DSIZE,
252	"SEGMENT SIZE ", hashp->SGSIZE,
253	"SEGMENT SHIFT ", hashp->SSHIFT,
254	"FILL FACTOR ", hashp->FFACTOR,
255	"MAX BUCKET ", hashp->MAX_BUCKET,
256	"OVFL POINT ", hashp->OVFL_POINT,
257	"LAST FREED ", hashp->LAST_FREED,
258	"HIGH MASK ", hashp->HIGH_MASK,
259	"LOW MASK ", hashp->LOW_MASK,
260	"NSEGS ", hashp->nsegs,
261	"NKEYS ", hashp->NKEYS);
262	#endif
263	#ifdef HASH_STATISTICS
264	hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
265	#endif
266	return (dbp);
267
268	error1:
269	if (hashp != NULL)
270	(void)close(hashp->fp);
271
272	error0:
273	free(hashp);
274	errno = save_errno;
275	return (NULL);
276	}
277
278	static int
279	hash_close(dbp)
280	DB *dbp;
281	{
282	HTAB *hashp;
283	int retval;
284
285	if (!dbp)
286	return (ERROR);
287
288	hashp = (HTAB *)dbp->internal;
289	retval = hdestroy(hashp);
290	free(dbp);
291	return (retval);
292	}
293
294	static int
295	hash_fd(dbp)
296	const DB *dbp;
297	{
298	HTAB *hashp;
299
300	if (!dbp)
301	return (ERROR);
302
303	hashp = (HTAB *)dbp->internal;
304	if (hashp->fp == -1) {
305	errno = ENOENT;
306	return (-1);
307	}
308	return (hashp->fp);
309	}
310
311	/************************ LOCAL CREATION ROUTINES ********************/
312	static HTAB *
313	init_hash(hashp, file, info)
314	HTAB *hashp;
315	const char *file;
316	const HASHINFO *info;
317	{
318	#ifdef __USE_INTERNAL_STAT64
319	struct stat64 statbuf;
320	#else
321	struct stat statbuf;
322	#endif
323	int nelem;
324
325	nelem = 1;
326	hashp->NKEYS = 0;
327	hashp->LORDER = DB_BYTE_ORDER;
328	hashp->BSIZE = DEF_BUCKET_SIZE;
329	hashp->BSHIFT = DEF_BUCKET_SHIFT;
330	hashp->SGSIZE = DEF_SEGSIZE;
331	hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
332	hashp->DSIZE = DEF_DIRSIZE;
333	hashp->FFACTOR = DEF_FFACTOR;
334	hashp->hash = __default_hash;
335	memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
336	memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
337
338	/* Fix bucket size to be optimal for file system */
339	if (file != NULL) {
340	#ifdef __USE_INTERNAL_STAT64
341	if (_stat64(file, &statbuf))
342	#else
343	if (stat(file, &statbuf))
344	#endif
345	return (NULL);
346	hashp->BSIZE = statbuf.st_blksize;
347	hashp->BSHIFT = __log2(hashp->BSIZE);
348	}
349
350	if (info) {
351	if (info->bsize) {
352	/* Round pagesize up to power of 2 */
353	hashp->BSHIFT = __log2(info->bsize);
354	hashp->BSIZE = 1 << hashp->BSHIFT;
355	if (hashp->BSIZE > MAX_BSIZE) {
356	errno = EINVAL;
357	return (NULL);
358	}
359	}
360	if (info->ffactor)
361	hashp->FFACTOR = info->ffactor;
362	if (info->hash)
363	hashp->hash = info->hash;
364	if (info->nelem)
365	nelem = info->nelem;
366	if (info->lorder) {
367	if (info->lorder != DB_BIG_ENDIAN &&
368	info->lorder != DB_LITTLE_ENDIAN) {
369	errno = EINVAL;
370	return (NULL);
371	}
372	hashp->LORDER = info->lorder;
373	}
374	}
375	/* init_htab should destroy the table and set errno if it fails */
376	if (init_htab(hashp, nelem))
377	return (NULL);
378	else
379	return (hashp);
380	}
381	/*
382	* This calls alloc_segs which may run out of memory. Alloc_segs will destroy
383	* the table and set errno, so we just pass the error information along.
384	*
385	* Returns 0 on No Error
386	*/
387	static int
388	init_htab(hashp, nelem)
389	HTAB *hashp;
390	int nelem;
391	{
392	int nbuckets, nsegs;
393	int l2;
394
395	/*
396	* Divide number of elements by the fill factor and determine a
397	* desired number of buckets. Allocate space for the next greater
398	* power of two number of buckets.
399	*/
400	nelem = (nelem - 1) / hashp->FFACTOR + 1;
401
402	l2 = __log2(MAX(nelem, 2));
403	nbuckets = 1 << l2;
404
405	hashp->SPARES[l2] = l2 + 1;
406	hashp->SPARES[l2 + 1] = l2 + 1;
407	hashp->OVFL_POINT = l2;
408	hashp->LAST_FREED = 2;
409
410	/* First bitmap page is at: splitpoint l2 page offset 1 */
411	if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
412	return (-1);
413
414	hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
415	hashp->HIGH_MASK = (nbuckets << 1) - 1;
416	hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
417	hashp->BSHIFT) + 1;
418
419	nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
420	nsegs = 1 << __log2(nsegs);
421
422	if (nsegs > hashp->DSIZE)
423	hashp->DSIZE = nsegs;
424	return (alloc_segs(hashp, nsegs));
425	}
426
427	/******************** DESTROY/CLOSE ROUTINES **********************/
428
429	/*
430	* Flushes any changes to the file if necessary and destroys the hashp
431	* structure, freeing all allocated space.
432	*/
433	static int
434	hdestroy(hashp)
435	HTAB *hashp;
436	{
437	int i, save_errno;
438
439	save_errno = 0;
440
441	#ifdef HASH_STATISTICS
442	(void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
443	hash_accesses, hash_collisions);
444	(void)fprintf(stderr, "hdestroy: expansions %ld\n",
445	hash_expansions);
446	(void)fprintf(stderr, "hdestroy: overflows %ld\n",
447	hash_overflows);
448	(void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
449	hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
450
451	for (i = 0; i < NCACHED; i++)
452	(void)fprintf(stderr,
453	"spares[%d] = %d\n", i, hashp->SPARES[i]);
454	#endif
455	/*
456	* Call on buffer manager to free buffers, and if required,
457	* write them to disk.
458	*/
459	if (__buf_free(hashp, 1, hashp->save_file))
460	save_errno = errno;
461	if (hashp->dir) {
462	free(hashp->dir); / Free initial segments */
463	/* Free extra segments */
464	while (hashp->exsegs--)
465	free(hashp->dir[--hashp->nsegs]);
466	free(hashp->dir);
467	}
468	if (flush_meta(hashp) && !save_errno)
469	save_errno = errno;
470	/* Free Bigmaps */
471	for (i = 0; i < hashp->nmaps; i++)
472	if (hashp->mapp[i])
473	free(hashp->mapp[i]);
474
475	if (hashp->fp != -1)
476	(void)close(hashp->fp);
477
478	free(hashp);
479
480	if (save_errno) {
481	errno = save_errno;
482	return (ERROR);
483	}
484	return (SUCCESS);
485	}
486	/*
487	* Write modified pages to disk
488	*
489	* Returns:
490	* 0 == OK
491	* -1 ERROR
492	*/
493	static int
494	hash_sync(dbp, flags)
495	const DB *dbp;
496	u_int flags;
497	{
498	HTAB *hashp;
499
500	if (flags != 0) {
501	errno = EINVAL;
502	return (ERROR);
503	}
504
505	if (!dbp)
506	return (ERROR);
507
508	hashp = (HTAB *)dbp->internal;
509	if (!hashp->save_file)
510	return (0);
511	if (__buf_free(hashp, 0, 1) \|\| flush_meta(hashp))
512	return (ERROR);
513	hashp->new_file = 0;
514	return (0);
515	}
516
517	/*
518	* Returns:
519	* 0 == OK
520	* -1 indicates that errno should be set
521	*/
522	static int
523	flush_meta(hashp)
524	HTAB *hashp;
525	{
526	HASHHDR *whdrp;
527	#if (BYTE_ORDER == LITTLE_ENDIAN)
528	HASHHDR whdr;
529	#endif
530	int fp, i, wsize;
531
532	if (!hashp->save_file)
533	return (0);
534	hashp->MAGIC = HASHMAGIC;
535	hashp->HASH_VERSION = HASHVERSION;
536	hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
537
538	fp = hashp->fp;
539	whdrp = &hashp->hdr;
540	#if (BYTE_ORDER == LITTLE_ENDIAN)
541	whdrp = &whdr;
542	swap_header_copy(&hashp->hdr, whdrp);
543	#endif
544	if ((lseek(fp, (off_t)0, SEEK_SET) == -1) \|\|
545	((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1))
546	return (-1);
547	else
548	if (wsize != sizeof(HASHHDR)) {
549	errno = EFTYPE;
550	hashp->error = errno;
551	return (-1);
552	}
553	for (i = 0; i < NCACHED; i++)
554	if (hashp->mapp[i])
555	if (__put_page(hashp, (char *)hashp->mapp[i],
556	hashp->BITMAPS[i], 0, 1))
557	return (-1);
558	return (0);
559	}
560
561	/*****************************SEARCH ROUTINES ***************************/
562	/*
563	* All the access routines return
564	*
565	* Returns:
566	* 0 on SUCCESS
567	* 1 to indicate an external ERROR (i.e. key not found, etc)
568	* -1 to indicate an internal ERROR (i.e. out of memory, etc)
569	*/
570	static int
571	hash_get(dbp, key, data, flag)
572	const DB *dbp;
573	const DBT *key;
574	DBT *data;
575	u_int flag;
576	{
577	HTAB *hashp;
578
579	hashp = (HTAB *)dbp->internal;
580	if (flag) {
581	hashp->error = errno = EINVAL;
582	return (ERROR);
583	}
584	return (hash_access(hashp, HASH_GET, (DBT *)key, data));
585	}
586
587	static int
588	hash_put(dbp, key, data, flag)
589	const DB *dbp;
590	DBT *key;
591	const DBT *data;
592	u_int flag;
593	{
594	HTAB *hashp;
595
596	hashp = (HTAB *)dbp->internal;
597	if (flag && flag != R_NOOVERWRITE) {
598	hashp->error = EINVAL;
599	errno = EINVAL;
600	return (ERROR);
601	}
602	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
603	hashp->error = errno = EPERM;
604	return (ERROR);
605	}
606	return (hash_access(hashp, flag == R_NOOVERWRITE ?
607	HASH_PUTNEW : HASH_PUT, (DBT )key, (DBT )data));
608	}
609
610	static int
611	hash_delete(dbp, key, flag)
612	const DB *dbp;
613	const DBT *key;
614	u_int flag; /* Ignored */
615	{
616	HTAB *hashp;
617
618	hashp = (HTAB *)dbp->internal;
619	if (flag && flag != R_CURSOR) {
620	hashp->error = errno = EINVAL;
621	return (ERROR);
622	}
623	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
624	hashp->error = errno = EPERM;
625	return (ERROR);
626	}
627	return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));
628	}
629
630	/*
631	* Assume that hashp has been set in wrapper routine.
632	*/
633	static int
634	hash_access(hashp, action, key, val)
635	HTAB *hashp;
636	ACTION action;
637	DBT key, val;
638	{
639	BUFHEAD *rbufp;
640	BUFHEAD bufp, save_bufp;
641	__uint16_t *bp;
642	int n, ndx, off, size;
643	char *kp;
644	__uint16_t pageno;
645
646	#ifdef HASH_STATISTICS
647	hash_accesses++;
648	#endif
649
650	off = hashp->BSIZE;
651	size = key->size;
652	kp = (char *)key->data;
653	rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
654	if (!rbufp)
655	return (ERROR);
656	save_bufp = rbufp;
657
658	/* Pin the bucket chain */
659	rbufp->flags \|= BUF_PIN;
660	for (bp = (__uint16_t )rbufp->page, n = bp++, ndx = 1; ndx < n;)
661	if (bp[1] >= REAL_KEY) {
662	/* Real key/data pair */
663	if (size == off - *bp &&
664	memcmp(kp, rbufp->page + *bp, size) == 0)
665	goto found;
666	off = bp[1];
667	#ifdef HASH_STATISTICS
668	hash_collisions++;
669	#endif
670	bp += 2;
671	ndx += 2;
672	} else if (bp[1] == OVFLPAGE) {
673	rbufp = __get_buf(hashp, *bp, rbufp, 0);
674	if (!rbufp) {
675	save_bufp->flags &= ~BUF_PIN;
676	return (ERROR);
677	}
678	/* FOR LOOP INIT */
679	bp = (__uint16_t *)rbufp->page;
680	n = *bp++;
681	ndx = 1;
682	off = hashp->BSIZE;
683	} else if (bp[1] < REAL_KEY) {
684	if ((ndx =
685	__find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)
686	goto found;
687	if (ndx == -2) {
688	bufp = rbufp;
689	if (!(pageno =
690	__find_last_page(hashp, &bufp))) {
691	ndx = 0;
692	rbufp = bufp;
693	break; /* FOR */
694	}
695	rbufp = __get_buf(hashp, pageno, bufp, 0);
696	if (!rbufp) {
697	save_bufp->flags &= ~BUF_PIN;
698	return (ERROR);
699	}
700	/* FOR LOOP INIT */
701	bp = (__uint16_t *)rbufp->page;
702	n = *bp++;
703	ndx = 1;
704	off = hashp->BSIZE;
705	} else {
706	save_bufp->flags &= ~BUF_PIN;
707	return (ERROR);
708	}
709	}
710
711	/* Not found */
712	switch (action) {
713	case HASH_PUT:
714	case HASH_PUTNEW:
715	if (__addel(hashp, rbufp, key, val)) {
716	save_bufp->flags &= ~BUF_PIN;
717	return (ERROR);
718	} else {
719	save_bufp->flags &= ~BUF_PIN;
720	return (SUCCESS);
721	}
722	case HASH_GET:
723	case HASH_DELETE:
724	default:
725	save_bufp->flags &= ~BUF_PIN;
726	return (ABNORMAL);
727	}
728
729	found:
730	switch (action) {
731	case HASH_PUTNEW:
732	save_bufp->flags &= ~BUF_PIN;
733	return (ABNORMAL);
734	case HASH_GET:
735	bp = (__uint16_t *)rbufp->page;
736	if (bp[ndx + 1] < REAL_KEY) {
737	if (__big_return(hashp, rbufp, ndx, val, 0))
738	return (ERROR);
739	} else {
740	val->data = (u_char *)rbufp->page + (int)bp[ndx + 1];
741	val->size = bp[ndx] - bp[ndx + 1];
742	}
743	break;
744	case HASH_PUT:
745	if ((__delpair(hashp, rbufp, ndx)) \|\|
746	(__addel(hashp, rbufp, key, val))) {
747	save_bufp->flags &= ~BUF_PIN;
748	return (ERROR);
749	}
750	break;
751	case HASH_DELETE:
752	if (__delpair(hashp, rbufp, ndx))
753	return (ERROR);
754	break;
755	default:
756	abort();
757	}
758	save_bufp->flags &= ~BUF_PIN;
759	return (SUCCESS);
760	}
761
762	static int
763	hash_seq(dbp, key, data, flag)
764	const DB *dbp;
765	DBT key, data;
766	u_int flag;
767	{
768	__uint32_t bucket;
769	BUFHEAD *bufp;
770	HTAB *hashp;
771	__uint16_t *bp, ndx;
772
773	hashp = (HTAB *)dbp->internal;
774	if (flag && flag != R_FIRST && flag != R_NEXT) {
775	hashp->error = errno = EINVAL;
776	return (ERROR);
777	}
778	#ifdef HASH_STATISTICS
779	hash_accesses++;
780	#endif
781	if ((hashp->cbucket < 0) \|\| (flag == R_FIRST)) {
782	hashp->cbucket = 0;
783	hashp->cndx = 1;
784	hashp->cpage = NULL;
785	}
786
787	for (bp = NULL; !bp \|\| !bp[0]; ) {
788	if (!(bufp = hashp->cpage)) {
789	for (bucket = hashp->cbucket;
790	bucket <= hashp->MAX_BUCKET;
791	bucket++, hashp->cndx = 1) {
792	bufp = __get_buf(hashp, bucket, NULL, 0);
793	if (!bufp)
794	return (ERROR);
795	hashp->cpage = bufp;
796	bp = (__uint16_t *)bufp->page;
797	if (bp[0])
798	break;
799	}
800	hashp->cbucket = bucket;
801	if (hashp->cbucket > hashp->MAX_BUCKET) {
802	hashp->cbucket = -1;
803	return (ABNORMAL);
804	}
805	} else
806	bp = (__uint16_t *)hashp->cpage->page;
807
808	#ifdef DEBUG
809	assert(bp);
810	assert(bufp);
811	#endif
812	while (bp[hashp->cndx + 1] == OVFLPAGE) {
813	bufp = hashp->cpage =
814	__get_buf(hashp, bp[hashp->cndx], bufp, 0);
815	if (!bufp)
816	return (ERROR);
817	bp = (__uint16_t *)(bufp->page);
818	hashp->cndx = 1;
819	}
820	if (!bp[0]) {
821	hashp->cpage = NULL;
822	++hashp->cbucket;
823	}
824	}
825	ndx = hashp->cndx;
826	if (bp[ndx + 1] < REAL_KEY) {
827	if (__big_keydata(hashp, bufp, key, data, 1))
828	return (ERROR);
829	} else {
830	key->data = (u_char *)hashp->cpage->page + bp[ndx];
831	key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
832	data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
833	data->size = bp[ndx] - bp[ndx + 1];
834	ndx += 2;
835	if (ndx > bp[0]) {
836	hashp->cpage = NULL;
837	hashp->cbucket++;
838	hashp->cndx = 1;
839	} else
840	hashp->cndx = ndx;
841	}
842	return (SUCCESS);
843	}
844
845	/******************************* UTILITIES **********************/
846
847	/*
848	* Returns:
849	* 0 ==> OK
850	* -1 ==> Error
851	*/
852	extern int
853	__expand_table(hashp)
854	HTAB *hashp;
855	{
856	__uint32_t old_bucket, new_bucket;
857	int dirsize, new_segnum, spare_ndx;
858
859	#ifdef HASH_STATISTICS
860	hash_expansions++;
861	#endif
862	new_bucket = ++hashp->MAX_BUCKET;
863	old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
864
865	new_segnum = new_bucket >> hashp->SSHIFT;
866
867	/* Check if we need a new segment */
868	if (new_segnum >= hashp->nsegs) {
869	/* Check if we need to expand directory */
870	if (new_segnum >= hashp->DSIZE) {
871	/* Reallocate directory */
872	dirsize = hashp->DSIZE * sizeof(SEGMENT *);
873	if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
874	return (-1);
875	hashp->DSIZE = dirsize << 1;
876	}
877	if ((hashp->dir[new_segnum] =
878	(SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
879	return (-1);
880	hashp->exsegs++;
881	hashp->nsegs++;
882	}
883	/*
884	* If the split point is increasing (MAX_BUCKET's log base 2
885	* * increases), we need to copy the current contents of the spare
886	* split bucket to the next bucket.
887	*/
888	spare_ndx = __log2(hashp->MAX_BUCKET + 1);
889	if (spare_ndx > hashp->OVFL_POINT) {
890	hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
891	hashp->OVFL_POINT = spare_ndx;
892	}
893
894	if (new_bucket > hashp->HIGH_MASK) {
895	/* Starting a new doubling */
896	hashp->LOW_MASK = hashp->HIGH_MASK;
897	hashp->HIGH_MASK = new_bucket \| hashp->LOW_MASK;
898	}
899	/* Relocate records to the new bucket */
900	return (__split_page(hashp, old_bucket, new_bucket));
901	}
902
903	/*
904	* If realloc guarantees that the pointer is not destroyed if the realloc
905	* fails, then this routine can go away.
906	*/
907	static void *
908	hash_realloc(p_ptr, oldsize, newsize)
909	SEGMENT **p_ptr;
910	int oldsize, newsize;
911	{
912	void *p;
913
914	if ( (p = malloc(newsize)) ) {
915	memmove(p, *p_ptr, oldsize);
916	memset((char *)p + oldsize, 0, newsize - oldsize);
917	free(*p_ptr);
918	*p_ptr = p;
919	}
920	return (p);
921	}
922
923	extern __uint32_t
924	__call_hash(hashp, k, len)
925	HTAB *hashp;
926	char *k;
927	int len;
928	{
929	int n, bucket;
930
931	n = hashp->hash(k, len);
932	bucket = n & hashp->HIGH_MASK;
933	if (bucket > hashp->MAX_BUCKET)
934	bucket = bucket & hashp->LOW_MASK;
935	return (bucket);
936	}
937
938	/*
939	* Allocate segment table. On error, destroy the table and set errno.
940	*
941	* Returns 0 on success
942	*/
943	static int
944	alloc_segs(hashp, nsegs)
945	HTAB *hashp;
946	int nsegs;
947	{
948	int i;
949	SEGMENT store;
950
951	int save_errno;
952
953	if ((hashp->dir =
954	(SEGMENT )calloc(hashp->DSIZE, sizeof(SEGMENT ))) == NULL) {
955	save_errno = errno;
956	(void)hdestroy(hashp);
957	errno = save_errno;
958	return (-1);
959	}
960	/* Allocate segments */
961	if ((store =
962	(SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
963	save_errno = errno;
964	(void)hdestroy(hashp);
965	errno = save_errno;
966	return (-1);
967	}
968	for (i = 0; i < nsegs; i++, hashp->nsegs++)
969	hashp->dir[i] = &store[i << hashp->SSHIFT];
970	return (0);
971	}
972
973	#if (BYTE_ORDER == LITTLE_ENDIAN)
974	/*
975	* Hashp->hdr needs to be byteswapped.
976	*/
977	static void
978	swap_header_copy(srcp, destp)
979	HASHHDR srcp, destp;
980	{
981	int i;
982
983	P_32_COPY(srcp->magic, destp->magic);
984	P_32_COPY(srcp->version, destp->version);
985	P_32_COPY(srcp->lorder, destp->lorder);
986	P_32_COPY(srcp->bsize, destp->bsize);
987	P_32_COPY(srcp->bshift, destp->bshift);
988	P_32_COPY(srcp->dsize, destp->dsize);
989	P_32_COPY(srcp->ssize, destp->ssize);
990	P_32_COPY(srcp->sshift, destp->sshift);
991	P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
992	P_32_COPY(srcp->last_freed, destp->last_freed);
993	P_32_COPY(srcp->max_bucket, destp->max_bucket);
994	P_32_COPY(srcp->high_mask, destp->high_mask);
995	P_32_COPY(srcp->low_mask, destp->low_mask);
996	P_32_COPY(srcp->ffactor, destp->ffactor);
997	P_32_COPY(srcp->nkeys, destp->nkeys);
998	P_32_COPY(srcp->hdrpages, destp->hdrpages);
999	P_32_COPY(srcp->h_charkey, destp->h_charkey);
1000	for (i = 0; i < NCACHED; i++) {
1001	P_32_COPY(srcp->spares[i], destp->spares[i]);
1002	P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
1003	}
1004	}
1005
1006	static void
1007	swap_header(hashp)
1008	HTAB *hashp;
1009	{
1010	HASHHDR *hdrp;
1011	int i;
1012
1013	hdrp = &hashp->hdr;
1014
1015	M_32_SWAP(hdrp->magic);
1016	M_32_SWAP(hdrp->version);
1017	M_32_SWAP(hdrp->lorder);
1018	M_32_SWAP(hdrp->bsize);
1019	M_32_SWAP(hdrp->bshift);
1020	M_32_SWAP(hdrp->dsize);
1021	M_32_SWAP(hdrp->ssize);
1022	M_32_SWAP(hdrp->sshift);
1023	M_32_SWAP(hdrp->ovfl_point);
1024	M_32_SWAP(hdrp->last_freed);
1025	M_32_SWAP(hdrp->max_bucket);
1026	M_32_SWAP(hdrp->high_mask);
1027	M_32_SWAP(hdrp->low_mask);
1028	M_32_SWAP(hdrp->ffactor);
1029	M_32_SWAP(hdrp->nkeys);
1030	M_32_SWAP(hdrp->hdrpages);
1031	M_32_SWAP(hdrp->h_charkey);
1032	for (i = 0; i < NCACHED; i++) {
1033	M_32_SWAP(hdrp->spares[i]);
1034	M_16_SWAP(hdrp->bitmaps[i]);
1035	}
1036	}
1037	#endif

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: trunk/libs/newlib/src/newlib/libc/search/hash.c @ 620

Download in other formats: