cups/api-array.shtml

   1 <!--
   2   "$Id: api-array.shtml 6649 2007-07-11 21:46:42Z 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> or
  35 <a href='#cupsArrayNew2'><code>cupsArrayNew2</code></a> functions. The
  36 first function creates a new array with the specified callback function
  37 and user data pointer:</p>
  38
  39 <pre class='example'>
  40 #include &lt;cups/array.h&gt;
  41
  42 static int compare_func(void *first, void *second, void *user_data);
  43
  44 void *user_data;
  45 <a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew'>cupsArrayNew</a>(compare_func, user_data);
  46 </pre>
  47
  48 <p>The comparison function (type
  49 <a href="#cups_arrayfunc_t"><code>cups_arrayfunc_t</code></a>) is called
  50 whenever an element is added to the array and can be <code>NULL</code> to
  51 create an unsorted array. The function returns -1 if the first element should
  52 come before the second, 0 if the first and second elements should have the same
  53 ordering, and 1 if the first element should come after the second.</p>
  54
  55 <p>The "user_data" pointer is passed to your comparison function. Pass
  56 <code>NULL</code> if you do not need to associate the elements in your array
  57 with additional information.</p>
  58
  59 <p>The <a href='#cupsArrayNew2'><code>cupsArrayNew2</code></a> function adds
  60 two more arguments to support hashed lookups, which can potentially provide
  61 instantaneous ("O(1)") lookups in your array:</p>
  62
  63 <pre class='example'>
  64 #include &lt;cups/array.h&gt;
  65
  66 #define HASH_SIZE 512 /* Size of hash table */
  67
  68 static int compare_func(void *first, void *second, void *user_data);
  69 static int hash_func(void *element, void *user_data);
  70
  71 void *user_data;
  72 <a href='#cups_array_t'>cups_array_t</a> *array = <a href='#cupsArrayNew2'>cupsArrayNew2</a>(compare_func, user_data, hash_func, HASH_SIZE);
  73 </pre>
  74
  75 <p>The hash function (type
  76 <a href="#cups_ahash_func_t"><code>cups_ahash_func_t</code></a>) returns a
  77 number from 0 to (hash_size-1) that (hopefully) uniquely identifies the
  78 element and is called whenever you look up an element in the array with
  79 <a href='#cupsArrayFind'><code>cupsArrayFind</code></a>. The hash size is
  80 only limited by available memory, but generally should not be larger than
  81 16384 to realize any performance improvement.</p>
  82
  83 <p>Once you have created the array, you add elements using the
  84 <a href='#cupsArrayAdd'><code>cupsArrayAdd</code></a>
  85 <a href='#cupsArrayInsert'><code>cupsArrayInsert</code></a> functions.
  86 The first function adds an element to the array, adding the new element
  87 after any elements that have the same order, while the second inserts the
  88 element before others with the same order. For unsorted arrays,
  89 <a href='#cupsArrayAdd'><code>cupsArrayAdd</code></a> appends the elemnt to
  90 the end of the array while
  91 <a href='#cupsArrayInsert'><code>cupsArrayInsert</code></a> inserts the
  92 element at the beginning of the array. For example, the following code
  93 creates a sorted array of character strings:</p>
  94
  95 <pre class='example'>
  96 #include &lt;cups/array.h&gt;
  97
  98 /* Use strcmp() to compare strings - it will ignore the user_data pointer */
  99 <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);
 100
 101 /* Add four strings to the array */
 102 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish");
 103 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish");
 104 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish");
 105 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish");
 106 </pre>
 107
 108 <p>Elements are removed using the
 109 <a href='#cupsArrayRemove'><code>cupsArrayRemove</code></a> function, for
 110 example:</p>
 111
 112 <pre class='example'>
 113 #include &lt;cups/array.h&gt;
 114
 115 /* Use strcmp() to compare strings - it will ignore the user_data pointer */
 116 <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);
 117
 118 /* Add four strings to the array */
 119 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish");
 120 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish");
 121 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish");
 122 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish");
 123
 124 /* Remove "Red Fish" */
 125 <a href='#cupsArrayRemove'>cupsArrayRemove</a>(array, "Red Fish");
 126 </pre>
 127
 128 <p>Finally, you free the memory used by the array using the
 129 <a href='#cupsArrayDelete'><code>cupsArrayDelete</code></a> function. All
 130 of the memory for the array and hash table (if any) is freed, however <em>CUPS
 131 does not free the elements</em> - if necessary, you must allocate and free the
 132 elements yourself.</p>
 133
 134 <h3><a name='FINDING_AND_ENUMERATING'>Finding and Enumerating Elements</a></h3>
 135
 136 <p>CUPS provides several functions to find and enumerate elements in an
 137 array. Each one sets or updates a "current index" into the array, such that
 138 future lookups will start where the last one left off:</p>
 139
 140 <dl>
 141         <dt><a href='#cupsArrayFind'><code>cupsArrayFind</code></a></dt>
 142         <dd>Returns the first matching element .</dd>
 143         <dt><a href='#cupsArrayFirst'><code>cupsArrayFirst</code></a></dt>
 144         <dd>Returns the first element in the array.</dd>
 145         <dt><a href='#cupsArrayIndex'><code>cupsArrayIndex</code></a></dt>
 146         <dd>Returns the Nth element in the array.</dd>
 147         <dt><a href='#cupsArrayLast'><code>cupsArrayLast</code></a></dt>
 148         <dd>Returns the last element in the array.</dd>
 149         <dt><a href='#cupsArrayNext'><code>cupsArrayNext</code></a></dt>
 150         <dd>Returns the next element in the array.</dd>
 151         <dt><a href='#cupsArrayPrev'><code>cupsArrayPrev</code></a></dt>
 152         <dd>Returns the previous element in the array.</dd>
 153 </dl>
 154
 155 <p>Each of these functions returns <code>NULL</code> when there is no
 156 corresponding element.  For example, a simple <code>for</code> loop using the
 157 <a href='#cupsArrayFirst'><code>cupsArrayFirst</code></a> and
 158 <a href='#cupsArrayNext'><code>cupsArrayNext</code></a> functions will
 159 enumerate all of the strings in our previous example:</p>
 160
 161 <pre class='example'>
 162 #include &lt;cups/array.h&gt;
 163
 164 /* Use strcmp() to compare strings - it will ignore the user_data pointer */
 165 <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);
 166
 167 /* Add four strings to the array */
 168 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "One Fish");
 169 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Two Fish");
 170 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Red Fish");
 171 <a href='#cupsArrayAdd'>cupsArrayAdd</a>(array, "Blue Fish");
 172
 173 /* Show all of the strings in the array */
 174 char *s;
 175 for (s = (char *)<a href='#cupsArrayFirst'>cupsArrayFirst</a>(array); s != NULL; s = (char *)<a href='#cupsArrayNext'>cupsArrayNext</a>(array))
 176   puts(s);
 177 </pre>