/*
- * "$Id: array.c 5493 2006-05-05 16:33:57Z mike $"
+ * "$Id: array.c 6649 2007-07-11 21:46:42Z mike $"
*
* Sorted array routines for the Common UNIX Printing System (CUPS).
*
- * Copyright 1997-2006 by Easy Software Products.
+ * Copyright 2007 by Apple Inc.
+ * Copyright 1997-2007 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
+ * 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.
*
* 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.
- * cupsArrayInsert() - Insert an 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.
- * cupsArrayUserData() - Return the user data for an array.
- * cups_array_add() - Insert or append an element to the array...
- * cups_array_find() - Find an element in the array...
+ * 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.
+ * cupsArrayGetIndex() - Get the index of the current element.
+ * cupsArrayGetInsert() - Get the index of the last inserted element.
+ * cupsArrayIndex() - Get the N-th element in the array.
+ * cupsArrayInsert() - Insert an 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.
+ * cupsArrayUserData() - Return the user data for an array.
+ * cups_array_add() - Insert or append an element to the array...
+ * cups_array_find() - Find an element in the array...
*/
/*
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 */
};
if (a->alloc_elements)
free(a->elements);
+ if (a->hashsize)
+ free(a->hash);
+
free(a);
}
void *e) /* I - Element */
{
int current, /* Current element */
- diff; /* Difference */
+ diff, /* Difference */
+ hash; /* Hash index */
/*
* Yes, look for a match...
*/
- current = cups_array_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)
{
/*
a->current = current;
+ if (hash >= 0)
+ a->hash[hash] = current;
+
return (a->elements[current]);
}
else
}
+/*
+ * 'cupsArrayGetIndex()' - Get the index of the current element.
+ *
+ * @since CUPS 1.3@
+ */
+
+int /* O - Index of the current element */
+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@
+ */
+
+int /* O - Index of the last inserted element */
+cupsArrayGetInsert(cups_array_t *a) /* I - Array */
+{
+ if (!a)
+ return (-1);
+ else
+ return (a->insert);
+}
+
+
/*
* 'cupsArrayIndex()' - Get the N-th element in the array.
*/
cups_array_t * /* O - Array */
cupsArrayNew(cups_array_func_t f, /* I - Comparison function */
void *d) /* I - User data */
+{
+ return (cupsArrayNew2(f, d, 0, 0));
+}
+
+
+/*
+ * 'cupsArrayNew2()' - Create a new array with hash.
+ *
+ * @since CUPS 1.3@
+ */
+
+cups_array_t * /* O - Array */
+cupsArrayNew2(cups_array_func_t f, /* I - Comparison function */
+ void *d, /* I - User data */
+ cups_ahash_func_t h, /* I - Hash function*/
+ int hsize) /* I - Hash size */
{
cups_array_t *a; /* Array */
a->num_saved = 0;
a->unique = 1;
+ if (hsize > 0 && h)
+ {
+ a->hashfunc = h;
+ a->hashsize = hsize;
+ a->hash = malloc(hsize * sizeof(int));
+
+ if (!a->hash)
+ {
+ free(a);
+ return (NULL);
+ }
+
+ memset(a->hash, -1, hsize * sizeof(int));
+ }
+
return (a);
}
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])
/*
- * End of "$Id: array.c 5493 2006-05-05 16:33:57Z mike $".
+ * End of "$Id: array.c 6649 2007-07-11 21:46:42Z mike $".
*/