Ingres CL HSH

From Ingres Community Wiki

Jump to: navigation, search

Ingres Compatability Library
Architecture - Overview - Suggestions - GL: BA - BT - ERGL - handy - HSH - LC - LL - MEGL - MM - MO - MU - PM - SP - TMGL - CL: CI - CK - CM - CP - CS - CSMT - CV - CX - DI - DL - DS - ER - ERold - EX - FP - GC - GV - handy - ID - JF - LG - LK - LO - ME - MH - NM - OL - PC - PE - QU - SA - SI - SR - ST - TC - TE - TH - TM - TR - UT

Contents

[edit]

Compatibility Library Specification - HSH

[edit]

Abstract

This is the specification of the Hash facility (HSH) provided by the compatibility library for allocating, deallocating, inserting, and searching a hash index.

Revision: 1.0, 2-June-2008

[edit]

Document History

  • Revision 1.0, 3-June-2008
    • Original document
[edit]

Specification

[edit]

Introduction

The hash module provides facilities for allocating, deallocating, inserting, and searching a hash index. HSH uses the Block Allocator BA Facility to allocate the individual items (called entries) in the index. Each hash index is a pointer to a linked-list described by the Linked List LL Facility. The entries are chained in a circular fashion so that no entry has a NULL.

Entries with identical hash values are in the same chain. The number of slots in the index is specified when the index is created (HSH_New). The number should be a prime number larger than twice the number of expected entries. This ensures a quick lookup.

Note that the hsh_entry is defined to be a pointer to a LNKDEF structure (defined in LL.H). It is assumed that the caller has other fields after the LNKDEF, especially the key value. The key must be a single piece of storage. It may consist of multiple fields, e.g., long, float, char. There are binary and string keys.

When a hash index is created, minimum and maximum values can be specified for the number of blocks to allocate. The minimum value ensures that a certain number of blocks are always kept allocated. The maximum value ensures that too many blocks are not allocated. If a block becomes free and more than the minimum are allocated, then that block will be deallocated.

The following executable interfaces are provided.

[edit]
HSH Functions

Click on the function name for detailed information.

Name Description
HSH_New Allocate a Hash Index and initialize the header
HSH_Dispose Free all entries and reset the header
HSH_AllocEntry Allocate an entry
HSH_DeallocEntry Deallocate an entry
HSH_Insert Allocate an entry and add it to the index
HSH_Delete Unchain an entry from the index & free it
HSH_AreEntries True if there are entries
HSH_Find Locate an indexed entry
HSH_GetLock Obtain a Hash index lock
HSH_ReleaseLock Release a Hash index lock
HSH_Link Insert the entry into the index
HSH_Unlink Remove the entry from the index
HSH_Next Locate the next indexed entry
HSH_Select Find and unlink a entry
[edit]

Library

GL

[edit]

Header File <hsh.h>

The header file <hsh.h> must be included before using any of the functions provided. It defines the following.

[edit]
_HSHDEF
struct _HSHDEF
{
	i4	hshSlotNum;		/* Number of Hash Slots (s/b a prime) */
	i4	hshEntryNum;		/* Number of entrys in the index  */
	i4	hshKeyOffset;		/* Offset to the key  */
	i4	hshIndexSize;		/* Size of the index */
	i4	hshFlag;		/* Flag indicators */
	LNKDEF	**hshIndex;		/* Address of Hash Slots */
	BLADEF	hshBlaHdr;		/* Block allocator */
	MU_SEMAPHORE hshSemaphore;	/* Hash semaphore  */
};
[edit]
HSHDEF
typedef struct _HSHDEF HSHDEF;
[edit]
hshFlag values
# define HSH_SHARED	1	/* support multiple simultaneous req */
# define HSH_VARIABLE   2	/* Variable length entrys	     */
# define HSH_STRKEY     4	/* Key is a string     */
# define HSH_USEBLA	8	/* Reserved use the block allocator */
[edit]

Executable Interface

The following functions are provided.

[edit]

HSH_New - Allocate and Initialize a new Hash Block and Index

Allocate a new Hash Index. Note: If max_blocks is 0, then the block allocator is not acive.

Inputs:

num_slots Number of hash index slots (A prime number > 2 * expected number of entries)
key_offset Offset to the key in the entry
entry_size size of an entry (avg. for VL entries)
min_blocks Minumum # of blocks to allocate
max_blocks Maximum # of blocks to allocate
sem_name Name given to the index semaphore
flag Shared / Variable (see BA.H)

Outputs:

none

Returns:

the hash index header

Side Effects:

Allocates enough pages of memory for the hash index
Initializes the Block Allocator (BA) for the index
Initializes the semaphore for the index

Definition: 

HSHDEF *HSH_New(	 	/* Allocate a Hash index & init the hdr	*/
	i4 	num_slots, 	/* number of slots in the index 	*/
	i4 	key_offset,	/* offset to the key 			*/
	i4	entry_size,	/* size of entry (avg. for VL entries)	*/
	i4	min_blocks,	/* minumum # of blocks to allocate	*/
	i4	max_blocks,	/* maximum # of blocks to allocate	*/
	char 	*sem_name, 	/* name given to the Index Semaphore	*/
	i4	flag	   	/* Flags: Shared / Variable 		*/
);
[edit]

HSH_Dispose - Dispose of a Hash Index

Dispose of a hash index created from HSH_New and release all associated memory.

Inputs:

hsh_blk the address of the hash block

Outputs:

none

Returns:

void

Side Effects:

Removes the hash index block semaphore
Frees all BA entries and associated memory

Definition: 

void HSH_Dispose(		/* Free all entries and reset the hdr */
	HSHDEF	*hsh_blk	/* Hash Index header  */
);
[edit]

HSH_AllocEntry - Allocate a new hash entry

Allocate a piece of storage to hold the new entry

Inputs:

hsh_blk the address of the hash block
hsh_key address of key. If NULL, the key information is ignored.
hsh_keylen length of key
hsh_entrylen the length of the entry to create

Outputs:

none

Returns:

The address of the hash entry

Definition: 

LNKDEF *HSH_AllocEntry(    		/* Allocate an entry */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	char	*hsh_key,		/* Hash Key	*/
	i4	hsh_keylen,		/* Hash Key Length */
	i4	hsh_entrylen		/* Hash Entry Length */
);
[edit]

HSH_DeallocEntry - Deallocate a hash entry

Release the piece of storage that holds the entry

Inputs:

hsh_blk address of the hash block
hsh_entry the entry to free

Outputs:

none

Returns:

void

Definition: 

void HSH_DeallocEntry(    		/* Deallocate an entry */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	LNKDEF	*hsh_entry		/* Entry to free */
);
[edit]

HSH_Insert - Allocate an entry and add it to the index

Allocate a piece of storage to hold the new entry. Get the hash index for this key. Insert the entry at the head of the proper chain.

Inputs:

hsh_blk address of the hash block
hsh_key address of key
hsh_keylen length of key
hsh_entrylen the length of the entry to create

Outputs:

none

Returns:

The address of the hash entry

Definition: 

LNKDEF *HSH_Insert(	 	/* Allocate an entry and add it to the index */
	HSHDEF	*hsh_blk,	/* Hash Index header	     */
	char	*hsh_key,	/* Hash Key	*/
	i4	hsh_keylen,	/* Hash Key Length */
	i4	hsh_entrylen	/* Hash Entry Length */
);
[edit]

HSH_Delete - Remove an entry from the hash index and free it

Locate the entry in the hash index. Unchain the entry and release its storage.

Inputs:

hsh_blk the address of the hash block
hsh_key address of key
hsh_keylen length of key
hsh_entry the entry to remove

Outputs:

none

Returns:

void

Side Effects:

Decrements the entry count
Holds the hash block semaphore during unchaining, then releases it
If this is the last entry, clears the hash index

Definition: 

void HSH_Delete(		/* Unchain an entry from the index & free it */
	HSHDEF	*hsh_blk,	/* Hash Index header */
	char	*hsh_key,	/* Hash Key	*/
	i4	hsh_keylen,	/* Hash Key Length */
	LNKDEF	*hsh_entry	/* Entry to remove */
);
[edit]

HSH_AreEntries - Are there any Entries?

Returns TRUE if there are entries in the hash block.

Inputs:

hsh_blk address of the hash block

Outputs:

none

Returns:

TRUE if there are entries in the hash block
FALSE otherwise

Definition: 

bool HSH_AreEntries(			/* True if there are entries */
	HSHDEF	*hsh_blk		/* Hash Index header  */
);
[edit]

HSH_Find - Locate a Key name via the Hash index

Get the hash index for this key. Search the chain for the matching name. Return the entry if found, NULL otherwise.

Inputs:

hsh_blk address of the hash block
hsh_key address of key
hsh_keylen length of key

Outputs:

none

Returns:

The address of the hash entry

Definition: 

LNKDEF *HSH_Find(	 		/* Locate an indexed entry */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	char	*hsh_key,		/* Hash Key	*/
	i4	hsh_keylen		/* Hash Key Length */
);
[edit]

HSH_GetLock - Obtain the Hash Index Lock

Get a lock with the hash index semaphore.

Inputs:

hsh_blk address of the hash block

Outputs:

none

Returns:

void

Definition: 

void HSH_GetLock(			/* Obtain a Hash index lock */
	HSHDEF	*hsh_blk		/* Hash Index header  */
);
[edit]

HSH_ReleaseLock - Release the Hash Index Lock

Release the lock with the hash index semaphore.

Inputs:

hsh_blk address of the hash block

Outputs:

none

Returns:

void

Definition: 

void HSH_ReleaseLock(			/* Release a Hash index lock */
	HSHDEF	*hsh_blk		/* Hash Index header  */
);
[edit]

HSH_Link - Insert an existing entry into a hash index

Hash to the correct index list and link to the head of the list.

Inputs:

hsh_blk the address of the hash block
hsh_key address of key
hsh_keylen length of key
hsh_entry the entry to remove

Outputs:

none

Returns:

void

Side Effects:

Holds the hash block semaphore during updating, then releases it
Increments the entry count

Definition: 

void HSH_Link(		 		/* Insert the entry into the index */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	char	*hsh_key,		/* Hash Key	*/
	i4	hsh_keylen,		/* Hash Key Length */
	LNKDEF	*hsh_entry		/* Entry to link into the index */
);
[edit]

HSH_Unlink - Remove an entry from a hash index

Hash to the correct index list. Find the entry in the list and unlink the entry.

Inputs:

hsh_blk the address of the hash block
hsh_key address of key
hsh_keylen length of key
hsh_entry the entry to remove

Outputs:

none

Returns:

void

Side Effects:

Holds the hash block semaphore during updating, then releases it
Decrements the entry count
If this is the last entry, clears the hash index

Definition: 

void HSH_Unlink(			/* Remove the entry from the index */
	HSHDEF	*hsh_blk,		/* Hash Index header	     */
	char	*hsh_key,		/* Hash Key	*/
	i4    	hsh_keylen,		/* Hash Key Length */
	LNKDEF	*hsh_entry		/* Entry to link into the index */
);
[edit]

HSH_Next - Return the next entry from a hash index

It is assumed that the caller has a shared lock on the hash index. If the entry is NULL, start at the first list; else start at the next entry. If there are no more entries in this list advance to the next list. If there are no more lists, return NULL; else return this entry and the next entry.

Inputs:

hsh_blk the address of the hash block
list the address of the current index slot (initially the address of the hash index)
entry the address of the current entry (initially NULL)
nentry the address of the next entry (used to start the next scan)

Outputs:

list the address of the current index slot
entry the address of the current entry (NULL when there are no more entries)

Returns:

void

Definition: 

void HSH_Next(				/* Locate the next indexed entry */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	LNKDEF	***list, 		/* Current index entry	*/
	LNKDEF	**entry,		/* Current Hash entry	*/
	LNKDEF	**nentry		/* Next Hash Entry	*/
);
[edit]

HSH_Select - Locate an entry via the Hash index and unlink it

Get the hash index for this key. Search the chain for the matching entry. If found, remove it from the chain. Return the entry if found, NULL otherwise.

Inputs:

hsh_blk the address of the hash block
hsh_key address of key
hsh_keylen length of key

Outputs:

none

Returns:

The address of the entry if found; NULL otherwise

Side Effects:

Holds the hash block semaphore during updating, then releases it
Decrements the entry count
If this is the last entry, clears the hash index

Definition: 

LNKDEF *HSH_Select(			/* Find and unlink a entry */
	HSHDEF	*hsh_blk,		/* Hash Index header  */
	char	*hsh_key,		/* Hash Key	*/
	i4    	hsh_keylen		/* Hash Key Length */
);

Ingres Compatability Library
Architecture - Overview - Suggestions - GL: BA - BT - ERGL - handy - HSH - LC - LL - MEGL - MM - MO - MU - PM - SP - TMGL - CL: CI - CK - CM - CP - CS - CSMT - CV - CX - DI - DL - DS - ER - ERold - EX - FP - GC - GV - handy - ID - JF - LG - LK - LO - ME - MH - NM - OL - PC - PE - QU - SA - SI - SR - ST - TC - TE - TH - TM - TR - UT

Retrieved from "http://community.ingres.com/wiki/Ingres_CL_HSH"
Personal tools
Developing With