hash.h

/*-
 * Copyright (c) 1990, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Margo Seltzer.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)hash.h	8.4 (Berkeley) 11/2/95
 */

#include "mpool.h"
#include "db-queue.h"

/* Operations */
typedef enum {
	HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
} ACTION;

/* cursor structure */
typedef struct cursor_t {
	TAILQ_ENTRY(cursor_t) queue;
	int (*get)	__P((const DB *, struct cursor_t *, DBT *, DBT *, \
			     u_int32_t));
	int (*delete) __P((const DB *, struct cursor_t *, u_int32_t));
	db_pgno_t	bucket;
	db_pgno_t	pgno;
	indx_t	ndx;
	indx_t	pgndx;
	u_int16_t *pagep;
	void *internal;
} CURSOR;


#define IS_BUCKET(X)	((X) & BUF_BUCKET)
#define IS_VALID(X)     (!((X) & BUF_INVALID))

/* Hash Table Information */
typedef struct hashhdr {	/* Disk resident portion */
	int32_t	magic;		/* Magic NO for hash tables */
	int32_t	version;	/* Version ID */
	int32_t	lorder;		/* Byte Order */
	u_int32_t	bsize;	/* Bucket/Page Size */
	int32_t	bshift;		/* Bucket shift */
	int32_t	ovfl_point;	/* Where overflow pages are being allocated */
	u_int32_t	last_freed;	/* Last overflow page freed */
	u_int32_t	max_bucket;	/* ID of Maximum bucket in use */
	u_int32_t	high_mask;	/* Mask to modulo into entire table */
	u_int32_t	low_mask;	/* Mask to modulo into lower half of table */
	u_int32_t	ffactor;	/* Fill factor */
	int32_t	nkeys;		/* Number of keys in hash table */
	u_int32_t	hdrpages;	/* Size of table header */
	u_int32_t	h_charkey;	/* value of hash(CHARKEY) */
#define NCACHED	32		/* number of bit maps and spare points */
	u_int32_t	spares[NCACHED];/* spare pages for overflow */
	u_int16_t	bitmaps[NCACHED];	/* address of overflow page bitmaps */
} HASHHDR;

typedef struct htab {		/* Memory resident data structure */
	TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue;
	HASHHDR hdr;		/* Header */
	u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */
	int32_t	flags;		/* Flag values */
	int32_t	fp;		/* File pointer */
	const char *fname;        	/* File path */
	u_int8_t *bigdata_buf;	/* Temporary Buffer for BIG data */
	u_int8_t *bigkey_buf;	/* Temporary Buffer for BIG keys */
	u_int16_t  *split_buf;	/* Temporary buffer for splits */
	CURSOR	*seq_cursor;	/* Cursor used for hash_seq */
	int32_t	local_errno;	/* Error Number -- for DBM compatibility */
	int32_t	new_file;	/* Indicates if fd is backing store or no */
	int32_t	save_file;	/* Indicates whether we need to flush file at
				 * exit */
	u_int32_t *mapp[NCACHED];/* Pointers to page maps */
	int32_t	nmaps;		/* Initial number of bitmaps */
	MPOOL	*mp;		/* mpool for buffer management */
} HTAB;

/*
 * Constants
 */
#define	MAX_BSIZE		65536		/* 2^16 */
#define MIN_BUFFERS		6
#define MINHDRSIZE		512
#define DEF_CACHESIZE	65536
#define DEF_BUCKET_SHIFT	12		/* log2(BUCKET) */
#define DEF_BUCKET_SIZE		(1<<DEF_BUCKET_SHIFT)
#define DEF_SEGSIZE_SHIFT	8		/* log2(SEGSIZE)	 */
#define DEF_SEGSIZE		(1<<DEF_SEGSIZE_SHIFT)
#define DEF_DIRSIZE		256
#define DEF_FFACTOR		65536
#define MIN_FFACTOR		4
#define SPLTMAX			8
#define CHARKEY			"%$sniglet^&"
#define NUMKEY			1038583
#define BYTE_SHIFT		3
#define INT32_T_TO_BYTE		2
#define INT32_T_BYTE_SHIFT		5
#define ALL_SET			((u_int32_t)0xFFFFFFFF)
#define ALL_CLEAR		0

#define PTROF(X)	((BUFHEAD *)((ptr_t)(X)&~0x3))
#define ISMOD(X)	((ptr_t)(X)&0x1)
#define DOMOD(X)	((X) = (int8_t *)((ptr_t)(X)|0x1))
#define ISDISK(X)	((ptr_t)(X)&0x2)
#define DODISK(X)	((X) = (int8_t *)((ptr_t)(X)|0x2))

#define BITS_PER_MAP	32

/* Given the address of the beginning of a big map, clear/set the nth bit */
#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
#define ISSET(A, N)	((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))

/* Overflow management */
/*
 * Overflow page numbers are allocated per split point.  At each doubling of
 * the table, we can allocate extra pages.  So, an overflow page number has
 * the top 5 bits indicate which split point and the lower 11 bits indicate
 * which page at that split point is indicated (pages within split points are
 * numberered starting with 1).
 */

#define SPLITSHIFT	11
#define SPLITMASK	0x7FF
#define SPLITNUM(N)	(((u_int32_t)(N)) >> SPLITSHIFT)
#define OPAGENUM(N)	((N) & SPLITMASK)
#define	OADDR_OF(S,O)	((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))

#define BUCKET_TO_PAGE(B) \
	((B) + hashp->hdr.hdrpages + ((B) \
	    ? hashp->hdr.spares[__log2((B)+1)-1] : 0))
#define OADDR_TO_PAGE(B) 	\
	(BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)))

#define POW2(N)  (1 << (N))

#define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize)

/* Shorthands for accessing structure */
#define METADATA_PGNO 0
#define SPLIT_PGNO 0xFFFF

typedef struct item_info {
	db_pgno_t 		pgno;
	db_pgno_t		bucket;
	indx_t		ndx;
	indx_t		pgndx;
	u_int8_t	status;
	u_int32_t	seek_size;
	db_pgno_t		seek_found_page;
	indx_t		key_off;
	indx_t		data_off;
	u_int8_t	caused_expand;
} ITEM_INFO;


#define	ITEM_ERROR	0
#define	ITEM_OK		1
#define	ITEM_NO_MORE	2

#define	ITEM_GET_FIRST	0
#define	ITEM_GET_NEXT	1
#define	ITEM_GET_RESET	2
#define	ITEM_GET_DONE	3
#define	ITEM_GET_N	4

#define	UNKNOWN		0xffffffff		/* for num_items */
#define	NO_EXPAND	0xfffffffe