COMMENT @%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	Copyright (c) Geoworks 1994 -- All Rights Reserved

PROJECT:	Legos
MODULE:		Hash library
FILE:		hash.def

AUTHOR:		Paul L. DuBois, Nov  4, 1994

MACROS:
	Name			Description
	----			-----------

REVISION HISTORY:
	Name	Date		Description
	----	----		-----------
	dubois	11/ 4/94	Initial revision


DESCRIPTION:
	Interface to hash table library
		
	$Id: hash.def,v 1.1 97/05/30 08:18:19 newdeal Exp $

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@
SetDef __HASH
StartLibrary	hash

;%%%% Exported hash table routines

global	HashTableCreate:far
; Description:	Create a new hash table
; Pass:		ds	- locked LMem block
;		al	- ObjChunkFlags to pass to LMemAlloc
;		bx	- HashTableFlags
;		cx	- size to reserver for header (0 is default)
;		dx	- initial # of list heads
;		stack	- vfptr to comparison function (pushed first)
;			  vfptr to hash function
;
; Return:	args not popped off stack
;		carry set if couldn't allocate space and LMF_RETURN_ERRORS
;		carry clear if array allocated:
;			*ds:ax	- table (block possibly moved)
; Destroyed:	nothing
; 
;   Hash function -
;   	Description:	Convert data to 16 pseudo-random bits
;	Pass:		cxdx	- data
;   			ds:di	- pointer to HashTableHeader
;	Return:		ax	- 16 bits of hash
;   	Can destroy:	bx, cx, dx
;   	Notes:		Do NOT do anything that would cause hash table's
;   			LMem heap to be shuffled!
;
;   Comparison function -
;   	Description:	Comparison callback routine for hash library
;   	Pass:		cxdx	- as passed to HashTableLookup
;   			axbx	- from element, as passed (as cxdx) to
;   				  HashTableAdd
;   			ds:di	- pointer to HashTableHeader
;   	Return:		carry	- set if not equal
;   	Can Destroy:	ax, bx, cx, dx
;   	Notes:		Do NOT do anything that would cause hash table's
;   			LMem heap to be shuffled!

global	HashTableAdd:far
; Description:	Add an entry to a table
; Pass:		*ds:si	- Hash table
;   		cxdx	- data (or cl, or cx, or cxdl)
; Return:	*ds:si	- Hash table (block possibly moved)
;   		carry	- set on error
; Destroyed:	WARNING: this routine MAY resize the LMem block etc.

global	HashTableLookup:far
; Description:	Look up an entry in the hash table
; Pass:		*ds:si	- Hash table
;   		ax	- hash value of item you're looking up
;   		cxdx	- passed to callback routine
; Return:	carry	- set if not found
;   		cxdx	- data from the table entry (if found)
; Destroyed:	nothing

global	HashTableRemove:far
; Description:	Remove up an entry in the hash table
; Pass:		*ds:si	- Hash table
;   		ax	- hash value of item you're looking up
;   		cxdx	- passed to callback routine
; Return:	carry	- set if not found
;   		cxdx	- data from the table entry (if found)
; Destroyed:	nothing

global	HashTableEnum:far
; Description:	Enumerate through all elements in hash table
; Pass:		*ds:si	- Hash table
;   		cxdx	- passed to callback routine
; Return:	carry	- set if not found
;   		cxdx	- data from the table entry (if found)

global	ECCheckHashTable:far
; Description:	Do some validity checking on a hash table
; Pass:		*ds:si	- hash table
; Return:	nothing
; Destroyed:	nothing

global	HashTableHash:far
; Description:	Hash a string
; Pass:		ds:si	- ASCIIZ string
; Return:	ax	- hash value
; Destroyed:	nothing

global	HashTableResize:far
; Description:	Expand and rehash a hash table
; Pass:		*ds:si	- hash table
;   		cx	- new # of hash buckets
; Return:	carry	- set on error
; Destroyed:	nothing

;%%%% Exported miniheap routines

global	MiniHeapCreate:far
; Description:	Allocate a new "mini-heap"
; Pass:		ds	- locked LMem block
;		al	- ObjChunkFlags to pass to LMemAlloc
;		cl	- size of entry (should be at least 2)
;
; Return:	carry	- set if couldn't allocate and LMF_RETURN_ERRORS
;		ax	- chunkhandle if carry clear, else garbage
; Destroyed:	nothing

global	MHAlloc:far
; Description:	Return a new chunklet from the free list
; Pass:		*ds:si	- MiniHeap chunk
; Return:	*ds:si	- same chunk (block possibly moved)
;	carry set:
;		bx	- offset within chunk of new chunklet
;	carry clear:
;		bx	- MH_NULL_ELEMENT -- allocation failed
;
; Destroyed:	nothing

global	MHFree:far
; Description:	Add a chunklet to the free list
; Pass:		*ds:si	- MiniHeap chunk
;		bx	- offset to chunklet
; Return:	nothing
; Destroyed:	nothing

global	MHMarkFree:far
; Description:	Mark free entries by nuking their next fields
; Pass:		*ds:si	- MiniHeap chunk
; Return:	nothing
; Destroyed:	nothing
;
; The MHE_next fields of free chunks will be set to MH_FREE_ELEMENT
; To reverse this, call MHRestoreFree.

global	MHRestoreFree:far
; Description:	Restore freelist after calling MHMarkFree
; Pass:		*ds:si	- MiniHeap chunk
; Return:	nothing
; Destroyed:	nothing

global	ECCheckMiniHeap:far
; Description:	Perform general sanity checking
; Pass:		ds:si	- mini heap
; Return:	nothing
; Destroyed:	nothing

global	ECCheckUsedChunklet:far
; Description:	Check the offset of a Mini heap entry.  Assert that it is
;		used (only with USE_EC_HEAP_TAGS)
; Pass:		ds:si	- mini heap
;		ds:si+bx - alleged (used) mini heap entry
; Return:	nothing
; Destroyed:	nothing

global	ECCheckChunklet:far
; Description:	Check the offset of a Mini heap entry.
; Pass:		ds:si	- mini heap
;		ds:si+bx - alleged (used) mini heap entry
; Return:	nothing
; Destroyed:	nothing

;%%%% Hash Structures and such

HashTableFlags	record
    :10
    HTF_POINTER_SEMANTICS:1	; pointers to data buffers are passed
    				; instead of the data itself.  Must be
    				; set for entry size > 4 (may go away)
    HTF_C_API_CALLBACKS:1	; callbacks are _pascal routines
    HTF_NO_REPEAT_INSERT:1	; turn on a little optimization
    HTF_ENTRY_SIZE:3		; number of bytes of data to store
				; with each entry
HashTableFlags	end

; size of this header should be kept even
HashTableHeader	struct
    HTH_flags		HashTableFlags
    HTH_tableSize	word		; # of list heads
    HTH_hashFunction	vfptr		; hashing function
    HTH_compFunction	vfptr		; comparison function
    HTH_heap		lptr		; chunk containing "heap" of entries
    HTH_headerSize	word
    even
HashTableHeader	ends

HashTableEntry	struct
    HTE_link		word		; link to next entry in chain
    HTE_keyBits		byte		; little bit of hash key
    HTE_data		label byte
HashTableEntry	ends

;%%%% Mini Heap Structures and such

; Reserve some constants to stick in MHE_next field.  Since a chunk
; can never get close to being 0xfff0 bytes long, this is safe.

; Used mainly for an end-of-list marker
MH_NULL_ELEMENT		equ	0xffff
; Used between calls to MHMarkFree and MHRestoreFree
MH_FREE_ELEMENT		equ	0xfffe

MiniHeapHeader	struct
    MHH_freeHead	word		; offset of free list head
    MHH_count		word		; # of used entries
    MHH_size		word		; # of entries
    MHH_entrySize	word		; for convenience
    even
    MHH_data	label	word
MiniHeapHeader	ends

; This structure used internally for free elements
MiniHeapEntry	struct
    MHE_next	word			; index of next element
    MHE_data	label	byte
MiniHeapEntry	ends

EndLibrary	hash
