cups/api-array.shtml

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