Content addressable memory

Keywords:   Content addressable memory udf uds

---

The following uses hash addressing to speed up searches in arrays.

Winbatch arrays are limited to 65535 items per dimension.

This is my attempt to break the 65535 barrier with the minimum of additional overhead by using two array dimensions to specify the index. It takes some additional - and ugly code, but it should not waste (much) additional memory.

In addition the first array element is consumed to hold the "prime" number of the count of active elements.

The array is allocated as (approximately):

floor(sqrt(prime)) x ceiling(sqrt(prime))

to be able to try to minimize the overhead without having to choose between various factors.

This solution is limited only by memory (and perhaps the 2GB memory address space that WinBatch's memory model uses).

;***************************************************************************
;**  DataSaver by Marty Williams
;**  With the actual hard parts done by Detlev Dalitz
;**  With support from Marty Williams
;**  Using Hash Addressing originally invented by Dr. Norm Peterson
;** 
;**  Purpose: Provide keyword addressable storage in an efficient manner
;***************************************************************************


;***************************************************************************
;**   DataSaverInit
;**   Use to initialize DataSaver storage area.
;**   
;**   Parameter(s)
;**            maxcount   Max number of items to store 
;**                       from 1 to unknown max (maybe 100 million??
;**   
;**   Return Value
;**            storage    "blind" array pointer.  Just pass to other functions
;**                       do not acess directly
;**   
;**   Call DataSaverInit at the beginning of your script, saving the return
;**   value to be whend when calling the DataPut and Dataget functions.
;**   
;***************************************************************************
#DefineFunction DataSaverInit(maxcount)
   ; if less than 10 elelemts make it 10
   if maxcount < 10 then maxcount=10
   amtalloc   = udfGetPrimeThisOrNext((2*maxcount)+1)  
   ;split into 2 chunks
   partA=Floor(sqrt(amtalloc))
   partB=Ceiling(amtalloc/partA)
   ds=ArrDimension(partA,partB,2)
   ds[0,0,0]="*&^SPECIALDATAAREA&^$#@!)("
   ds[0,0,1]=amtalloc
   return (ds)
#EndFunction




;***************************************************************************
;**   DataPut
;**      Stores information for later retrieval
;** 
;**      Parameter(s)
;**         storage - value returned from the DataSaverInit function
;**         key     - unique data value later used to fetch the data
;**                   may be integer, float, or string.  In this version,
;**                   key is NOT case sensitive.
;**         data    - Data to save.  May be any legal type that can be
;**                   stored in an array
;** 
;**      Returns    - Array index where data was saved.  This value is
;**                   not normally used or retained for any reasons.
;**                   Mostly available for UDF debugging
;** 
;** 
;***************************************************************************
#DefineFunction DataPut(storage,key,data)
    DataHash(storage,key,0,data)
#EndFunction


;***************************************************************************
;**   DataGet
;**      Retrieves stored information
;** 
;**      Parameter(s)
;**         storage - value returned from the DataSaverInit function
;**         key     - unique data value later used to fetch the data
;**                   may be integer, float, or string
;** 
;**      Returns    - Data previously saved with key.  If no data was
;**                   previously saved with the key, returns a null string
;** 
;** 
;** 
;***************************************************************************
#DefineFunction DataGet(storage,key)
    return DataHash(storage,key,1,0)
#EndFunction




;***************************************************************************
;** 
;**   Support functions.  Not meant to be called directly by the user
;** 
;***************************************************************************
;----------------------------------------------------------------------
;Determine if the passed parameter is a prime number
#DefineFunction udfIsPrimeNumber (iNumber)
iLimit = Int(Sqrt(iNumber))
iIsPrime = 1
For i=2 To iLimit
   iIsPrime = iNumber mod i
   If !iIsPrime Then Break
Next
Return (iIsPrime)
#EndFunction
;----------------------------------------------------------------------
;Determine if passed number is prime.  If so return that number,
;else locate and return next highest prime number
#DefineFunction udfGetPrimeThisOrNext (iNumber)
While !udfIsPrimeNumber (iNumber)
   iNumber = iNumber+1
EndWhile
Return (iNumber)
#EndFunction
;----------------------------------------------------------------------

;Most od the real work happens in here.  My condolences.
#DefineFunction DataHash (aArray, Key, type, optdata)
iElements = aArray[0,0,1]
PartB=ArrInfo(aArray,2)
key=strlower(key) ; makes key case insensitive
klen=strlen(key)
iHash=0
for xx=1 to klen
   iHash = (iHash) | (Char2Num(Strsub(key,xx,1)) << ((xx mod 4)*8))
next
iHash = iHash mod iElements
iIndex = iHash
iNext = 0
While 1
   If (!VarType(aArray[iIndex/PartB,iIndex mod PartB,0]))  
      aArray[iIndex/PartB,iIndex mod PartB,0] = Key      
   endif
   If  aArray[iIndex/PartB,iIndex mod PartB,0]==Key
      if type==0 ; set
         aArray[iIndex/PartB,iIndex mod PartB,1] = optdata
         return (iIndex)
      else   ; get
         if !VarType(aArray[iIndex/PartB,iIndex mod PartB,1]) then return("")
         else   return(aArray[iIndex/PartB,iIndex mod PartB,1])
      endif
   EndIf
   iNext = iNext+1
   If (iNext>iElements) Then Return (-1)
   iIndex = (iHash+(iNext*iNext)) mod iElements  ; Square linked list.
EndWhile
#EndFunction                              
;----------------------------------------------------------------------

   


maxitems=100
DS=DataSaverInit(maxitems)

DataPut(DS, "apple",   "An apple a day keeys the doctor away.")
DataPut(DS, "stitch",  "A stitch in time saves nine.")
DataPut(DS, "cloud",   "Most clouds look like clouds.")
DataPut(DS, "feather", "Birds of a feather flock together.")
DataPut(DS, "popcorn", "I like popcorn.")
DataPut(DS, "purple",  "Purple is another color.")
DataPut(DS, "other",   "Something or other.")


test="Apple"
Message(test,DataGet(DS,test))
test="purple"
Message(test,DataGet(DS,test))
test="Cloud"
Message(test,DataGet(DS,test))
test="orchrd"
Message(test,DataGet(DS,test))


Message("All","Doned")


exit

---

Article ID:   W15309