Usage

This section contains an overview of some of the common enumerations used in the library, along with some descriptions on how most data structures can be constructed, destructed, cleared, as well as many other common operations shared among the data structures.

Enumerations

Defined under the cds_common.h header file are some enumerations used in the library that are worth noting. Many of these enumerations are used as return values in most of the API calls for all of the data structures. More detail on this is outlined in below sections.

Booleans

The Boolean enumeration is used as a return value for operations whose result can be described as true or false (or where the outcome can only be one of two things). The boolean is mostly used for syntactic sugar and can be used to make basic conditionals in C more readable. In basic C, the value 0 is considered false, and !0 is considered true, so the boolean FALSE can be used in place of 0, and TRUE for !0.

Name	Description
FALSE	The condition is regarded as 'false'.
TRUE	The condition is regarded as 'true'.

Statuses

For many of the operations, a simple true/false return value may not be enough to describe the result of the operation. For example, if an operation fails, a simple false value won't really describe the reason the operation failed in the first place. The operation could have failed due to a failed malloc() call, or the caller may have passed an invalid index, or the item could not be found. Therefore, many of the data structure operations return a Status enumeration. Each of these statuses and what they represent are listed below:

Name	Description
OK	Operation was successful and no additional checks are needed.
INSERTED	Status reserved for the put() method for the HashMap and TreeMap. Indicates that the key-value entry did not exists before the insert operation, but has now been successfully inserted.
REPLACED	Status reserved for the put() method for the HashMap and TreeMap. Indicates that the key-value entry does exist before the insert operation, and the new specified value has successfully replaced the old value.
ALREADY_EXISTS	Operation could not be completed due to an already existing entry in the structure. This is for set-like structures where only one of a kind elements are allowed, but the caller has attempted to insert an identical item.
STRUCT_EMPTY	Operation could not be completed due to an empty structure. This is most common for retrieval and removal operations on empty structures that have no elements to search, retrieve, or delete.
STRUCT_FULL	Operation could not be completed due to a full structure. This is most common for insertion operations on structures that have a capacity on the number of elements it may contain at once.
ITER_END	The previous call to iterator_next() did not yield an item since the current iteration has ended.
INDEX_INVALID	Operation could not be completed due to an invalid index specified. This is for data structures whose elements may be accessed via a specified array index. The index a caller may specify could fall outside the valid range (i.e. the value is below 0 or greater than the largest index allowed).
NOT_FOUND	Operation could not be completed due to a missing entry. This is for structure operations where a caller may search for a specific item that does not exist. Think of a key missing in a HashMap, an entry not found in a set, etc.
ALLOC_FAILURE	A call to any of the dynamic memory allocator methods (i.e. malloc(), realloc(), etc.) has failed during instantiation, additions, resizing, or any other operation that requires allocating heap memory.

Constructors

When creating a new instance of an ADT, you will need to declare a pointer to the structure type that you plan to use, then provide the pointer of that variable to the constructor method for that structure. This should always be the first parameter for each of the constructor methods. Depending on what structure you are using, you may also need to provide additional parameters such as a capacity, pointer to a comparator function, etc. The return value for the constructor is a Status enumeration indicating if the structure was successfully initialized or not. For more information regarding the constructors and the possible & default parameters allowed, refer to the documentation in the header file or the structure's API page.

An example of constructing the BoundedStack is shown below. The second parameter in this example is the capacity for the newly constructed stack. In this case, a value of 0 or below will result in the stack being initialized with a default capacity that should be documented in the header file.

BoundedStack *stack;
Status status = boundedstack_new(&stack, 16L);

if (status == ALLOC_FAILURE) {
    // Do some work here, maybe print an error message?
    return -1;
}

// At this point, status is OK, stack is successfully created

Destructors

Since no garbage collection exists in C, we are responsible for managing all memory allocated from the heap. This includes the structure itself, along with all void * pointers stored inside our ADT. Therefore, once an ADT is no longer needed, you should invoke its destructor method to free all of its memory back to the heap. If you have allocated memory for the void * elements stored inside the ADT, you may also provide a custom destructor method along as a parameter in each of the destructor methods that will be invoked on each of the items prior to the ADT destruction. If your items were not allocated from the heap, you may pass NULL to skip this step.

For example, a BoundedStack may store char * elements that have been allocated from the heap via the char *strdup(const char *) method. Rather than popping each item from the stack to invoke free() on it, we can simply pass free() as the destructor function. In this example, the BoundedStack is destroyed, along with each existing char * element currently present.

/*
 * Destructor method to free the stack items. Simply used to mask the compiler warning
 * for unmatched method signature.
 */
static void freeElement(void *item) {
    free((char *)item);
}

/*
 * Destroys the specified bounded stack.
 */
static void destroyStack(BoundedStack *stack) {
    boundedstack_destroy(stack, freeElement);
}

Clearing

In some cases, you may not want to destroy the ADT itself, but clear out all of its elements. Each ADT comes with a clear method that does just this. Just like the destructor methods, an additional parameter for a destructor for each of the items stored is available for each of the clear methods. You should provide a function for this if the items in your ADT were allocated from the heap. Otherwise, you may also pass NULL for this parameter.

In this example, we have a BoundedStack containing char * items that were allocated via the char *strdup(const char *) method. The clear method will remove all items from the stack and, in addition, invoke the free() method on each item to avoid memory leaks.

/*
 * Destructor method to free the stack items. Simply used to mask the compiler warning
 * for unmatched method signature.
 */
static void freeElement(void *item) {
    free((char *)item);
}

/*
 * Clears the specified bounded stack of all its elements.
 */
static void clearStack(BoundedStack *stack) {
    boundedstack_clear(stack, freeElement);
}

isEmpty, isFull, size, capacity

Sometimes you may need to know the size of an ADT or if an ADT is currently empty. Every ADT comes with a isEmpty() and size() method. Bounded structures will also provide isFull() and capacity() methods as well. These methods used by almost every popular data structure implementation are pretty self-explanatory. A long is returned indicating the size and capacity of your ADTs, and a Boolean enumeration is returned indicating if the structure is currently empty or full.

/*
 * Returns string representation of the specified boolean.
 */
static char *printBoolean(Boolean boolean) {
    return boolean == TRUE ? "TRUE" : "FALSE";
}

/*
 * Prints out the specified stack's size, capacity, and other statistics.
 */
static void printStatus(BoundedStack *stack) {
    printf("isEmpty: %s\n" printBoolean( boundedstack_isEmpty(stack) ));
    printf("isFull: %s\n" printBoolean( boundedstack_isFull(stack) ));
    printf("Size: %ld\n" boundedstack_size(stack));
    printf("Capacity: %ld\n" boundedstack_capacity(stack));
}

Arrays

In many of Java's classes, there exists the toArray() method that returns an array of all the structure's elements in proper ordering. Each of the ADTs in this library also come with this function. The array returned will provide the collection of items in proper ordering in relation to the ADT. For example, a stack's elements are typically accessed and ordered from the top item down to the bottom item. Therefore, when we call toArray(), we can expect the items in the resulting array to be ordered in the same way. This means that the first index will be the top item in the stack, the second index points to the second from the top, and so forth. Finally, the last index will point to the bottom of the stack. Each ADT's ordering is different, and will result in different orderings for each of their respective toArray() method. Refer to the header documentation for how the ADT's elements are ordered.

In each of the toArray methods, the return value is a Status indicating whether allocation was successful or not. One of the parameters is also an indirect pointer to an Array struct where the array of items will be loaded. If the method was successful, you should be able to access the array items, but you must ensure you free the array structure and the array when finished. See the example code below:

/*
 * Prints the representation of the stack.
 */
static void printStack(BoundedStack *stack) {

    Array *array;
    Status status = boundedstack_toArray(stack, &array);

    // Checks for failed statuses
    if (status == ALLOC_FAILURE) {
        printf("malloc() failed.\n");
        return;
    } else if (status == STRUCT_EMPTY) {
        printf("stack is currently empty.\n");
        return;
    }

    // Loop through array of elements, printing each one
    long i;
    for (i = 0L; i < array->len; i++) {
        printf("%s\n", array->items[i]);
    }

    // Need to destroy the array when we're done
    FREE_ARRAY(array);
}

⚠️ A warning about arrays

Note that the array itself is a shallow copy of the ADT. This means that any modifications done directly to any of the array items will reflect back into the ADT itself. Directly modifying, nullifying, or anything else on the array items can produce unexpected or disastrous results in your application. Perform at your own risk.

Iterators

Along with the toArray method, there also exists an iterator method for each ADT. With arrays, you can directly access any of the items you want through an index between 0 and the size minus one. However, with iterators, you are restricted to accessing only the element that the iterator is currently pointing to. Once you are done accessing the iterator's item, you invoke the next() method to proceed to the next item in the iteration. This process continues until the next call to next() fails, or the iterator's hasNext() method returns FALSE. The order of the iterated items will be the exact same as they are in the array generated from the toArray() method.

An example of iterating over the BoundedStack items is shown below:

/*
 * Prints the representation of the stack.
 */
static void printStack(BoundedStack *stack) {

    Iterator *iter;
    Status status = boundedstack_iterator(stack, &iter);

    // Checks for failed statuses
    if (status == ALLOC_FAILURE) {
        printf("malloc() failed.\n");
        return;
    } else if (status == STRUCT_EMPTY) {
        printf("stack is currently empty.\n");
        return;
    }

    // Iterate through the items
    char *item
    while (iterator_hasNext(iter)) {
        (void)iterator_next(iter, (void **)&item);
        printf("%s\n", item);
    }

    // Need to destroy iterator when we're done
    iterator_destroy(iter);
}

ℹ️ A note about thread-safe iterators

With thread-safe iterators, there is a possible issue that the ADT could change during the iteration. Therefore, the concurrent iterator obtains an exclusive lock on the ADT after it is constructed, and releases it back once it is destroyed.

Locking & Unlocking

In each of the thread-safe ADT implementations exists a lock() and unlock() function. In cases where one thread may need some exclusive access to the ADT, these function pairs are available to provide this. Since the lock internally held by the concurrent ADTs is a recursive lock, each thread can call lock() safely, but you should make sure that an equal number of unlock() invocations are represent so one thread doesn't retain exclusive access.

Check this example shown below:

static void addItem(BoundedStack *stack, void *item) {

    // Request exclusive access
    ts_boundedstack_lock(stack);

    // Only add the item if not currently full
    if (ts_boundedstack_isFull(stack)) {
        printf("Stack is currently full.\n");
    } else {
        (void)ts_boundedstack_push(stack, item);
    }

    // Releases the exclusive lock
    ts_boundedstack_unlock(stack);
}