The MemSL for C and C++

Includes a complete data structures/collection classes library, memory tracing, memory debugging, entry/exit tracing, exception handling, definable memory handlers, built-in threads support and much more.

Memory Structures Library (MemSL), Version 4.0

• Single, Double, and Circular Linked Lists
• AVL Balanced and Threaded Binary Trees
• Dynamic Hashing Tables
• Stacks, Queues and Dequeues (using arrays or linked lists)
• Sets (Pascal implementation, with union, difference, intersection, etc.)
• Bags, Tables and Dictionaries
• Priority Heaps (uses the MemSL multi-dimensional array allocator)
• Priority Search Queue
• Data Handling and User Defined Functions
• Using Multiple MemSL Data Structures to Index the same Data
• Portability

Memory Debugging, Error Handling and Entry/Exit Tracing

• Memory Tracing/Debugging (C Only)
• Runtime Memory Tracing/Debugging (C Only)
• Definable Memory Handlers (C Only)
• Error/Warning Message Handlers
• Entry/Exit Source Code Tracing/Debugging
• Runtime Entry/Exit Source Code Tracing/Debugging

View/Download a Few Freebies From Version 4.0

• View/Download the priority heap macros used by the MemSL
• View/Download some very useful bit manipulation macros used by the MemSL

The MemSL has implementations of structures (i.e. AVL trees, threaded trees, dynamic hashing) that are extremely hard to find and far harder to implement.

C Overview of the Memory Structures Library (MemSL)

The Memory Structures Library, MemSL for short, is a library of useful routines allowing the efficient use of complex data structures in C. The MemSL contains routines for managing:

• Multi-Dimensional Dynamically Allocated Arrays
• Single Linked Lists
• Double Linked Lists
• Circular Linked Lists
• Cut, Copy and Paste with Linked Lists
• Multiple Positional Pointers to Linked Lists
• Stacks
• Queues
• Dequeues
• Sets
• Bags
• Tables
• Dictionaries
• Hash Tables with Separate Chaining
• Hash Tables with User-Defined Paging
• Hash Tables with Dynamic Paging
• Binary Search Trees
• Threaded Binary Search Trees
• AVL Balanced Binary Search Trees
• AVL Balanced Threaded Binary Search Trees
• Priority Heaps
• Fully Dynamic Priority Search Queues

As you can see this is an impressive list of data structures. But even more impressive is the fact that the MemSL leaves no corners unturned. Each of the MemSL data structures are designed with the format known as an Abstract Data Type (ADT). ADT's are similar in concept to classes in object oriented languages such as C++.

Basically ADT's usually have a structure and several functions that operate on the structure. Under no circumstances is the structure to be accessed directly. If an item needs to change in the structure, a function is used to change the item. Likewise, if an item in the structure needs to be accessed, a function is used to access the item.

ADT's usually have a function that sets up the ADT and returns a pointer to a data structure that will be used by the remaining functions in the ADT. ADT's also have a function used for cleaning up the data in the ADT structure. With the MemSL these two functions are always Open() and Close().

Basically ADT's allow the programmer to arrange the source in such a way as to make changes simpler as well as providing an easy to understand user interface. They also allow a logical connection between the data being used and the functions that manipulate the data. A brief description of ADT's is given here because the MemSL follows this practice strictly. All MemSL routines are part of an Abstract Data Type.

The MemSL also follows strict naming conventions. For every function in the MemSL, you can expect the following naming convention:

    WB[ADT]Function(WB[ADT] *adtptr, ...);

Where [ADT] is replaced with a name that closely resembles what the group of functions do. And "Function" describes what the given function does within the ADT. For example, following is a partial list of functions used to add items to the different MemSL data structures:

    WBQUEUE *queue;
    queue = WBQueueOpen(NULL,0,0,0);
    WBQueueAdd(queue,"Item");
    
    WBHASH *hash;
    hash = WBHashOpen(NULL,100);
    WBHashAdd(hash,"Item");
    
    WBTREE *tree;
    tree = WBTreeOpen(NULL);
    WBTreeAdd(tree,"Item");

Following are some additional highlights of the MemSL:

• All MemSL data structure ADT's can be used to store any type of data.
• All MemSL data structure ADT's can be used together to multiply index your data (i.e. you can have a linked list (for traversing) and an AVL tree (for searching) working with the same data at the same time).
• Since no direct contact with the actual data structures is required, the MemSL is very easy to use, even for programmers with little or no knowledge of data structures.
• The MemSL comes with an easy to read manual (200+ pages) covering all functions, and when and where to use them.
• All decisions about the stored data are made by the programmer through user-defined functions.
• The MemSL is multi-thread safe. With built in locking abilities where needed.
• The MemSL also supports read only thread locks where possible.
• User-defined functions can be defined for threads locking with WB[ADT]LockF(), WB[ADT]UnlockF(), WB[ADT]RLockF() and WB[ADT]RUnlockF().

And following are some highlights regarding specific data structures provided by the MemSL:

• Dynamic arrays of any size and any number of dimensions can be allocated at any time.
• Stacks, queues, and dequeues can use linked lists or arrays.
• When using stacks, queues and dequeues with arrays, you can define a limit to the size of the stack, queue or dequeue which creates what is known as a circular ring buffer.
• Cut, copy, and paste with single or double lists.
• Linked lists can be circular
• Linked Lists can also be sorted.
• Dynamic hashing tables allow the table size to grow and shrink as needed.
• MemSL Sets provide a full Pascal style implementation including: IsMember(), Union(), Intersection(), Difference(), Subset(), Superset(), etc.
• AVL balanced trees allow fast and efficient searching.
• Threaded trees allow for linked list like traversing abilities with get first, get last, get next, get previous, get equal, get equal or greater, get less than, and get equal or less than, as well as, having the same searching speed and abilities expected with trees.
• AVL balanced trees can find any item in a tree containing four billion items with only 32 comparisons.
• The MemSL provides two types of priority queues: priority heaps (using arrays) and fully dynamic and searchable, priority search trees.

Included with the MemSL are some routines that make debugging programs much simpler. While there is no substitute for having a full screen debugger, there are some things full screen debuggers don't usually help with. One of these is memory.

As C programmers we know that half our problems and bugs are due to dynamic memory usage or more likely, the invalid use there of. Therefore, the MemSL provides a full featured dynamic memory tracing facility with the following abilities:

• Zero byte allocations are logged.
• All allocations are tracked so that they can later be matched up with their subsequent frees.
• If an item is allocated and not later freed, a message indicating the error is logged at program termination.
• Null pointer frees are caught and logged.
• Frees that cannot be matched with an earlier allocation are caught and logged.
• Memory region overwrites are monitored on both sides of the allocated region.
• The allocator and deallocator functions can be user-defined.
• The message/errors logging can be user-defined.
• Malloc(), calloc(), realloc(), and free() can be user-defined memory handlers.
• Any user-defined function for allocation or deallocation can be incorporated into the MemSL memory handlers.
• Comments consisting of: Offending function, module name and line number are associated with each allocation and free so the problem is easily located in the source code.

Since full screen debugging is not always an option and many times the programs we are fixing are at a remote location or in production and at a customer site, the MemSL provides a simple means of getting debug information from your programs without a debugger.

The MemSL provides this debugging facility through what is known as entry/exit tracing. This simply allows the programmer to add additional information to the program source that is used by the MemSL to provide a detailed trace of what the program is doing. All entry/exit tracing abilities are turned on with environment variables and by default are turned off. Following are some highlights of the MemSL entry/exit tracing facility:

• Function entry tracing with arguments
• Function exit tracing with return values
• Tracing provides easy to read comments with source module name and line number information for each entry in the trace file
• Tracing provides date, time and trace level information with time down to the millisecond (depending on the granularity your system provides) for each tracing entry
• Tracing will automatically print the command line arguments of a program at startup
• Tracing will also automatically print the programs current environment at startup
• Tracing provides the ability to completely list all variables with a printf() style format, for easy reading
• Tracing provides the ability to completely list all variables with a hexadecimal dump format, allowing binary data to be dumped
• Tracing allows for variable watches, which will dump in hexadecimal format when ever the variable changes and the watches are automatically removed when leaving a function
• The MemSL allows for the grouping of functions and modules so that specific areas of a program can be traced, with out tracing the entire program
• All entry/exit tracing options are controlled by environment variables
• Entry/Exit tracing creates a trace file with C style syntax complete with braces and indentation so the programmer/debugger can easily locate the programs problem
• Since all programmer accessible entry/exit tracing functionality is provided through macros, all programs using entry/exit tracing can easily be compiled with or without entry/exit tracing, with out having to change a single line of source code

C++ Overview of the Memory Structures Library (MemSL)

The Memory Structures Library, MemSL for short, is a library of useful routines allowing the efficient use of complex data structures in C++. The MemSL contains routines for managing:

• Multi-Dimensional Dynamically Allocated Arrays
• Single Linked Lists
• Double Linked Lists
• Circular Linked Lists
• Cut, Copy and Paste with Linked Lists
• Multiple Positional Pointers to Linked Lists
• Stacks
• Queues
• Dequeues
• Sets
• Bags
• Tables
• Dictionaries
• Hash Tables with Separate Chaining
• Hash Tables with User-Defined Paging
• Hash Tables with Dynamic Paging
• Binary Search Trees
• Threaded Binary Search Trees
• AVL Balanced Binary Search Trees
• AVL Balanced Threaded Binary Search Trees
• Priority Heaps
• Fully Dynamic Priority Search Queues

As you can see this is an impressive list of data structures. But even more impressive is the fact that the MemSL leaves no corners unturned. Following are some additional highlights of the MemSL:

• All MemSL data structure classes can be used to store any type of data.
• All MemSL data structure classes can be used together to multiply index your data (i.e. you can have a linked list (for traversing) and an AVL tree (for searching) working with the same data at the same time).
• Since no direct contact with the actual data structures is required, the MemSL is very easy to use, even for programmers with little or no knowledge of data structures.
• The MemSL comes with an easy to read manual (200+ pages) covering all functions, and when and where to use them.
• All decisions about the stored data are made by the programmer through user-defined functions.
• The MemSL is multi-thread safe. With built in locking abilities where needed.
• The MemSL also supports read only thread locks where possible.
• User-defined functions can be defined for threads locking.

And following are some highlights regarding specific data structures provided by the MemSL:

• Dynamic arrays of any size and any number of dimensions can be allocated at any time.
• Stacks, queues, and dequeues can use linked lists or arrays.
• When using stacks, queues and dequeues with arrays, you can define a limit to the size of the stack, queue or dequeue which creates what is known as a circular ring buffer.
• Cut, copy, and paste with single or double lists.
• Linked lists can be circular
• Linked Lists can also be sorted.
• Dynamic hashing tables allow the table size to grow and shrink as needed.
• MemSL Sets provide a full Pascal style implementation including: IsMember(), Union(), Intersection(), Difference(), Subset(), Superset(), etc.
• AVL balanced trees allow fast and efficient searching.
• Threaded trees allow for linked list like traversing abilities with get first, get last, get next, get previous, get equal, get equal or greater, get less than, and get equal or less than, as well as, having the same searching speed and abilities expected with trees.
• AVL balanced trees can find any item in a tree containing four billion items with only 32 comparisons.
• The MemSL provides two types of priority queues: priority heaps (using arrays) and fully dynamic and searchable, priority search trees.

Since full screen debugging is not always an option and many times the programs we are fixing are at a remote location or in production and at a customer site, the MemSL provides a simple means of getting debug information from your programs without a debugger.

The MemSL provides this debugging facility through what is known as entry/exit tracing. This simply allows the programmer to add additional information to the program source that is used by the MemSL to provide a detailed trace of what the program is doing. All entry/exit tracing abilities are turned on with environment variables and by default are turned off. Following are some highlights of the MemSL entry/exit tracing facility:

• Function entry tracing with arguments
• Function exit tracing with return values
• Tracing provides easy to read comments with source module name and line number information for each entry in the trace file
• Tracing provides date, time and trace level information with time down to the millisecond (depending on the granularity your system provides) for each tracing entry
• Tracing will automatically print the command line arguments of a program at startup
• Tracing will also automatically print the programs current environment at startup
• Tracing provides the ability to completely list all variables with a printf() style format, for easy reading
• Tracing provides the ability to completely list all variables with a hexadecimal dump format, allowing binary data to be dumped
• Tracing allows for variable watches, which will dump in hexadecimal format when ever the variable changes and the watches are automatically removed when leaving a function
• The MemSL allows for the grouping of functions and modules so that specific areas of a program can be traced, with out tracing the entire program
• All entry/exit tracing options are controlled by environment variables
• Entry/Exit tracing creates a trace file with C++ style syntax complete with braces and indentation so the programmer/debugger can easily locate the programs problem
• Since all programmer accessible entry/exit tracing functionality is provided through macros, all programs using entry/exit tracing can easily be compiled with or without entry/exit tracing, with out having to change a single line of source code