hash.h revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright (c) 1999, 2001 by Sun Microsystems, Inc.
* All rights reserved.
*/
#ifndef _HASH_H
#define _HASH_H
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* hash.h: Hash Table structures, defines, and prototypes.
*
* The locking strategy behind hash.c is actually quite simple,
* but does need some explaining. Basically, we have three different
* locks to worry about; one at the hash table level, one at the
* bucket level and one at the node level.
*
* +===================+
* | Hash | Hash | +---------+ +---------+
* | Table | Bucket |<--->|HashEntry|<--->|HashEntry|
* | | | +---------+ +---------+
* | * | * | / \ / \
* | | | | |
* | | | \ / \ /
* | | | +---------+ +---------+
* | | | | * Node | | * Node |
* +===================+ +---------+ +---------+
*
* * = Lock is present
*
* When we walk through the Hash Table to add an item, it first
* gets the hash bucket index, and locks the whole row (or bucket)
* with a write lock. a HashEntry is then added at the head of the
* bucket queue. If a node lock was requested, via a function
* parameter, the node is locked. This is particularly useful if
* additional work will be done to the node. The Hash Table lock
* is then locked with a write lock, and the table counter is
* incremented, then the lock is unlocked. Lastly, the hash
* bucket is unlocked, and the function returns.
*
* When the code needs to find a node in the hash table, the
* hash bucket (row) is locked, and all nodes in the row are
* compare with the key provided. The caller may also provide
* a pointer to a helper routine, which is used to further
* qualify searches. If a match is found, the node is locked
* (if requested), and the pointer to the node is retruned to
* the caller.
*
* If a node is to be deleted from the table, the row is write
* locked, the row is searched for a match, based on the key and
* the data to the pointer. If a match is found, the HashEntry
* is deleted. The table lock is then write locked, decremented
* and unlocked. Finally, the bucket lock is released.
*
*/
#ifdef __cplusplus
extern "C" {
#endif
enum {
};
typedef struct hash_entry {
struct hash_entry *next;
enum {
} hashKeyType;
void *data;
unsigned char keyLen; /* keyLen can't be more than 255 chars now */
unsigned char *keyData;
} HashEntry;
#define HASH_TBL_SIZE 256
/*
* If uniqueData is set to non-zero, then the bucket will be searched for
* for uniqueness.
*/
typedef struct hash_table {
int uniqueData;
} HashTable;
#define HASH_BIT_COUNT 8
#ifdef _BIG_ENDIAN
& ~(~0 << HASH_BIT_COUNT))
#else
#endif
void *, int);
uint32_t, int);
uint32_t, int);
uint32_t);
extern void *enumerateAllHashTableEntries(HashTable *,
uint32_t *,
uint32_t *,
int);
extern void initEnumeratorState(void *, size_t);
#ifdef __cplusplus
}
#endif
#endif /* _HASH_H */