17c478bd9Sstevel@tonic-gate /* 256a424ccSmp * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 37c478bd9Sstevel@tonic-gate * Use is subject to license terms. 47c478bd9Sstevel@tonic-gate */ 57c478bd9Sstevel@tonic-gate 67c478bd9Sstevel@tonic-gate #ifndef _KRB5_DB2_HASH_H 77c478bd9Sstevel@tonic-gate #define _KRB5_DB2_HASH_H 87c478bd9Sstevel@tonic-gate 97c478bd9Sstevel@tonic-gate #ifdef __cplusplus 107c478bd9Sstevel@tonic-gate extern "C" { 117c478bd9Sstevel@tonic-gate #endif 127c478bd9Sstevel@tonic-gate 137c478bd9Sstevel@tonic-gate /*- 147c478bd9Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994 157c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved. 167c478bd9Sstevel@tonic-gate * 177c478bd9Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by 187c478bd9Sstevel@tonic-gate * Margo Seltzer. 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 217c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions 227c478bd9Sstevel@tonic-gate * are met: 237c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 247c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 257c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 267c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 277c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 287c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software 297c478bd9Sstevel@tonic-gate * must display the following acknowledgement: 307c478bd9Sstevel@tonic-gate * This product includes software developed by the University of 317c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors. 327c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors 337c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software 347c478bd9Sstevel@tonic-gate * without specific prior written permission. 357c478bd9Sstevel@tonic-gate * 367c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 377c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 387c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 397c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 407c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 417c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 427c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 437c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 447c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 457c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 467c478bd9Sstevel@tonic-gate * SUCH DAMAGE. 477c478bd9Sstevel@tonic-gate * 487c478bd9Sstevel@tonic-gate * @(#)hash.h 8.4 (Berkeley) 11/2/95 497c478bd9Sstevel@tonic-gate */ 507c478bd9Sstevel@tonic-gate 517c478bd9Sstevel@tonic-gate #include "mpool.h" 527c478bd9Sstevel@tonic-gate #include "db-queue.h" 537c478bd9Sstevel@tonic-gate 547c478bd9Sstevel@tonic-gate /* Operations */ 557c478bd9Sstevel@tonic-gate typedef enum { 567c478bd9Sstevel@tonic-gate HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 577c478bd9Sstevel@tonic-gate } ACTION; 587c478bd9Sstevel@tonic-gate 597c478bd9Sstevel@tonic-gate /* cursor structure */ 607c478bd9Sstevel@tonic-gate typedef struct cursor_t { 617c478bd9Sstevel@tonic-gate TAILQ_ENTRY(cursor_t) queue; 627c478bd9Sstevel@tonic-gate int (*get) __P((const DB *, struct cursor_t *, DBT *, DBT *, \ 637c478bd9Sstevel@tonic-gate u_int32_t)); 647c478bd9Sstevel@tonic-gate int (*delete) __P((const DB *, struct cursor_t *, u_int32_t)); 657c478bd9Sstevel@tonic-gate db_pgno_t bucket; 667c478bd9Sstevel@tonic-gate db_pgno_t pgno; 677c478bd9Sstevel@tonic-gate indx_t ndx; 687c478bd9Sstevel@tonic-gate indx_t pgndx; 697c478bd9Sstevel@tonic-gate u_int16_t *pagep; 707c478bd9Sstevel@tonic-gate void *internal; 717c478bd9Sstevel@tonic-gate } CURSOR; 727c478bd9Sstevel@tonic-gate 737c478bd9Sstevel@tonic-gate 747c478bd9Sstevel@tonic-gate #define IS_BUCKET(X) ((X) & BUF_BUCKET) 757c478bd9Sstevel@tonic-gate #define IS_VALID(X) (!((X) & BUF_INVALID)) 767c478bd9Sstevel@tonic-gate 777c478bd9Sstevel@tonic-gate /* Hash Table Information */ 787c478bd9Sstevel@tonic-gate typedef struct hashhdr { /* Disk resident portion */ 797c478bd9Sstevel@tonic-gate int32_t magic; /* Magic NO for hash tables */ 807c478bd9Sstevel@tonic-gate int32_t version; /* Version ID */ 817c478bd9Sstevel@tonic-gate int32_t lorder; /* Byte Order */ 827c478bd9Sstevel@tonic-gate int32_t bsize; /* Bucket/Page Size */ 837c478bd9Sstevel@tonic-gate int32_t bshift; /* Bucket shift */ 847c478bd9Sstevel@tonic-gate int32_t ovfl_point; /* Where overflow pages are being allocated */ 857c478bd9Sstevel@tonic-gate int32_t last_freed; /* Last overflow page freed */ 867c478bd9Sstevel@tonic-gate int32_t max_bucket; /* ID of Maximum bucket in use */ 877c478bd9Sstevel@tonic-gate int32_t high_mask; /* Mask to modulo into entire table */ 887c478bd9Sstevel@tonic-gate int32_t low_mask; /* Mask to modulo into lower half of table */ 897c478bd9Sstevel@tonic-gate int32_t ffactor; /* Fill factor */ 907c478bd9Sstevel@tonic-gate int32_t nkeys; /* Number of keys in hash table */ 917c478bd9Sstevel@tonic-gate int32_t hdrpages; /* Size of table header */ 927c478bd9Sstevel@tonic-gate int32_t h_charkey; /* value of hash(CHARKEY) */ 937c478bd9Sstevel@tonic-gate #define NCACHED 32 /* number of bit maps and spare points */ 947c478bd9Sstevel@tonic-gate int32_t spares[NCACHED];/* spare pages for overflow */ 957c478bd9Sstevel@tonic-gate u_int16_t bitmaps[NCACHED]; /* address of overflow page bitmaps */ 967c478bd9Sstevel@tonic-gate } HASHHDR; 977c478bd9Sstevel@tonic-gate 987c478bd9Sstevel@tonic-gate typedef struct htab { /* Memory resident data structure */ 997c478bd9Sstevel@tonic-gate TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue; 1007c478bd9Sstevel@tonic-gate HASHHDR hdr; /* Header */ 1017c478bd9Sstevel@tonic-gate u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */ 1027c478bd9Sstevel@tonic-gate int32_t flags; /* Flag values */ 1037c478bd9Sstevel@tonic-gate int32_t fp; /* File pointer */ 10456a424ccSmp const char *fname; /* File path */ 1057c478bd9Sstevel@tonic-gate u_int8_t *bigdata_buf; /* Temporary Buffer for BIG data */ 1067c478bd9Sstevel@tonic-gate u_int8_t *bigkey_buf; /* Temporary Buffer for BIG keys */ 1077c478bd9Sstevel@tonic-gate u_int16_t *split_buf; /* Temporary buffer for splits */ 1087c478bd9Sstevel@tonic-gate CURSOR *seq_cursor; /* Cursor used for hash_seq */ 1097c478bd9Sstevel@tonic-gate int32_t local_errno; /* Error Number -- for DBM compatability */ 1107c478bd9Sstevel@tonic-gate int32_t new_file; /* Indicates if fd is backing store or no */ 1117c478bd9Sstevel@tonic-gate int32_t save_file; /* Indicates whether we need to flush file at 1127c478bd9Sstevel@tonic-gate * exit */ 1137c478bd9Sstevel@tonic-gate u_int32_t *mapp[NCACHED];/* Pointers to page maps */ 1147c478bd9Sstevel@tonic-gate int32_t nmaps; /* Initial number of bitmaps */ 1157c478bd9Sstevel@tonic-gate MPOOL *mp; /* mpool for buffer management */ 1167c478bd9Sstevel@tonic-gate } HTAB; 1177c478bd9Sstevel@tonic-gate 1187c478bd9Sstevel@tonic-gate /* 1197c478bd9Sstevel@tonic-gate * Constants 1207c478bd9Sstevel@tonic-gate */ 1217c478bd9Sstevel@tonic-gate #define MAX_BSIZE 65536 /* 2^16 */ 1227c478bd9Sstevel@tonic-gate #define MIN_BUFFERS 6 1237c478bd9Sstevel@tonic-gate #define MINHDRSIZE 512 1247c478bd9Sstevel@tonic-gate #define DEF_CACHESIZE 65536 1257c478bd9Sstevel@tonic-gate #define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ 1267c478bd9Sstevel@tonic-gate #define DEF_BUCKET_SIZE (1<<DEF_BUCKET_SHIFT) 1277c478bd9Sstevel@tonic-gate #define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 1287c478bd9Sstevel@tonic-gate #define DEF_SEGSIZE (1<<DEF_SEGSIZE_SHIFT) 1297c478bd9Sstevel@tonic-gate #define DEF_DIRSIZE 256 1307c478bd9Sstevel@tonic-gate #define DEF_FFACTOR 65536 1317c478bd9Sstevel@tonic-gate #define MIN_FFACTOR 4 1327c478bd9Sstevel@tonic-gate #define SPLTMAX 8 1337c478bd9Sstevel@tonic-gate #define CHARKEY "%$sniglet^&" 1347c478bd9Sstevel@tonic-gate #define NUMKEY 1038583 1357c478bd9Sstevel@tonic-gate #define BYTE_SHIFT 3 1367c478bd9Sstevel@tonic-gate #define INT32_T_TO_BYTE 2 1377c478bd9Sstevel@tonic-gate #define INT32_T_BYTE_SHIFT 5 1387c478bd9Sstevel@tonic-gate #define ALL_SET ((u_int32_t)0xFFFFFFFF) 1397c478bd9Sstevel@tonic-gate #define ALL_CLEAR 0 1407c478bd9Sstevel@tonic-gate 1417c478bd9Sstevel@tonic-gate #define PTROF(X) ((BUFHEAD *)((ptr_t)(X)&~0x3)) 1427c478bd9Sstevel@tonic-gate #define ISMOD(X) ((ptr_t)(X)&0x1) 1437c478bd9Sstevel@tonic-gate #define DOMOD(X) ((X) = (int8_t *)((ptr_t)(X)|0x1)) 1447c478bd9Sstevel@tonic-gate #define ISDISK(X) ((ptr_t)(X)&0x2) 1457c478bd9Sstevel@tonic-gate #define DODISK(X) ((X) = (int8_t *)((ptr_t)(X)|0x2)) 1467c478bd9Sstevel@tonic-gate 1477c478bd9Sstevel@tonic-gate #define BITS_PER_MAP 32 1487c478bd9Sstevel@tonic-gate 1497c478bd9Sstevel@tonic-gate /* Given the address of the beginning of a big map, clear/set the nth bit */ 1507c478bd9Sstevel@tonic-gate #define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 1517c478bd9Sstevel@tonic-gate #define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 1527c478bd9Sstevel@tonic-gate #define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 1537c478bd9Sstevel@tonic-gate 1547c478bd9Sstevel@tonic-gate /* Overflow management */ 1557c478bd9Sstevel@tonic-gate /* 1567c478bd9Sstevel@tonic-gate * Overflow page numbers are allocated per split point. At each doubling of 1577c478bd9Sstevel@tonic-gate * the table, we can allocate extra pages. So, an overflow page number has 1587c478bd9Sstevel@tonic-gate * the top 5 bits indicate which split point and the lower 11 bits indicate 1597c478bd9Sstevel@tonic-gate * which page at that split point is indicated (pages within split points are 1607c478bd9Sstevel@tonic-gate * numberered starting with 1). 1617c478bd9Sstevel@tonic-gate */ 1627c478bd9Sstevel@tonic-gate 1637c478bd9Sstevel@tonic-gate #define SPLITSHIFT 11 1647c478bd9Sstevel@tonic-gate #define SPLITMASK 0x7FF 1657c478bd9Sstevel@tonic-gate #define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT) 1667c478bd9Sstevel@tonic-gate #define OPAGENUM(N) ((N) & SPLITMASK) 1677c478bd9Sstevel@tonic-gate #define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O)) 1687c478bd9Sstevel@tonic-gate 1697c478bd9Sstevel@tonic-gate #define BUCKET_TO_PAGE(B) \ 1707c478bd9Sstevel@tonic-gate ((B) + hashp->hdr.hdrpages + ((B) \ 1717c478bd9Sstevel@tonic-gate ? hashp->hdr.spares[__log2((B)+1)-1] : 0)) 1727c478bd9Sstevel@tonic-gate #define OADDR_TO_PAGE(B) \ 1737c478bd9Sstevel@tonic-gate (BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B))) 1747c478bd9Sstevel@tonic-gate 1757c478bd9Sstevel@tonic-gate #define POW2(N) (1 << (N)) 1767c478bd9Sstevel@tonic-gate 1777c478bd9Sstevel@tonic-gate #define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize) 1787c478bd9Sstevel@tonic-gate 1797c478bd9Sstevel@tonic-gate /* Shorthands for accessing structure */ 1807c478bd9Sstevel@tonic-gate #define METADATA_PGNO 0 1817c478bd9Sstevel@tonic-gate #define SPLIT_PGNO 0xFFFF 1827c478bd9Sstevel@tonic-gate 1837c478bd9Sstevel@tonic-gate typedef struct item_info { 1847c478bd9Sstevel@tonic-gate db_pgno_t pgno; 1857c478bd9Sstevel@tonic-gate db_pgno_t bucket; 1867c478bd9Sstevel@tonic-gate indx_t ndx; 1877c478bd9Sstevel@tonic-gate indx_t pgndx; 1887c478bd9Sstevel@tonic-gate u_int8_t status; 1897c478bd9Sstevel@tonic-gate int32_t seek_size; 1907c478bd9Sstevel@tonic-gate db_pgno_t seek_found_page; 1917c478bd9Sstevel@tonic-gate indx_t key_off; 1927c478bd9Sstevel@tonic-gate indx_t data_off; 1937c478bd9Sstevel@tonic-gate u_int8_t caused_expand; 1947c478bd9Sstevel@tonic-gate } ITEM_INFO; 1957c478bd9Sstevel@tonic-gate 1967c478bd9Sstevel@tonic-gate 1977c478bd9Sstevel@tonic-gate #define ITEM_ERROR 0 1987c478bd9Sstevel@tonic-gate #define ITEM_OK 1 1997c478bd9Sstevel@tonic-gate #define ITEM_NO_MORE 2 2007c478bd9Sstevel@tonic-gate 2017c478bd9Sstevel@tonic-gate #define ITEM_GET_FIRST 0 2027c478bd9Sstevel@tonic-gate #define ITEM_GET_NEXT 1 2037c478bd9Sstevel@tonic-gate #define ITEM_GET_RESET 2 2047c478bd9Sstevel@tonic-gate #define ITEM_GET_DONE 3 2057c478bd9Sstevel@tonic-gate #define ITEM_GET_N 4 2067c478bd9Sstevel@tonic-gate 2077c478bd9Sstevel@tonic-gate #define UNKNOWN 0xffffffff /* for num_items */ 208*1da57d55SToomas Soome #define NO_EXPAND 0xfffffffe 2097c478bd9Sstevel@tonic-gate 2107c478bd9Sstevel@tonic-gate #ifdef __cplusplus 2117c478bd9Sstevel@tonic-gate } 2127c478bd9Sstevel@tonic-gate #endif 2137c478bd9Sstevel@tonic-gate 2147c478bd9Sstevel@tonic-gate #endif /* !_KRB5_DB2_HASH_H */ 215