.Title	HTM - Hashed Table Management
	.Ident  /V01.01/
;+
; Hashed table management presents set of routines to store and retrieve
; variable length blocks of data accessed on random basis by a key value.
; Data access is optimized by simple hashing table, both data and table
; are stored within single memmory array.
; Current version does not allow for block deletion - once allocated, the
; block remains in memmory.
; Only Longword key set of routines is provided now, however, update for
; fixed length character string key is straightforward. TH.KSIZ field is
; allready provided for future compatibility.
;
; HTM_L_xxx handles access based on LONGWORD key
; HTM_C_xxx handles access based on fixed length character string key
;  	
;+
; Table header offset definitons
;-
$DEFINI	TH,LOCAL
$DEF 	TH.BASE	.BLKL	1	; Memmory base address (stored for control only)
$DEF 	TH.SIZE	.BLKL	1	; Memmory array size (overall)
$DEF	TH.KSIZ .BLKL	1	; Key overall size  (for compatibility)
$DEF 	TH.HSIZ	.BLKL	1	; Hashing field size (also hash table size fact)
$DEF 	TH.HPOS	.BLKL	1	; Hashing field position within the key
$DEF 	TH.HASH	.BLKL	1	; Hash table starting address
$DEF	TH.ENDH	.BLKL	1	; Hash table end adress (last pointer)
$DEF 	TH.FREE	.BLKL	1	; Address of the first free block
$DEF 	TH.ENDM	.BLKL	1	; Address of the end of memmory table array
$DEF 	TH.EHDR			; End of the table header
$DEFEND TH,LOCAL,DEF
;+
; Table block offsets definitions
; Note, TB.PNTR,TB.SIZE,TB.KEY are internal fields, not returned to the user
; For memmory savings, header is limited to one longword and que instructions
; can not be used.
;-
$DEFINI TB,LOCAL
$DEF	TB.PNTR	.BLKL	1	; Pointer to the next sequential block
$DEF	TB.SIZE	.BLKW	1	; Block size in bytes (stored as word only)
$DEF	TB.KEY	.BLKL	1	; Block key 
$DEF	TB.USER			; Start of the user block area
$DEFEND TB,LOCAL,DEF
;
;+
; HTM_L_INIT (Array,Size,Hsiz,Hpos)
;
; Initialization routine for Hashed Table Management. Must be called before
; any data storage/retrieval. This routine assumes LONGWORD key, but it
; does not check for proper values Hsize, Hpos.
; Note, that hashing field size determines the size of the hash table, thus
; field size 6 will require 2**6 longwords for hash table (64*4 bytes)
;
;-
;
  	.ENTRY	HTM_L_INIT,^M<R10,R11>		; Initalize the table 
;	
I.Array	= 4	; (Ref,byte,w) Table memmory array 
I.Size	= 8	; (Ref,long,r) Array size bytes
I.Hsiz  = 12	; (Ref,byte,r) Hashing field size (in bits)
I.Hpos	= 16	; (Ref,byte,r) Hashing field position in the key (bit offset)
;
  	MOVL	#SS$_INSFARG,R0			; Assume wrong call
  	CMPB	#4,(AP)				; Check number of params
  	BNEQ	300$				; Ne - wrong call
;
  	MOVL	I.Array(AP),R11			; Set up table base register
  	MOVL	R11,TH.BASE(r11)		; and save it for verification
  	MOVL	@I.SIZE(AP),TH.SIZE(r11)	; Get array size
	MOVL	#4,TH.KSIZ(r11)			; Set-up key length
  	MOVZBL	@I.HSIZ(AP),TH.HSIZ(r11)	; Hash field size (no checks)
  	MOVZBL	@I.HPOS(AP),TH.HPOS(r11)	; Hash field position (no check)
  	ADDL3	#TH.EHDR,R11,TH.HASH(r11)	; Hash table start
  	EXTZV	#0,TH.HSIZ(r11),#^XFFFFFFFF,R10 ; Extract full mask, add one
  	INCL	R10				; to compute Hash table size
  	ASHL	#2,R10,R10			; in longwords
  	ADDL3	R10,TH.HASH(R11),TH.FREE(r11)	; Free area starts past hash 
	SUBL3	#4,TH.FREE(r11),TH.ENDH(r11)	; End of hash table
  	ADDL3	TH.SIZE(r11),r11,TH.ENDM(r11)	; End of table array addr
	MOVL	#SS$_INSFMEM,R0			; Assume not enough memmory
	CMPL	TH.ENDM(R11),TH.ENDH(R11)	; Enough memmory for hash table 
	BLEQU	300$				; LEQU = no, exit	
	MOVL	TH.HASH(R11),R0			; Get hash table base
200$:  	CLRL	(r0)+				; Init pointer to zero
  	CMPL	TH.FREE(R11),r0			; End of hash table ?
  	BGTRU	200$				; GTRU - no, loop
  	MOVL	#SS$_NORMAL,R0			; Mark success
300$:	RET					; 
;
;+
;  HTM_L_FIND (Array, Key, Blkreq, Blkadr, Blksiz)
;
;  Find the block by the longword KEY value. 
;  If not found, either allocate the new one using Blkreq length (bytes)
;  or return SS$_NOENTRY if zero length rquested.
;  In case of the full table, return SS$_INSFMEM.
;-
  	.ENTRY	HTM_L_FIND,^M<r7,r8,r9,r10,r11>
;
F.Array	= 4	; (Ref,byte,w) Table array 
F.Key	= 8	; (Ref,long,r) Requested block key (longword key only now)
F.Blkreq= 12	; (Ref,long,r) Requested block size if not found in table 
  		;              or zero to suppress block allocation (bytes)
F.Blkoff= 16	; (Ref,byte,w) Found block byte offset from the array base
F.Blksiz= 20	; (Ref,long,w) Found block size (bytes)
;
  	MOVL	#SS$_INSFARG,R0			; Assume wrong call
  	CMPB	#5,(AP)				; Check number of params
  	BNEQ	250$				; Ne = invalid call
;
  	MOVL	F.Array(ap),R11			; Set-up table base
  	MOVL	#SS$_IVADDR,r0			; Assume wrong table supplied
  	CMPL	TH.BASE(r11),R11		; Check table base
  	BNEQU	250$				; Ne = invalid address supplied
;
;	Extract hashing mask from the key, and pick-up starting pointer
;	from hashing table
;
  	EXTZV	TH.HPOS(r11),TH.HSIZ(r11),@F.Key(ap),R10 ; Extract hash index
  	ASHL	#2,R10,R10			; Change to longword index
  	ADDL2	TH.HASH(r11),R10		; (INDEX instr.might be longer)
100$:	MOVL	R10,R9				; Copy current pointer
  	MOVL	(r10),R10			; Get next block base (if any)
  	BEQL	300$				; Eq = block not allocated
;
  	CMPL	@F.Key(AP),TB.KEY(R10)		; Compare keys
  	BGTRU	100$				; Table key is higher, try next
  	BLSSU	300$				; Lower = not present yet
;
;	We found block with the key that matches our
;
200$:	MOVAB	TB.USER(R10),@F.Blkoff(AP)	; Return block address
	SUBL	R11,@F.Blkoff(AP)		; subtract base to get offset
  	MOVZWL	TB.SIZE(r10),@F.Blksiz(AP)	; Return block size
  	MOVL	#SS$_NORMAL,R0			; Return success
250$:  	RET
;
;	We have to allocate the new block
;
300$:	CLRL	@F.Blksiz(AP)			; Assume block not allocated
  	MOVL	#SS$_NOENTRY,R0			; Set-up no entry found
  	TSTL	@F.Blkreq(AP)			; Allocation requested ?
  	BEQL	250$				; EQ = no, return warning
	MOVL	#SS$_INSFMEM,R0			; Assume not enough memmory
  	MOVL	TH.FREE(R11),R8			; Use next free block
	ADDL3	#TB.USER,r8,r7			; Add user transparent size
  	ADDL2	@F.Blkreq(AP),R7		; Compute next free addr
  	CMPL	R7,TH.ENDM(R11)			; Are we past end of table ?
  	BGTRU	250$				; GT = yes, fatal exit, no mem.
  	MOVL	R7,TH.FREE(R11)			; Update next free block
  	MOVL	R10,(R8)			; Set up pointer to next block
  	MOVL	R8,(R9)				; Update previous pointer to us
  	MOVL	R8,R10				; Use allocated block as current
  	MOVW	@F.Blkreq(AP),TB.SIZE(R10)	; Save block size
	MOVL	@F.Key(AP),   TB.KEY (R10)	; Save the key
  	BRB	200$				; Use common return
;
;+
;  HTM_L_SEQR (Array, Hcontext, Bcontext, Key, Blkoff, Blksiz)
;
;  Retun data blocks sequentially, sorted by hash field and index ascending.
;  Values Hcont,Bcont are used to save context between calls.
;  For initial call, Hcontext should be set to zero, NEVER modify this values
;  between calls.
;  At the end of table SS$_NOENTRY status is returned
;
;-
  	.ENTRY	HTM_L_SEQR,^M<r9,r10,r11>
;
S.Array	= 4	; (Ref,byte,w) Table array 
S.Hcntx	= 8	; (Ref,long,w) Hash context. On first call should be zero
S.Bcntx = 12	; (Ref,long,w) Block context.
S.Key	= 16	; (Ref,long,r) Returned block key (longword key only now)
S.Blkoff= 20	; (Ref,byte,w) Returned block byte offset from the array base
S.Blksiz= 24	; (Ref,long,w) Returned block size (bytes)
;
  	MOVL	#SS$_INSFARG,R0			; Assume wrong call
  	CMPB	#6,(AP)				; Check number of params
  	BNEQ	50$				; Ne = invalid call
;
  	MOVL	S.Array(ap),R11			; Set-up table base
  	MOVL	#SS$_IVADDR,r0			; Assume wrong table supplied
  	CMPL	TH.BASE(r11),R11		; Check table base
  	BNEQU	50$				; Ne = invalid address supplied
;
;	Check for initial call marked by zero Hcntx. Validitate Hcntx value
;
	MOVL	@S.Bcntx(AP),R10		; Pick up block context
	MOVL	@S.Hcntx(AP),R9			; Pick up hash context
	BEQL	80$				; Eq = initial call
	CMPL	TH.HASH(R11),R9			; Check if in Hash table
	BGTRU	50$				; Gtru = no, error
	CMPL	TH.ENDH(R11),R9			; Check if in Hash table
	BGEQU	100$				; Gequ = O.K., valid context
50$:	MOVL	#SS$_IVADDR,r0			; Return invalid address
	RET
80$:	MOVL	TH.HASH(R11),R9			; Set up starting hash	
	BRB	120$				;
100$:	MOVL	(R10),R10			; Point to next block
	BNEQ	200$				; Valid next block, use it
;
;  If there are no entries in current hash slot, advance to the next one.
;
110$:	MOVL	#SS$_NOENTRY,R0			; Assume end of tables
	ADDL2	#4,R9				; Advance in hash table
	CMPL	TH.ENDH(r11),R9			; End of hash table ?
	BGEQU	120$				; GEQU = not yet
	RET					; return end of data
120$:	MOVL	(R9),R10			; Set pointer to first block
	BEQL	110$				; No block, try next hash
;
;  Return current block and set-up contexts
;
200$:	CMPL	TH.ENDH(R11),R10		; Check if in our table
	BGEQU	50$				; Gequ = no, error
	CMPL	TH.ENDM(R11),R10		; Check upper bound
	BLSSU	50$				; Lssu = no, error
	MOVL	R9 ,@S.Hcntx(AP)		; Save hash context
	MOVL	R10,@S.Bcntx(AP)		; Save block context
	MOVL	TB.KEY (r10),@S.Key(AP)		; Return key
	MOVAB	TB.USER(R10),@S.Blkoff(AP)	; Return block address
	SUBL	R11,@S.Blkoff(AP)		; subtract base to get offset
  	MOVZWL	TB.SIZE(r10),@S.Blksiz(AP)	; Return block size
  	MOVL	#SS$_NORMAL,R0			; Return success
	RET
;
  	.END