Overview

The CUPS array API provides a high-performance generic array container. The contents of the array container can be sorted and the container itself is designed for optimal speed and memory usage under a wide variety of conditions. Sorted arrays use a binary search algorithm from the last found or inserted element to quickly find matching elements in the array. Arrays created with the optional hash function can often find elements with a single lookup. The cups_array_t type is used when referring to a CUPS array.

The CUPS scheduler (cupsd) and many of the CUPS API functions use the array API to efficiently manage large lists of data.

Managing Arrays

Arrays are created using either the cupsArrayNew, cupsArrayNew2, or cupsArrayNew3 functions. The first function creates a new array with the specified callback function and user data pointer:

#include <cups/array.h>

static int compare_func(void *first, void *second, void *user_data);

void *user_data;
cups_array_t *array = cupsArrayNew(compare_func, user_data);

The comparison function (type cups_arrayfunc_t) is called whenever an element is added to the array and can be NULL to create an unsorted array. The function returns -1 if the first element should come before the second, 0 if the first and second elements should have the same ordering, and 1 if the first element should come after the second.

The "user_data" pointer is passed to your comparison function. Pass NULL if you do not need to associate the elements in your array with additional information.

The cupsArrayNew2 function adds two more arguments to support hashed lookups, which can potentially provide instantaneous ("O(1)") lookups in your array:

#include <cups/array.h>

#define HASH_SIZE 512 /* Size of hash table */

static int compare_func(void *first, void *second, void *user_data);
static int hash_func(void *element, void *user_data);

void *user_data;
cups_array_t *hash_array = cupsArrayNew2(compare_func, user_data, hash_func, HASH_SIZE);

The hash function (type cups_ahash_func_t) should return a number from 0 to (hash_size-1) that (hopefully) uniquely identifies the element and is called whenever you look up an element in the array with cupsArrayFind. The hash size is only limited by available memory, but generally should not be larger than 16384 to realize any performance improvement.

The cupsArrayNew3 function adds copy and free callbacks to support basic memory management of elements:

#include <cups/array.h>

#define HASH_SIZE 512 /* Size of hash table */

static int compare_func(void *first, void *second, void *user_data);
static void *copy_func(void *element, void *user_data);
static void free_func(void *element, void *user_data);
static int hash_func(void *element, void *user_data);

void *user_data;
cups_array_t *array = cupsArrayNew3(compare_func, user_data, NULL, 0, copy_func, free_func);

cups_array_t *hash_array = cupsArrayNew3(compare_func, user_data, hash_func, HASH_SIZE, copy_func, free_func);

Once you have created the array, you add elements using the cupsArrayAdd cupsArrayInsert functions. The first function adds an element to the array, adding the new element after any elements that have the same order, while the second inserts the element before others with the same order. For unsorted arrays, cupsArrayAdd appends the element to the end of the array while cupsArrayInsert inserts the element at the beginning of the array. For example, the following code creates a sorted array of character strings:

#include <cups/array.h>

/* Use strcmp() to compare strings - it will ignore the user_data pointer */
cups_array_t *array = cupsArrayNew((cups_array_func_t)strcmp, NULL);

/* Add four strings to the array */
cupsArrayAdd(array, "One Fish");
cupsArrayAdd(array, "Two Fish");
cupsArrayAdd(array, "Red Fish");
cupsArrayAdd(array, "Blue Fish");

Elements are removed using the cupsArrayRemove function, for example:

#include <cups/array.h>

/* Use strcmp() to compare strings - it will ignore the user_data pointer */
cups_array_t *array = cupsArrayNew((cups_array_func_t)strcmp, NULL);

/* Add four strings to the array */
cupsArrayAdd(array, "One Fish");
cupsArrayAdd(array, "Two Fish");
cupsArrayAdd(array, "Red Fish");
cupsArrayAdd(array, "Blue Fish");

/* Remove "Red Fish" */
cupsArrayRemove(array, "Red Fish");

Finally, you free the memory used by the array using the cupsArrayDelete function. All of the memory for the array and hash table (if any) is freed, however CUPS does not free the elements unless you provide copy and free functions.

Finding and Enumerating Elements

CUPS provides several functions to find and enumerate elements in an array. Each one sets or updates a "current index" into the array, such that future lookups will start where the last one left off:

cupsArrayFind
Returns the first matching element.
cupsArrayFirst
Returns the first element in the array.
cupsArrayIndex
Returns the Nth element in the array, starting at 0.
cupsArrayLast
Returns the last element in the array.
cupsArrayNext
Returns the next element in the array.
cupsArrayPrev
Returns the previous element in the array.

Each of these functions returns NULL when there is no corresponding element. For example, a simple for loop using the cupsArrayFirst and cupsArrayNext functions will enumerate all of the strings in our previous example:

#include <cups/array.h>

/* Use strcmp() to compare strings - it will ignore the user_data pointer */
cups_array_t *array = cupsArrayNew((cups_array_func_t)strcmp, NULL);

/* Add four strings to the array */
cupsArrayAdd(array, "One Fish");
cupsArrayAdd(array, "Two Fish");
cupsArrayAdd(array, "Red Fish");
cupsArrayAdd(array, "Blue Fish");

/* Show all of the strings in the array */
char *s;
for (s = (char *)cupsArrayFirst(array); s != NULL; s = (char *)cupsArrayNext(array))
  puts(s);