/*
- * "$Id: array.c 4921 2006-01-12 21:26:26Z mike $"
- *
- * Sorted array routines for the Common UNIX Printing System (CUPS).
- *
- * Copyright 1997-2006 by Easy Software Products.
- *
- * These coded instructions, statements, and computer programs are the
- * property of Easy Software Products and are protected by Federal
- * copyright law. Distribution and use rights are outlined in the file
- * "LICENSE.txt" which should have been included with this file. If this
- * file is missing or damaged please contact Easy Software Products
- * at:
- *
- * Attn: CUPS Licensing Information
- * Easy Software Products
- * 44141 Airport View Drive, Suite 204
- * Hollywood, Maryland 20636 USA
- *
- * Voice: (301) 373-9600
- * EMail: cups-info@cups.org
- * WWW: http://www.cups.org
- *
- * This file is subject to the Apple OS-Developed Software exception.
- *
- * Contents:
- *
- * cupsArrayAdd() - Add an element to the array.
- * cupsArrayClear() - Clear the array.
- * cupsArrayCount() - Get the number of elements in the array.
- * cupsArrayCurrent() - Return the current element in the array.
- * cupsArrayDelete() - Free all memory used by the array.
- * cupsArrayDup() - Duplicate the array.
- * cupsArrayFind() - Find an element in the array.
- * cupsArrayFirst() - Get the first element in the array.
- * cupsArrayIndex() - Get the N-th element in the array.
- * cupsArrayLast() - Get the last element in the array.
- * cupsArrayNew() - Create a new array.
- * cupsArrayNext() - Get the next element in the array.
- * cupsArrayPrev() - Get the previous element in the array.
- * cupsArrayRemove() - Remove an element from the array.
- * cupsArrayRestore() - Reset the current element to the last cupsArraySave.
- * cupsArraySave() - Mark the current element for a later cupsArrayRestore.
- * cups_find() - Find an element in the array...
+ * Sorted array routines for CUPS.
+ *
+ * Copyright 2007-2014 by Apple Inc.
+ * Copyright 1997-2007 by Easy Software Products.
+ *
+ * These coded instructions, statements, and computer programs are the
+ * property of Apple Inc. and are protected by Federal copyright
+ * law. Distribution and use rights are outlined in the file "LICENSE.txt"
+ * which should have been included with this file. If this file is
+ * file is missing or damaged, see the license at "http://www.cups.org/".
+ *
+ * This file is subject to the Apple OS-Developed Software exception.
*/
/*
* Include necessary headers...
*/
-#include "array.h"
-#include "string.h"
-#include "debug.h"
+#include <cups/cups.h>
+#include "string-private.h"
+#include "debug-private.h"
+#include "array-private.h"
/*
alloc_elements, /* Allocated array elements */
current, /* Current element */
insert, /* Last inserted element */
+ unique, /* Are all elements unique? */
num_saved, /* Number of saved elements */
saved[_CUPS_MAXSAVE];
/* Saved elements */
void **elements; /* Array elements */
cups_array_func_t compare; /* Element comparison function */
void *data; /* User data passed to compare */
+ cups_ahash_func_t hashfunc; /* Hash function */
+ int hashsize, /* Size of hash */
+ *hash; /* Hash array */
+ cups_acopy_func_t copyfunc; /* Copy function */
+ cups_afree_func_t freefunc; /* Free function */
};
* Local functions...
*/
-static int cups_find(cups_array_t *a, void *e, int prev, int *rdiff);
+static int cups_array_add(cups_array_t *a, void *e, int insert);
+static int cups_array_find(cups_array_t *a, void *e, int prev, int *rdiff);
/*
* 'cupsArrayAdd()' - Add an element to the array.
+ *
+ * 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.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
int /* O - 1 on success, 0 on failure */
cupsArrayAdd(cups_array_t *a, /* I - Array */
void *e) /* I - Element */
{
- int i, /* Looping var */
- current, /* Current element */
- diff; /* Comparison with current element */
-
-
- DEBUG_printf(("cupsArrayAdd(a=%p, e=%p)\n", a, e));
+ DEBUG_printf(("2cupsArrayAdd(a=%p, e=%p)", (void *)a, e));
/*
* Range check input...
if (!a || !e)
{
- DEBUG_puts("cupsArrayAdd: returning 0");
+ DEBUG_puts("3cupsArrayAdd: returning 0");
return (0);
}
/*
- * Verify we have room for the new element...
+ * Append the element...
*/
- if (a->num_elements >= a->alloc_elements)
- {
- /*
- * Allocate additional elements; start with 16 elements, then
- * double the size until 1024 elements, then add 1024 elements
- * thereafter...
- */
-
- void **temp; /* New array elements */
- int count; /* New allocation count */
+ return (cups_array_add(a, e, 0));
+}
- if (a->alloc_elements == 0)
- {
- count = 16;
- temp = malloc(count * sizeof(void *));
- }
- else
- {
- if (a->alloc_elements < 1024)
- count = a->alloc_elements * 2;
- else
- count = a->alloc_elements + 1024;
+/*
+ * '_cupsArrayAddStrings()' - Add zero or more delimited strings to an array.
+ *
+ * Note: The array MUST be created using the @link _cupsArrayNewStrings@
+ * function. Duplicate strings are NOT added. If the string pointer "s" is NULL
+ * or the empty string, no strings are added to the array.
+ */
- temp = realloc(a->elements, count * sizeof(void *));
- }
+int /* O - 1 on success, 0 on failure */
+_cupsArrayAddStrings(cups_array_t *a, /* I - Array */
+ const char *s, /* I - Delimited strings or NULL */
+ char delim)/* I - Delimiter character */
+{
+ char *buffer, /* Copy of string */
+ *start, /* Start of string */
+ *end; /* End of string */
+ int status = 1; /* Status of add */
- DEBUG_printf(("cupsArrayAdd: count=%d\n", count));
- if (!temp)
- {
- DEBUG_puts("cupsAddAdd: allocation failed, returning 0");
- return (0);
- }
+ DEBUG_printf(("_cupsArrayAddStrings(a=%p, s=\"%s\", delim='%c')", (void *)a, s, delim));
- a->alloc_elements = count;
- a->elements = temp;
+ if (!a || !s || !*s)
+ {
+ DEBUG_puts("1_cupsArrayAddStrings: Returning 0");
+ return (0);
}
- /*
- * Find the insertion point for the new element; if there is no
- * compare function or elements, just add it to the end...
- */
-
- if (!a->num_elements || !a->compare)
+ if (delim == ' ')
{
/*
- * Append to the end...
+ * Skip leading whitespace...
*/
- current = a->num_elements;
- }
- else
- {
- /*
- * Do a binary search for the insertion point...
- */
+ DEBUG_puts("1_cupsArrayAddStrings: Skipping leading whitespace.");
- current = cups_find(a, e, a->insert, &diff);
+ while (*s && isspace(*s & 255))
+ s ++;
- if (diff > 0)
- current ++;
+ DEBUG_printf(("1_cupsArrayAddStrings: Remaining string \"%s\".", s));
}
- /*
- * Insert or append the element...
- */
-
- if (current < a->num_elements)
+ if (!strchr(s, delim) &&
+ (delim != ' ' || (!strchr(s, '\t') && !strchr(s, '\n'))))
{
/*
- * Shift other elements to the right...
+ * String doesn't contain a delimiter, so add it as a single value...
*/
- memmove(a->elements + current + 1, a->elements + current,
- (a->num_elements - current) * sizeof(void *));
-
- if (a->current >= current)
- a->current ++;
-
- for (i = 0; i < a->num_saved; i ++)
- if (a->saved[i] >= current)
- a->saved[i] ++;
+ DEBUG_puts("1_cupsArrayAddStrings: No delimiter seen, adding a single "
+ "value.");
- DEBUG_printf(("cupsArrayAdd: insert element at index %d...\n", current));
+ if (!cupsArrayFind(a, (void *)s))
+ status = cupsArrayAdd(a, (void *)s);
+ }
+ else if ((buffer = strdup(s)) == NULL)
+ {
+ DEBUG_puts("1_cupsArrayAddStrings: Unable to duplicate string.");
+ status = 0;
}
-#ifdef DEBUG
else
- printf("cupsArrayAdd: append element at %d...\n", current);
-#endif /* DEBUG */
+ {
+ for (start = end = buffer; *end; start = end)
+ {
+ /*
+ * Find the end of the current delimited string and see if we need to add
+ * it...
+ */
- a->elements[current] = e;
- a->num_elements ++;
- a->insert = current;
+ if (delim == ' ')
+ {
+ while (*end && !isspace(*end & 255))
+ end ++;
+ while (*end && isspace(*end & 255))
+ *end++ = '\0';
+ }
+ else if ((end = strchr(start, delim)) != NULL)
+ *end++ = '\0';
+ else
+ end = start + strlen(start);
-#ifdef DEBUG
- for (current = 0; current < a->num_elements; current ++)
- printf("cupsArrayAdd: a->elements[%d]=%p\n", current, a->elements[current]);
-#endif /* DEBUG */
+ DEBUG_printf(("1_cupsArrayAddStrings: Adding \"%s\", end=\"%s\"", start,
+ end));
- DEBUG_puts("cupsArrayAdd: returning 1");
+ if (!cupsArrayFind(a, start))
+ status &= cupsArrayAdd(a, start);
+ }
- return (1);
+ free(buffer);
+ }
+
+ DEBUG_printf(("1_cupsArrayAddStrings: Returning %d.", status));
+
+ return (status);
}
/*
* 'cupsArrayClear()' - Clear the array.
+ *
+ * This function is equivalent to removing all elements in the array.
+ * The caller is responsible for freeing the memory used by the
+ * elements themselves.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
void
if (!a)
return;
+ /*
+ * Free the existing elements as needed..
+ */
+
+ if (a->freefunc)
+ {
+ int i; /* Looping var */
+ void **e; /* Current element */
+
+ for (i = a->num_elements, e = a->elements; i > 0; i --, e ++)
+ (a->freefunc)(*e, a->data);
+ }
+
/*
* Set the number of elements to 0; we don't actually free the memory
* here - that is done in cupsArrayDelete()...
a->num_elements = 0;
a->current = -1;
a->insert = -1;
+ a->unique = 1;
a->num_saved = 0;
}
/*
* 'cupsArrayCount()' - Get the number of elements in the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
int /* O - Number of elements */
/*
* 'cupsArrayCurrent()' - Return the current element in the array.
+ *
+ * The current element is undefined until you call @link cupsArrayFind@,
+ * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
void * /* O - Element */
/*
* 'cupsArrayDelete()' - Free all memory used by the array.
+ *
+ * The caller is responsible for freeing the memory used by the
+ * elements themselves.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
void
return;
/*
- * Free the array of element pointers - the caller is responsible
- * for freeing the elements themselves...
+ * Free the elements if we have a free function (otherwise the caller is
+ * responsible for doing the dirty work...)
+ */
+
+ if (a->freefunc)
+ {
+ int i; /* Looping var */
+ void **e; /* Current element */
+
+ for (i = a->num_elements, e = a->elements; i > 0; i --, e ++)
+ (a->freefunc)(*e, a->data);
+ }
+
+ /*
+ * Free the array of element pointers...
*/
if (a->alloc_elements)
free(a->elements);
+ if (a->hashsize)
+ free(a->hash);
+
free(a);
}
/*
* 'cupsArrayDup()' - Duplicate the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
cups_array_t * /* O - Duplicate array */
da->data = a->data;
da->current = a->current;
da->insert = a->insert;
+ da->unique = a->unique;
da->num_saved = a->num_saved;
memcpy(da->saved, a->saved, sizeof(a->saved));
* Allocate memory for the elements...
*/
- da->elements = malloc(a->num_elements * sizeof(void *));
+ da->elements = malloc((size_t)a->num_elements * sizeof(void *));
if (!da->elements)
{
free(da);
* Copy the element pointers...
*/
- memcpy(da->elements, a->elements, a->num_elements * sizeof(void *));
+ if (a->copyfunc)
+ {
+ /*
+ * Use the copy function to make a copy of each element...
+ */
+
+ int i; /* Looping var */
+
+ for (i = 0; i < a->num_elements; i ++)
+ da->elements[i] = (a->copyfunc)(a->elements[i], a->data);
+ }
+ else
+ {
+ /*
+ * Just copy raw pointers...
+ */
+
+ memcpy(da->elements, a->elements, (size_t)a->num_elements * sizeof(void *));
+ }
+
da->num_elements = a->num_elements;
da->alloc_elements = a->num_elements;
}
/*
* 'cupsArrayFind()' - Find an element in the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - Element found or NULL */
+void * /* O - Element found or @code NULL@ */
cupsArrayFind(cups_array_t *a, /* I - Array */
void *e) /* I - Element */
{
int current, /* Current element */
- diff; /* Difference */
+ diff, /* Difference */
+ hash; /* Hash index */
/*
* Yes, look for a match...
*/
- current = cups_find(a, e, a->current, &diff);
+ if (a->hash)
+ {
+ hash = (*(a->hashfunc))(e, a->data);
+
+ if (hash < 0 || hash >= a->hashsize)
+ {
+ current = a->current;
+ hash = -1;
+ }
+ else
+ {
+ current = a->hash[hash];
+
+ if (current < 0 || current >= a->num_elements)
+ current = a->current;
+ }
+ }
+ else
+ {
+ current = a->current;
+ hash = -1;
+ }
+
+ current = cups_array_find(a, e, current, &diff);
if (!diff)
{
/*
- * Found a match...
+ * Found a match! If the array does not contain unique values, find
+ * the first element that is the same...
*/
+ if (!a->unique && a->compare)
+ {
+ /*
+ * The array is not unique, find the first match...
+ */
+
+ while (current > 0 && !(*(a->compare))(e, a->elements[current - 1],
+ a->data))
+ current --;
+ }
+
a->current = current;
+ if (hash >= 0)
+ a->hash[hash] = current;
+
return (a->elements[current]);
}
else
/*
* 'cupsArrayFirst()' - Get the first element in the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - First element or NULL */
+void * /* O - First element or @code NULL@ if the array is empty */
cupsArrayFirst(cups_array_t *a) /* I - Array */
{
/*
}
+/*
+ * 'cupsArrayGetIndex()' - Get the index of the current element.
+ *
+ * The current element is undefined until you call @link cupsArrayFind@,
+ * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@.
+ *
+ * @since CUPS 1.3/OS X 10.5@
+ */
+
+int /* O - Index of the current element, starting at 0 */
+cupsArrayGetIndex(cups_array_t *a) /* I - Array */
+{
+ if (!a)
+ return (-1);
+ else
+ return (a->current);
+}
+
+
+/*
+ * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
+ *
+ * @since CUPS 1.3/OS X 10.5@
+ */
+
+int /* O - Index of the last inserted element, starting at 0 */
+cupsArrayGetInsert(cups_array_t *a) /* I - Array */
+{
+ if (!a)
+ return (-1);
+ else
+ return (a->insert);
+}
+
+
/*
* 'cupsArrayIndex()' - Get the N-th element in the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - N-th element or NULL */
+void * /* O - N-th element or @code NULL@ */
cupsArrayIndex(cups_array_t *a, /* I - Array */
int n) /* I - Index into array, starting at 0 */
{
}
+/*
+ * 'cupsArrayInsert()' - Insert an element in the array.
+ *
+ * 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.
+ *
+ * @since CUPS 1.2/OS X 10.5@
+ */
+
+int /* O - 0 on failure, 1 on success */
+cupsArrayInsert(cups_array_t *a, /* I - Array */
+ void *e) /* I - Element */
+{
+ DEBUG_printf(("2cupsArrayInsert(a=%p, e=%p)", (void *)a, e));
+
+ /*
+ * Range check input...
+ */
+
+ if (!a || !e)
+ {
+ DEBUG_puts("3cupsArrayInsert: returning 0");
+ return (0);
+ }
+
+ /*
+ * Insert the element...
+ */
+
+ return (cups_array_add(a, e, 1));
+}
+
+
/*
* 'cupsArrayLast()' - Get the last element in the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - Last element or NULL */
+void * /* O - Last element or @code NULL@ if the array is empty */
cupsArrayLast(cups_array_t *a) /* I - Array */
{
/*
/*
* 'cupsArrayNew()' - Create a new array.
+ *
+ * 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 @code strcmp@ can be used for sorted string arrays.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
cups_array_t * /* O - Array */
-cupsArrayNew(cups_array_func_t f, /* I - Comparison function */
- void *d) /* I - User data */
+cupsArrayNew(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */
+ void *d) /* I - User data pointer or @code NULL@ */
+{
+ return (cupsArrayNew3(f, d, 0, 0, 0, 0));
+}
+
+
+/*
+ * 'cupsArrayNew2()' - Create a new array with hash.
+ *
+ * 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 @code strcmp@ can be used for sorted string arrays.
+ *
+ * The hash function ("h") is used to implement cached lookups with the
+ * specified hash size ("hsize").
+ *
+ * @since CUPS 1.3/OS X 10.5@
+ */
+
+cups_array_t * /* O - Array */
+cupsArrayNew2(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */
+ void *d, /* I - User data or @code NULL@ */
+ cups_ahash_func_t h, /* I - Hash function or @code NULL@ for unhashed lookups */
+ int hsize) /* I - Hash size (>= 0) */
+{
+ return (cupsArrayNew3(f, d, h, hsize, 0, 0));
+}
+
+
+/*
+ * 'cupsArrayNew3()' - Create a new array with hash and/or free function.
+ *
+ * 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 @code 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.
+ *
+ * @since CUPS 1.5/OS X 10.7@
+ */
+
+cups_array_t * /* O - Array */
+cupsArrayNew3(cups_array_func_t f, /* I - Comparison function or @code NULL@ for an unsorted array */
+ void *d, /* I - User data or @code NULL@ */
+ cups_ahash_func_t h, /* I - Hash function or @code NULL@ for unhashed lookups */
+ int hsize, /* I - Hash size (>= 0) */
+ cups_acopy_func_t cf, /* I - Copy function */
+ cups_afree_func_t ff) /* I - Free function */
{
cups_array_t *a; /* Array */
a->current = -1;
a->insert = -1;
a->num_saved = 0;
+ a->unique = 1;
+
+ if (hsize > 0 && h)
+ {
+ a->hashfunc = h;
+ a->hashsize = hsize;
+ a->hash = malloc((size_t)hsize * sizeof(int));
+
+ if (!a->hash)
+ {
+ free(a);
+ return (NULL);
+ }
+
+ memset(a->hash, -1, (size_t)hsize * sizeof(int));
+ }
+
+ a->copyfunc = cf;
+ a->freefunc = ff;
+
+ return (a);
+}
+
+
+/*
+ * '_cupsArrayNewStrings()' - Create a new array of comma-delimited strings.
+ *
+ * Note: The array automatically manages copies of the strings passed. If the
+ * string pointer "s" is NULL or the empty string, no strings are added to the
+ * newly created array.
+ */
+
+cups_array_t * /* O - Array */
+_cupsArrayNewStrings(const char *s, /* I - Delimited strings or NULL */
+ char delim) /* I - Delimiter character */
+{
+ cups_array_t *a; /* Array */
+
+
+ if ((a = cupsArrayNew3((cups_array_func_t)strcmp, NULL, NULL, 0,
+ (cups_acopy_func_t)_cupsStrAlloc,
+ (cups_afree_func_t)_cupsStrFree)) != NULL)
+ _cupsArrayAddStrings(a, s, delim);
return (a);
}
/*
* 'cupsArrayNext()' - Get the next element in the array.
+ *
+ * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) + 1)".
+ *
+ * The next element is undefined until you call @link cupsArrayFind@,
+ * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
+ * to set the current element.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - Next element or NULL */
+void * /* O - Next element or @code NULL@ */
cupsArrayNext(cups_array_t *a) /* I - Array */
{
/*
/*
* 'cupsArrayPrev()' - Get the previous element in the array.
+ *
+ * This function is equivalent to "cupsArrayIndex(a, cupsArrayGetIndex(a) - 1)".
+ *
+ * The previous element is undefined until you call @link cupsArrayFind@,
+ * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
+ * to set the current element.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
-void * /* O - Previous element or NULL */
+void * /* O - Previous element or @code NULL@ */
cupsArrayPrev(cups_array_t *a) /* I - Array */
{
/*
/*
* 'cupsArrayRemove()' - Remove an element from the array.
+ *
+ * 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.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
int /* O - 1 on success, 0 on failure */
cupsArrayRemove(cups_array_t *a, /* I - Array */
void *e) /* I - Element */
{
- int i, /* Looping var */
- current, /* Current element */
- diff; /* Difference */
+ ssize_t i, /* Looping var */
+ current; /* Current element */
+ int diff; /* Difference */
/*
if (!a->num_elements)
return (0);
- current = cups_find(a, e, a->current, &diff);
+ current = cups_array_find(a, e, a->current, &diff);
if (diff)
return (0);
a->num_elements --;
+ if (a->freefunc)
+ (a->freefunc)(a->elements[current], a->data);
+
if (current < a->num_elements)
memmove(a->elements + current, a->elements + current + 1,
- (a->num_elements - current) * sizeof(void *));
+ (size_t)(a->num_elements - current) * sizeof(void *));
if (current <= a->current)
a->current --;
- if (current <= a->insert)
+ if (current < a->insert)
a->insert --;
+ else if (current == a->insert)
+ a->insert = -1;
for (i = 0; i < a->num_saved; i ++)
if (current <= a->saved[i])
a->saved[i] --;
+ if (a->num_elements <= 1)
+ a->unique = 1;
+
return (1);
}
/*
- * 'cupsArrayRestore()' - Reset the current element to the last cupsArraySave.
+ * 'cupsArrayRestore()' - Reset the current element to the last @link cupsArraySave@.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
void * /* O - New current element */
/*
- * 'cupsArraySave()' - Mark the current element for a later cupsArrayRestore.
+ * 'cupsArraySave()' - Mark the current element for a later @link cupsArrayRestore@.
+ *
+ * The current element is undefined until you call @link cupsArrayFind@,
+ * @link cupsArrayFirst@, or @link cupsArrayIndex@, or @link cupsArrayLast@
+ * to set the current element.
*
* The save/restore stack is guaranteed to be at least 32 elements deep.
+ *
+ * @since CUPS 1.2/OS X 10.5@
*/
int /* O - 1 on success, 0 on failure */
/*
- * 'cups_find()' - Find an element in the array...
+ * 'cupsArrayUserData()' - Return the user data for an array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
+ */
+
+void * /* O - User data */
+cupsArrayUserData(cups_array_t *a) /* I - Array */
+{
+ if (a)
+ return (a->data);
+ else
+ return (NULL);
+}
+
+
+/*
+ * 'cups_array_add()' - Insert or append an element to the array.
+ *
+ * @since CUPS 1.2/OS X 10.5@
+ */
+
+static int /* O - 1 on success, 0 on failure */
+cups_array_add(cups_array_t *a, /* I - Array */
+ void *e, /* I - Element to add */
+ int insert) /* I - 1 = insert, 0 = append */
+{
+ int i, /* Looping var */
+ current; /* Current element */
+ int diff; /* Comparison with current element */
+
+
+ DEBUG_printf(("7cups_array_add(a=%p, e=%p, insert=%d)", (void *)a, e, insert));
+
+ /*
+ * Verify we have room for the new element...
+ */
+
+ if (a->num_elements >= a->alloc_elements)
+ {
+ /*
+ * Allocate additional elements; start with 16 elements, then
+ * double the size until 1024 elements, then add 1024 elements
+ * thereafter...
+ */
+
+ void **temp; /* New array elements */
+ int count; /* New allocation count */
+
+
+ if (a->alloc_elements == 0)
+ {
+ count = 16;
+ temp = malloc((size_t)count * sizeof(void *));
+ }
+ else
+ {
+ if (a->alloc_elements < 1024)
+ count = a->alloc_elements * 2;
+ else
+ count = a->alloc_elements + 1024;
+
+ temp = realloc(a->elements, (size_t)count * sizeof(void *));
+ }
+
+ DEBUG_printf(("9cups_array_add: count=" CUPS_LLFMT, CUPS_LLCAST count));
+
+ if (!temp)
+ {
+ DEBUG_puts("9cups_array_add: allocation failed, returning 0");
+ return (0);
+ }
+
+ a->alloc_elements = count;
+ a->elements = temp;
+ }
+
+ /*
+ * Find the insertion point for the new element; if there is no
+ * compare function or elements, just add it to the beginning or end...
+ */
+
+ if (!a->num_elements || !a->compare)
+ {
+ /*
+ * No elements or comparison function, insert/append as needed...
+ */
+
+ if (insert)
+ current = 0; /* Insert at beginning */
+ else
+ current = a->num_elements; /* Append to the end */
+ }
+ else
+ {
+ /*
+ * Do a binary search for the insertion point...
+ */
+
+ current = cups_array_find(a, e, a->insert, &diff);
+
+ if (diff > 0)
+ {
+ /*
+ * Insert after the current element...
+ */
+
+ current ++;
+ }
+ else if (!diff)
+ {
+ /*
+ * Compared equal, make sure we add to the begining or end of
+ * the current run of equal elements...
+ */
+
+ a->unique = 0;
+
+ if (insert)
+ {
+ /*
+ * Insert at beginning of run...
+ */
+
+ while (current > 0 && !(*(a->compare))(e, a->elements[current - 1],
+ a->data))
+ current --;
+ }
+ else
+ {
+ /*
+ * Append at end of run...
+ */
+
+ do
+ {
+ current ++;
+ }
+ while (current < a->num_elements &&
+ !(*(a->compare))(e, a->elements[current], a->data));
+ }
+ }
+ }
+
+ /*
+ * Insert or append the element...
+ */
+
+ if (current < a->num_elements)
+ {
+ /*
+ * Shift other elements to the right...
+ */
+
+ memmove(a->elements + current + 1, a->elements + current,
+ (size_t)(a->num_elements - current) * sizeof(void *));
+
+ if (a->current >= current)
+ a->current ++;
+
+ for (i = 0; i < a->num_saved; i ++)
+ if (a->saved[i] >= current)
+ a->saved[i] ++;
+
+ DEBUG_printf(("9cups_array_add: insert element at index " CUPS_LLFMT, CUPS_LLCAST current));
+ }
+#ifdef DEBUG
+ else
+ DEBUG_printf(("9cups_array_add: append element at " CUPS_LLFMT, CUPS_LLCAST current));
+#endif /* DEBUG */
+
+ if (a->copyfunc)
+ {
+ if ((a->elements[current] = (a->copyfunc)(e, a->data)) == NULL)
+ {
+ DEBUG_puts("8cups_array_add: Copy function returned NULL, returning 0");
+ return (0);
+ }
+ }
+ else
+ a->elements[current] = e;
+
+ a->num_elements ++;
+ a->insert = current;
+
+#ifdef DEBUG
+ for (current = 0; current < a->num_elements; current ++)
+ DEBUG_printf(("9cups_array_add: a->elements[" CUPS_LLFMT "]=%p", CUPS_LLCAST current, a->elements[current]));
+#endif /* DEBUG */
+
+ DEBUG_puts("9cups_array_add: returning 1");
+
+ return (1);
+}
+
+
+/*
+ * 'cups_array_find()' - Find an element in the array.
*/
static int /* O - Index of match */
-cups_find(cups_array_t *a, /* I - Array */
- void *e, /* I - Element */
- int prev, /* I - Previous index */
- int *rdiff) /* O - Difference of match */
+cups_array_find(cups_array_t *a, /* I - Array */
+ void *e, /* I - Element */
+ int prev, /* I - Previous index */
+ int *rdiff) /* O - Difference of match */
{
int left, /* Left side of search */
right, /* Right side of search */
diff; /* Comparison with current element */
- DEBUG_printf(("cups_find(a=%p, e=%p, prev=%d, rdiff=%p)\n", a, e, prev,
- rdiff));
+ DEBUG_printf(("7cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)", (void *)a, e, prev, (void *)rdiff));
if (a->compare)
{
* Do a binary search for the element...
*/
- DEBUG_puts("cups_find: binary search");
+ DEBUG_puts("9cups_array_find: binary search");
if (prev >= 0 && prev < a->num_elements)
{
* Exact or edge match, return it!
*/
- DEBUG_printf(("cups_find: Returning %d, diff=%d\n", prev, diff));
+ DEBUG_printf(("9cups_array_find: Returning %d, diff=%d", prev, diff));
*rdiff = diff;
current = (left + right) / 2;
diff = (*(a->compare))(e, a->elements[current], a->data);
- DEBUG_printf(("cups_find: left=%d, right=%d, current=%d, diff=%d\n",
+ DEBUG_printf(("9cups_array_find: left=%d, right=%d, current=%d, diff=%d",
left, right, current, diff));
if (diff == 0)
* Do a linear pointer search...
*/
- DEBUG_puts("cups_find: linear search");
+ DEBUG_puts("9cups_array_find: linear search");
- diff = 0;
+ diff = 1;
for (current = 0; current < a->num_elements; current ++)
if (a->elements[current] == e)
+ {
+ diff = 0;
break;
+ }
}
/*
* Return the closest element and the difference...
*/
- DEBUG_printf(("cups_find: Returning %d, diff=%d\n", current, diff));
+ DEBUG_printf(("8cups_array_find: Returning %d, diff=%d", current, diff));
*rdiff = diff;
return (current);
}
-
-
-/*
- * End of "$Id: array.c 4921 2006-01-12 21:26:26Z mike $".
- */
projects / thirdparty / cups.git / blobdiff