QBDS

[a740g]

QBDS is a collection of generic data structure libraries for QB64-PE (v4.2+). It provides containers such as queues, lists, stacks, maps, and more.

Backstory

Many programming projects benefit from containers like stacks, lists, queues, and hash maps. However, QB64 does not offer these capabilities natively. It also lacks features like pointers, making the implementation of such data structures challenging, if not impossible.

An interesting discussion on the forum (https://qb64phoenix.com/forum/showthread.php?tid=1547) piqued my interest while I was exploring a hash map implementation for InForm-PE. I could have written wrappers around C++ std containers, but I wanted a solution in pure QB64 to keep the InForm-PE codebase simple.

I set out to implement a generic container library in pure QB64, with these goals:

• Cross-platform compatibility.
  
• No C/C++ code, except for DECLARE LIBRARY when absolutely necessary (e.g., memcpy).
  
• Ease of use with minimal boilerplate.
  
• Multiple instance support without using shared global variables or arrays.
  
• Performance with dynamic growth based on requirements.
  
• Automatic memory management (i.e., containers free themselves when out of scope).
  
• Support for multiple data types, including UDTs.
  
• Unit tests to ensure reliability.
  

To meet these requirements, I implemented everything using QB64 arrays. I considered _MEM, but it has quirks and fails the automatic memory management requirement. Using strings as containers was another idea, but it introduced too many complexities. Arrays aren't perfect either, but they felt cleaner and easier to manage. Yes, I still use strings internally for some operations, but far less than if I had chosen strings as the primary container.

After months of slow development and moving the repo across systems, I believe the library is now stable enough to share. I've hosted it on my private GitHub and am releasing it here for testing and feedback.

Array Library

The Array library provides a generic dynamic array implementation for QB64-PE. It supports storing various data types and automatically resizes itself as needed. Array index always beings at 1.

Usage

To use the Array library, you need to include Array.bi and Array.bm in your project.

Code: (Select All)

'$INCLUDE:'Array.bi'



' Declare a dynamic array of Array

REDIM arr(0) AS Array



' Initialize the array

Array_Initialize arr()



' Add some items

Array_PushBackString arr(), "Hello"

Array_PushBackInteger arr(), 42



' Access items

PRINT Array_GetString(arr(), 1) ' Prints `Hello`

PRINT Array_GetInteger(arr(), 2) ' Print `42`



' Get count

PRINT Array_GetCount(arr()) ' Print `2`



' Remove an item

DIM popped AS INTEGER

popped = Array_PopBackInteger(arr())

PRINT popped ' Prints 42

PRINT Array_GetCount(arr()) ' Prints `1`



' Clean up

Array_Free arr()



'$INCLUDE:'Array.bm'

Notes

• See docs/Array.md for full documentation.
  
• The growth factor is x2, which amortizes the reallocation cost.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  
• Attempting to pop data off of an empty stack will also trigger these errors.
  
• Use Array_GetElementDataType to check the stored type before retrieval to avoid type mismatch errors (when working with mixed data types).
  

HMap Library

The HMap library provides a generic hash map for QB64-PE. It allows you to store and retrieve values of different data types using string keys. The hash map automatically resizes itself as needed.

Usage

To use the HMap library, include HMap.bi and HMap.bm in your project.

Code: (Select All)

'$INCLUDE:'HMap.bi'



' Declare a dynamic array of HMap

REDIM myMap(0) AS HMap



' Initialize the map

HMap_Initialize myMap()



' Set and get values

HMap_SetString myMap(), "name", "John Doe"

HMap_SetInteger myMap(), "age", 30



PRINT HMap_GetString(myMap(), "name")

PRINT HMap_GetInteger(myMap(), "age")



' Free the map

HMap_Free myMap()



'$INCLUDE:'HMap.bm'

Notes

• See docs/HMap.md for full documentation.
  
• Uses FNV-1a for computing hash values. See research/ for some fun stuff.
  
• Growth factor is x2, which amortizes reallocation cost and avoids division (MOD) when reducing the hash to an array index.
  
• Growth triggers at 75% capacity to reduce collisions and maintain performance.
  
• I investigated using buckets, but that would've required multiple arrays, making setup and usage more complex.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  
• Use HMap_GetEntryDataType to check the stored type before retrieval to avoid type mismatch errors (when working with mixed data types).
  

HMap64 Library

The HMap64 library provides a simple, high-performance map implementation for QB64-PE, using _UNSIGNED _INTEGER64 keys. It supports storing multiple data types and automatically resizes as needed.

Usage

To use the HMap64 library, include both HMap64.bi and HMap64.bm in your project.

Code: (Select All)

'$INCLUDE:'HMap64.bi'



' Declare a dynamic array of HMap64

REDIM myMap(0) AS HMap64



' Initialize the map

HMap64_Initialize myMap()



' Set and get values

HMap64_SetString myMap(), 25, "Apple"

HMap64_SetInteger myMap(), 100, 10



PRINT HMap64_GetString(myMap(), 25)

PRINT HMap64_GetInteger(myMap(), 100)



' Free the map

HMap64_Free myMap()



'$INCLUDE:'HMap64.bm'

Notes

• See docs/HMap64.md for full documentation.
  
• This library does not use a traditional hash function. As a result, data access is significantly faster (~6x) compared to HMap.
  
• Use HMap64 instead of HMap if your use case can work with integer keys.
  
• Growth factor is x2, which amortizes reallocation cost and avoids expensive MOD operations.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  
• Use HMap64_GetDataType to check the stored type before retrieval to avoid type mismatch errors (when working with mixed data types).
  

HSet Library

The HSet library provides a generic hash set implementation for QB64-PE. It supports storing various data types and automatically resizes itself as needed.

Usage

To use the HSet library, you need to include HSet.bi and HSet.bm in your project.

Code: (Select All)

'$INCLUDE:'HSet.bi'



' Declare a dynamic array of HSet

REDIM mySet(0) AS HSet



' Initialize the set

HSet_Initialize mySet()



' Add some items

HSet_AddString mySet(), "Apple"

HSet_AddString mySet(), "Banana"

HSet_AddInteger mySet(), 42



' Check for items

PRINT HSet_ContainsString(mySet(), "Apple") ' Prints -1

PRINT HSet_ContainsInteger(mySet(), 123)    ' Prints 0



' Get count

PRINT HSet_GetCount(mySet()) ' Prints 3



' Remove an item

HSet_RemoveString mySet(), "Banana"

PRINT HSet_GetCount(mySet()) ' Prints 2

PRINT HSet_ContainsString(mySet(), "Banana") ' Prints 0 (False)



' Clean up

HSet_Free mySet()



'$INCLUDE:'HSet.bm'

Notes

• See docs/HSet.md for full documentation.
  
• Uses FNV-1a for computing hash values. See research/ for some fun stuff.
  
• Growth factor is x2, which amortizes reallocation cost and avoids division (MOD) when reducing the hash to an array index.
  
• Growth triggers at 75% capacity to reduce collisions and maintain performance.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  

LList Library

The LList library provides a generic doubly-linked list implementation for QB64-PE. It supports storing various data types and automatically resizes itself as needed.

Usage

To use the LList library, you need to include LList.bi and LList.bm in your project.

Code: (Select All)

'$INCLUDE:'LList.bi'



' Declare a dynamic array of LList

REDIM myList(0) AS LList



' Initialize the list

LList_Initialize myList()



' Add elements

LList_PushBackString myList(), "Hello"

LList_PushFrontString myList(), "World"



' Iterate through the list

DIM node AS _UNSIGNED _OFFSET: node = LList_GetFrontNode(myList())

WHILE node

    PRINT LList_GetString(myList(), node)



    node = LList_GetNextNode(myList(), node) ' Move to the next node

WEND



' Free the list

LList_Free myList()



'$INCLUDE:'LList.bm'

Notes

• See docs/LList.md for full documentation.
  
• Growth factor is x2, which amortizes reallocation cost.
  
• Unlike other container libraries, LList may throw "Subscript out of range" errors if you access invalid nodes. Just like QB64 does when accessing an array with an out-of-bounds index.
  
• Use LList_NodeExists to check if a node exists before accessing it.
  
• It may also throw errors from QB64's MK$/CV functions (used internally).
  
• Use LList_GetNodeDataType to verify the stored type before retrieval when working with mixed data types.
  
• Supports forward and backward iteration.
  
• Allows inserting nodes at the head, tail, or before/after any node.
  
• Can be used like a queue or stack, but for pure queue/stack functionality, use the Queue/Stack library (faster and more memory-efficient).
  
• You can make the list circular by connecting the head and tail. See LList_MakeCircular and LList_IsCircular.
  
• Be careful when iterating circular lists. See demos/llist_demo.bas for safe traversal methods.
  
• There are currently no "find" or "sort" functions. However, these can be easily implemented. See LList_SwapNodeValues and the demos/UDT/LList_UDT.bas example.
  

Queue Library

The Queue library provides a generic queue implementation for QB64-PE. It supports storing various data types and automatically resizes itself as needed.

Usage

To use the Queue library, you need to include Queue.bi and Queue.bm in your project.

Code: (Select All)

'$INCLUDE:'Queue.bi'



' Declare a dynamic array of Queue

REDIM myQueue(0) AS Queue



' Initialize the queue

Queue_Initialize myQueue()



' Enqueue and dequeue values

Queue_EnqueueString myQueue(), "Hello"

Queue_EnqueueString myQueue(), "World"

Queue_EnqueueInteger myQueue(), 64



PRINT Queue_DequeueString(myQueue()) ' Prints "Hello"

PRINT Queue_DequeueString(myQueue()) ' Prints "World"

PRINT Queue_DequeueInteger(myQueue()) ' Prints 64



' Free the queue

Queue_Free myQueue()



'$INCLUDE:'Queue.bm'

Notes

• See docs/Queue.md for full documentation.
  
• It is implemented as a ring buffer with a head and a tail pointer.
  
• When full, the capacity is automatically doubled, and the queue is unwrapped.
  
• The growth factor is x2, which amortizes the reallocation cost.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  
• Attempting to dequeue data off of an empty queue will also trigger these errors.
  
• Use Queue_PeekElementDataType to check the stored type before retrieval to avoid type mismatch errors (when working with mixed data types).
  

Stack Library

The Stack library provides a generic stack implementation for QB64-PE. It supports storing various data types and automatically resizes itself as needed.

Usage

To use the Stack library, you need to include Stack.bi and Stack.bm in your project.

Code: (Select All)

'$INCLUDE:'Stack.bi'



' Declare a dynamic array of Stack

REDIM myStack(0) AS Stack



' Initialize the stack

Stack_Initialize myStack()



' Push and pop values

Stack_PushString myStack(), "Hello"

Stack_PushString myStack(), "World"

Stack_PushInteger myStack(), 64



PRINT Stack_PopInteger(myStack()) ' Prints 64

PRINT Stack_PopString(myStack()) ' Prints "World"

PRINT Stack_PopString(myStack()) ' Prints "Hello"



' Free the stack

Stack_Free myStack()



'$INCLUDE:'Stack.bm'

Notes

• See docs/Stack.md for full documentation.
  
• The growth factor is x2, which amortizes the reallocation cost.
  
• The library does not throw custom errors; any errors are those naturally raised by QB64's MK$/CV functions (used internally).
  
• Attempting to pop data off of an empty stack will also trigger these errors.
  
• Use Stack_PeekElementDataType to check the stored type before retrieval to avoid type mismatch errors (when working with mixed data types).
  

Working with UDTs

What's the point of all this if you can't store your own UDTs in a container?
The good news: all QBDS libraries support UDTs with minimal effort.
All you need to do is create simple getter and setter wrapper SUBs for your UDTs, and you're ready to go.
Check out the demos/UDT directory for examples across all container libraries.

Note

• Avoid using variable-length strings in UDTs when working with any QBDS container. You'll save yourself a lot of trouble.
  

Bonus: The Catch test framework.

I borrowed the name and concept from the popular C++ Catch2 unit testing framework because I've been using Catch2 in another project and was impressed by its simplicity and intuitiveness. Inspired by that, I created a minimalistic test framework for QB64-PE, and I'm happy with how it turned out. There's still room for improvement, and I already have ideas for future enhancements, but this framework helped me catch some nasty bugs while developing QBDS.

So, the Catch library provides a lightweight test framework for QB64-PE, inspired by Catch2 for C++. It allows you to write test cases and assertions to verify the correctness of your code.

Usage

To use the Catch library, include Catch.bi, Catch.bm, and optionally CatchError.bi in your project tests.

Code: (Select All)

'$INCLUDE:'Catch.bi'

'$INCLUDE:'CatchError.bi' ' Optional: Enables runtime error handling



TEST_BEGIN_ALL



    TEST_CASE_BEGIN "My Test Case"



        TEST_CHECK 1 = 1, "This should pass"

        TEST_REQUIRE 2 > 1, "This is required"



    TEST_CASE_END



TEST_END_ALL



'$INCLUDE:'Catch.bm'

Including CatchError.bi enables runtime error handling and lets your test program exit cleanly if a runtime error occurs.



Notes:

• See docs/Catch.md for full documentation.
  
• Unlike Catch2, all tests are evaluated because these are SUBs, not macros. I may improve this in the future.
  
• I deliberately chose UPPER_SNAKE_CASE for function names to make them stand out.
  
• Including CatchError.bi enables clean handling of QB64 runtime errors.
  
• It supports timing your tests, so you can use it for simple benchmarks and performance comparisons.
  
• See tests/test_ds.bas for a working demo. Run it from the terminal to view the formatted output.
  

Your feedback is both welcome and appreciated, as I plan to integrate these libraries into InForm-PE.

Cheers!

[a740g]

Update

• Added support for Array, Set, and Queue.
  
• Removed API documentation clutter from the main post.
  
• New download link available in the first post.
  

[justsomeguy]

Great work! I've had to roll my own on most my projects.

[a740g]

Great work! I've had to roll my own on most my projects.

Thanks!