;license:MIT ;(c) 2018-2021 by 4am & qkumba ; ; Ordered key/value store (6502 compatible)(256+ records compatible) ; ; Public functions ; - okvs_len(address) get number of keys ; - okvs_update(address, key, value) update key/value pair ; - okvs_get(address, key) get value by key lookup ; - okvs_find(address, key) get key by key lookup ; - okvs_nth(address, n) get key by numeric index ; - okvs_next(address, n) get next key by numeric index ; - okvs_iter(address, callback) iterate through keys ; - okvs_iter_values(address, callback) iterate through values ; ; Call init() once. Call it again to reset the store to 0 records. ; ; Records are maintained in a singly linked list, so most functions are O(n). ; len() is always O(1). okvs_nth() can be O(1) if some other code produces ; a key lookup table and stores its address in the 'free space pointer ; after last record' field in the header. ; ; Record count is stored as a word, so a store can hold 65535 records. ; ; Keys and values are length-prefixed strings (Pascal style), so max length ; of any single key or value is 255 bytes. Record length is stored as a byte ; that includes itself, so the maximum data length of a record is 254 bytes. ; ; Keys are case-sensitive. Lookups are an exact byte-for-byte comparison. ; ; All functions take the starting address of the store's data buffer in ; memory, so there can be multiple independent stores at one time. Only the ; size of a record is stored, so stores are easily relocatable. There is no ; overflow protection because this is assembly. ; ; There is an append() function but it has been separated out of this version ; because it is only used once during program startup, so it does not need ; to persist in LC RAM. ; ; There is no sort() function. ; ; There is no delete() function. ; ; Keys can be duplicated, but get() and find() will always return the first ; match. ; ; Records can technically have more fields than key and value, but callers ; are on their own for navigating inside the record. If you have a pointer ; to one length-prefixed field (including key or value), okvs_next_field() ; will find the start of the next field. ; ; Structures: ; ; Store ; +0 number of records (word) ; +2 free space pointer after last record (word) or $0000 ; +4 Record ; ...Record... ; ...Record... ; ; Record ; +0 record length (including this field) ; +1 key length ; +2 key ; +K+2 value length (actual length, not max length) ; +K+3 value ; ... filler bytes up to value max length (set at append() time) ;------------------------------------------------------------------------------ ; okvs_len ; okvs_len_imm ; ; in: A/Y = handle to storage space ; out: $WCOUNT contains number of keys in this store ; X preserved ; A, Y clobbered ; Z set if no keys ; $00/$01 clobbered ; $02/$03 clobbered ;------------------------------------------------------------------------------ okvs_len jsr GetStoreAddressFromAY ; PTR -> store ; Y = 0 okvs_len_imm lda (PTR), y ; get number of keys in store (word) sta WCOUNT iny lda (PTR), y sta WCOUNT+1 ora WCOUNT rts ;------------------------------------------------------------------------------ ; okvs_find / okvs_get ; ; in: stack contains 4 bytes of parameters: ; +1 [word] handle to storage space ; +3 [word] address of key ; out: if C clear, record was found ; A/Y = lo/hi address of key (okvs_find) or value (okvs_get) ; $WINDEX = index of found record (word) ; if C set, keyrecord was not found and X/Y are clobbered, A=0 ; all other flags clobbered ; $00/$01 clobbered ; $02/$03 clobbered ; $04/$05 clobbered ;------------------------------------------------------------------------------ okvs_find lda #$60 +HIDE_NEXT_2_BYTES okvs_get lda #$EA sta @maybeGetValue +PARAMS_ON_STACK 4 jsr GetStoreAddress ; PTR -> store ; Y = 0 jsr okvs_len_imm beq @fail ; no keys, fail immediately jsr incptr4 ; PTR -> first record +LDPARAMPTR 3, SRC ; SRC -> key we want to find ldy #0 sty WINDEX sty WINDEX+1 lda (SRC),y tay iny sty KEYLEN @matchRecordLoop +LD16 PTR tax inx bne + iny + stx DEST ; DEST -> key of this record sty DEST+1 ldy #0 @matchKeyLoop lda (SRC),y cmp (DEST),y bne @next iny KEYLEN = *+1 cpy #$D1 ; SMC bne @matchKeyLoop +LD16 DEST clc @maybeGetValue brk ; SMC jsr okvs_next_field +LD16 PTR clc rts @next jsr stepptr ; PTR -> next record inc WINDEX bne + inc WINDEX+1 + lda WINDEX cmp WCOUNT bne @matchRecordLoop lda WINDEX+1 eor WCOUNT+1 bne @matchRecordLoop @fail sec rts ;------------------------------------------------------------------------------ ; okvs_next ; get (N+1)th key, with wraparound ; ; in: A/Y = handle to storage space ; $WINDEX = record index (word) ; out: A/Y = lo/hi address of ($WINDEX+1)th key, or first key if $WINDEX was the last record ; $WINDEX = record index of next record ; see okvs_nth for other exit conditions ;------------------------------------------------------------------------------ okvs_next +ST16 PARAM inc WINDEX bne + inc WINDEX+1 + jsr okvs_len +LD16 WINDEX +CMP16ADDR_NE WCOUNT, + sta WINDEX sta WINDEX+1 + +LD16 PARAM ; /!\ execution falls through here to okvs_nth ;------------------------------------------------------------------------------ ; okvs_nth ; get (N)th key ; ; in: A/Y = handle to storage space ; $WINDEX = record index ; out: A/Y = lo/hi address of nth key ; $WINDEX preserved ; all other flags clobbered ; $PTR clobbered ;------------------------------------------------------------------------------ okvs_nth jsr GetStoreAddressFromAY ; PTR -> store +LD16 WINDEX +ST16 SAVE jsr incptr2 ; PTR -> store+2 ldy #1 lda (PTR), y beq @slowpath ; if no key lookup table, iterate through store pha ; otherwise look up key address and return it dey lda (PTR), y sta PTR pla sta PTR+1 ; PTR -> key lookup table asl SAVE rol SAVE+1 ; SAVE = WINDEX*2 (16-bit) lda SAVE clc adc PTR bcc + clc inc PTR+1 + sta PTR lda SAVE+1 adc PTR+1 sta PTR+1 ; PTR -> nth record key lookup table lda (PTR), y pha iny lda (PTR), y tay pla ; A/Y -> nth key in store rts @slowpath jsr incptr2 ; PTR -> first record bne @next ; always branches - jsr stepptr @next lda SAVE dec SAVE tay bne - lda SAVE+1 dec SAVE+1 tay bne - jsr incptr +LD16 PTR rts ;------------------------------------------------------------------------------ ; okvs_update ; ; in: stack contains 6 bytes of parameters: ; +1 [word] handle to storage space ; +3 [word] address of key ; +5 [word] address of new value ; out: if C clear, key was found and value was updated ; if C set, key was not found ; all registers are clobbered ; all other flags clobbered ; $00/$01 clobbered ; $02/$03 clobbered ; $04/$05 clobbered ;------------------------------------------------------------------------------ okvs_update +PARAMS_ON_STACK 6 ldy #6 lda (PARAM),y sta SAVE+1 dey lda (PARAM),y sta SAVE dey - lda (PARAM),y sta @getparams,y dey bne - jsr okvs_get @getparams=*-1 !word $FDFD ; SMC !word $FDFD ; SMC bcs @exit +ST16 DEST ldy #0 lda (SAVE),y tay - lda (SAVE),y sta (DEST),y dey cpy #$FF bne - clc @exit rts ;------------------------------------------------------------------------------ ; okvs_iter / okvs_iter_values ; ; in: stack contains 4 bytes of parameters: ; +1 [word] handle to storage space ; +3 [word] address of callback ; out: will be called for each record in the store, in order, with ; $WINDEX = numeric index of record (word) ; A/Y = address of key or value (depends on which entry point you call) ; all registers are clobbered ; Z=1 ; all other flags clobbered ; PARAM clobbered ; PTR clobbered ; WINDEX clobbered ; WCOUNT clobbered ;------------------------------------------------------------------------------ okvs_iter lda #$D0 ; 'BNE' opcode +HIDE_NEXT_2_BYTES okvs_iter_values lda #$24 ; 'BIT' opcode sta @branch +PARAMS_ON_STACK 4 jsr GetStoreAddress ; PTR -> store ; Y = 0 jsr okvs_len_imm beq @exit ; no keys, exit immediately +LDPARAMPTR 3, @callback jsr incptr4 ; PTR -> first record lda #0 sta WINDEX sta WINDEX+1 @loop lda #1 ; for iter, skip length = 1 @branch bne + ; SMC (iter_values puts a BIT here, so no branch) ; for iter_values, skip length = length(key) + 1 + 1 tay ;;ldy #1 lda (PTR),y ; A = length of key clc adc #2 ; skip over record length (1 byte) + key length (1 byte) + sta @skiplen lda WCOUNT+1 ; save WCOUNT on stack pha lda WCOUNT pha lda WINDEX+1 ; save WINDEX on stack pha lda WINDEX pha lda PTR+1 tay pha lda PTR pha ; save PTR on stack clc @skiplen=*+1 adc #$FD ; SMC skip over pointer (and possibly key) bcc + iny ; A/Y -> value + @callback=*+1 jsr $FDFD ; SMC pla sta PTR pla sta PTR+1 ; restore PTR from stack pla sta WINDEX pla sta WINDEX+1 pla sta WCOUNT pla sta WCOUNT+1 jsr stepptr ; PTR -> next record inc WINDEX bne + inc WINDEX+1 + lda WINDEX cmp WCOUNT bne @loop lda WINDEX+1 cmp WCOUNT+1 bne @loop @exit rts ;------------------------------------------------------------------------------ ; internal functions okvs_next_field ; out: Y = 0 +ST16 PTR okvs_next_field_PTR_is_already_set jsr stepptr jmp incptr ; do NOT change this to BNE ; because if the low byte of PTR is 0 ; and the value of (PTR) is also 0 ; then stepptr will return with Z=1 and ; we will fall through here unexpectedly incptr4 jsr incptr2 incptr2 jsr incptr incptr ; preserves A, X, and Y inc PTR bne + inc PTR+1 + rts GetStoreAddressFromAY +ST16 PTR jmp derefptr GetStoreAddress ; in: PARAM = address of stack params (any PARAMS_ON_STACK macro will do this) ; out: PTR = address of store (always the first parameter on stack) ; preserves X ldy #1 lda (PARAM),y sta PTR iny lda (PARAM),y sta PTR+1 ; PTR -> first parameter on stack ; execution falls through here derefptr ; out: Y = 0 ; preserves X ldy #1 lda (PTR),y pha dey lda (PTR),y sta PTR pla sta PTR+1 rts stepptr ; out: Y = 0 ; preserves X ldy #0 lda (PTR),y clc adc PTR sta PTR bcc + inc PTR+1 + rts