Bilgus Posted April 11, 2020 Share Posted April 11, 2020 Went looking for a FIFO queue there are a few examples here on the forum but I didn't like the complexit/lack of flexibility in what I found The Queue Ive implemented uses a single dimension array set up as a circular buffer The position and Item Count are stored in an extra slot of the array inside a 'DllStruct' Convenience Functions are included FifoQueue_Create($iSlots) ;Initialize the Queue Func FifoQueue_($eFQ, ByRef $aQ) ;For Status Functions - (So you don't have to supply $vOut) Available operations: $eFQ_Create = 0, $eFQ_Push, $eFQ_Peek, $eFQ_Pop, $eFQ_IsEmpty, $eFQ_IsFull, $eFQ_Count, $eFQ_Empty, $eFQ_IsInit Spoiler expandcollapse popupGlobal Enum $eFQ_Create = 0, $eFQ_Push, $eFQ_Peek, $eFQ_Pop, $eFQ_IsEmpty, $eFQ_IsFull, $eFQ_Count, $eFQ_Empty, $eFQ_IsInit Func FifoQueue($eFQ, ByRef $aQ, ByRef $vOut) ;Bilgus 2020 Local Const $IDInit = 0xF1F0 Local $iErr = 0 Local $iPos, $iItems Local $tKey, $IDKey Local $iSlots = UBound($aQ, 1) - 1 If $iSlots > 0xFFFE Then Return SetError(0xFFFE, -1, $vOut) If $eFQ <> $eFQ_Create Then If Not IsArray($aQ) Or $iSlots < 2 Then $iErr = 1 ;Queue not initialized ElseIf IsDllStruct($aQ[$iSlots]) Then $tKey = $aQ[$iSlots] ;MQ_Create adds an extra Slot -- pos data is stored there.. $iPos = DllStructGetData($tKey, 1, 1) $iItems = DllStructGetData($tKey, 1, 2) If DllStructGetData($tKey, 1, 3) <> $IDInit Then $iErr += 2 ;Queue not initialized (BY MQ_Create) EndIf If $iErr And $eFQ <> $eFQ_IsInit Then ConsoleWrite("Queue Error: " & $iErr & @CRLF) Return SetError($iErr, 0, $vOut) EndIf Else If $iSlots < 2 Then $iSlots = 10 Local $a[$iSlots + 1] $tKey = DllStructCreate("USHORT[4]") DllStructSetData($tKey, 1, 0xF1F0, 3) $a[$iSlots] = $tKey $vOut = $a ;ConsoleWrite("Created Queue[" & $iSlots & "]" & @CRLF) Return SetError($iErr, $iSlots, $vOut) EndIf ;Circular Queue Logic Switch ($eFQ) Case $eFQ_Push If $iItems >= $iSlots Then Return False ;Rollover after last element $aQ[Mod($iItems + $iPos, $iSlots)] = $vOut $iItems += 1 Case $eFQ_Peek If $iItems = 0 Then Return False $vOut = $aQ[$iPos] Case $eFQ_Pop If $iItems = 0 Then Return False $vOut = $aQ[$iPos] $iPos += 1 $iItems -= 1 Case $eFQ_IsEmpty Return ($iItems = 0) Case $eFQ_IsFull Return ($iItems >= $iSlots) Case $eFQ_Count Return $iItems Case $eFQ_Empty $iItems = 0 Case $eFQ_IsInit Return ($iErr = 0) Case Else Return False EndSwitch $iPos = Mod($iPos, $iSlots) ;Rollover after last element DllStructSetData($tKey, 1, $iPos, 1) DllStructSetData($tKey, 1, $iItems, 2) Return SetError($iErr, $iItems, True) EndFunc ;==>FifoQueue ;--Convenience Functions------------------------------- Func FifoQueue_Create($iSlots = 10) Local $aE Return FifoQueue($eFQ_Create, $iSlots, $aE) EndFunc ;==>FifoQueue_Create Func FifoQueue_($eFQ, ByRef $aQ) Local $aE If $eFQ < $eFQ_IsEmpty Then $aE = FifoQueue($eFQ, $aQ, $aE) Return SetError(@error, 0, $aE) Else Return FifoQueue($eFQ, $aQ, $aE) EndIf EndFunc ;==>FifoQueue_ ;--Convenience Functions------------------------------- Example (With Debug function) Spoiler expandcollapse popup;Bilgus 2020 Global Enum $eFQ_Create = 0, $eFQ_Push, $eFQ_Peek, $eFQ_Pop, $eFQ_IsEmpty, $eFQ_IsFull, $eFQ_Count, $eFQ_Empty, $eFQ_IsInit Global $aQueue ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsInit, $aQueue) ? " IS " : " NOT ") & "initialized" & @CRLF) $aQueue = FifoQueue_Create(4) ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsInit, $aQueue) ? " IS " : " NOT ") & "initialized" & @CRLF) FifoQueueTest() Func FifoQueueTest() Local $aTest If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("!%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) ConsoleWrite("!Push 9" & @CRLF) For $i = 0 To 80 Step 10 Local $aIn[4] = [$i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Pop All" & @CRLF) While FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) WEnd ConsoleWrite("!Push 9" & @CRLF) For $i = 100 To 900 Step 100 Local $aIn[4] = [$i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsFull, $aQueue) ? " IS " : " NOT ") & "full" & @CRLF) ConsoleWrite("!Queue Items: " & FifoQueue_($eFQ_Count, $aQueue) & @CRLF) ConsoleWrite("!Push 1" & @CRLF) Local $aIn[6] = [5555, 6666, 7777, 8888] FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) If FifoQueue_Dbg($eFQ_Peek, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) ConsoleWrite("!Pop 2" & @CRLF) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsFull, $aQueue) ? " IS " : " NOT ") & "full" & @CRLF) ConsoleWrite("!Queue Items: " & FifoQueue_($eFQ_Count, $aQueue) & @CRLF) ConsoleWrite("!Push 4" & @CRLF) For $i = 1000 To 5000 Step 1000 Local $aIn[4] = [$i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Pop 2" & @CRLF) For $i = 1 To 2 If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) Next ConsoleWrite("!Push 7" & @CRLF) For $i = 10000 To 70000 Step 10000 Local $aIn[4] = [$i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Pop 2" & @CRLF) For $i = 1 To 2 If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) Next ConsoleWrite("!PopAll" & @CRLF) While FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) WEnd ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsEmpty, $aQueue) ? " IS " : " NOT ") & "empty" & @CRLF) ConsoleWrite("!Push 6" & @CRLF) For $i = 0 To 50 Step 10 Local $aIn[4] = [$i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Pop 4 [2]" & @CRLF) Local $aTest[2] For $i = 1 To 4 If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s" & @CRLF, $aTest[0], $aTest[1])) Next Local $aTest = 0 ConsoleWrite("!Push 7" & @CRLF) For $i = 100 To 700 Step 100 Local $aIn[4] = ["N" & $i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Empty All" & @CRLF) FifoQueue_($eFQ_Empty, $aQueue) ConsoleWrite("!Queue" & (FifoQueue_($eFQ_IsEmpty, $aQueue) ? " IS " : " NOT ") & "empty" & @CRLF) ConsoleWrite("!Push 10" & @CRLF) For $i = 0 To 9 Local $aIn[4] = ["A" & $i, $i + 1, $i + 2, $i + 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Next ConsoleWrite("!Pop 2" & @CRLF) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) ConsoleWrite("!Push 1" & @CRLF) Local $aIn[6] = [5555, 6666, 7777, 8888] FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) ConsoleWrite("!Pop 2" & @CRLF) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) If FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) ConsoleWrite("!Push 2" & @CRLF) Local $aIn[4] = ["P" & 0, 1, 2, 3] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf Local $aIn[4] = ["P" & 10, 20, 30, 40] If FifoQueue_Dbg($eFQ_Push, $aQueue, $aIn) Then ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aIn[0], $aIn[1], $aIn[2], $aIn[3])) EndIf ConsoleWrite("!Queue Items: " & FifoQueue_($eFQ_Count, $aQueue) & @CRLF) ConsoleWrite("!PopAll" & @CRLF) While FifoQueue_Dbg($eFQ_Pop, $aQueue, $aTest) ConsoleWrite(StringFormat("%s, %s, %s, %s" & @CRLF, $aTest[0], $aTest[1], $aTest[2], $aTest[3])) WEnd EndFunc ;==>FifoQueueTest ;--Convenience Functions------------------------------- Func FifoQueue_Create($iSlots = 10) Local $aE Return FifoQueue($eFQ_Create, $iSlots, $aE) EndFunc ;==>FifoQueue_Create Func FifoQueue_($eFQ, ByRef $aQ) Local $aE If $eFQ < $eFQ_IsEmpty Then $aE = FifoQueue($eFQ, $aQ, $aE) Return SetError(@error, 0, $aE) Else Return FifoQueue($eFQ, $aQ, $aE) EndIf EndFunc ;==>FifoQueue_ ;--Convenience Functions------------------------------- Func FifoQueue_Dbg($eFQ, ByRef $aQ, ByRef $vOut) Local Const $aDbg[9] = ["<>Create", ">Push [%d]", "<Peek [%d]", "<Pop [%d]", "=IsEmpty", "=IsFull", "=Count", "<>Empty", "=IsInit"] Local $iSlots = UBound($aQ, 1) - 1 If $iSlots > 65534 Then MsgBox(0, "ERROR", "Too many Slots") If $iSlots > 0 Then If IsDllStruct($aQ[$iSlots]) Then $tKey = $aQ[$iSlots] Local $iElKey = DllStructGetData($tKey, 1, 3) Local $iItems = DllStructGetData($tKey, 1, 2) Local $iPos = DllStructGetData($tKey, 1, 1) If $eFQ > $eFQ_Pop Then ConsoleWrite($aDbg[$eFQ] & @CRLF) ElseIf $eFQ = $eFQ_Push Then ConsoleWrite(StringFormat($aDbg[$eFQ] & @CRLF, Mod($iItems + $iPos, $iSlots))) Else ConsoleWrite(StringFormat($aDbg[$eFQ] & @CRLF, $iPos)) EndIf Else ConsoleWrite("Invalid Array $aQ" & @CRLF) EndIf Else ConsoleWrite($aDbg[$eFQ] & @CRLF) EndIf Local $aRes = FifoQueue($eFQ, $aQ, $vOut) Return $aRes EndFunc ;==>FifoQueue_Dbg Func FifoQueue($eFQ, ByRef $aQ, ByRef $vOut) ;Bilgus 2020 Local Const $IDInit = 0xF1F0 Local $iErr = 0 Local $iPos, $iItems Local $tKey, $IDKey Local $iSlots = UBound($aQ, 1) - 1 If $iSlots > 0xFFFE Then Return SetError(0xFFFE, -1, $vOut) If $eFQ <> $eFQ_Create Then If Not IsArray($aQ) Or $iSlots < 2 Then $iErr = 1 ;Queue not initialized ElseIf IsDllStruct($aQ[$iSlots]) Then $tKey = $aQ[$iSlots] ;MQ_Create adds an extra Slot -- pos data is stored there.. $iPos = DllStructGetData($tKey, 1, 1) $iItems = DllStructGetData($tKey, 1, 2) If DllStructGetData($tKey, 1, 3) <> $IDInit Then $iErr += 2 ;Queue not initialized (BY MQ_Create) EndIf If $iErr And $eFQ <> $eFQ_IsInit Then ConsoleWrite("Queue Error: " & $iErr & @CRLF) Return SetError($iErr, 0, $vOut) EndIf Else If $iSlots < 2 Then $iSlots = 10 Local $a[$iSlots + 1] $tKey = DllStructCreate("USHORT[4]") DllStructSetData($tKey, 1, 0xF1F0, 3) $a[$iSlots] = $tKey $vOut = $a ;ConsoleWrite("Created Queue[" & $iSlots & "]" & @CRLF) Return SetError($iErr, $iSlots, $vOut) EndIf ;Circular Queue Logic Switch ($eFQ) Case $eFQ_Push If $iItems >= $iSlots Then Return False ;Rollover after last element $aQ[Mod($iItems + $iPos, $iSlots)] = $vOut $iItems += 1 Case $eFQ_Peek If $iItems = 0 Then Return False $vOut = $aQ[$iPos] Case $eFQ_Pop If $iItems = 0 Then Return False $vOut = $aQ[$iPos] $iPos += 1 $iItems -= 1 Case $eFQ_IsEmpty Return ($iItems = 0) Case $eFQ_IsFull Return ($iItems >= $iSlots) Case $eFQ_Count Return $iItems Case $eFQ_Empty $iItems = 0 Case $eFQ_IsInit Return ($iErr = 0) Case Else Return False EndSwitch $iPos = Mod($iPos, $iSlots) ;Rollover after last element DllStructSetData($tKey, 1, $iPos, 1) DllStructSetData($tKey, 1, $iItems, 2) Return SetError($iErr, $iItems, True) EndFunc ;==>FifoQueue Link to comment Share on other sites More sharing options...
Bilgus Posted April 13, 2020 Author Share Posted April 13, 2020 Here is a second version with Redim supported Note redim only works when items are in the array if you are making it larger Queue needs to be empty to redim smaller. It also BitXORs the number of slots with 0xF1F0 to be a bit more robust with checking if the Queue array is valid Spoiler expandcollapse popupGlobal Enum $eFQ_Create = 0, $eFQ_Push, $eFQ_Peek, $eFQ_Pop, $eFQ_Redim, $eFQ_Empty, $eFQ_IsEmpty, $eFQ_IsFull, $eFQ_Count, $eFQ_IsInit, $eFQ_ENUMCOUNT Func FifoQueue($eFQ, ByRef $aQ, ByRef $vOut) Local Const $IDInit = 0xF1F0, $_FQ_Error = -1 Local Enum $eiPos = 1, $eiItems, $eID, $eiSlots Local $tKey, $iPos, $iItems, $iErr = 0 Local $iSlots = UBound($aQ, 1) - 1 If $iSlots > 0xFFFE Then Return SetError(0xFFFE, -1, $vOut) If $eFQ <> $eFQ_Create Then If Not IsArray($aQ) Or $iSlots < 2 Then $iErr = 1 ;Queue not initialized ElseIf IsDllStruct($aQ[$iSlots]) Then $tKey = $aQ[$iSlots] ;MQ_Create adds an extra Slot -- pos data is stored there.. If DllStructGetData($tKey, 1, $eID) <> $IDInit Then $iErr += 2 ;Queue not initialized (BY MQ_Create) If BitXOR($iSlots, $IDInit) <> DllStructGetData($tKey, 1, $eiSlots) Then $iErr += 4 ;number of slots doesn't match $iPos = DllStructGetData($tKey, 1, $eiPos) $iItems = DllStructGetData($tKey, 1, $eiItems) EndIf If $iErr And $eFQ <> $eFQ_IsInit Then $eFQ = $_FQ_Error Else $iSlots = $aQ ; If $iSlots < 2 Then $iSlots = 10 Local $a[$iSlots + 1] $tKey = DllStructCreate("USHORT keys[4]") DllStructSetData($tKey, 1, $IDInit, $eID) DllStructSetData($tKey, 1, BitXOR($iSlots, $IDInit), $eiSlots) $a[$iSlots] = $tKey $vOut = $a ;ConsoleWrite("Created Queue[" & $iSlots & "]" & @CRLF) Return SetError($iErr, $iSlots, $vOut) EndIf ;Circular Queue Logic Switch ($eFQ) Case $_FQ_Error ConsoleWrite("Queue Error: " & $iErr & @CRLF) Return SetError($iErr, 0, $vOut) Case $eFQ_Push If $iItems >= $iSlots Then Return False ;Rollover after last element $aQ[Mod($iItems + $iPos, $iSlots)] = $vOut $iItems += 1 Case $eFQ_Peek If $iItems = 0 Then Return False $vOut = $aQ[$iPos] Return True ; Speed up peek Case $eFQ_Pop If $iItems = 0 Then Return False $vOut = $aQ[$iPos] $iPos += 1 $iItems -= 1 Case $eFQ_Redim If $vOut <= $iSlots or $iItems <> 0 Then Return False If $iItems = 0 Then $iPos = 0 ;Reset to empty $vOut += 10 $aQ[$iSlots] = Default ReDim $aQ[$vOut + 1] $aQ[$vOut] = $tKey DllStructSetData($tKey, 1, BitXOR($vOut, $IDInit), $eiSlots) Case $eFQ_Empty $iItems = 0 Case $eFQ_IsEmpty Return ($iItems = 0) Case $eFQ_IsFull Return ($iItems >= $iSlots) Case $eFQ_Count Return SetExtended($iSlots, $iItems) Case $eFQ_IsInit Return ($iErr = 0) Case Else Return False EndSwitch $iPos = Mod($iPos, $iSlots) ;Rollover after last element DllStructSetData($tKey, 1, $iPos, $eiPos) DllStructSetData($tKey, 1, $iItems, $eiItems) Return SetError($iErr, $iItems, True) EndFunc ;==>FifoQueue ;--Convenience Functions------------------------------- Func FifoQueue_Create($iSlots = 10) Local $aE Return FifoQueue($eFQ_Create, $iSlots, $aE) EndFunc ;==>FifoQueue_Create Func FifoQueue_($eFQ, ByRef $aQ) Local $aE $aE = FifoQueue($eFQ, $aQ, $aE) Return SetError(@error, @extended, $aE) EndFunc ;==>FifoQueue_ ;--Convenience Functions------------------------------- Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now