comments
Uses: FileMap2.inc, FileMemMang2.inc
Uses those modules to create an extremely fast, file-based, Long List.
traverse & get 100,000 Key/Values = 0.046 seconds
raverse 100,000 items without testing data = 0.000000000001165 seconds
Uses: FileMap2.inc, FileMemMang2.inc
Uses those modules to create an extremely fast, file-based, Long List.
traverse & get 100,000 Key/Values = 0.046 seconds
raverse 100,000 items without testing data = 0.000000000001165 seconds
Code:
'pb 5/9 'FLLList1.inc ' ' File Based: Long/Long Key/Value List ' ' keep in mind; this 100% file-based list ' ' add 100,000 Key/Value pairs = 0.62 seconds ' traverse & get 100,000 Key/Values = 0.046 seconds ' ' add 100,000 Key/Value pairs after file expanded = 0.062 seconds ' traverse 100,000 items without testing data = 0.000000000001165 seconds ' ' #Include Once "C:\PB9\FileMapping\FileMap2.inc" #Include Once "C:\PB9\FileMapping\FileMemMang2.inc" ' %FLLListHeaderValidation = 3427467078 %FLLListNodeSize = 16 %FLLListHeaderSize = 16 ' $FLLList_Err_InvalidFile = "FLLList: invalid file" $FLLList_Err_InvalidFileName = "FLLList: invalid file name" $FLLList_Err_FileExist = "FLLList: file exist" $FLLList_Err_FileNotFound = "FLLList: file not found" $FLLList_Err_FileNotOpen = "FLLList: file not open" $FLLList_Err_FileCreateFail = "FLLList: file creation failed" $FLLList_Err_FileOpenFail = "FLLList: file open failed" $FLLList_Err_NullHandle = "FLLList: null handle" $FLLList_Err_NullPointer = "FLLList: null pointer" $FLLList_Err_FileMemMangErr = "FLLList: file memory manager error" ' Macro FLLList_ExitFalse(test, procedure, msg) If test Then Else #Debug Print FuncName$ +": "+ msg t.isErr = %TRUE t.errMsg = msg Exit procedure End If End Macro Macro FLLList_ExitTrue(test, procedure, msg) If test Then #Debug Print FuncName$ +": "+ msg t.isErr = %TRUE t.errMsg = msg Exit procedure End If End Macro Macro FLLList_GoFalse(test, MARKER, msg) If test Then Else #Debug Print FuncName$ +": "+ msg t.isErr = %TRUE t.errMsg = msg GoTo MARKER End If End Macro Macro FLLList_GoTrue(test, MARKER, msg) If test Then #Debug Print FuncName$ +": "+ msg t.isErr = %TRUE t.errMsg = msg GoTo MARKER End If End Macro ' ' ' Type FLLListNodeT hLeft As Long hRight As Long key As Long value As Long End Type Type FLLListHeaderT validate As Dword Count As Long hFirst As Long hLast As Long End Type Type FLLListT hdr As FLLListHeaderT mem As FMemT isOpen As Long isErr As Long errMsg As Asciiz * 256 End Type ' ' ' Function FLLList_Create(t As FLLListT, ByVal file As String) As Long 'create new file - open for use - True/False success Local hHdr As Long Local pHdr As FLLListHeaderT Ptr ' t.isErr = %FALSE t.isOpen = %FALSE FLLList_ExitTrue(file = "", Function, $FLLList_Err_InvalidFileName) FLLList_ExitTrue(IsFile(file), Function, $FLLList_Err_FileExist) FLLList_ExitFalse(FMem_Create(t.mem, file), Function, $FLLList_Err_FileCreateFail) t.hdr.validate = %FLLListHeaderValidation t.hdr.count = 0 t.hdr.hFirst = %NULL hHdr = FMem_Alloc(t.mem, %FLLListHeaderSize) : FLLList_GoFalse(hHdr, CLOSE_FILE, $FLLList_Err_NullHandle) pHdr = FMem_Get(t.mem, hHdr) : FMem_GoFalse(pHdr, CLOSE_FILE, $FMem_Err_NullPtr) @pHdr = t.hdr FMem_SetUser t.mem, 1, hHdr ' t.isOpen = %TRUE Function = %TRUE Exit Function ' CLOSE_FILE: FMem_Close t.mem End Function ' Function FLLList_Open(t As FLLListT, ByVal file As String) As Long 'open existing file created with, FLLList_Create() 'True/False success Local hHdr As Long Local pHdr As FLLListHeaderT Ptr ' t.isErr = %FALSE t.isOpen = %FALSE FLLList_ExitTrue(file = "", Function, $FLLList_Err_InvalidFileName) FLLList_ExitFalse(IsFile(file), Function, $FLLList_Err_FileNotFound) FLLList_ExitFalse(FMem_Open(t.mem, file), Function, $FLLList_Err_FileOpenFail) hHdr = FMem_GetUser(t.mem, 1) : FLLList_GoFalse(hHdr, CLOSE_FILE, $FLLList_Err_NullHandle) pHdr = FMem_Get(t.mem, hHdr) : FLLList_GoFalse(pHdr, CLOSE_FILE, $FLLList_Err_NullPointer) t.hdr = @pHdr FLLList_GoFalse(t.hdr.validate = %FLLListHeaderValidation, CLOSE_FILE, $FLLList_Err_InvalidFile) ' t.isOpen = %TRUE Function = %TRUE Exit Function ' CLOSE_FILE: FMem_Close t.mem End Function ' Sub FLLList_Close(t As FLLListT) 'close file Local hHdr As Long Local pHdr As FLLListHeaderT Ptr ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Sub, $FLLList_Err_FileNotOpen) ' - get header handle hHdr = FMem_GetUser(t.mem, 1) : FLLList_GoFalse(hHdr, CLOSE_FILE, $FLLList_Err_NullHandle) ' - set pointer to header pHdr = FMem_Get(t.mem, hHdr) : FLLList_GoFalse(pHdr, CLOSE_FILE, $FLLList_Err_NullPointer) ' - store header in file @pHdr = t.hdr CLOSE_FILE: FMem_Close t.mem t.isOpen = %FALSE End Sub ' Sub FLLList_Clear(t As FLLListT) 'delete all data - shrink file Local hHdr As Long Local pHdr As FLLListHeaderT Ptr ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Sub, $FLLList_Err_FileNotOpen) FMem_Clear t.mem : FMem_ExitTrue(t.mem.isErr, Sub, $FLLList_Err_FileMemMangErr) t.hdr.count = 0 t.hdr.hFirst = %NULL t.hdr.hLast = %NULL ' - have to allocate space and restore header hHdr = FMem_Alloc(t.mem, %FLLListHeaderSize) : FLLList_ExitFalse(hHdr, Sub, $FLLList_Err_NullHandle) pHdr = FMem_Get(t.mem, hHdr) : FLLList_ExitFalse(pHdr, Sub, $FLLList_Err_NullPointer) @pHdr = t.hdr ' - restore header handle in File Memory Manager user slot 1 FMem_SetUser t.mem, 1, hHdr End Sub ' Function FLLList_Count(t As FLLListT) As Long 'get stack count t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) Function = t.hdr.count End Function ' Function FLLList_Add(t As FLLListT, ByVal key As Long, ByVal value As Long) As Long 'append Key/Value to end of list 'return node handle - False if fail Local hNode As Long ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) ' hNode = FLLList_Node_Alloc(t) : FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) FLLList_Node_SetKey t, hNode, key FLLList_Node_SetValue t, hNode, value ' If t.hdr.hLast Then FLLList_Node_SetRight t, t.hdr.hLast, hNode FLLList_Node_SetLeft t, hNode, t.hdr.hLast t.hdr.hLast = hNode If t.hdr.hFirst = %NULL Then t.hdr.hFirst = hNode Function = hNode End Function ' Function FLLList_Insert(t As FLLListT, ByVal key As Long, ByVal value As Long) As Long 'insert Key/Value in front of list 'return node handle - False if fail Local hNode As Long ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) ' hNode = FLLList_Node_Alloc(t) : FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) FLLList_Node_SetKey t, hNode, key FLLList_Node_SetValue t, hNode, value ' If t.hdr.hFirst Then FLLList_Node_SetLeft t, t.hdr.hFirst, hNode FLLList_Node_SetRight t, hNode, t.hdr.hFirst t.hdr.hFirst = hNode If t.hdr.hLast = %NULL Then t.hdr.hLast = hNode Function = hNode End Function ' Function FLLList_InsertAt(t As FLLListT, ByVal hNode As Long, ByVal key As Long, ByVal value As Long) As Long 'insert Key/Value before hNode 'return node handle - False if fail Local hNew, hNodeLeft As Long ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) If hNode = t.hdr.hFirst Then Function = FLLList_Insert(t, key, value) Else hNew = FLLList_Node_Alloc(t) : FLLList_ExitFalse(hNew, Function, $FLLList_Err_NullHandle) FLLList_Node_SetKey t, hNew, key FLLList_Node_SetValue t, hNew, value ' 1 2 x>3 4 5 FLLList_Node_SetLeft t, hNew, FLLList_Node_GetLeft(t, hNode) hNodeLeft = FLLList_Node_GetLeft(t, hNode) If hNodeLeft Then FLLList_Node_SetRight t, hNodeLeft, hNew FLLList_Node_SetRight t, hNew, hNode FLLList_Node_SetLeft t, hNode, hNew Function = hNew End If End Function ' Sub FLLList_DeleteAt(t As FLLListT, ByVal hNode As Long) 'remove node from list Local hLeft, hRight As Long ' t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Sub, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) ' 1 2 (3) 4 5 If t.hdr.hFirst = hNode Then t.hdr.hFirst = FLLList_Node_GetRight(t, hNode) If t.hdr.hLast = hNode Then t.hdr.hLast = FLLList_Node_GetLeft(t, hNode) ' hLeft = FLLList_Node_GetLeft(t, hNode) hRight = FLLList_Node_GetRight(t, hNode) ' If hLeft Then FLLList_Node_SetRight t, hLeft, hRight If hRight Then FLLList_Node_SetLeft t, hRight, hLeft ' FLLList_Node_Free t, hNode End Sub ' Function FLLList_First(t As FLLListT) As Long 'move to first node in list - return node handle - False if fail t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) Function = t.hdr.hFirst End Function ' Function FLLList_Last(t As FLLListT) As Long 'move to last node in list - return node handle - False if fail t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) Function = t.hdr.hLast End Function ' Function FLLList_Right(t As FLLListT, ByVal hNode As Long) As Long 'move right from current node - return node handle - False if fail t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) If hNode Then Function = FLLList_Node_GetRight(t, hNode) End Function ' Function FLLList_Left(t As FLLListT, ByVal hNode As Long) As Long 'move left from current node - return node handle - False if fail t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) If hNode Then Function = FLLList_Node_GetLeft(t, hNode) End Function ' Sub FLLList_SetKeyAt(t As FLLListT, ByVal hNode As Long, ByVal key As Long) 'change Key at current position t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Sub, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) FLLList_Node_SetKey t, hNode, key End Sub ' Function FLLList_GetKeyAt(t As FLLListT, ByVal hNode As Long) As Long 'get Key at current position t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) Function = FLLList_Node_GetKey(t, hNode) End Function ' Sub FLLList_SetValueAt(t As FLLListT, ByVal hNode As Long, ByVal value As Long) 'change Value at current position t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Sub, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) FLLList_Node_SetValue t, hNode, value End Sub ' Function FLLList_GetValueAt(t As FLLListT, ByVal hNode As Long) As Long 'get Value at current position t.isErr = %FALSE FLLList_ExitFalse(t.isOpen, Function, $FLLList_Err_FileNotOpen) FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) Function = FLLList_Node_GetValue(t, hNode) End Function ' Function FLLList_IsErr(t As FLLListT) As Long 'True/False if last operation caused an error Function = t.isErr End Function ' Function FLLList_ErrMsg(t As FLLListT) As String 'get error message If t.isErr Then Function = t.errMsg End Function ' ' ----------------------------------- ' internal ' ----------------------------------- ' Function FLLList_Node_Alloc(t As FLLListT) As Long 'internal - allocate file space for new node Local hNode As Long Local pNode As FLLListNodeT Ptr ' hNode = FMem_Alloc(t.mem, %FLLListNodeSize) : FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FMem_ExitFalse(pNode, Function, $FMem_Err_NullPtr) @pNode.hLeft = %NULL @pNode.hRight = %NULL @pNode.key = %NULL @pNode.value = %NULL Incr t.hdr.count Function = hNode End Function ' Sub FLLList_Node_Free(t As FLLListT, ByVal hNode As Long) FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) FMem_Free t.mem, hNode, %FLLListNodeSize Decr t.hdr.count End Sub ' Sub FLLList_Node_SetLeft(t As FLLListT, ByVal hNode As Long, ByVal hLeft As Long) Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Sub, $FLLList_Err_NullPointer) @pNode.hLeft = hLeft End Sub ' Function FLLList_Node_GetLeft(t As FLLListT, ByVal hNode As Long) As Long Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Function, $FLLList_Err_NullPointer) Function = @pNode.hLeft End Function ' Sub FLLList_Node_SetRight(t As FLLListT, ByVal hNode As Long, ByVal hRight As Long) Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Sub, $FLLList_Err_NullPointer) @pNode.hRight = hRight End Sub ' Function FLLList_Node_GetRight(t As FLLListT, ByVal hNode As Long) As Long Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Function, $FLLList_Err_NullPointer) Function = @pNode.hRight End Function ' Sub FLLList_Node_SetKey(t As FLLListT, ByVal hNode As Long, ByVal key As Long) Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Sub, $FLLList_Err_NullPointer) @pNode.key = key End Sub ' Function FLLList_Node_GetKey(t As FLLListT, ByVal hNode As Long) As Long Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Function, $FLLList_Err_NullPointer) Function = @pNode.key End Function ' Sub FLLList_Node_SetValue(t As FLLListT, ByVal hNode As Long, ByVal value As Long) Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Sub, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Sub, $FLLList_Err_NullPointer) @pNode.value = value End Sub ' Function FLLList_Node_GetValue(t As FLLListT, ByVal hNode As Long) As Long Local pNode As FLLListNodeT Ptr ' FLLList_ExitFalse(hNode, Function, $FLLList_Err_NullHandle) pNode = FMem_Get(t.mem, hNode) : FLLList_ExitFalse(pNode, Function, $FLLList_Err_NullPointer) Function = @pNode.value End Function '
Comment