cups/api-array.shtml

   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.
  17 The contents of the array container can be sorted and the container itself is
  18 designed for optimal speed and memory usage under a wide variety of conditions.
  19 Sorted arrays use a binary search algorithm from the last found or inserted
  20 element to quickly find matching elements in the array. Arrays created with the
  21 optional 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
  23 referring to a CUPS array.</p>
  24
  25 <p>The CUPS scheduler (<tt>cupsd</tt>) and many of the CUPS API
  26 functions use the array API to efficiently manage large lists of
  27 data.</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
  35 first function creates a new array with the specified callback function
  36 and user data pointer:</p>
  37
  38 <pre class='example'>
  39 #include &lt;cups/array.h&gt;
  40
  41 static int compare_func(void *first, void *second, void *user_data);
  42
  43 void *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
  49 whenever an element is added to the array and can be <code>NULL</code> to
  50 create an unsorted array. The function returns -1 if the first element should
  51 come before the second, 0 if the first and second elements should have the same
  52 ordering, 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
  56 with additional information.</p>
  57
  58 <p>The <a href='#cupsArrayNew2'><code>cupsArrayNew2</code></a> function adds
  59 two more arguments to support hashed lookups, which can potentially provide
  60 instantaneous ("O(1)") lookups in your array:</p>
  61
  62 <pre class='example'>
  63 #include &lt;cups/array.h&gt;
  64
  65 #define HASH_SIZE 512 /* Size of hash table */
  66
  67 static int compare_func(void *first, void *second, void *user_data);
  68 static int hash_func(void *element, void *user_data);
  69
  70 void *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
  76 number from 0 to (hash_size-1) that (hopefully) uniquely identifies the
  77 element 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
  79 only limited by available memory, but generally should not be larger than
  80 16384 to realize any performance improvement.</p>
  81
  82 <p>The <a href='#cupsArrayNew3'><code>cupsArrayNew3</code></a> function adds
  83 copy and free callbacks to support basic memory management of elements:</p>
  84
  85 <pre class='example'>
  86 #include &lt;cups/array.h&gt;
  87
  88 #define HASH_SIZE 512 /* Size of hash table */
  89
  90 static int compare_func(void *first, void *second, void *user_data);
  91 static void *copy_func(void *element, void *user_data);
  92 static void free_func(void *element, void *user_data);
  93 static int hash_func(void *element, void *user_data);
  94
  95 void *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.
 104 The first function adds an element to the array, adding the new element
 105 after any elements that have the same order, while the second inserts the
 106 element before others with the same order. For unsorted arrays,
 107 <a href='#cupsArrayAdd'><code>cupsArrayAdd</code></a> appends the element to
 108 the end of the array while
 109 <a href='#cupsArrayInsert'><code>cupsArrayInsert</code></a> inserts the
 110 element at the beginning of the array. For example, the following code
 111 creates a sorted array of character strings:</p>
 112
 113 <pre class='example'>
 114 #include &lt;cups/array.h&gt;
 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
 128 example:</p>
 129
 130 <pre class='example'>
 131 #include &lt;cups/array.h&gt;
 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
 148 of the memory for the array and hash table (if any) is freed, however <em>CUPS
 149 does 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
 154 array. Each one sets or updates a "current index" into the array, such that
 155 future 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
 173 corresponding 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
 176 enumerate all of the strings in our previous example:</p>
 177
 178 <pre class='example'>
 179 #include &lt;cups/array.h&gt;
 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 */
 191 char *s;
 192 for (s = (char *)<a href='#cupsArrayFirst'>cupsArrayFirst</a>(array); s != NULL; s = (char *)<a href='#cupsArrayNext'>cupsArrayNext</a>(array))
 193   puts(s);
 194 </pre>