| Header | cups/array.h |
|---|---|
| Library | -lcups |
| See Also | Programming: Introduction to CUPS Programming |
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.
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.
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:
cupsArrayFindcupsArrayFirstcupsArrayIndexcupsArrayLastcupsArrayNextcupsArrayPrevEach 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);
Add an element to the array.
int cupsArrayAdd (
cups_array_t *a,
void *e
);
1 on success, 0 on failure
When adding an element to a sorted array, non-unique elements are appended at the end of the run of identical elements. For unsorted arrays, the element is appended to the end of the array.
Clear the array.
void cupsArrayClear (
cups_array_t *a
);
This function is equivalent to removing all elements in the array. The caller is responsible for freeing the memory used by the elements themselves.
Get the number of elements in the array.
int cupsArrayCount (
cups_array_t *a
);
Number of elements
Return the current element in the array.
void *cupsArrayCurrent (
cups_array_t *a
);
Element
The current element is undefined until you call cupsArrayFind,
cupsArrayFirst, or cupsArrayIndex, or cupsArrayLast.
Free all memory used by the array.
void cupsArrayDelete (
cups_array_t *a
);
The caller is responsible for freeing the memory used by the elements themselves.
Duplicate the array.
cups_array_t *cupsArrayDup (
cups_array_t *a
);
Duplicate array
Find an element in the array.
void *cupsArrayFind (
cups_array_t *a,
void *e
);
Element found or NULL
Get the first element in the array.
void *cupsArrayFirst (
cups_array_t *a
);
First element or NULL if the array is empty
Get the index of the current element.
int cupsArrayGetIndex (
cups_array_t *a
);
Index of the current element, starting at 0
The current element is undefined until you call cupsArrayFind,
cupsArrayFirst, or cupsArrayIndex, or cupsArrayLast.
Get the index of the last inserted element.
int cupsArrayGetInsert (
cups_array_t *a
);
Index of the last inserted element, starting at 0
Get the N-th element in the array.
void *cupsArrayIndex (
cups_array_t *a,
int n
);
N-th element or NULL
Insert an element in the array.
int cupsArrayInsert (
cups_array_t *a,
void *e
);
0 on failure, 1 on success
When inserting an element in a sorted array, non-unique elements are inserted at the beginning of the run of identical elements. For unsorted arrays, the element is inserted at the beginning of the array.
Get the last element in the array.
void *cupsArrayLast (
cups_array_t *a
);
Last element or NULL if the array is empty
Create a new array.
cups_array_t *cupsArrayNew (
cups_array_func_t f,
void *d
);
NULL for an unsorted arrayNULLArray
The comparison function ("f") is used to create a sorted array. The function
receives pointers to two elements and the user data pointer ("d") - the user
data pointer argument can safely be omitted when not required so functions
like strcmp can be used for sorted string arrays.
Create a new array with hash.
cups_array_t *cupsArrayNew2 (
cups_array_func_t f,
void *d,
cups_ahash_func_t h,
int hsize
);
NULL for an unsorted arrayNULLNULL for unhashed lookupsArray
The comparison function ("f") is used to create a sorted array. The function
receives pointers to two elements and the user data pointer ("d") - the user
data pointer argument can safely be omitted when not required so functions
like strcmp can be used for sorted string arrays.
The hash function ("h") is used to implement cached lookups with the
specified hash size ("hsize").
Create a new array with hash and/or free function.
cups_array_t *cupsArrayNew3 (
cups_array_func_t f,
void *d,
cups_ahash_func_t h,
int hsize,
cups_acopy_func_t cf,
cups_afree_func_t ff
);
NULL for an unsorted arrayNULLNULL for unhashed lookupsArray
The comparison function ("f") is used to create a sorted array. The function
receives pointers to two elements and the user data pointer ("d") - the user
data pointer argument can safely be omitted when not required so functions
like strcmp can be used for sorted string arrays.
The hash function ("h") is used to implement cached lookups with the
specified hash size ("hsize").
The copy function ("cf") is used to automatically copy/retain elements when
added or the array is copied.
The free function ("cf") is used to automatically free/release elements when
removed or the array is deleted.
Get the next element in the array.
void *cupsArrayNext (
cups_array_t *a
);
Next element or NULL
This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
The next element is undefined until you call cupsArrayFind,
cupsArrayFirst, or cupsArrayIndex, or cupsArrayLast
to set the current element.
Get the previous element in the array.
void *cupsArrayPrev (
cups_array_t *a
);
Previous element or NULL
This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
The previous element is undefined until you call cupsArrayFind,
cupsArrayFirst, or cupsArrayIndex, or cupsArrayLast
to set the current element.
Remove an element from the array.
int cupsArrayRemove (
cups_array_t *a,
void *e
);
1 on success, 0 on failure
If more than one element matches "e", only the first matching element is
removed.
The caller is responsible for freeing the memory used by the
removed element.
Reset the current element to the last cupsArraySave.
void *cupsArrayRestore (
cups_array_t *a
);
New current element
Mark the current element for a later cupsArrayRestore.
int cupsArraySave (
cups_array_t *a
);
1 on success, 0 on failure
The current element is undefined until you call cupsArrayFind,
cupsArrayFirst, or cupsArrayIndex, or cupsArrayLast
to set the current element.
The save/restore stack is guaranteed to be at least 32 elements deep.
Return the user data for an array.
void *cupsArrayUserData (
cups_array_t *a
);
User data
Array element copy function
typedef void *(*cups_acopy_func_t)(void *element, void *data);
Array element free function
typedef void (*cups_afree_func_t)(void *element, void *data);
Array hash function
typedef int (*cups_ahash_func_t)(void *element, void *data);
Array comparison function
typedef int (*cups_array_func_t)(void *first, void *second, void *data);
CUPS array type
typedef struct _cups_array_s cups_array_t;