1<!-- 2 Array API introduction for CUPS. 3 4 Copyright 2007-2011 by Apple Inc. 5 Copyright 1997-2006 by Easy Software Products, all rights reserved. 6 7 These coded instructions, statements, and computer programs are the 8 property of Apple Inc. and are protected by Federal copyright 9 law. Distribution and use rights are outlined in the file "LICENSE.txt" 10 which should have been included with this file. If this file is 11 file is missing or damaged, see the license at "http://www.cups.org/". 12--> 13 14<h2 class='title'><a name='OVERVIEW'>Overview</a></h2> 15 16<p>The CUPS array API provides a high-performance generic array container. 17The contents of the array container can be sorted and the container itself is 18designed for optimal speed and memory usage under a wide variety of conditions. 19Sorted arrays use a binary search algorithm from the last found or inserted 20element to quickly find matching elements in the array. Arrays created with the 21optional hash function can often find elements with a single lookup. The 22<a href='#cups_array_t'><code>cups_array_t</code></a> type is used when 23referring to a CUPS array.</p> 24 25<p>The CUPS scheduler (<tt>cupsd</tt>) and many of the CUPS API 26functions use the array API to efficiently manage large lists of 27data.</p> 28 29<h3><a name='MANAGING_ARRAYS'>Managing Arrays</a></h3> 30 31<p>Arrays are created using either the 32<a href='#cupsArrayNew'><code>cupsArrayNew</code></a>, 33<a href='#cupsArrayNew2'><code>cupsArrayNew2</code></a>, or 34<a href='#cupsArrayNew2'><code>cupsArrayNew3</code></a> functions. The 35first function creates a new array with the specified callback function 36and user data pointer:</p> 37 38<pre class='example'> 39#include <cups/array.h> 40 41static int compare_func(void *first, void *second, void *user_data); 42 43void *user_data; 44<a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew'>cupsArrayNew</a>(compare_func, user_data); 45</pre> 46 47<p>The comparison function (type 48<a href="#cups_arrayfunc_t"><code>cups_arrayfunc_t</code></a>) is called 49whenever an element is added to the array and can be <code>NULL</code> to 50create an unsorted array. The function returns -1 if the first element should 51come before the second, 0 if the first and second elements should have the same 52ordering, and 1 if the first element should come after the second.</p> 53 54<p>The "user_data" pointer is passed to your comparison function. Pass 55<code>NULL</code> if you do not need to associate the elements in your array 56with additional information.</p> 57 58<p>The <a href='#cupsArrayNew2'><code>cupsArrayNew2</code></a> function adds 59two more arguments to support hashed lookups, which can potentially provide 60instantaneous ("O(1)") lookups in your array:</p> 61 62<pre class='example'> 63#include <cups/array.h> 64 65#define HASH_SIZE 512 /* Size of hash table */ 66 67static int compare_func(void *first, void *second, void *user_data); 68static int hash_func(void *element, void *user_data); 69 70void *user_data; 71<a href='#cups_array_t'>cups_array_t</a> *hash_array = <a href='#cupsArrayNew2'>cupsArrayNew2</a>(compare_func, user_data, hash_func, HASH_SIZE); 72</pre> 73 74<p>The hash function (type 75<a href="#cups_ahash_func_t"><code>cups_ahash_func_t</code></a>) should return a 76number from 0 to (hash_size-1) that (hopefully) uniquely identifies the 77element and is called whenever you look up an element in the array with 78<a href='#cupsArrayFind'><code>cupsArrayFind</code></a>. The hash size is 79only limited by available memory, but generally should not be larger than 8016384 to realize any performance improvement.</p> 81 82<p>The <a href='#cupsArrayNew3'><code>cupsArrayNew3</code></a> function adds 83copy and free callbacks to support basic memory management of elements:</p> 84 85<pre class='example'> 86#include <cups/array.h> 87 88#define HASH_SIZE 512 /* Size of hash table */ 89 90static int compare_func(void *first, void *second, void *user_data); 91static void *copy_func(void *element, void *user_data); 92static void free_func(void *element, void *user_data); 93static int hash_func(void *element, void *user_data); 94 95void *user_data; 96<a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew3'>cupsArrayNew3</a>(compare_func, user_data, NULL, 0, copy_func, free_func); 97 98<a href='#cups_array_t'>cups_array_t</a> *hash_array = <a href='#cupsArrayNew3'>cupsArrayNew3</a>(compare_func, user_data, hash_func, HASH_SIZE, copy_func, free_func); 99</pre> 100 101<p>Once you have created the array, you add elements using the 102<a href='#cupsArrayAdd'><code>cupsArrayAdd</code></a> 103<a href='#cupsArrayInsert'><code>cupsArrayInsert</code></a> functions. 104The first function adds an element to the array, adding the new element 105after any elements that have the same order, while the second inserts the 106element before others with the same order. For unsorted arrays, 107<a href='#cupsArrayAdd'><code>cupsArrayAdd</code></a> appends the element to 108the end of the array while 109<a href='#cupsArrayInsert'><code>cupsArrayInsert</code></a> inserts the 110element at the beginning of the array. For example, the following code 111creates a sorted array of character strings:</p> 112 113<pre class='example'> 114#include <cups/array.h> 115 116/* Use strcmp() to compare strings - it will ignore the user_data pointer */ 117<a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew'>cupsArrayNew</a>((<a href='#cups_array_func_t'>cups_array_func_t</a>)strcmp, NULL); 118 119/* Add four strings to the array */ 120<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish"); 121<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish"); 122<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish"); 123<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish"); 124</pre> 125 126<p>Elements are removed using the 127<a href='#cupsArrayRemove'><code>cupsArrayRemove</code></a> function, for 128example:</p> 129 130<pre class='example'> 131#include <cups/array.h> 132 133/* Use strcmp() to compare strings - it will ignore the user_data pointer */ 134<a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew'>cupsArrayNew</a>((<a href='#cups_array_func_t'>cups_array_func_t</a>)strcmp, NULL); 135 136/* Add four strings to the array */ 137<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish"); 138<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish"); 139<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish"); 140<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish"); 141 142/* Remove "Red Fish" */ 143<a href='#cupsArrayRemove'>cupsArrayRemove</a>(array, "Red Fish"); 144</pre> 145 146<p>Finally, you free the memory used by the array using the 147<a href='#cupsArrayDelete'><code>cupsArrayDelete</code></a> function. All 148of the memory for the array and hash table (if any) is freed, however <em>CUPS 149does not free the elements unless you provide copy and free functions</em>.</p> 150 151<h3><a name='FINDING_AND_ENUMERATING'>Finding and Enumerating Elements</a></h3> 152 153<p>CUPS provides several functions to find and enumerate elements in an 154array. Each one sets or updates a "current index" into the array, such that 155future lookups will start where the last one left off:</p> 156 157<dl> 158 <dt><a href='#cupsArrayFind'><code>cupsArrayFind</code></a></dt> 159 <dd>Returns the first matching element.</dd> 160 <dt><a href='#cupsArrayFirst'><code>cupsArrayFirst</code></a></dt> 161 <dd>Returns the first element in the array.</dd> 162 <dt><a href='#cupsArrayIndex'><code>cupsArrayIndex</code></a></dt> 163 <dd>Returns the Nth element in the array, starting at 0.</dd> 164 <dt><a href='#cupsArrayLast'><code>cupsArrayLast</code></a></dt> 165 <dd>Returns the last element in the array.</dd> 166 <dt><a href='#cupsArrayNext'><code>cupsArrayNext</code></a></dt> 167 <dd>Returns the next element in the array.</dd> 168 <dt><a href='#cupsArrayPrev'><code>cupsArrayPrev</code></a></dt> 169 <dd>Returns the previous element in the array.</dd> 170</dl> 171 172<p>Each of these functions returns <code>NULL</code> when there is no 173corresponding element. For example, a simple <code>for</code> loop using the 174<a href='#cupsArrayFirst'><code>cupsArrayFirst</code></a> and 175<a href='#cupsArrayNext'><code>cupsArrayNext</code></a> functions will 176enumerate all of the strings in our previous example:</p> 177 178<pre class='example'> 179#include <cups/array.h> 180 181/* Use strcmp() to compare strings - it will ignore the user_data pointer */ 182<a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew'>cupsArrayNew</a>((<a href='#cups_array_func_t'>cups_array_func_t</a>)strcmp, NULL); 183 184/* Add four strings to the array */ 185<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish"); 186<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish"); 187<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish"); 188<a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish"); 189 190/* Show all of the strings in the array */ 191char *s; 192for (s = (char *)<a href='#cupsArrayFirst'>cupsArrayFirst</a>(array); s != NULL; s = (char *)<a href='#cupsArrayNext'>cupsArrayNext</a>(array)) 193 puts(s); 194</pre> 195