;==========================================================================================================================================
; CAM v1.02 - Content Addressable Memory - DataSaver - Hashed array access in WinBatch
;==========================================================================================================================================
;** CAM / DataSaver by Marty Williams. Monday, September 02, 2002 06:18 PM.
;** With the actual hard parts done by Detlev Dalitz
;** With support from Marty Williams
;** Using Hash Addressing originally invented by Dr. Norm Peterson
;** Slightly modified by Detlev Dalitz.20030215.20030220
;**
;** Purpose: Provide keyword addressable storage in an efficient manner
;==========================================================================================================================================
; Functions and Syntax:
; a:CAMStorage = camInit (i:MaxCount)
; i:BooleanValue = camCheck (a:CAMStorage)
; is:CamPutValue = camPut (a:CAMStorage, ifs:Key, ifs:Data)
; ifs:CAMGetValue = camGet (a:CAMStorage, ifs:Key)
;
; (Datatype: i=integer, f=float, s=string, a=array)
;==========================================================================================================================================
;------------------------------------------------------------------------------------------------------------------------------------------
;** 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
;------------------------------------------------------------------------------------------------------------------------------------------
;------------------------------------------------------------------------------------------------------------------------------------------
;** 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 camInit(iMaxCount)
; Assumption: Content Addressable Memory should have at least 10 Elements.
iMaxCount=Max(10,iMaxCount)
; Hashing goes better with prime and double sized area.
CAMMaxCells=xmtGetPrimeThisOrNext((2*iMaxCount)+1)
; Split into 2 vectors.
CAMPartA=Floor(Sqrt(CAMMaxCells))
CAMPartB=Ceiling(CAMMaxCells/CAMPartA)
CAM=ArrDimension(CAMPartA,CAMPartB,2)
CAMLastCell = ArrInfo(CAM,6)-1
; Brand the array with the literal "*CAM*" and a unique Number, retrieved from current machine time.
CAM[0,0,0]="*CAM*"
CAM[0,0,1]=CAMMaxCells
CAM[CAMPartA-1,CAMPartB-1,0]="*EOF*CAM*"
CAM[CAMPartA-1,CAMPartB-1,1]=TimeYmdHms()
Return(CAM)
#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 camPut(CAMStorage,Key,Data)
Return(camHash(CAMStorage,0,Key,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 camGet(CAMStorage,Key)
Return(camHash(CAMStorage,1,Key,0))
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------
;------------------------------------------------------------------------------------------------------------------------------------------
#DefineFunction camCheck(CAMStorage)
If (VarType(CAMStorage)<>256) Then Return(@FALSE) ; Parameter is not an array.
If (ArrInfo(CAMStorage,0)<>3) Then Return(@FALSE) ; Possibly not a valid CAM array.
If (ArrInfo(CAMStorage,6)<20) Then Return(@FALSE) ; Possibly not a valid CAM array.
If (CAMStorage[0,0,0]<>"*CAM*") Then Return(@FALSE) ; Not a valid CAM array.
If (!xmtIsPrime(CAMStorage[0,0,1])) Then Return(@FALSE) ; Not a valid CAM array.
PartA=ArrInfo(CAMStorage,1)
PartB=ArrInfo(CAMStorage,2)
If (CAMStorage[PartA-1,PartB-1,0]<>"*EOF*CAM*") Then Return(@FALSE) ; Not a valid CAM array.
Return(@TRUE)
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------
;------------------------------------------------------------------------------------------------------------------------------------------
; Most of the real work happens in here. My condolences.
;..........................................................................................................................................
#DefineFunction camHash (CAMStorage, Mode, Key, optData)
If (Key=="") Then Return("*EOF*CAM*") ; Key is invalid.
PartA=ArrInfo(CAMStorage,1)
PartB=ArrInfo(CAMStorage,2)
iCAMaxCells=Max(1,CAMStorage[0,0,1])
If (VarType(key)==2) Then Key=StrLower(Key) ; Makes Key case insensitive.
;..........................................................................................................................................
; Alternative methods of Hash calculation ...
;
; From Marty:
; iHash=0
; klen=StrLen(key)
; for xx=1 to klen
; iHash = (iHash) | (Char2Num(Strsub(key,xx,1)) << ((xx mod 4)*8))
; next
;..........................................................................................................................................
; From Detlev:
iHash=xmtStrChecksum(Key,1) ; uses the "xmtdd34i.dll" extender.
;..........................................................................................................................................
iHash=iHash mod iCAMaxCells
iIndex=iHash
iNext=0
Switch Min(Max(Mode,0),1)
Case 1
; Get
While 1
iIndexA=iIndex/PartB
iIndexB=iIndex mod PartB
If (VarType(CAMStorage[iIndexA,iIndexB,0])==VarType(Key))
If (CAMStorage[iIndexA,iIndexB,0]==Key)
; Key found, but Data VarType is undefined, so return empty string.
If (!VarType(CAMStorage[iIndexA,iIndexB,1])) Then Return("")
; Else Return DataValue.
Return(CAMStorage[iIndexA,iIndexB,1])
EndIf
EndIf
iNext=iNext+1
; On Get: Key not found.
If (iNext>iCAMaxCells) Then Return("*EOF*CAM*")
iIndex=(iHash+(iNext*iNext)) mod iCAMaxCells ; Square linked list.
EndWhile
Break
Case 0
; Put
While 1
iIndexA=iIndex/PartB
iIndexB=iIndex mod PartB
; If Key VarType is undefined then store the Key.
If (!VarType(CAMStorage[iIndexA,iIndexB,0]))
CAMStorage[iIndexA,iIndexB,0]=Key
; ArrayCell gets VarType from Key.
EndIf
If (VarType(CAMStorage[iIndexA,iIndexB,0])==VarType(Key))
If (CAMStorage[iIndexA,iIndexB,0]==Key)
CAMStorage[iIndexA,iIndexB,1]=optData ; Store the DataValue.
Return(@TRUE) ; put success=@TRUE
EndIf
EndIf
iNext=iNext+1
; On Put: No location available. Enlarge the CAM array.
If (iNext>iCAMaxCells) Then Return("*EOF*CAM*")
iIndex=(iHash+(iNext*iNext)) mod iCAMaxCells ; Square linked list.
EndWhile
Break
EndSwitch
#EndFunction
;------------------------------------------------------------------------------------------------------------------------------------------
;--- test ---
AddExtender("xmtDD34i.dll") ; exported functions: xmtIsPrime, xmtGetPrimeThisOrNext, xmtStrChecksum.
maxitems=10
DS=camInit(maxitems)
camPut(DS, "apple", "An apple a day keeys the doctor away.")
camPut(DS, "stitch", "A stitch in time saves nine.")
camPut(DS, "cloud", "Most clouds look like clouds.")
camPut(DS, "feather", "Birds of a feather flock together.")
camPut(DS, "popcorn", "I like popcorn.")
camPut(DS, "purple", "Purple is another color.")
camPut(DS, "other", "Something or other.")
camPut(DS, 12345678901234567890, 333333333333)
camPut(DS,"12345678901234567890","333333333333")
test="Apple"
Message(test,camGet(DS,test))
test="purple"
Message(test,camGet(DS,test))
test="Cloud"
Message(test,camGet(DS,test))
test="orchrd"
Message(test,camGet(DS,test))
camPut(DS, 1.10, 2.20)
camPut(DS, 3.14, "Stitch")
camPut(DS, "Cloud", 9)
camPut(DS, "Feather", "none")
camPut(DS, "Popcorn", 11)
camPut(DS, "Purple", 22)
camPut(DS, "Other", "Something or other.")
test=3.1400
Message(test,camGet(DS,test))
test=1.1
Message(test,camGet(DS,test))
test=2.2
Message(test,camGet(DS,test))
test=""
Message(test,camGet(DS,test))
test="Feather"
Message(test,camGet(DS,test))
test=12345678901234567890
Message(test,camGet(DS,test))
test="12345678901234567890"
Message(test,camGet(DS,test))
test="orchrd"
Message(test,camGet(DS,test))
Message("All","Doned")
Exit
;------------------------------------------------------------------------------------------------------------------------------------------
;------------------------------------------------------------------------------------------------------------------------------------------
:AnotherTest
AddExtender("xmtdd34i.dll") ; exported functions: xmtIsPrime, xmtGetPrimeThisOrNext, xmtStrChecksum.
iCAMMax = 50
; That means: 50 Key-Data pairs should be stored collision free.
; More Key-Data pairs are possible but access time decreases.
aCAM = camInit(iCAMMax)
If (camCheck(aCAM)==@TRUE)
Message("Test xCAM","This CAM array seems to be valid and applicable. Here we go.")
Else
Message("Test xCAM","Sorry. This CAM array seems to be invalid. Execution stops now.")
Exit
EndIf
; We read the WIL.CLR file and put each line
; as a Key-Data pair into the CAM until *EOF*CAM* is reached.
BoxOpen("Test xCAM","Reading Key-Data pairs ...")
sFilename = StrCat(DirHome(),"wil.clr")
hFR = FileOpen(sFilename,"READ")
i=1
While @TRUE
sLine = FileRead(hFR)
If (sLine=="*EOF*") Then Break
If (sLine>"") Then ifsResult = camPut(aCAM,sline,sline)
BoxText(StrCat(i,@TAB,ifsResult))
i=i+1
If (ifsResult=="*EOF*CAM*") Then Break
EndWhile
FileClose(hFR)
Pause("Test xCAM","We've just put some data into the CAM.%@LF%Now we try to get the data back from CAM.")
; Now we read the Data-Part back from the CAM.
; Again we use the keys stored in the WIL.CLR file.
TimeNow = TimeYmdHms()
sTestOut = StrCat(Environment("temp"),"\Test.xCAM.txt")
hFR = FileOpen(sFilename,"READ")
i=1
While @TRUE
sLine = FileRead(hFR)
If (sLine=="*EOF*") Then Break
If (sLine>"")
ifsResult = camGet(aCAM,sline)
BoxText(StrCat(i,@LF,"K: ",sLine,@LF,"D: ",ifsResult))
IniWritePvt(StrCat("Test xCAM ",TimeNow),StrCat(i,": ",sline),ifsResult,sTestOut)
i=i+1
EndIf
If (ifsResult=="*EOF*CAM*") Then Break ; Key not found. Should not happen in this test.
EndWhile
FileClose(hFR)
Run(sTestOut,"")
; Note:
; We get back the Data Values from the CAM by 'indexing' the CAM array with the Key Value.
; In this test there is no integer as an array indexer involved, only string keys are used.
Exit
;------------------------------------------------------------------------------------------------------------------------------------------
*EOF*
|
