Page Date
2004-05-18
DD-Software
Kapitel zurück / previous Chapter
Main Index
 
Seite zurück / previous page
Backward
Seite vor / next page
Forward
 
Seitenanfang/TopOfPage
Top
Seitenende/EndOfPage
Bottom
MyWbtHelp current version

CAM - Content Addressable Memory - DataSaver


The WinBatch xCAM Array Extender is described there: WinBatch Scripting - Extender (3rd Party and Free)
Download xCAM Extender xcam34i.v34032.zip


Seitenanfang/TopOfPage Seitenende/EndOfPage
Seitenanfang/TopOfPage Seitenende/EndOfPage

CAM - Content Addressable Memory - DataSaver

;==========================================================================================================================================
;    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*


Page Date
2004-05-18
DD-Software
Kapitel zurück / previous Chapter
Main Index
 
Seite zurück / previous page
Backward
Seite vor / next page
Forward
 
Seitenanfang/TopOfPage
Top
Seitenende/EndOfPage
Bottom
MyWbtHelp current version