2 * "$Id: array.c 6477 2007-04-25 19:55:45Z mike $"
4 * Sorted array routines for the Common UNIX Printing System (CUPS).
6 * Copyright 1997-2007 by Easy Software Products.
8 * These coded instructions, statements, and computer programs are the
9 * property of Easy Software Products and are protected by Federal
10 * copyright law. Distribution and use rights are outlined in the file
11 * "LICENSE.txt" which should have been included with this file. If this
12 * file is missing or damaged please contact Easy Software Products
15 * Attn: CUPS Licensing Information
16 * Easy Software Products
17 * 44141 Airport View Drive, Suite 204
18 * Hollywood, Maryland 20636 USA
20 * Voice: (301) 373-9600
21 * EMail: cups-info@cups.org
22 * WWW: http://www.cups.org
24 * This file is subject to the Apple OS-Developed Software exception.
28 * cupsArrayAdd() - Add an element to the array.
29 * cupsArrayClear() - Clear the array.
30 * cupsArrayCount() - Get the number of elements in the array.
31 * cupsArrayCurrent() - Return the current element in the array.
32 * cupsArrayDelete() - Free all memory used by the array.
33 * cupsArrayDup() - Duplicate the array.
34 * cupsArrayFind() - Find an element in the array.
35 * cupsArrayFirst() - Get the first element in the array.
36 * cupsArrayGetIndex() - Get the index of the current element.
37 * cupsArrayGetInsert() - Get the index of the last inserted element.
38 * cupsArrayIndex() - Get the N-th element in the array.
39 * cupsArrayInsert() - Insert an element in the array.
40 * cupsArrayLast() - Get the last element in the array.
41 * cupsArrayNew() - Create a new array.
42 * cupsArrayNext() - Get the next element in the array.
43 * cupsArrayPrev() - Get the previous element in the array.
44 * cupsArrayRemove() - Remove an element from the array.
45 * cupsArrayRestore() - Reset the current element to the last cupsArraySave.
46 * cupsArraySave() - Mark the current element for a later
48 * cupsArrayUserData() - Return the user data for an array.
49 * cups_array_add() - Insert or append an element to the array...
50 * cups_array_find() - Find an element in the array...
54 * Include necessary headers...
66 #define _CUPS_MAXSAVE 32 /**** Maximum number of saves ****/
70 * Types and structures...
73 struct _cups_array_s
/**** CUPS array structure ****/
76 * The current implementation uses an insertion sort into an array of
77 * sorted pointers. We leave the array type private/opaque so that we
78 * can change the underlying implementation without affecting the users
82 int num_elements
, /* Number of array elements */
83 alloc_elements
, /* Allocated array elements */
84 current
, /* Current element */
85 insert
, /* Last inserted element */
86 unique
, /* Are all elements unique? */
87 num_saved
, /* Number of saved elements */
90 void **elements
; /* Array elements */
91 cups_array_func_t compare
; /* Element comparison function */
92 void *data
; /* User data passed to compare */
93 cups_ahash_func_t hashfunc
; /* Hash function */
94 int hashsize
, /* Size of hash */
95 *hash
; /* Hash array */
103 static int cups_array_add(cups_array_t
*a
, void *e
, int insert
);
104 static int cups_array_find(cups_array_t
*a
, void *e
, int prev
, int *rdiff
);
108 * 'cupsArrayAdd()' - Add an element to the array.
110 * When adding an element to a sorted array, non-unique elements are
111 * appended at the end of the run. For unsorted arrays, the element
112 * is inserted at the end of the array.
115 int /* O - 1 on success, 0 on failure */
116 cupsArrayAdd(cups_array_t
*a
, /* I - Array */
117 void *e
) /* I - Element */
119 DEBUG_printf(("cupsArrayAdd(a=%p, e=%p)\n", a
, e
));
122 * Range check input...
127 DEBUG_puts("cupsArrayAdd: returning 0");
132 * Append the element...
135 return (cups_array_add(a
, e
, 0));
140 * 'cupsArrayClear()' - Clear the array.
144 cupsArrayClear(cups_array_t
*a
) /* I - Array */
147 * Range check input...
154 * Set the number of elements to 0; we don't actually free the memory
155 * here - that is done in cupsArrayDelete()...
167 * 'cupsArrayCount()' - Get the number of elements in the array.
170 int /* O - Number of elements */
171 cupsArrayCount(cups_array_t
*a
) /* I - Array */
174 * Range check input...
181 * Return the number of elements...
184 return (a
->num_elements
);
189 * 'cupsArrayCurrent()' - Return the current element in the array.
192 void * /* O - Element */
193 cupsArrayCurrent(cups_array_t
*a
) /* I - Array */
196 * Range check input...
203 * Return the current element...
206 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
207 return (a
->elements
[a
->current
]);
214 * 'cupsArrayDelete()' - Free all memory used by the array.
218 cupsArrayDelete(cups_array_t
*a
) /* I - Array */
221 * Range check input...
228 * Free the array of element pointers - the caller is responsible
229 * for freeing the elements themselves...
232 if (a
->alloc_elements
)
243 * 'cupsArrayDup()' - Duplicate the array.
246 cups_array_t
* /* O - Duplicate array */
247 cupsArrayDup(cups_array_t
*a
) /* I - Array */
249 cups_array_t
*da
; /* Duplicate array */
253 * Range check input...
260 * Allocate memory for the array...
263 da
= calloc(1, sizeof(cups_array_t
));
267 da
->compare
= a
->compare
;
269 da
->current
= a
->current
;
270 da
->insert
= a
->insert
;
271 da
->unique
= a
->unique
;
272 da
->num_saved
= a
->num_saved
;
274 memcpy(da
->saved
, a
->saved
, sizeof(a
->saved
));
279 * Allocate memory for the elements...
282 da
->elements
= malloc(a
->num_elements
* sizeof(void *));
290 * Copy the element pointers...
293 memcpy(da
->elements
, a
->elements
, a
->num_elements
* sizeof(void *));
294 da
->num_elements
= a
->num_elements
;
295 da
->alloc_elements
= a
->num_elements
;
299 * Return the new array...
307 * 'cupsArrayFind()' - Find an element in the array.
310 void * /* O - Element found or NULL */
311 cupsArrayFind(cups_array_t
*a
, /* I - Array */
312 void *e
) /* I - Element */
314 int current
, /* Current element */
315 diff
, /* Difference */
316 hash
; /* Hash index */
320 * Range check input...
327 * See if we have any elements...
330 if (!a
->num_elements
)
334 * Yes, look for a match...
339 hash
= (*(a
->hashfunc
))(e
, a
->data
);
341 if (hash
< 0 || hash
>= a
->hashsize
)
343 current
= a
->current
;
348 current
= a
->hash
[hash
];
350 if (current
< 0 || current
>= a
->num_elements
)
351 current
= a
->current
;
356 current
= a
->current
;
360 current
= cups_array_find(a
, e
, current
, &diff
);
364 * Found a match! If the array does not contain unique values, find
365 * the first element that is the same...
368 if (!a
->unique
&& a
->compare
)
371 * The array is not unique, find the first match...
374 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
379 a
->current
= current
;
382 a
->hash
[hash
] = current
;
384 return (a
->elements
[current
]);
400 * 'cupsArrayFirst()' - Get the first element in the array.
403 void * /* O - First element or NULL */
404 cupsArrayFirst(cups_array_t
*a
) /* I - Array */
407 * Range check input...
414 * Return the first element...
419 return (cupsArrayCurrent(a
));
424 * 'cupsArrayGetIndex()' - Get the index of the current element.
429 int /* O - Index of the current element */
430 cupsArrayGetIndex(cups_array_t
*a
) /* I - Array */
440 * 'cupsArrayGetInsert()' - Get the index of the last inserted element.
445 int /* O - Index of the last inserted element */
446 cupsArrayGetInsert(cups_array_t
*a
) /* I - Array */
456 * 'cupsArrayIndex()' - Get the N-th element in the array.
459 void * /* O - N-th element or NULL */
460 cupsArrayIndex(cups_array_t
*a
, /* I - Array */
461 int n
) /* I - Index into array, starting at 0 */
468 return (cupsArrayCurrent(a
));
473 * 'cupsArrayInsert()' - Insert an element in the array.
475 * When inserting an element in a sorted array, non-unique elements are
476 * inserted at the beginning of the run. For unsorted arrays, the element
477 * is inserted at the beginning of the array.
480 int /* O - 0 on failure, 1 on success */
481 cupsArrayInsert(cups_array_t
*a
, /* I - Array */
482 void *e
) /* I - Element */
484 DEBUG_printf(("cupsArrayInsert(a=%p, e=%p)\n", a
, e
));
487 * Range check input...
492 DEBUG_puts("cupsArrayInsert: returning 0");
497 * Insert the element...
500 return (cups_array_add(a
, e
, 1));
505 * 'cupsArrayLast()' - Get the last element in the array.
508 void * /* O - Last element or NULL */
509 cupsArrayLast(cups_array_t
*a
) /* I - Array */
512 * Range check input...
519 * Return the last element...
522 a
->current
= a
->num_elements
- 1;
524 return (cupsArrayCurrent(a
));
529 * 'cupsArrayNew()' - Create a new array.
532 cups_array_t
* /* O - Array */
533 cupsArrayNew(cups_array_func_t f
, /* I - Comparison function */
534 void *d
) /* I - User data */
536 return (cupsArrayNew2(f
, d
, 0, 0));
541 * 'cupsArrayNew2()' - Create a new array with hash.
546 cups_array_t
* /* O - Array */
547 cupsArrayNew2(cups_array_func_t f
, /* I - Comparison function */
548 void *d
, /* I - User data */
549 cups_ahash_func_t h
, /* I - Hash function*/
550 int hsize
) /* I - Hash size */
552 cups_array_t
*a
; /* Array */
556 * Allocate memory for the array...
559 a
= calloc(1, sizeof(cups_array_t
));
574 a
->hash
= malloc(hsize
* sizeof(int));
582 memset(a
->hash
, -1, hsize
* sizeof(int));
590 * 'cupsArrayNext()' - Get the next element in the array.
593 void * /* O - Next element or NULL */
594 cupsArrayNext(cups_array_t
*a
) /* I - Array */
597 * Range check input...
604 * Return the next element...
607 if (a
->current
< a
->num_elements
)
610 return (cupsArrayCurrent(a
));
615 * 'cupsArrayPrev()' - Get the previous element in the array.
618 void * /* O - Previous element or NULL */
619 cupsArrayPrev(cups_array_t
*a
) /* I - Array */
622 * Range check input...
629 * Return the previous element...
635 return (cupsArrayCurrent(a
));
640 * 'cupsArrayRemove()' - Remove an element from the array.
643 int /* O - 1 on success, 0 on failure */
644 cupsArrayRemove(cups_array_t
*a
, /* I - Array */
645 void *e
) /* I - Element */
647 int i
, /* Looping var */
648 current
, /* Current element */
649 diff
; /* Difference */
653 * Range check input...
660 * See if the element is in the array...
663 if (!a
->num_elements
)
666 current
= cups_array_find(a
, e
, a
->current
, &diff
);
671 * Yes, now remove it...
676 if (current
< a
->num_elements
)
677 memmove(a
->elements
+ current
, a
->elements
+ current
+ 1,
678 (a
->num_elements
- current
) * sizeof(void *));
680 if (current
<= a
->current
)
683 if (current
< a
->insert
)
685 else if (current
== a
->insert
)
688 for (i
= 0; i
< a
->num_saved
; i
++)
689 if (current
<= a
->saved
[i
])
692 if (a
->num_elements
<= 1)
700 * 'cupsArrayRestore()' - Reset the current element to the last cupsArraySave.
703 void * /* O - New current element */
704 cupsArrayRestore(cups_array_t
*a
) /* I - Array */
709 if (a
->num_saved
<= 0)
713 a
->current
= a
->saved
[a
->num_saved
];
715 if (a
->current
>= 0 && a
->current
< a
->num_elements
)
716 return (a
->elements
[a
->current
]);
723 * 'cupsArraySave()' - Mark the current element for a later cupsArrayRestore.
725 * The save/restore stack is guaranteed to be at least 32 elements deep.
728 int /* O - 1 on success, 0 on failure */
729 cupsArraySave(cups_array_t
*a
) /* I - Array */
734 if (a
->num_saved
>= _CUPS_MAXSAVE
)
737 a
->saved
[a
->num_saved
] = a
->current
;
745 * 'cupsArrayUserData()' - Return the user data for an array.
748 void * /* O - User data */
749 cupsArrayUserData(cups_array_t
*a
) /* I - Array */
759 * 'cups_array_add()' - Insert or append an element to the array...
762 static int /* O - 1 on success, 0 on failure */
763 cups_array_add(cups_array_t
*a
, /* I - Array */
764 void *e
, /* I - Element to add */
765 int insert
) /* I - 1 = insert, 0 = append */
767 int i
, /* Looping var */
768 current
, /* Current element */
769 diff
; /* Comparison with current element */
772 DEBUG_printf(("cups_array_add(a=%p, e=%p, insert=%d)\n", a
, e
, insert
));
775 * Verify we have room for the new element...
778 if (a
->num_elements
>= a
->alloc_elements
)
781 * Allocate additional elements; start with 16 elements, then
782 * double the size until 1024 elements, then add 1024 elements
786 void **temp
; /* New array elements */
787 int count
; /* New allocation count */
790 if (a
->alloc_elements
== 0)
793 temp
= malloc(count
* sizeof(void *));
797 if (a
->alloc_elements
< 1024)
798 count
= a
->alloc_elements
* 2;
800 count
= a
->alloc_elements
+ 1024;
802 temp
= realloc(a
->elements
, count
* sizeof(void *));
805 DEBUG_printf(("cups_array_add: count=%d\n", count
));
809 DEBUG_puts("cupsAddAdd: allocation failed, returning 0");
813 a
->alloc_elements
= count
;
818 * Find the insertion point for the new element; if there is no
819 * compare function or elements, just add it to the beginning or end...
822 if (!a
->num_elements
|| !a
->compare
)
825 * No elements or comparison function, insert/append as needed...
829 current
= 0; /* Insert at beginning */
831 current
= a
->num_elements
; /* Append to the end */
836 * Do a binary search for the insertion point...
839 current
= cups_array_find(a
, e
, a
->insert
, &diff
);
844 * Insert after the current element...
852 * Compared equal, make sure we add to the begining or end of
853 * the current run of equal elements...
861 * Insert at beginning of run...
864 while (current
> 0 && !(*(a
->compare
))(e
, a
->elements
[current
- 1],
871 * Append at end of run...
878 while (current
< a
->num_elements
&&
879 !(*(a
->compare
))(e
, a
->elements
[current
], a
->data
));
885 * Insert or append the element...
888 if (current
< a
->num_elements
)
891 * Shift other elements to the right...
894 memmove(a
->elements
+ current
+ 1, a
->elements
+ current
,
895 (a
->num_elements
- current
) * sizeof(void *));
897 if (a
->current
>= current
)
900 for (i
= 0; i
< a
->num_saved
; i
++)
901 if (a
->saved
[i
] >= current
)
904 DEBUG_printf(("cups_array_add: insert element at index %d...\n", current
));
908 printf("cups_array_add: append element at %d...\n", current
);
911 a
->elements
[current
] = e
;
916 for (current
= 0; current
< a
->num_elements
; current
++)
917 printf("cups_array_add: a->elements[%d]=%p\n", current
, a
->elements
[current
]);
920 DEBUG_puts("cups_array_add: returning 1");
927 * 'cups_array_find()' - Find an element in the array...
930 static int /* O - Index of match */
931 cups_array_find(cups_array_t
*a
, /* I - Array */
932 void *e
, /* I - Element */
933 int prev
, /* I - Previous index */
934 int *rdiff
) /* O - Difference of match */
936 int left
, /* Left side of search */
937 right
, /* Right side of search */
938 current
, /* Current element */
939 diff
; /* Comparison with current element */
942 DEBUG_printf(("cups_array_find(a=%p, e=%p, prev=%d, rdiff=%p)\n", a
, e
, prev
,
948 * Do a binary search for the element...
951 DEBUG_puts("cups_array_find: binary search");
953 if (prev
>= 0 && prev
< a
->num_elements
)
956 * Start search on either side of previous...
959 if ((diff
= (*(a
->compare
))(e
, a
->elements
[prev
], a
->data
)) == 0 ||
960 (diff
< 0 && prev
== 0) ||
961 (diff
> 0 && prev
== (a
->num_elements
- 1)))
964 * Exact or edge match, return it!
967 DEBUG_printf(("cups_array_find: Returning %d, diff=%d\n", prev
, diff
));
976 * Start with previous on right side...
985 * Start wih previous on left side...
989 right
= a
->num_elements
- 1;
995 * Start search in the middle...
999 right
= a
->num_elements
- 1;
1004 current
= (left
+ right
) / 2;
1005 diff
= (*(a
->compare
))(e
, a
->elements
[current
], a
->data
);
1007 DEBUG_printf(("cups_array_find: left=%d, right=%d, current=%d, diff=%d\n",
1008 left
, right
, current
, diff
));
1017 while ((right
- left
) > 1);
1022 * Check the last 1 or 2 elements...
1025 if ((diff
= (*(a
->compare
))(e
, a
->elements
[left
], a
->data
)) <= 0)
1029 diff
= (*(a
->compare
))(e
, a
->elements
[right
], a
->data
);
1037 * Do a linear pointer search...
1040 DEBUG_puts("cups_array_find: linear search");
1044 for (current
= 0; current
< a
->num_elements
; current
++)
1045 if (a
->elements
[current
] == e
)
1053 * Return the closest element and the difference...
1056 DEBUG_printf(("cups_array_find: Returning %d, diff=%d\n", current
, diff
));
1065 * End of "$Id: array.c 6477 2007-04-25 19:55:45Z mike $".