1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gsa.c - generic sorted arrays
6 (C) Copyright 2001-2004 by Pavel Pisa - Originator
8 The uLan utilities library can be used, copied and modified under
10 - GPL - GNU General Public License
11 - LGPL - GNU Lesser General Public License
12 - MPL - Mozilla Public License
13 - and other licenses added by project originators
14 Code can be modified and re-distributed under any combination
15 of the above listed licenses. If contributor does not agree with
16 some of the licenses, he/she can delete appropriate line.
17 Warning, if you delete all lines, you are not allowed to
18 distribute source code and/or binaries utilizing code.
20 See files COPYING and README for details.
22 *******************************************************************/
25 #include "ul_utmalloc.h"
30 #define GSA_ALLOC_STEP 8
31 #define GSA_DEALLOC_STEP 32
34 * gsa_struct_init - Initialize GSA Structure
35 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
36 * @key_offs: offset to the order controlling field obtained by %UL_OFFSETOF
37 * @cmp_fnc: function defining order of items by comparing fields at offset
41 gsa_struct_init(gsa_array_t *array, int key_offs,
42 gsa_cmp_fnc_t *cmp_fnc)
44 array->key_offs=key_offs;
45 array->cmp_fnc=cmp_fnc;
52 * gsa_delete_all - Delete Pointers to the All Items in the Array
53 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
55 * This function releases all internally allocated memory,
56 * but does not release memory of the @array structure
59 gsa_delete_all(gsa_array_t *array)
61 if(array->items) free(array->items);
69 * gsa_bsearch_indx - Search for Item or Place for Item by Key
70 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
71 * @key: key value searched for
72 * @key_offs: offset to the order controlling field obtained by %UL_OFFSETOF
73 * @cmp_fnc: function defining order of items by comparing fields
74 * @mode: mode of the search operation
75 * @indx: pointer to place, where store value of found item array index
76 * or index where new item should be inserted
78 * Core search routine for GSA arrays
79 * binary searches for item with field at offset @key_off equal to @key value
80 * Values are compared by function pointed by *@cmp_fnc field in the array
82 * Integer @mode modifies search algorithm:
83 * %GSA_FANY .. finds item with field value *@key,
84 * %GSA_FFIRST .. finds the first item with field value *@key,
85 * %GSA_FAFTER .. index points after last item with *@key value,
86 * reworded - index points at first item with higher
87 * value of field or after last item
88 * Return Value: Return of nonzero value indicates match found.
91 gsa_bsearch_indx(gsa_array_t *array, void *key, int key_offs,
92 gsa_cmp_fnc_t *cmp_fnc, int mode, unsigned *indx)
96 if(!array->items || !array->count || !cmp_fnc){
106 r=cmp_fnc((char*)array->items[c]+key_offs,key);
118 /* equal items can be in range a to b-1 */
119 /* routine looks for first one */
123 r=cmp_fnc((char*)array->items[c]+key_offs,key);
130 } else if(mode&GSA_FAFTER) {
131 /* equal items can be in range a to b-1 */
132 /* return index after last one */
136 r=cmp_fnc((char*)array->items[c]+key_offs,key);
149 * gsa_find - Find Item for Provided Key
150 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
151 * @key: key value searched for
153 * Return Value: pointer to item associated to key value or %NULL.
156 gsa_find(gsa_array_t *array, void *key)
159 if(gsa_bsearch_indx(array,key,array->key_offs,
160 array->cmp_fnc,0,&indx))
161 return array->items[indx];
166 * gsa_find_first - Find the First Item for Provided Key
167 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
168 * @key: key value searched for
170 * same as above, but first matching item is found.
171 * Return Value: pointer to the first item associated to key value or %NULL.
174 gsa_find_first(gsa_array_t *array, void *key)
177 if(gsa_bsearch_indx(array,key,array->key_offs,
178 array->cmp_fnc,GSA_FFIRST,&indx))
179 return array->items[indx];
184 * gsa_find_indx - Find the First Item with Key Value and Return Its Index
185 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
186 * @key: key value searched for
187 * @indx: pointer to place for index, at which new item should be inserted
189 * same as above, but additionally stores item index value.
190 * Return Value: pointer to the first item associated to key value or %NULL.
193 gsa_find_indx(gsa_array_t *array, void *key, int *indx)
195 if(gsa_bsearch_indx(array,key,array->key_offs,
196 array->cmp_fnc,GSA_FFIRST,indx))
197 return array->items[*indx];
202 * gsa_insert_at - Insert Existing Item to the Specified Array Index
203 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
204 * @item: pointer to inserted Item
205 * @where: at which index should be @item inserted
207 * Return Value: positive or zero value informs about success
210 gsa_insert_at(gsa_array_t *array, void *item, unsigned where)
212 unsigned acnt=array->alloc_count;
213 unsigned cnt=array->count;
215 if(where>cnt) where=cnt;
216 if((cnt+1>=acnt)||!array->items)
218 acnt+=GSA_ALLOC_STEP;
220 items=malloc(acnt*sizeof(void*));
222 items=realloc(array->items,acnt*sizeof(void*));
223 if(!items) return -1;
224 array->alloc_count=acnt;
227 else items=array->items;
229 memmove(p+1,p,(char*)(items+cnt)-(char*)p);
236 * gsa_insert - Insert Existing into Ordered Item Array
237 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
238 * @item: pointer to inserted Item
239 * @mode: if mode is %GSA_FAFTER, multiple items with same key can
240 * be stored into array, else strict ordering is required
242 * Return Value: positive or zero value informs about success
245 gsa_insert(gsa_array_t *array, void *item, int mode)
249 res=gsa_bsearch_indx(array,(char*)item+array->key_offs,
250 array->key_offs,array->cmp_fnc,mode,&indx);
254 if(gsa_insert_at(array,item,indx)<0)
260 * gsa_delete_at - Delete Item from the Specified Array Index
261 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
262 * @indx: index of deleted item
264 * Return Value: positive or zero value informs about success
267 gsa_delete_at(gsa_array_t *array, unsigned indx)
269 unsigned acnt=array->alloc_count;
270 unsigned cnt=array->count;
271 void **items=array->items;
273 if(indx>=cnt) return -1;
276 memmove(p,p+1,(items+cnt-p)*sizeof(void *));
277 if(acnt-cnt>GSA_DEALLOC_STEP+GSA_ALLOC_STEP)
279 acnt-=GSA_DEALLOC_STEP;
280 items=realloc(array->items,acnt*sizeof(void*));
282 array->alloc_count=acnt;
290 * gsa_delete - Delete Item from the Array
291 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
292 * @item: pointer to deleted Item
294 * Return Value: positive or zero value informs about success
297 gsa_delete(gsa_array_t *array, void *item)
300 int key_offs=array->key_offs;
301 gsa_cmp_fnc_t *cmp_fnc=array->cmp_fnc;
302 if(!gsa_bsearch_indx(array,(char*)item+key_offs,
303 key_offs,cmp_fnc,GSA_FFIRST,&indx))
306 while(array->items[indx]!=item){
307 if(++indx>=array->count) return -1;
309 if(cmp_fnc((char*)(array->items[indx])+key_offs,
310 (char*)item+key_offs))
314 return gsa_delete_at(array,indx);
318 * gsa_resort_buble - Sort Again Array If Sorting Criteria Are Changed
319 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
320 * @key_offs: offset to the order controlling field obtained by %UL_OFFSETOF
321 * @cmp_fnc: function defining order of items by comparing fields
323 * Return Value: non-zero value informs, that resorting changed order
326 gsa_resort_buble(gsa_array_t *array, int key_offs,
327 gsa_cmp_fnc_t *cmp_fnc)
332 if(array->count<2) return 0;
333 a=(char**)array->items; m=0;
334 b=(char**)&array->items[array->count-1];
341 if(cmp_fnc(k1,k2)>0) {
349 if((a==--b)||!m1) return m;
355 if(cmp_fnc(k1,k2)<0) {
363 if((++a==b)||!m1) return m;
368 * gsa_setsort - Change Array Sorting Criterion
369 * @array: pointer to the array structure declared through %GSA_ARRAY_FOR
370 * @key_offs: new value of offset to the order controlling field
371 * @cmp_fnc: new function defining order of items by comparing fields at
374 * Return Value: non-zero value informs, that resorting changed order
377 gsa_setsort(gsa_array_t *array, int key_offs,
378 gsa_cmp_fnc_t *cmp_fnc)
380 if(key_offs>=0) array->key_offs=key_offs;
381 if(cmp_fnc!=NULL) array->cmp_fnc=cmp_fnc;
382 return gsa_resort_buble(array,array->key_offs,array->cmp_fnc);
385 int gsa_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT
387 return *(int*)a-*(int*)b;
390 int gsa_cmp_ulong(const void *a, const void *b) UL_ATTR_REENTRANT
392 return *(unsigned long*)a-*(unsigned long*)b;