-/*
- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
- *
- * @APPLE_LICENSE_HEADER_START@
- *
- * The contents of this file constitute Original Code as defined in and
- * are subject to the Apple Public Source License Version 1.1 (the
- * "License"). You may not use this file except in compliance with the
- * License. Please obtain a copy of the License at
- * http://www.apple.com/publicsource and read it before using this file.
- *
- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
- * License for the specific language governing rights and limitations
- * under the License.
- *
- * @APPLE_LICENSE_HEADER_END@
- */
-/*
- * Copyright (c) 1990, 1993
+/*-
+ * 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
* 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.3 (Berkeley) 5/31/94
+ * $FreeBSD: src/lib/libc/db/hash/hash.h,v 1.6 2002/03/21 22:46:26 obrien Exp $
*/
/* Operations */
typedef struct _bufhead BUFHEAD;
struct _bufhead {
- BUFHEAD *prev; /* LRU links */
- BUFHEAD *next; /* LRU links */
- BUFHEAD *ovfl; /* Overflow page buffer header */
- u_int addr; /* Address of this page */
- char *page; /* Actual page data */
- char flags;
+ BUFHEAD *prev; /* LRU links */
+ BUFHEAD *next; /* LRU links */
+ BUFHEAD *ovfl; /* Overflow page buffer header */
+ u_int32_t addr; /* Address of this page */
+ char *page; /* Actual page data */
+ char flags;
#define BUF_MOD 0x0001
#define BUF_DISK 0x0002
#define BUF_BUCKET 0x0004
typedef BUFHEAD **SEGMENT;
/* Hash Table Information */
-typedef struct hashhdr { /* Disk resident portion */
- int magic; /* Magic NO for hash tables */
- int version; /* Version ID */
- long lorder; /* Byte Order */
- int bsize; /* Bucket/Page Size */
- int bshift; /* Bucket shift */
- int dsize; /* Directory Size */
- int ssize; /* Segment Size */
- int sshift; /* Segment shift */
- int ovfl_point; /* Where overflow pages are being allocated */
- int last_freed; /* Last overflow page freed */
- int max_bucket; /* ID of Maximum bucket in use */
- int high_mask; /* Mask to modulo into entire table */
- int low_mask; /* Mask to modulo into lower half of table */
- int ffactor; /* Fill factor */
- int nkeys; /* Number of keys in hash table */
- int hdrpages; /* Size of table header */
- int h_charkey; /* value of hash(CHARKEY) */
-#define NCACHED 32 /* number of bit maps and spare points */
- int spares[NCACHED];/* spare pages for overflow */
- u_short bitmaps[NCACHED]; /* address of overflow page bitmaps */
+typedef struct hashhdr { /* Disk resident portion */
+ int magic; /* Magic NO for hash tables */
+ int version; /* Version ID */
+ u_int32_t lorder; /* Byte Order */
+ int bsize; /* Bucket/Page Size */
+ int bshift; /* Bucket shift */
+ int dsize; /* Directory Size */
+ int ssize; /* Segment Size */
+ int sshift; /* Segment shift */
+ int ovfl_point; /* Where overflow pages are being
+ * allocated */
+ int last_freed; /* Last overflow page freed */
+ int max_bucket; /* ID of Maximum bucket in use */
+ int high_mask; /* Mask to modulo into entire table */
+ int low_mask; /* Mask to modulo into lower half of
+ * table */
+ int ffactor; /* Fill factor */
+ int nkeys; /* Number of keys in hash table */
+ int hdrpages; /* Size of table header */
+ int h_charkey; /* value of hash(CHARKEY) */
+#define NCACHED 32 /* number of bit maps and spare
+ * points */
+ int spares[NCACHED];/* spare pages for overflow */
+ u_int16_t bitmaps[NCACHED]; /* address of overflow page
+ * bitmaps */
} HASHHDR;
-typedef struct htab { /* Memory resident data structure */
- HASHHDR hdr; /* Header */
- int nsegs; /* Number of allocated segments */
- int exsegs; /* Number of extra allocated segments */
- u_int32_t /* Hash function */
- (*hash)__P((const void *, size_t));
- int flags; /* Flag values */
- int fp; /* File pointer */
- char *tmp_buf; /* Temporary Buffer for BIG data */
- char *tmp_key; /* Temporary Buffer for BIG keys */
- BUFHEAD *cpage; /* Current page */
- int cbucket; /* Current bucket */
- int cndx; /* Index of next item on cpage */
- int error; /* Error Number -- for DBM compatability */
- int new_file; /* Indicates if fd is backing store or no */
- int save_file; /* Indicates whether we need to flush file at
- * exit */
- u_long *mapp[NCACHED]; /* Pointers to page maps */
- int nmaps; /* Initial number of bitmaps */
- int nbufs; /* Number of buffers left to allocate */
- BUFHEAD bufhead; /* Header of buffer lru list */
- SEGMENT *dir; /* Hash Bucket directory */
+typedef struct htab { /* Memory resident data structure */
+ HASHHDR hdr; /* Header */
+ int nsegs; /* Number of allocated segments */
+ int exsegs; /* Number of extra allocated
+ * segments */
+ u_int32_t /* Hash function */
+ (*hash)(const void *, size_t);
+ int flags; /* Flag values */
+ int fp; /* File pointer */
+ char *tmp_buf; /* Temporary Buffer for BIG data */
+ char *tmp_key; /* Temporary Buffer for BIG keys */
+ BUFHEAD *cpage; /* Current page */
+ int cbucket; /* Current bucket */
+ int cndx; /* Index of next item on cpage */
+ int error; /* Error Number -- for DBM
+ * compatibility */
+ int new_file; /* Indicates if fd is backing store
+ * or no */
+ int save_file; /* Indicates whether we need to flush
+ * file at
+ * exit */
+ u_int32_t *mapp[NCACHED]; /* Pointers to page maps */
+ int nmaps; /* Initial number of bitmaps */
+ int nbufs; /* Number of buffers left to
+ * allocate */
+ BUFHEAD bufhead; /* Header of buffer lru list */
+ SEGMENT *dir; /* Hash Bucket directory */
+ /* other flags */
+ int nextkey_eof :1; /* dbm_nextkey() reached EOF */
} HTAB;
/*
#define BYTE_SHIFT 3
#define INT_TO_BYTE 2
#define INT_BYTE_SHIFT 5
-#define ALL_SET ((u_int)0xFFFFFFFF)
+#define ALL_SET ((u_int32_t)0xFFFFFFFF)
#define ALL_CLEAR 0
-#define PTROF(X) ((BUFHEAD *)((u_int)(X)&~0x3))
-#define ISMOD(X) ((u_int)(X)&0x1)
-#define DOMOD(X) ((X) = (char *)((u_int)(X)|0x1))
-#define ISDISK(X) ((u_int)(X)&0x2)
-#define DODISK(X) ((X) = (char *)((u_int)(X)|0x2))
+#define PTROF(X) ((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
+#define ISMOD(X) ((u_int32_t)(ptrdiff_t)(X)&0x1)
+#define DOMOD(X) ((X) = (char *)((ptrdiff_t)(X)|0x1))
+#define ISDISK(X) ((u_int32_t)(ptrdiff_t)(X)&0x2)
+#define DODISK(X) ((X) = (char *)((ptrdiff_t)(X)|0x2))
#define BITS_PER_MAP 32
#define SPLITSHIFT 11
#define SPLITMASK 0x7FF
-#define SPLITNUM(N) (((u_int)(N)) >> SPLITSHIFT)
+#define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT)
#define OPAGENUM(N) ((N) & SPLITMASK)
-#define OADDR_OF(S,O) ((u_int)((u_int)(S) << SPLITSHIFT) + (O))
+#define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
#define BUCKET_TO_PAGE(B) \
(B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
* so it starts on this page and continues on the next.
* The format of the page is:
* KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
- *
+ *
* KEY_OFF -- offset of the beginning of the key
* PARTIAL_KEY -- 1
* OVFL_PAGENO - page number of the next overflow page
* OVFL_PAGENO - page number of the next overflow page
* OVFLPAGE -- 0
*
- * FULL_KEY_DATA
+ * FULL_KEY_DATA
* This must be the first key/data pair on the page.
* There are two cases:
*
projects / apple / libc.git / blobdiff