1 /*
2 * Copyright (C) 2011 Christos Tsantilas
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
17 * MA 02110-1301 USA.
18 */
19
20 #include "common.h"
21 #include "c-icap.h"
22 #include "debug.h"
23 #include "mem.h"
24 #include "array.h"
25 #include <assert.h>
26
27 #define array_item_size(type) ( (size_t)&((type *)0)[1])
28
ci_array_new(size_t size)29 ci_array_t * ci_array_new(size_t size)
30 {
31 ci_array_t *array;
32 ci_mem_allocator_t *packer;
33 void *buffer;
34
35 buffer = ci_buffer_alloc(size);
36 if (!buffer)
37 return NULL;
38
39 packer = ci_create_pack_allocator_on_memblock(buffer, size);
40 if (!packer) {
41 ci_buffer_free(buffer);
42 return NULL;
43 }
44
45 array = ci_pack_allocator_alloc(packer, sizeof(ci_array_t));
46 if (!array) {
47 ci_buffer_free(buffer);
48 ci_mem_allocator_destroy(packer);
49 return NULL;
50 }
51
52 array->max_size = size;
53 array->count = 0;
54 array->items = NULL;
55 array->mem = buffer;
56 array->alloc = packer;
57 return array;
58 }
59
ci_array_new2(size_t items,size_t item_size)60 ci_array_t * ci_array_new2(size_t items, size_t item_size)
61 {
62 size_t array_size;
63 array_size = ci_pack_allocator_required_size() +
64 _CI_ALIGN(sizeof(ci_array_t)) +
65 items * (_CI_ALIGN(item_size) + _CI_ALIGN(sizeof(ci_array_item_t)));
66 return ci_array_new(array_size);
67 }
68
ci_array_destroy(ci_array_t * array)69 void ci_array_destroy(ci_array_t *array)
70 {
71 void *buffer = array->mem;
72 assert(buffer);
73 if (array->alloc)
74 ci_mem_allocator_destroy(array->alloc);
75 ci_buffer_free(buffer);
76 }
77
ci_array_add(ci_array_t * array,const char * name,const void * value,size_t size)78 const ci_array_item_t * ci_array_add(ci_array_t *array, const char *name, const void *value, size_t size)
79 {
80 ci_array_item_t *item;
81 ci_mem_allocator_t *packer = array->alloc;
82 assert(packer);
83 item = ci_pack_allocator_alloc_unaligned(packer, array_item_size(ci_array_item_t));
84 if (item) {
85 item->name = ci_pack_allocator_alloc_from_rear(packer, strlen(name) + 1);
86 item->value = ci_pack_allocator_alloc_from_rear(packer, size);
87 }
88
89 if (!item || !item->name || !item->value) {
90 ci_debug_printf(2, "Not enough space to add the new item to array!\n");
91 return NULL;
92 }
93
94 strcpy(item->name, name);
95 memcpy(item->value, value, size);
96
97 /*The array->items should point to the first item...*/
98 if (array->items == NULL)
99 array->items = item;
100
101 array->count++;
102 return item;
103 }
104
ci_array_search(ci_array_t * array,const char * name)105 const void * ci_array_search(ci_array_t *array, const char *name)
106 {
107 int i;
108 for (i = 0; i < array->count; i++) {
109 if (strcmp(array->items[i].name, name) == 0) {
110 return array->items[i].value;
111 }
112 }
113 return NULL;
114 }
115
ci_array_iterate(const ci_array_t * array,void * data,int (* fn)(void * data,const char * name,const void *))116 void ci_array_iterate(const ci_array_t *array, void *data, int (*fn)(void *data, const char *name, const void *))
117 {
118 int i, ret = 0;
119 for (i = 0; i < array->count && ret == 0; i++) {
120 ret = (*fn)(data, array->items[i].name, array->items[i].value);
121 }
122 }
123
124 #define MIN_P(p1, p2) ((void *)p1 < (void *)p2 ? (void *)p1 : (void *)p2)
ci_array_pop(ci_array_t * array)125 const ci_array_item_t *ci_array_pop(ci_array_t *array)
126 {
127 ci_array_item_t *item;
128 if (array->count == 0)
129 return NULL;
130 /*Delete the last element*/
131 item = &array->items[array->count-1];
132 ci_pack_allocator_set_start_pos(array->alloc, item);
133
134 /*Delete the content of the last element*/
135 array->count--;
136 if (array->count == 0)
137 ci_pack_allocator_set_end_pos(array->alloc, NULL);
138 else
139 ci_pack_allocator_set_end_pos(array->alloc, MIN_P(array->items[array->count-1].name, array->items[array->count-1].value) );
140
141 return item;
142 }
143
ci_array_get_item(ci_array_t * array,int pos)144 const ci_array_item_t *ci_array_get_item(ci_array_t *array, int pos)
145 {
146 if (pos >= array->count)
147 return NULL;
148 return &(array->items[pos]);
149 }
150
ci_ptr_array_new2(size_t items)151 ci_ptr_array_t * ci_ptr_array_new2(size_t items)
152 {
153 size_t array_size;
154 array_size = ci_pack_allocator_required_size() +
155 _CI_ALIGN(sizeof(ci_ptr_array_t)) +
156 items * (_CI_ALIGN(sizeof(void *)) + _CI_ALIGN(sizeof(ci_array_item_t)));
157 return ci_ptr_array_new(array_size);
158 }
159
ci_ptr_array_search(ci_ptr_array_t * array,const char * name)160 void * ci_ptr_array_search(ci_ptr_array_t *array, const char *name)
161 {
162 return (void *)ci_array_search(array, name);
163 }
164
ci_ptr_array_add(ci_ptr_array_t * ptr_array,const char * name,void * value)165 const ci_array_item_t * ci_ptr_array_add(ci_ptr_array_t *ptr_array, const char *name, void *value)
166 {
167 ci_array_item_t *item;
168 ci_mem_allocator_t *packer = ptr_array->alloc;
169 assert(packer);
170 item = ci_pack_allocator_alloc_unaligned(packer, array_item_size(ci_array_item_t));
171 if (item)
172 item->name = ci_pack_allocator_alloc_from_rear(packer, strlen(name) + 1);
173
174 if (!item || !item->name) {
175 ci_debug_printf(2, "Not enough space to add the new item to array!\n");
176 return NULL;
177 }
178 strcpy(item->name, name);
179 item->value = value;
180
181 /*The array->items should point to the first item...*/
182 if (ptr_array->items == NULL)
183 ptr_array->items = item;
184
185 ptr_array->count++;
186 return item;
187 }
188
ci_ptr_array_pop(ci_ptr_array_t * ptr_array)189 const ci_array_item_t *ci_ptr_array_pop(ci_ptr_array_t *ptr_array)
190 {
191 ci_array_item_t *item;
192 if (ptr_array->count == 0)
193 return NULL;
194 item = &ptr_array->items[ptr_array->count-1];
195 ci_pack_allocator_set_start_pos(ptr_array->alloc, item);
196 ptr_array->count--;
197 return item;
198 }
199
ci_ptr_array_pop_value(ci_ptr_array_t * ptr_array,char * name,size_t name_size)200 void * ci_ptr_array_pop_value(ci_ptr_array_t *ptr_array, char *name, size_t name_size)
201 {
202 const ci_array_item_t *item = ci_ptr_array_pop(ptr_array);
203 if (!item)
204 return NULL;
205 strncpy(name, item->name, name_size);
206 name[name_size-1] = '\0';
207 return item->value;
208 }
209
210 /**************************************************************************/
211
ci_dyn_array_new(size_t size)212 ci_dyn_array_t * ci_dyn_array_new(size_t size)
213 {
214 /*use 25% of memory for index.*/
215 size_t index_memory = size / 4;
216 size_t items_memory = size - index_memory;
217 size_t items_count = index_memory / sizeof(ci_array_item_t *);
218 size_t item_size = items_memory / items_count;
219 if (item_size < sizeof(ci_array_item_t))
220 item_size = sizeof(ci_array_item_t);
221
222 return ci_dyn_array_new2(items_count, item_size);
223 }
224
ci_dyn_array_new2(size_t items,size_t item_size)225 ci_dyn_array_t * ci_dyn_array_new2(size_t items, size_t item_size)
226 {
227 ci_dyn_array_t *array;
228 ci_mem_allocator_t *packer;
229 size_t array_size;
230
231 /*
232 Items of size = item_size + sizeof(ci_array_item)+sizeof(name)
233 for sizeof(name) assume a size of 16 bytes.
234 We can not be accurate here....
235 */
236 array_size = _CI_ALIGN(sizeof(ci_dyn_array_t)) +
237 items * (_CI_ALIGN(item_size) + _CI_ALIGN(sizeof(ci_array_item_t)) + _CI_ALIGN(16));
238
239 packer = ci_create_serial_allocator(array_size);
240 if (!packer) {
241 return NULL;
242 }
243
244 array = packer->alloc(packer, sizeof(ci_dyn_array_t));
245 if (!array) {
246 ci_mem_allocator_destroy(packer);
247 return NULL;
248 }
249
250 if (items < 32)
251 items = 32;
252
253 array->max_items = items;
254 array->items = ci_buffer_alloc(items*sizeof(ci_array_item_t *));
255 array->count = 0;
256 array->alloc = packer;
257 return array;
258 }
259
ci_dyn_array_destroy(ci_dyn_array_t * array)260 void ci_dyn_array_destroy(ci_dyn_array_t *array)
261 {
262 if (array->items)
263 ci_buffer_free(array->items);
264
265 if (array->alloc)
266 ci_mem_allocator_destroy(array->alloc);
267 }
268
ci_dyn_array_add(ci_dyn_array_t * array,const char * name,const void * value,size_t size)269 const ci_array_item_t * ci_dyn_array_add(ci_dyn_array_t *array, const char *name, const void *value, size_t size)
270 {
271 ci_array_item_t *item;
272 ci_array_item_t **items_space;
273 ci_mem_allocator_t *packer = array->alloc;
274 int name_size;
275
276 if (array->count == array->max_items) {
277 items_space = ci_buffer_realloc(array->items, (array->max_items + 32)*sizeof(ci_array_item_t *));
278 if (!items_space)
279 return NULL;
280 array->items = items_space;
281 array->max_items += 32;
282 }
283
284 assert(packer);
285 item = packer->alloc(packer, sizeof(ci_array_item_t));
286 if (!item) {
287 ci_debug_printf(2, "Not enough space to add the new item %s to array!\n", name);
288 return NULL;
289 }
290 name_size = strlen(name) + 1;
291 item->name = packer->alloc(packer, name_size);
292 if (size > 0)
293 item->value = packer->alloc(packer, size);
294 else
295 item->value = NULL;
296
297 if (!item->name || (!item->value && size > 0)) {
298 ci_debug_printf(2, "Not enough space to add the new item %s to array!\n", name);
299 /*packer->free does not realy free anything bug maybe in the future will be able to release memory*/
300 if (item->name) packer->free(packer, item->name);
301 if (item->value) packer->free(packer, item->value);
302 packer->free(packer, item);
303 return NULL;
304 }
305
306 /*copy values*/
307 memcpy(item->name, name, name_size);
308 if (size > 0)
309 memcpy(item->value, value, size);
310 else
311 item->value = (void *)value;
312
313 array->items[array->count++] = item;
314 return item;
315 }
316
ci_dyn_array_search(ci_dyn_array_t * array,const char * name)317 const void * ci_dyn_array_search(ci_dyn_array_t *array, const char *name)
318 {
319 int i;
320 for (i = 0; i < array->count; ++i)
321 if (strcmp(array->items[i]->name, name) == 0)
322 return array->items[i]->value;
323
324 /*did not found anything*/
325 return NULL;
326 }
327
ci_dyn_array_iterate(const ci_dyn_array_t * array,void * data,int (* fn)(void * data,const char * name,const void * value))328 void ci_dyn_array_iterate(const ci_dyn_array_t *array, void *data, int (*fn)(void *data, const char *name, const void *value))
329 {
330 int i, ret = 0;
331 for (i = 0; i < array->count && ret == 0; i++)
332 ret = (*fn)(data, array->items[i]->name, array->items[i]->value);
333 }
334
ci_ptr_dyn_array_add(ci_ptr_dyn_array_t * array,const char * name,void * value)335 const ci_array_item_t * ci_ptr_dyn_array_add(ci_ptr_dyn_array_t *array, const char *name, void *value)
336 {
337 return ci_dyn_array_add(array, name, value, 0);
338 }
339
340 /**************/
341 /* Vectors API */
342
ci_vector_create(size_t max_size)343 ci_vector_t * ci_vector_create(size_t max_size)
344 {
345 ci_vector_t *vector;
346 ci_mem_allocator_t *packer;
347 void *buffer;
348 void **indx;
349
350 buffer = ci_buffer_alloc(max_size);
351 if (!buffer)
352 return NULL;
353
354 packer = ci_create_pack_allocator_on_memblock(buffer, max_size);
355 if (!packer) {
356 ci_buffer_free(buffer);
357 return NULL;
358 }
359
360 vector = ci_pack_allocator_alloc(packer, sizeof(ci_vector_t));
361 /*Allocate mem for the first item which points to NULL. Vectors are NULL terminated*/
362 indx = ci_pack_allocator_alloc_unaligned(packer, array_item_size(void *));
363 if (!vector || ! indx) {
364 ci_buffer_free(buffer);
365 ci_mem_allocator_destroy(packer);
366 return NULL;
367 }
368 *indx = NULL;
369
370 vector->max_size = max_size;
371 vector->mem = buffer;
372 vector->items = indx;
373 vector->last = indx;
374 vector->count = 0;
375 vector->alloc = packer;
376 return vector;
377
378 }
379
ci_vector_cast_to_voidvoid(ci_vector_t * vector)380 const void **ci_vector_cast_to_voidvoid(ci_vector_t *vector)
381 {
382 return (const void **)vector->items;
383 }
384
ci_vector_cast_from_voidvoid(const void ** p)385 ci_vector_t *ci_vector_cast_from_voidvoid(const void **p)
386 {
387 const void *buf;
388 ci_vector_t *v;
389 v = (ci_vector_t *)((void *)p - _CI_ALIGN(sizeof(ci_vector_t)));
390 buf = (void *)v - ci_pack_allocator_required_size();
391 /*Check if it is a valid vector. The ci_buffer_blocksize will return 0, if buf is not a ci_buffer object*/
392 assert(v->mem == buf);
393 assert(ci_buffer_blocksize(buf) != 0);
394 return v;
395 }
396
ci_vector_destroy(ci_vector_t * vector)397 void ci_vector_destroy(ci_vector_t *vector)
398 {
399 void *buffer = vector->mem;
400 assert(buffer);
401 if (vector->alloc)
402 ci_mem_allocator_destroy(vector->alloc);
403 ci_buffer_free(buffer);
404 }
405
ci_vector_add(ci_vector_t * vector,const void * value,size_t size)406 void * ci_vector_add(ci_vector_t *vector, const void *value, size_t size)
407 {
408 void *item, **indx;
409 ci_mem_allocator_t *packer = vector->alloc;
410 assert(packer);
411 indx = ci_pack_allocator_alloc_unaligned(packer, array_item_size(void *));
412 item = ci_pack_allocator_alloc_from_rear(packer, size);
413 if (!item || !indx) {
414 ci_debug_printf(2, "Not enough space to add the new item to vector!\n");
415 return NULL;
416 }
417
418 memcpy(item, value, size);
419 *(vector->last) = item;
420 vector->last = indx;
421 *(vector->last) = NULL;
422 vector->count++;
423 return item;
424 }
425
ci_vector_pop(ci_vector_t * vector)426 void * ci_vector_pop(ci_vector_t *vector)
427 {
428 void *p;
429 if (vector->count == 0)
430 return NULL;
431
432 /*Delete the last NULL element*/
433 ci_pack_allocator_set_start_pos(vector->alloc, vector->last);
434
435 /*Set last to the preview ellement*/
436 vector->count--;
437 vector->last = &vector->items[vector->count];
438
439 /*Erase the content of last element*/
440 if (vector->count == 0)
441 ci_pack_allocator_set_end_pos(vector->alloc, NULL);
442 else
443 ci_pack_allocator_set_end_pos(vector->alloc, vector->items[vector->count-1]);
444
445 /*The last element must point to NULL*/
446 p = *(vector->last);
447 *(vector->last) = NULL;
448 return p;
449 }
450
ci_vector_iterate(const ci_vector_t * vector,void * data,int (* fn)(void * data,const void *))451 void ci_vector_iterate(const ci_vector_t *vector, void *data, int (*fn)(void *data, const void *))
452 {
453 int i, ret = 0;
454 for (i = 0; vector->items[i] != NULL && ret == 0; i++)
455 ret = (*fn)(data, vector->items[i]);
456 }
457
458
459 /*ci_str_vector functions */
ci_str_vector_iterate(const ci_str_vector_t * vector,void * data,int (* fn)(void * data,const char *))460 void ci_str_vector_iterate(const ci_str_vector_t *vector, void *data, int (*fn)(void *data, const char *))
461 {
462 ci_vector_iterate(vector, data, (int(*)(void *, const void *))fn);
463 }
464
ci_str_vector_search(ci_str_vector_t * vector,const char * item)465 const char * ci_str_vector_search(ci_str_vector_t *vector, const char *item)
466 {
467 int i;
468 for (i = 0; vector->items[i] != NULL; i++) {
469 if (strcmp(vector->items[i], item) == 0)
470 return vector->items[i];
471 }
472
473 return NULL;
474 }
475
476
477 /*ci_ptr_vector functions....*/
ci_ptr_vector_add(ci_vector_t * vector,void * value)478 void * ci_ptr_vector_add(ci_vector_t *vector, void *value)
479 {
480 void **indx;
481 ci_mem_allocator_t *packer = vector->alloc;
482 assert(packer);
483
484 if (!value)
485 return NULL;
486
487 indx = ci_pack_allocator_alloc_unaligned(packer, array_item_size(void *));
488 if (!indx) {
489 ci_debug_printf(2, "Not enough space to add the new item to ptr_vector!\n");
490 return NULL;
491 }
492 /*Store the pointer to the last ellement */
493 *(vector->last) = value;
494
495 /*And create a new NULL terminated item: */
496 vector->last = indx;
497 *(vector->last) = NULL;
498 vector->count++;
499 return value;
500 }
501
502
503 /****************/
504 /* Lists API */
505
ci_list_create(size_t init_size,size_t obj_size)506 ci_list_t * ci_list_create(size_t init_size, size_t obj_size)
507 {
508 ci_list_t *list = NULL;
509 ci_mem_allocator_t *alloc = NULL;
510 if (init_size < 1024)
511 init_size = 1024;
512
513 alloc = ci_create_serial_allocator(init_size);
514 list = alloc->alloc(alloc, sizeof(ci_list_t));
515 list->alloc = alloc;
516 list->items = NULL;
517 list->last = NULL;
518 list->trash = NULL;
519 list->cursor = NULL;
520 list->obj_size = obj_size;
521
522 /*By default do not use any handler*/
523 list->cmp_func = NULL;
524 list->copy_func = NULL;
525 list->free_func = NULL;
526 return list;
527 }
528
ci_list_destroy(ci_list_t * list)529 void ci_list_destroy(ci_list_t *list)
530 {
531 ci_mem_allocator_t *alloc = list->alloc;
532 ci_mem_allocator_destroy(alloc);
533 }
534
ci_list_cmp_handler(ci_list_t * list,int (* cmp_func)(const void * obj,const void * user_data,size_t user_data_size))535 void ci_list_cmp_handler(ci_list_t *list, int (*cmp_func)(const void *obj, const void *user_data, size_t user_data_size))
536 {
537 list->cmp_func = cmp_func;
538 }
539
ci_list_free_handler(ci_list_t * list,void (* free_func)(void * obj))540 void ci_list_free_handler(ci_list_t *list, void (*free_func)(void *obj))
541 {
542 list->free_func = free_func;
543 }
544
ci_list_copy_handler(ci_list_t * list,int (* copy_func)(void * newObj,const void * oldObj))545 void ci_list_copy_handler(ci_list_t *list, int (*copy_func)(void *newObj, const void *oldObj))
546 {
547 list->copy_func = copy_func;
548 }
549
ci_list_iterate(ci_list_t * list,void * data,int (* fn)(void * data,const void * obj))550 void ci_list_iterate(ci_list_t *list, void *data, int (*fn)(void *data, const void *obj))
551 {
552 ci_list_item_t *it;
553 for (list->cursor = list->items; list->cursor != NULL; ) {
554 it = list->cursor;
555 list->cursor = list->cursor->next;
556 if ((*fn)(data, it->item))
557 return;
558 }
559 }
560
list_alloc_item(ci_list_t * list,const void * data)561 static ci_list_item_t *list_alloc_item(ci_list_t *list, const void *data)
562 {
563 ci_list_item_t *it;
564 if (list->trash) {
565 it = list->trash;
566 list->trash = list->trash->next;
567 } else {
568 it = list->alloc->alloc(list->alloc, sizeof(ci_list_item_t));
569 if (!it)
570 return NULL;
571
572 if (list->obj_size) {
573 it->item = list->alloc->alloc(list->alloc, list->obj_size);
574 if (!it->item)
575 return NULL;
576 }
577 }
578 it->next = NULL;
579 if (list->obj_size) {
580 memcpy(it->item, data, list->obj_size);
581 if (list->copy_func)
582 list->copy_func(it->item, data);
583 } else
584 it->item = (void *)data;
585 return it;
586 }
587
ci_list_push(ci_list_t * list,const void * data)588 const void * ci_list_push(ci_list_t *list, const void *data)
589 {
590 ci_list_item_t *it = list_alloc_item(list, data);
591 if (!it)
592 return NULL;
593 if (list->items) {
594 it->next = list->items;
595 list->items = it;
596 } else {
597 list->items = list->last = it;
598 }
599 return it->item;
600 }
601
ci_list_push_back(ci_list_t * list,const void * data)602 const void * ci_list_push_back(ci_list_t *list, const void *data)
603 {
604 ci_list_item_t *it = list_alloc_item(list, data);
605 if (!it)
606 return NULL;
607 if (list->last != NULL) {
608 list->last->next = it;
609 list->last = it;
610 } else {
611 list->items = list->last = it;
612 }
613 return it->item;
614 }
615
ci_list_pop(ci_list_t * list,void * data)616 void *ci_list_pop(ci_list_t *list, void *data)
617 {
618 ci_list_item_t *it = list->items;
619 if (list->items == NULL)
620 return NULL;
621
622 if (list->last == list->items) {
623 list->last = NULL;
624 list->items = NULL;
625 list->cursor = NULL;
626 } else {
627 if (list->cursor == list->items)
628 list->cursor = list->items->next;
629 list->items = list->items->next;
630 }
631
632 it->next = list->trash;
633 list->trash = it;
634
635 if (list->obj_size) {
636 memcpy(data, it->item, list->obj_size);
637 if (list->copy_func)
638 list->copy_func(data, it->item);
639 if (list->free_func)
640 list->free_func(it->item);
641 return data;
642 } else
643 return (*((void **)data) = it->item);
644 }
645
ci_list_pop_back(ci_list_t * list,void * data)646 void *ci_list_pop_back(ci_list_t *list, void *data)
647 {
648 ci_list_item_t *tmp, *it = list->last;
649 if (list->items == NULL)
650 return NULL;
651
652 if (list->last == list->items) {
653 list->last = NULL;
654 list->items = NULL;
655 list->cursor = NULL;
656 } else {
657 if (list->cursor == list->last)
658 list->cursor = NULL;
659 for (tmp = list->items; tmp != NULL && tmp->next != list->last; tmp = tmp->next);
660 assert(tmp != NULL);
661 list->last = tmp;
662 list->last->next = NULL;
663 }
664
665 it->next = list->trash;
666 list->trash = it;
667
668 if (list->obj_size) {
669 memcpy(data, it->item, list->obj_size);
670 if (list->copy_func)
671 list->copy_func(data, it->item);
672 if (list->free_func)
673 list->free_func(it->item);
674 return data;
675 } else
676 return (*((void **)data) = it->item);
677 }
678
default_cmp(const void * obj1,const void * obj2,size_t size)679 static int default_cmp(const void *obj1, const void *obj2, size_t size)
680 {
681 return memcmp(obj1, obj2, size);
682 }
683
pointers_cmp(const void * obj1,const void * obj2,size_t size)684 static int pointers_cmp(const void *obj1, const void *obj2, size_t size)
685 {
686 return (obj1 == obj2 ? 0 : (obj1 > obj2 ? 1 : -1));
687 }
688
ci_list_remove(ci_list_t * list,const void * obj)689 int ci_list_remove(ci_list_t *list, const void *obj)
690 {
691 ci_list_item_t *it, *prev;
692 int (*cmp_func)(const void *, const void *, size_t);
693
694 if (list->cmp_func)
695 cmp_func = list->cmp_func;
696 else if (list->obj_size)
697 cmp_func = default_cmp;
698 else
699 cmp_func = pointers_cmp;
700
701 prev = NULL;
702 for (it = list->items; it != NULL; prev = it,it = it->next) {
703 if (cmp_func(it->item, obj, list->obj_size) == 0) {
704 if (prev) {
705 prev->next = it->next;
706 } else { /*it is the first item*/
707 list->items = it->next;
708 }
709 if (list->cursor == it)
710 list->cursor = list->cursor->next;
711 it->next = list->trash;
712 list->trash = it;
713 if (list->free_func && list->obj_size)
714 list->free_func(it->item);
715 return 1;
716 }
717 }
718
719 return 0;
720 }
721
ci_list_search(ci_list_t * list,const void * data)722 const void * ci_list_search(ci_list_t *list, const void *data)
723 {
724 ci_list_item_t *it;
725 int (*cmp_func)(const void *, const void *, size_t);
726
727 if (list->cmp_func)
728 cmp_func = list->cmp_func;
729 else if (list->obj_size)
730 cmp_func = default_cmp;
731 else
732 cmp_func = pointers_cmp;
733
734 for (it = list->items; it != NULL; it = it->next) {
735 if (cmp_func(it->item, data, list->obj_size) == 0)
736 return it->item;
737 }
738 return NULL;
739 }
740
ci_list_search2(ci_list_t * list,const void * data,int (* cmp_func)(const void * obj,const void * user_data,size_t user_data_size))741 const void * ci_list_search2(ci_list_t *list, const void *data, int (*cmp_func)(const void *obj, const void *user_data, size_t user_data_size))
742 {
743 ci_list_item_t *it;
744 for (it = list->items; it != NULL; it = it->next) {
745 if (cmp_func(it->item, data, list->obj_size) == 0)
746 return it->item;
747 }
748 return NULL;
749 }
750
ci_list_sort(ci_list_t * list)751 void ci_list_sort(ci_list_t *list)
752 {
753 int (*cmp_func)(const void *, const void *, size_t);
754
755 if (list->cmp_func)
756 cmp_func = list->cmp_func;
757 else if (list->obj_size)
758 cmp_func = default_cmp;
759 else
760 cmp_func = pointers_cmp;
761
762 ci_list_sort2(list, cmp_func);
763 }
764
ci_list_sort2(ci_list_t * list,int (* cmp_func)(const void * obj1,const void * obj2,size_t obj_size))765 void ci_list_sort2(ci_list_t *list, int (*cmp_func)(const void *obj1, const void *obj2, size_t obj_size))
766 {
767 ci_list_item_t *it;
768 ci_list_item_t *sortedHead = NULL, *sortedTail = NULL;
769 ci_list_item_t **currentSorted, *currentHead;
770 if (!list->items || ! list->items->next)
771 return;
772
773 it = list->items;
774 while (it) {
775 currentHead = it;
776 it = it->next;
777 currentSorted = &sortedHead;
778 while (!(*currentSorted == NULL || cmp_func(currentHead->item, (*currentSorted)->item, list->obj_size) < 0))
779 currentSorted = &(*currentSorted)->next;
780 currentHead->next = *currentSorted;
781 *currentSorted = currentHead;
782 if ((*currentSorted)->next == NULL)
783 sortedTail = (*currentSorted);
784 }
785 list->items = sortedHead;
786 list->last = sortedTail;
787 }
788