1 /*
2 * Copyright (c) 2007,2008,2009,2010 Mij <mij@bitchx.it>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17
18 /*
19 * SimCList library. See http://mij.oltrelinux.com/devel/simclist
20 */
21
22 /* SimCList implementation, version 1.5, with local modifications */
23
24 #include <stdlib.h>
25 #include <string.h>
26 #include <errno.h> /* for setting errno */
27 #include <sys/types.h>
28 #if !defined(_WIN32)
29 #include <arpa/inet.h> /* for htons() */
30 #include <unistd.h>
31 #ifdef HAVE_SYS_TIME_H
32 #include <sys/time.h> /* for gettimeofday() */
33 #endif
34 #include <stdint.h>
35 #else
36 #include <winsock2.h>
37 #endif
38 #ifdef SIMCLIST_DUMPRESTORE
39 #ifndef _WIN32
40 #include <sys/uio.h> /* for READ_ERRCHECK() and write() */
41 #endif
42 #include <fcntl.h> /* for open() etc */
43 #endif
44 #include <time.h> /* for time() for random seed */
45 #include <sys/stat.h> /* for open()'s access modes S_IRUSR etc */
46 #include <limits.h>
47
48
49 #ifdef SIMCLIST_DUMPRESTORE
50 /* convert 64bit integers from host to network format */
51 #define hton64(x) (\
52 htons(1) == 1 ? \
53 (uint64_t)x /* big endian */ \
54 : /* little endian */ \
55 ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
56 (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
57 (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
58 (((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \
59 (((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \
60 (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
61 (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
62 (((uint64_t)(x) & 0x00000000000000ffULL) << 56))) \
63 )
64
65 /* convert 64bit integers from network to host format */
66 #define ntoh64(x) (hton64(x))
67 #endif
68
69 /* some OSes don't have EPROTO (eg OpenBSD) */
70 #ifndef EPROTO
71 #define EPROTO EIO
72 #endif
73
74 /* disable asserts */
75 #ifndef SIMCLIST_DEBUG
76 #ifndef NDEBUG
77 #define NDEBUG
78 #endif
79 #endif
80
81 #include <assert.h>
82
83 #ifdef SIMCLIST_WITH_THREADS
84 /* limit (approx) to the number of threads running
85 * for threaded operations. Only meant when
86 * SIMCLIST_WITH_THREADS is defined */
87 #define SIMCLIST_MAXTHREADS 2
88 #endif
89
90 /*
91 * how many elems to keep as spare. During a deletion, an element
92 * can be saved in a "free-list", not free()d immediately. When
93 * latter insertions are performed, spare elems can be used instead
94 * of malloc()ing new elems.
95 *
96 * about this param, some values for appending
97 * 10 million elems into an empty list:
98 * (#, time[sec], gain[%], gain/no[%])
99 * 0 2,164 0,00 0,00 <-- feature disabled
100 * 1 1,815 34,9 34,9
101 * 2 1,446 71,8 35,9 <-- MAX gain/no
102 * 3 1,347 81,7 27,23
103 * 5 1,213 95,1 19,02
104 * 8 1,064 110,0 13,75
105 * 10 1,015 114,9 11,49 <-- MAX gain w/ likely sol
106 * 15 1,019 114,5 7,63
107 * 25 0,985 117,9 4,72
108 * 50 1,088 107,6 2,15
109 * 75 1,016 114,8 1,53
110 * 100 0,988 117,6 1,18
111 * 150 1,022 114,2 0,76
112 * 200 0,939 122,5 0,61 <-- MIN time
113 */
114 #ifndef SIMCLIST_MAX_SPARE_ELEMS
115 #define SIMCLIST_MAX_SPARE_ELEMS 5
116 #endif
117
118
119 #ifdef SIMCLIST_WITH_THREADS
120 #include <pthread.h>
121 #endif
122
123 #include "simclist.h"
124
125
126 /* minimum number of elements for sorting with quicksort instead of insertion */
127 #define SIMCLIST_MINQUICKSORTELS 24
128
129
130 /* list dump declarations */
131 #define SIMCLIST_DUMPFORMAT_VERSION 1 /* (short integer) version of fileformat managed by _dump* and _restore* functions */
132
133 #define SIMCLIST_DUMPFORMAT_HEADERLEN 30 /* length of the header */
134
135 /* header for a list dump */
136 struct list_dump_header_s {
137 uint16_t ver; /* version */
138 int64_t timestamp; /* dump timestamp */
139 int32_t rndterm; /* random value terminator -- terminates the data sequence */
140
141 uint32_t totlistlen; /* sum of every element' size, bytes */
142 uint32_t numels; /* number of elements */
143 uint32_t elemlen; /* bytes length of an element, for constant-size lists, <= 0 otherwise */
144 int32_t listhash; /* hash of the list at the time of dumping, or 0 if to be ignored */
145 };
146
147
148
149 /* deletes tmp from list, with care wrt its position (head, tail, middle) */
150 static int list_drop_elem(list_t *simclist_restrict l, struct list_entry_s *tmp, unsigned int pos);
151
152 /* set default values for initialized lists */
153 static int list_attributes_setdefaults(list_t *simclist_restrict l);
154
155 #ifndef NDEBUG
156 /* check whether the list internal REPresentation is valid -- Costs O(n) */
157 static int list_repOk(const list_t *simclist_restrict l);
158
159 /* check whether the list attribute set is valid -- Costs O(1) */
160 static int list_attrOk(const list_t *simclist_restrict l);
161 #endif
162
163 /* do not inline, this is recursive */
164 static void list_sort_quicksort(list_t *simclist_restrict l, int versus,
165 unsigned int first, struct list_entry_s *fel,
166 unsigned int last, struct list_entry_s *lel);
167
168 static simclist_inline void list_sort_selectionsort(list_t *simclist_restrict l, int versus,
169 unsigned int first, struct list_entry_s *fel,
170 unsigned int last, struct list_entry_s *lel);
171
172 static void *list_get_minmax(const list_t *simclist_restrict l, int versus);
173
174 static simclist_inline struct list_entry_s *list_findpos(const list_t *simclist_restrict l, int posstart);
175
176 #ifdef SIMCLIST_DUMPRESTORE
177 /* write() decorated with error checking logic */
178 #define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \
179 if (write(fd, msgbuf, msglen) < 0) return -1; \
180 } while (0);
181 /* READ_ERRCHECK() decorated with error checking logic */
182 #define READ_ERRCHECK(fd, msgbuf, msglen) do { \
183 if (read(fd, msgbuf, msglen) != msglen) { \
184 /*errno = EPROTO;*/ \
185 free(buf); \
186 return -1; \
187 } \
188 } while (0);
189 #endif
190
191 /*
192 * Random Number Generator
193 *
194 * The user is expected to seed the RNG (ie call srand()) if
195 * SIMCLIST_SYSTEM_RNG is defined.
196 *
197 * Otherwise, a self-contained RNG based on LCG is used; see
198 * http://en.wikipedia.org/wiki/Linear_congruential_generator .
199 *
200 * Facts pro local RNG:
201 * 1. no need for the user to call srand() on his own
202 * 2. very fast, possibly faster than OS
203 * 3. avoid interference with user's RNG
204 *
205 * Facts pro system RNG:
206 * 1. may be more accurate (irrelevant for SimCList random purposes)
207 * 2. why reinvent the wheel
208 *
209 * Default to local RNG for user's ease of use.
210 */
211
212 #ifdef SIMCLIST_SYSTEM_RNG
213 /* keep track whether we initialized already (non-0) or not (0) */
214 static unsigned random_seed = 0;
215
216 /* use local RNG */
seed_random()217 static simclist_inline void seed_random() {
218 if (random_seed == 0)
219 random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
220 }
221
get_random()222 static simclist_inline long get_random() {
223 random_seed = (1664525 * random_seed + 1013904223);
224 return random_seed;
225 }
226
227 #else
228 /* use OS's random generator */
229 # define seed_random()
230 # define get_random() (rand())
231 #endif
232
233
234 /* list initialization */
list_init(list_t * simclist_restrict l)235 int list_init(list_t *simclist_restrict l) {
236 if (l == NULL) {
237 return -1;
238 }
239
240 memset(l, 0, sizeof *l);
241
242 seed_random();
243
244 l->numels = 0;
245
246 /* head/tail sentinels and mid pointer */
247 l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
248 l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
249 if (l->tail_sentinel == NULL || l->head_sentinel == NULL) {
250 return -1;
251 }
252 l->head_sentinel->next = l->tail_sentinel;
253 l->tail_sentinel->prev = l->head_sentinel;
254 l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
255 l->head_sentinel->data = l->tail_sentinel->data = NULL;
256
257 /* iteration attributes */
258 l->iter_active = 0;
259 l->iter_pos = 0;
260 l->iter_curentry = NULL;
261
262 /* free-list attributes */
263 l->spareelsnum = 0;
264 l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *));
265 if (l->spareels == NULL) {
266 return -1;
267 }
268
269 #ifdef SIMCLIST_WITH_THREADS
270 l->threadcount = 0;
271 #endif
272
273 if (0 != list_attributes_setdefaults(l)) {
274 return -1;
275 }
276
277 assert(list_repOk(l));
278 assert(list_attrOk(l));
279
280 return 0;
281 }
282
list_destroy(list_t * simclist_restrict l)283 void list_destroy(list_t *simclist_restrict l) {
284 unsigned int i;
285
286 list_clear(l);
287 for (i = 0; i < l->spareelsnum; i++) {
288 free(l->spareels[i]);
289 }
290 free(l->spareels);
291 free(l->head_sentinel);
292 free(l->tail_sentinel);
293 }
294
list_attributes_setdefaults(list_t * simclist_restrict l)295 int list_attributes_setdefaults(list_t *simclist_restrict l) {
296 l->attrs.comparator = NULL;
297 l->attrs.seeker = NULL;
298
299 /* also free() element data when removing and element from the list */
300 l->attrs.meter = NULL;
301 l->attrs.copy_data = 0;
302
303 l->attrs.hasher = NULL;
304
305 /* serializer/unserializer */
306 l->attrs.serializer = NULL;
307 l->attrs.unserializer = NULL;
308
309 assert(list_attrOk(l));
310
311 return 0;
312 }
313
314 /* setting list properties */
list_attributes_comparator(list_t * simclist_restrict l,element_comparator comparator_fun)315 int list_attributes_comparator(list_t *simclist_restrict l, element_comparator comparator_fun) {
316 if (l == NULL) return -1;
317
318 l->attrs.comparator = comparator_fun;
319
320 assert(list_attrOk(l));
321
322 return 0;
323 }
324
list_attributes_seeker(list_t * simclist_restrict l,element_seeker seeker_fun)325 int list_attributes_seeker(list_t *simclist_restrict l, element_seeker seeker_fun) {
326 if (l == NULL) return -1;
327
328 l->attrs.seeker = seeker_fun;
329 assert(list_attrOk(l));
330
331 return 0;
332 }
333
list_attributes_copy(list_t * simclist_restrict l,element_meter metric_fun,int copy_data)334 int list_attributes_copy(list_t *simclist_restrict l, element_meter metric_fun, int copy_data) {
335 if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1;
336
337 l->attrs.meter = metric_fun;
338 l->attrs.copy_data = copy_data;
339
340 assert(list_attrOk(l));
341
342 return 0;
343 }
344
list_attributes_hash_computer(list_t * simclist_restrict l,element_hash_computer hash_computer_fun)345 int list_attributes_hash_computer(list_t *simclist_restrict l, element_hash_computer hash_computer_fun) {
346 if (l == NULL) return -1;
347
348 l->attrs.hasher = hash_computer_fun;
349 assert(list_attrOk(l));
350 return 0;
351 }
352
list_attributes_serializer(list_t * simclist_restrict l,element_serializer serializer_fun)353 int list_attributes_serializer(list_t *simclist_restrict l, element_serializer serializer_fun) {
354 if (l == NULL) return -1;
355
356 l->attrs.serializer = serializer_fun;
357 assert(list_attrOk(l));
358 return 0;
359 }
360
list_attributes_unserializer(list_t * simclist_restrict l,element_unserializer unserializer_fun)361 int list_attributes_unserializer(list_t *simclist_restrict l, element_unserializer unserializer_fun) {
362 if (l == NULL) return -1;
363
364 l->attrs.unserializer = unserializer_fun;
365 assert(list_attrOk(l));
366 return 0;
367 }
368
list_append(list_t * simclist_restrict l,const void * data)369 int list_append(list_t *simclist_restrict l, const void *data) {
370 return list_insert_at(l, data, l->numels);
371 }
372
list_prepend(list_t * simclist_restrict l,const void * data)373 int list_prepend(list_t *simclist_restrict l, const void *data) {
374 return list_insert_at(l, data, 0);
375 }
376
list_fetch(list_t * simclist_restrict l)377 void *list_fetch(list_t *simclist_restrict l) {
378 return list_extract_at(l, 0);
379 }
380
list_get_at(const list_t * simclist_restrict l,unsigned int pos)381 void *list_get_at(const list_t *simclist_restrict l, unsigned int pos) {
382 struct list_entry_s *tmp;
383
384 tmp = list_findpos(l, pos);
385
386 return (tmp != NULL ? tmp->data : NULL);
387 }
388
list_get_max(const list_t * simclist_restrict l)389 void *list_get_max(const list_t *simclist_restrict l) {
390 return list_get_minmax(l, +1);
391 }
392
list_get_min(const list_t * simclist_restrict l)393 void *list_get_min(const list_t *simclist_restrict l) {
394 return list_get_minmax(l, -1);
395 }
396
397 /* REQUIRES {list->numels >= 1}
398 * return the min (versus < 0) or max value (v > 0) in l */
list_get_minmax(const list_t * simclist_restrict l,int versus)399 static void *list_get_minmax(const list_t *simclist_restrict l, int versus) {
400 void *curminmax;
401 struct list_entry_s *s;
402
403 if (l->attrs.comparator == NULL || l->numels == 0)
404 return NULL;
405
406 curminmax = l->head_sentinel->next->data;
407 for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
408 if (l->attrs.comparator(curminmax, s->data) * versus > 0)
409 curminmax = s->data;
410 }
411
412 return curminmax;
413 }
414
415 /* set tmp to point to element at index posstart in l */
list_findpos(const list_t * simclist_restrict l,int posstart)416 static simclist_inline struct list_entry_s *list_findpos(const list_t *simclist_restrict l, int posstart) {
417 struct list_entry_s *ptr;
418 float x;
419 int i;
420
421 if (l->head_sentinel == NULL || l->tail_sentinel == NULL) return NULL;
422
423 /* accept 1 slot overflow for fetching head and tail sentinels */
424 if (posstart < -1 || posstart > (int)l->numels) return NULL;
425
426 x = l->numels ? (float)(posstart+1) / l->numels : 0;
427 if (x <= 0.25) {
428 /* first quarter: get to posstart from head */
429 for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
430 } else if (x < 0.5) {
431 /* second quarter: get to posstart from mid */
432 for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
433 } else if (x <= 0.75) {
434 /* third quarter: get to posstart from mid */
435 for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
436 } else {
437 /* fourth quarter: get to posstart from tail */
438 for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
439 }
440
441 return ptr;
442 }
443
list_extract_at(list_t * simclist_restrict l,unsigned int pos)444 void *list_extract_at(list_t *simclist_restrict l, unsigned int pos) {
445 struct list_entry_s *tmp;
446 void *data;
447
448 if (l->iter_active || pos >= l->numels) return NULL;
449
450 tmp = list_findpos(l, pos);
451 if (tmp == NULL) {
452 return NULL;
453 }
454 data = tmp->data;
455
456 tmp->data = NULL; /* save data from list_drop_elem() free() */
457 list_drop_elem(l, tmp, pos);
458 l->numels--;
459
460 assert(list_repOk(l));
461
462 return data;
463 }
464
list_insert_at(list_t * simclist_restrict l,const void * data,unsigned int pos)465 int list_insert_at(list_t *simclist_restrict l, const void *data, unsigned int pos) {
466 struct list_entry_s *lent, *succ, *prec;
467
468 if (l->iter_active || pos > l->numels) return -1;
469
470 /* this code optimizes malloc() with a free-list */
471 if (l->spareelsnum > 0) {
472 lent = l->spareels[l->spareelsnum-1];
473 l->spareelsnum--;
474 } else {
475 lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
476 if (lent == NULL) {
477 return -1;
478 }
479 }
480
481 if (l->attrs.copy_data) {
482 /* make room for user' data (has to be copied) */
483 size_t datalen = l->attrs.meter(data);
484 lent->data = (struct list_entry_s *)malloc(datalen);
485 if (lent->data == NULL) {
486 if (!(l->spareelsnum > 0)) {
487 free(lent);
488 }
489 return -1;
490 }
491 memcpy(lent->data, data, datalen);
492 } else {
493 lent->data = (void*)data;
494 }
495
496 /* actually append element */
497 prec = list_findpos(l, pos-1);
498 if (prec == NULL) {
499 if (l->attrs.copy_data) {
500 free(lent->data);
501 }
502 if (!(l->spareelsnum > 0)) {
503 free(lent);
504 }
505 return -1;
506 }
507 succ = prec->next;
508
509 prec->next = lent;
510 lent->prev = prec;
511 lent->next = succ;
512 succ->prev = lent;
513
514 l->numels++;
515
516 /* fix mid pointer */
517 if (l->numels == 1) { /* first element, set pointer */
518 l->mid = lent;
519 } else if (l->numels % 2) { /* now odd */
520 if (pos >= (l->numels-1)/2) l->mid = l->mid->next;
521 } else { /* now even */
522 if (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
523 }
524
525 assert(list_repOk(l));
526
527 return 1;
528 }
529
list_delete(list_t * simclist_restrict l,const void * data)530 int list_delete(list_t *simclist_restrict l, const void *data) {
531 int pos, r;
532
533 pos = list_locate(l, data);
534 if (pos < 0)
535 return -1;
536
537 r = list_delete_at(l, pos);
538 if (r < 0)
539 return -1;
540
541 assert(list_repOk(l));
542
543 return 0;
544 }
545
list_delete_at(list_t * simclist_restrict l,unsigned int pos)546 int list_delete_at(list_t *simclist_restrict l, unsigned int pos) {
547 struct list_entry_s *delendo;
548
549
550 if (l->iter_active || pos >= l->numels) return -1;
551
552 delendo = list_findpos(l, pos);
553
554 list_drop_elem(l, delendo, pos);
555
556 l->numels--;
557
558
559 assert(list_repOk(l));
560
561 return 0;
562 }
563
list_delete_range(list_t * simclist_restrict l,unsigned int posstart,unsigned int posend)564 int list_delete_range(list_t *simclist_restrict l, unsigned int posstart, unsigned int posend) {
565 struct list_entry_s *lastvalid, *tmp, *tmp2;
566 unsigned int i;
567 int movedx;
568 unsigned int numdel, midposafter;
569
570 if (l->iter_active || posend < posstart || posend >= l->numels) return -1;
571
572 tmp = list_findpos(l, posstart); /* first el to be deleted */
573 if (tmp == NULL) {
574 return -1;
575 }
576 lastvalid = tmp->prev; /* last valid element */
577
578 numdel = posend - posstart + 1;
579 midposafter = (l->numels-1-numdel)/2;
580
581 midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
582 movedx = midposafter - (l->numels-1)/2;
583
584 if (movedx > 0) { /* move right */
585 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++);
586 } else { /* move left */
587 movedx = -movedx;
588 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++);
589 }
590
591 assert(posstart == 0 || lastvalid != l->head_sentinel);
592 i = posstart;
593 if (l->attrs.copy_data) {
594 /* also free element data */
595 for (; i <= posend; i++) {
596 tmp2 = tmp;
597 tmp = tmp->next;
598 if (tmp2->data != NULL) free(tmp2->data);
599 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
600 l->spareels[l->spareelsnum++] = tmp2;
601 } else {
602 free(tmp2);
603 }
604 }
605 } else {
606 /* only free containers */
607 for (; i <= posend; i++) {
608 tmp2 = tmp;
609 tmp = tmp->next;
610 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
611 l->spareels[l->spareelsnum++] = tmp2;
612 } else {
613 free(tmp2);
614 }
615 }
616 }
617 assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));
618
619 lastvalid->next = tmp;
620 tmp->prev = lastvalid;
621
622 l->numels -= posend - posstart + 1;
623
624 assert(list_repOk(l));
625
626 return 0;
627 }
628
list_clear(list_t * simclist_restrict l)629 int list_clear(list_t *simclist_restrict l) {
630 struct list_entry_s *s;
631
632 if (l->iter_active) return -1;
633
634 if (l->head_sentinel && l->tail_sentinel) {
635 if (l->attrs.copy_data) { /* also free user data */
636 /* spare a loop conditional with two loops: spareing elems and freeing elems */
637 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
638 /* move elements as spares as long as there is room */
639 if (s->data != NULL) free(s->data);
640 l->spareels[l->spareelsnum++] = s;
641 }
642 while (s != l->tail_sentinel) {
643 /* free the remaining elems */
644 if (s->data != NULL) free(s->data);
645 s = s->next;
646 free(s->prev);
647 }
648 l->head_sentinel->next = l->tail_sentinel;
649 l->tail_sentinel->prev = l->head_sentinel;
650 } else { /* only free element containers */
651 /* spare a loop conditional with two loops: spareing elems and freeing elems */
652 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
653 /* move elements as spares as long as there is room */
654 l->spareels[l->spareelsnum++] = s;
655 }
656 while (s != l->tail_sentinel) {
657 /* free the remaining elems */
658 s = s->next;
659 free(s->prev);
660 }
661 l->head_sentinel->next = l->tail_sentinel;
662 l->tail_sentinel->prev = l->head_sentinel;
663 }
664 }
665 l->numels = 0;
666 l->mid = NULL;
667
668 assert(list_repOk(l));
669
670 return 0;
671 }
672
list_size(const list_t * simclist_restrict l)673 unsigned int list_size(const list_t *simclist_restrict l) {
674 return l->numels;
675 }
676
list_empty(const list_t * simclist_restrict l)677 int list_empty(const list_t *simclist_restrict l) {
678 return (l->numels == 0);
679 }
680
list_locate(const list_t * simclist_restrict l,const void * data)681 int list_locate(const list_t *simclist_restrict l, const void *data) {
682 struct list_entry_s *el;
683 int pos = 0;
684
685 if (l->head_sentinel == NULL || l->tail_sentinel == NULL) return -1;
686
687 if (l->attrs.comparator != NULL) {
688 /* use comparator */
689 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
690 if (l->attrs.comparator(data, el->data) == 0) break;
691 }
692 } else {
693 /* compare references */
694 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
695 if (el->data == data) break;
696 }
697 }
698 if (el == l->tail_sentinel) return -1;
699
700 return pos;
701 }
702
list_seek(list_t * simclist_restrict l,const void * indicator)703 void *list_seek(list_t *simclist_restrict l, const void *indicator) {
704 const struct list_entry_s *iter;
705
706 if (l->attrs.seeker == NULL) return NULL;
707
708 if (l->head_sentinel == NULL || l->tail_sentinel == NULL) return NULL;
709
710 for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
711 if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data;
712 }
713
714 return NULL;
715 }
716
list_contains(const list_t * simclist_restrict l,const void * data)717 int list_contains(const list_t *simclist_restrict l, const void *data) {
718 return (list_locate(l, data) >= 0);
719 }
720
list_concat(const list_t * l1,const list_t * l2,list_t * simclist_restrict dest)721 int list_concat(const list_t *l1, const list_t *l2, list_t *simclist_restrict dest) {
722 struct list_entry_s *el, *srcel;
723 unsigned int cnt;
724 int err;
725
726 if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
727 return -1;
728
729 if (l1->head_sentinel == NULL || l1->tail_sentinel == NULL
730 || l2->head_sentinel == NULL || l2->tail_sentinel == NULL) return -1;
731
732 if (0 != list_init(dest)) {
733 return -1;
734 }
735
736 dest->numels = l1->numels + l2->numels;
737 if (dest->numels == 0)
738 return 0;
739
740 /* copy list1 */
741 srcel = l1->head_sentinel->next;
742 el = dest->head_sentinel;
743 while (srcel != l1->tail_sentinel) {
744 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
745 if (el->next == NULL) {
746 return -1;
747 }
748 el->next->prev = el;
749 el = el->next;
750 el->data = srcel->data;
751 srcel = srcel->next;
752 }
753 dest->mid = el; /* approximate position (adjust later) */
754 /* copy list 2 */
755 srcel = l2->head_sentinel->next;
756 while (srcel != l2->tail_sentinel) {
757 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
758 if (el->next == NULL) {
759 return -1;
760 }
761 el->next->prev = el;
762 el = el->next;
763 el->data = srcel->data;
764 srcel = srcel->next;
765 }
766 el->next = dest->tail_sentinel;
767 dest->tail_sentinel->prev = el;
768
769 /* fix mid pointer */
770 err = l2->numels - l1->numels;
771 if ((err+1)/2 > 0) { /* correct pos RIGHT (err-1)/2 moves */
772 err = (err+1)/2;
773 for (cnt = 0; dest->mid && cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next;
774 } else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */
775 err = -err/2;
776 for (cnt = 0; dest->mid && cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev;
777 }
778
779 assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));
780
781 return 0;
782 }
783
list_sort(list_t * simclist_restrict l,int versus)784 int list_sort(list_t *simclist_restrict l, int versus) {
785 if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */
786 return -1;
787
788 if (l->numels <= 1)
789 return 0;
790
791 if (l->head_sentinel == NULL || l->tail_sentinel == NULL) return -1;
792
793 list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
794 assert(list_repOk(l));
795 return 0;
796 }
797
798 #ifdef SIMCLIST_WITH_THREADS
799 struct list_sort_wrappedparams {
800 list_t *simclist_restrict l;
801 int versus;
802 unsigned int first, last;
803 struct list_entry_s *fel, *lel;
804 };
805
list_sort_quicksort_threadwrapper(void * wrapped_params)806 static void *list_sort_quicksort_threadwrapper(void *wrapped_params) {
807 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params;
808 list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
809 free(wp);
810 pthread_exit(NULL);
811 return NULL;
812 }
813 #endif
814
list_sort_selectionsort(list_t * simclist_restrict l,int versus,unsigned int first,struct list_entry_s * fel,unsigned int last,struct list_entry_s * lel)815 static simclist_inline void list_sort_selectionsort(list_t *simclist_restrict l, int versus,
816 unsigned int first, struct list_entry_s *fel,
817 unsigned int last, struct list_entry_s *lel) {
818 struct list_entry_s *cursor, *toswap, *firstunsorted;
819 void *tmpdata;
820
821 if (last <= first) /* <= 1-element lists are always sorted */
822 return;
823
824 for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
825 /* find min or max in the remainder of the list */
826 for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
827 if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
828 if (toswap != firstunsorted) { /* swap firstunsorted with toswap */
829 tmpdata = firstunsorted->data;
830 firstunsorted->data = toswap->data;
831 toswap->data = tmpdata;
832 }
833 }
834 }
835
list_sort_quicksort(list_t * simclist_restrict l,int versus,unsigned int first,struct list_entry_s * fel,unsigned int last,struct list_entry_s * lel)836 static void list_sort_quicksort(list_t *simclist_restrict l, int versus,
837 unsigned int first, struct list_entry_s *fel,
838 unsigned int last, struct list_entry_s *lel) {
839 unsigned int pivotid;
840 unsigned int i;
841 register struct list_entry_s *pivot;
842 struct list_entry_s *left, *right;
843 void *tmpdata;
844 #ifdef SIMCLIST_WITH_THREADS
845 pthread_t tid;
846 int traised;
847 #endif
848
849
850 if (last <= first) /* <= 1-element lists are always sorted */
851 return;
852
853 if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
854 list_sort_selectionsort(l, versus, first, fel, last, lel);
855 return;
856 }
857
858 /* base of iteration: one element list */
859 if (! (last > first)) return;
860
861 pivotid = (get_random() % (last - first + 1));
862 /* pivotid = (last - first + 1) / 2; */
863
864 /* find pivot */
865 if (pivotid < (last - first + 1)/2) {
866 for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
867 } else {
868 for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
869 }
870
871 /* smaller PIVOT bigger */
872 left = fel;
873 right = lel;
874 /* iterate --- left ---> PIV <--- right --- */
875 while (left != pivot && right != pivot) {
876 for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
877 /* left points to a smaller element, or to pivot */
878 for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
879 /* right points to a bigger element, or to pivot */
880 if (left != pivot && right != pivot) {
881 /* swap, then move iterators */
882 tmpdata = left->data;
883 left->data = right->data;
884 right->data = tmpdata;
885
886 left = left->next;
887 right = right->prev;
888 }
889 }
890
891 /* now either left points to pivot (end run), or right */
892 if (right == pivot) { /* left part longer */
893 while (left != pivot) {
894 if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
895 tmpdata = left->data;
896 left->data = pivot->prev->data;
897 pivot->prev->data = pivot->data;
898 pivot->data = tmpdata;
899 pivot = pivot->prev;
900 pivotid--;
901 if (pivot == left) break;
902 } else {
903 left = left->next;
904 }
905 }
906 } else { /* right part longer */
907 while (right != pivot) {
908 if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
909 /* move current right before pivot */
910 tmpdata = right->data;
911 right->data = pivot->next->data;
912 pivot->next->data = pivot->data;
913 pivot->data = tmpdata;
914 pivot = pivot->next;
915 pivotid++;
916 if (pivot == right) break;
917 } else {
918 right = right->prev;
919 }
920 }
921 }
922
923 /* sort sublists A and B : |---A---| pivot |---B---| */
924
925 #ifdef SIMCLIST_WITH_THREADS
926 traised = 0;
927 if (pivotid > 0) {
928 /* prepare wrapped args, then start thread */
929 if (l->threadcount < SIMCLIST_MAXTHREADS-1) {
930 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams));
931 if (wp == NULL) {
932 return -1;
933 }
934 l->threadcount++;
935 traised = 1;
936 wp->l = l;
937 wp->versus = versus;
938 wp->first = first;
939 wp->fel = fel;
940 wp->last = first+pivotid-1;
941 wp->lel = pivot->prev;
942 if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
943 free(wp);
944 traised = 0;
945 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
946 }
947 } else {
948 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
949 }
950 }
951 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
952 if (traised) {
953 pthread_join(tid, (void **)NULL);
954 l->threadcount--;
955 }
956 #else
957 if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
958 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
959 #endif
960 }
961
list_iterator_start(list_t * simclist_restrict l)962 int list_iterator_start(list_t *simclist_restrict l) {
963 if (l->iter_active) return 0;
964 if (l->head_sentinel == NULL) return -1;
965 l->iter_pos = 0;
966 l->iter_active = 1;
967 l->iter_curentry = l->head_sentinel->next;
968 return 1;
969 }
970
list_iterator_next(list_t * simclist_restrict l)971 void *list_iterator_next(list_t *simclist_restrict l) {
972 void *toret;
973
974 if (! l->iter_active) return NULL;
975
976 toret = l->iter_curentry->data;
977 l->iter_curentry = l->iter_curentry->next;
978 l->iter_pos++;
979
980 return toret;
981 }
982
list_iterator_hasnext(const list_t * simclist_restrict l)983 int list_iterator_hasnext(const list_t *simclist_restrict l) {
984 if (! l->iter_active) return 0;
985 return (l->iter_pos < l->numels);
986 }
987
list_iterator_stop(list_t * simclist_restrict l)988 int list_iterator_stop(list_t *simclist_restrict l) {
989 if (! l->iter_active) return 0;
990 l->iter_pos = 0;
991 l->iter_active = 0;
992 return 1;
993 }
994
list_hash(const list_t * simclist_restrict l,list_hash_t * simclist_restrict hash)995 int list_hash(const list_t *simclist_restrict l, list_hash_t *simclist_restrict hash) {
996 struct list_entry_s *x;
997 list_hash_t tmphash;
998
999 assert(hash != NULL);
1000
1001 tmphash = l->numels * 2 + 100;
1002 if (l->attrs.hasher == NULL) {
1003 #ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES
1004 /* ENABLE WITH CARE !! */
1005 #warning "Memlocation-based hash is consistent only for testing modification in the same program run."
1006 int i;
1007
1008 /* only use element references */
1009 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1010 for (i = 0; i < sizeof(x->data); i++) {
1011 tmphash += (tmphash ^ (uintptr_t)x->data);
1012 }
1013 tmphash += tmphash % l->numels;
1014 }
1015 #else
1016 return -1;
1017 #endif
1018 } else {
1019 /* hash each element with the user-given function */
1020 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1021 tmphash += tmphash ^ l->attrs.hasher(x->data);
1022 tmphash +=* hash % l->numels;
1023 }
1024 }
1025
1026 *hash = tmphash;
1027
1028 return 0;
1029 }
1030
1031 #ifdef SIMCLIST_DUMPRESTORE
1032 /* Workaround for a missing gettimeofday on Windows */
1033 #if defined(_MSC_VER) || defined(__MINGW32__)
gettimeofday(struct timeval * tp,void * tzp)1034 int gettimeofday(struct timeval* tp, void* tzp) {
1035 DWORD t;
1036 t = timeGetTime();
1037 tp->tv_sec = t / 1000;
1038 tp->tv_usec = t % 1000;
1039 return 0;
1040 }
1041 #endif
list_dump_getinfo_filedescriptor(int fd,list_dump_info_t * simclist_restrict info)1042 int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *simclist_restrict info) {
1043 int32_t terminator_head, terminator_tail;
1044 uint32_t elemlen;
1045 off_t hop;
1046
1047
1048 /* version */
1049 READ_ERRCHECK(fd, & info->version, sizeof(info->version));
1050 info->version = ntohs(info->version);
1051 if (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
1052 errno = EILSEQ;
1053 return -1;
1054 }
1055
1056 /* timestamp */
1057 READ_ERRCHECK(fd, & info->timestamp, sizeof(info->timestamp));
1058 info->timestamp = hton64(info->timestamp);
1059
1060 /* list terminator (to check thereafter) */
1061 READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head));
1062 terminator_head = ntohl(terminator_head);
1063
1064 /* list size */
1065 READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size));
1066 info->list_size = ntohl(info->list_size);
1067
1068 /* number of elements */
1069 READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels));
1070 info->list_numels = ntohl(info->list_numels);
1071
1072 /* length of each element (for checking for consistency) */
1073 READ_ERRCHECK(fd, & elemlen, sizeof(elemlen));
1074 elemlen = ntohl(elemlen);
1075
1076 /* list hash */
1077 READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash));
1078 info->list_hash = ntohl(info->list_hash);
1079
1080 /* check consistency */
1081 if (elemlen > 0) {
1082 /* constant length, hop by size only */
1083 hop = info->list_size;
1084 } else {
1085 /* non-constant length, hop by size + all element length blocks */
1086 hop = info->list_size + elemlen*info->list_numels;
1087 }
1088 if (lseek(fd, hop, SEEK_CUR) == -1) {
1089 return -1;
1090 }
1091
1092 /* read the trailing value and compare with terminator_head */
1093 READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail));
1094 terminator_tail = ntohl(terminator_tail);
1095
1096 if (terminator_head == terminator_tail)
1097 info->consistent = 1;
1098 else
1099 info->consistent = 0;
1100
1101 return 0;
1102 }
1103
list_dump_getinfo_file(const char * simclist_restrict filename,list_dump_info_t * simclist_restrict info)1104 int list_dump_getinfo_file(const char *simclist_restrict filename, list_dump_info_t *simclist_restrict info) {
1105 int fd, ret;
1106
1107 fd = open(filename, O_RDONLY, 0);
1108 if (fd < 0) return -1;
1109
1110 ret = list_dump_getinfo_filedescriptor(fd, info);
1111 close(fd);
1112
1113 return ret;
1114 }
1115
list_dump_filedescriptor(const list_t * simclist_restrict l,int fd,size_t * simclist_restrict len)1116 int list_dump_filedescriptor(const list_t *simclist_restrict l, int fd, size_t *simclist_restrict len) {
1117 struct list_entry_s *x;
1118 void *ser_buf;
1119 uint32_t bufsize;
1120 struct timeval timeofday;
1121 struct list_dump_header_s header;
1122
1123 if (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
1124 errno = ENOTTY;
1125 return -1;
1126 }
1127
1128 /**** DUMP FORMAT ****
1129
1130 [ ver timestamp | totlen numels elemlen hash | DATA ]
1131
1132 where DATA can be:
1133 @ for constant-size list (element size is constant; elemlen > 0)
1134 [ elem elem ... elem ]
1135 @ for other lists (element size dictated by element_meter each time; elemlen <= 0)
1136 [ size elem size elem ... size elem ]
1137
1138 all integers are encoded in NETWORK BYTE FORMAT
1139 *****/
1140
1141
1142 /* prepare HEADER */
1143 /* version */
1144 header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );
1145
1146 /* timestamp */
1147 gettimeofday(&timeofday, NULL);
1148 header.timestamp = (int64_t)timeofday.tv_sec * 1000000 + (int64_t)timeofday.tv_usec;
1149 header.timestamp = hton64(header.timestamp);
1150
1151 header.rndterm = htonl((int32_t)get_random());
1152
1153 /* total list size is postprocessed afterwards */
1154
1155 /* number of elements */
1156 header.numels = htonl(l->numels);
1157
1158 /* include an hash, if possible */
1159 if (l->attrs.hasher != NULL) {
1160 if (htonl(list_hash(l, & header.listhash)) != 0) {
1161 /* could not compute list hash! */
1162 return -1;
1163 }
1164 } else {
1165 header.listhash = htonl(0);
1166 }
1167
1168 header.totlistlen = header.elemlen = 0;
1169
1170 /* leave room for the header at the beginning of the file */
1171 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
1172 /* errno set by lseek() */
1173 return -1;
1174 }
1175
1176 /* write CONTENT */
1177 if (l->numels > 0) {
1178 /* SPECULATE that the list has constant element size */
1179
1180 if (l->attrs.serializer != NULL) { /* user user-specified serializer */
1181 /* get preliminary length of serialized element in header.elemlen */
1182 ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
1183 free(ser_buf);
1184 /* request custom serialization of each element */
1185 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1186 ser_buf = l->attrs.serializer(x->data, &bufsize);
1187 header.totlistlen += bufsize;
1188 if (header.elemlen != 0) { /* continue on speculation */
1189 if (header.elemlen != bufsize) {
1190 free(ser_buf);
1191 /* constant element length speculation broken! */
1192 header.elemlen = 0;
1193 header.totlistlen = 0;
1194 x = l->head_sentinel;
1195 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
1196 /* errno set by lseek() */
1197 return -1;
1198 }
1199 /* restart from the beginning */
1200 continue;
1201 }
1202 /* speculation confirmed */
1203 WRITE_ERRCHECK(fd, ser_buf, bufsize);
1204 } else { /* speculation found broken */
1205 WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t));
1206 WRITE_ERRCHECK(fd, ser_buf, bufsize);
1207 }
1208 free(ser_buf);
1209 }
1210 } else if (l->attrs.meter != NULL) {
1211 header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);
1212
1213 /* serialize the element straight from its data */
1214 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1215 bufsize = l->attrs.meter(x->data);
1216 header.totlistlen += bufsize;
1217 if (header.elemlen != 0) {
1218 if (header.elemlen != bufsize) {
1219 /* constant element length speculation broken! */
1220 header.elemlen = 0;
1221 header.totlistlen = 0;
1222 x = l->head_sentinel;
1223 /* restart from the beginning */
1224 continue;
1225 }
1226 WRITE_ERRCHECK(fd, x->data, bufsize);
1227 } else {
1228 WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t));
1229 WRITE_ERRCHECK(fd, x->data, bufsize);
1230 }
1231 }
1232 }
1233 /* adjust endianness */
1234 header.elemlen = htonl(header.elemlen);
1235 header.totlistlen = htonl(header.totlistlen);
1236 }
1237
1238 /* write random terminator */
1239 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* list terminator */
1240
1241
1242 /* write header */
1243 lseek(fd, 0, SEEK_SET);
1244
1245 WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver)); /* version */
1246 WRITE_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp)); /* timestamp */
1247 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* random terminator */
1248
1249 WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); /* total length of elements */
1250 WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels)); /* number of elements */
1251 WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); /* size of each element, or 0 for independent */
1252 WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); /* list hash, or 0 for "ignore" */
1253
1254
1255 /* possibly store total written length in "len" */
1256 if (len != NULL) {
1257 *len = sizeof(header) + ntohl(header.totlistlen);
1258 }
1259
1260 return 0;
1261 }
1262
list_restore_filedescriptor(list_t * simclist_restrict l,int fd,size_t * simclist_restrict len)1263 int list_restore_filedescriptor(list_t *simclist_restrict l, int fd, size_t *simclist_restrict len) {
1264 struct list_dump_header_s header;
1265 unsigned long cnt;
1266 void *buf = NULL;
1267 uint32_t elsize, totreadlen, totmemorylen;
1268
1269 memset(& header, 0, sizeof(header));
1270
1271 /* read header */
1272
1273 /* version */
1274 READ_ERRCHECK(fd, &header.ver, sizeof(header.ver));
1275 header.ver = ntohs(header.ver);
1276 if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
1277 errno = EILSEQ;
1278 return -1;
1279 }
1280
1281 /* timestamp */
1282 READ_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp));
1283
1284 /* list terminator */
1285 READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));
1286
1287 header.rndterm = ntohl(header.rndterm);
1288
1289 /* total list size */
1290 READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));
1291 header.totlistlen = ntohl(header.totlistlen);
1292
1293 /* number of elements */
1294 READ_ERRCHECK(fd, & header.numels, sizeof(header.numels));
1295 header.numels = ntohl(header.numels);
1296
1297 /* length of every element, or '0' = variable */
1298 READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));
1299 header.elemlen = ntohl(header.elemlen);
1300
1301 /* list hash, or 0 = 'ignore' */
1302 READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));
1303 header.listhash = ntohl(header.listhash);
1304
1305
1306 /* read content */
1307 totreadlen = totmemorylen = 0;
1308 if (header.elemlen > 0) {
1309 /* elements have constant size = header.elemlen */
1310 if (l->attrs.unserializer != NULL) {
1311 /* use unserializer */
1312 buf = malloc(header.elemlen);
1313 if (buf == NULL) {
1314 return -1;
1315 }
1316 for (cnt = 0; cnt < header.numels; cnt++) {
1317 READ_ERRCHECK(fd, buf, header.elemlen);
1318 list_append(l, l->attrs.unserializer(buf, & elsize));
1319 totmemorylen += elsize;
1320 }
1321 } else {
1322 /* copy verbatim into memory */
1323 for (cnt = 0; cnt < header.numels; cnt++) {
1324 buf = malloc(header.elemlen);
1325 if (buf == NULL) {
1326 return -1;
1327 }
1328 READ_ERRCHECK(fd, buf, header.elemlen);
1329 list_append(l, buf);
1330 }
1331 totmemorylen = header.numels * header.elemlen;
1332 }
1333 totreadlen = header.numels * header.elemlen;
1334 } else {
1335 /* elements have variable size. Each element is preceded by its size */
1336 if (l->attrs.unserializer != NULL) {
1337 /* use unserializer */
1338 for (cnt = 0; cnt < header.numels; cnt++) {
1339 READ_ERRCHECK(fd, & elsize, sizeof(elsize));
1340 buf = malloc((size_t)elsize);
1341 if (buf == NULL) {
1342 return -1;
1343 }
1344 READ_ERRCHECK(fd, buf, elsize);
1345 totreadlen += elsize;
1346 list_append(l, l->attrs.unserializer(buf, & elsize));
1347 totmemorylen += elsize;
1348 }
1349 } else {
1350 /* copy verbatim into memory */
1351 for (cnt = 0; cnt < header.numels; cnt++) {
1352 READ_ERRCHECK(fd, & elsize, sizeof(elsize));
1353 buf = malloc(elsize);
1354 if (buf == NULL) {
1355 return -1;
1356 }
1357 READ_ERRCHECK(fd, buf, elsize);
1358 totreadlen += elsize;
1359 list_append(l, buf);
1360 }
1361 totmemorylen = totreadlen;
1362 }
1363 }
1364
1365 READ_ERRCHECK(fd, &elsize, sizeof(elsize)); /* read list terminator */
1366 elsize = ntohl(elsize);
1367
1368 /* possibly verify the list consistency */
1369 /* wrt hash */
1370 /* don't do that
1371 if (header.listhash != 0 && header.listhash != list_hash(l)) {
1372 errno = ECANCELED;
1373 return -1;
1374 }
1375 */
1376
1377 /* wrt header */
1378 if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
1379 errno = EPROTO;
1380 return -1;
1381 }
1382
1383 /* wrt file */
1384 if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
1385 errno = EPROTO;
1386 return -1;
1387 }
1388
1389 if (len != NULL) {
1390 *len = totmemorylen;
1391 }
1392
1393 return 0;
1394 }
1395
list_dump_file(const list_t * simclist_restrict l,const char * simclist_restrict filename,size_t * simclist_restrict len)1396 int list_dump_file(const list_t *simclist_restrict l, const char *simclist_restrict filename, size_t *simclist_restrict len) {
1397 int fd, mode;
1398 size_t sizetoret;
1399 mode = O_RDWR | O_CREAT | O_TRUNC;
1400 #ifndef _WIN32
1401 mode |= S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;
1402 #endif
1403 fd = open(filename, mode);
1404 if (fd < 0) return -1;
1405
1406 sizetoret = list_dump_filedescriptor(l, fd, len);
1407 close(fd);
1408
1409 return sizetoret;
1410 }
1411
list_restore_file(list_t * simclist_restrict l,const char * simclist_restrict filename,size_t * simclist_restrict len)1412 int list_restore_file(list_t *simclist_restrict l, const char *simclist_restrict filename, size_t *simclist_restrict len) {
1413 int fd;
1414 size_t totdata;
1415
1416 fd = open(filename, O_RDONLY, 0);
1417 if (fd < 0) return -1;
1418
1419 totdata = list_restore_filedescriptor(l, fd, len);
1420 close(fd);
1421
1422 return totdata;
1423 }
1424 #endif /* ifdef SIMCLIST_DUMPRESTORE */
1425
1426
list_drop_elem(list_t * simclist_restrict l,struct list_entry_s * tmp,unsigned int pos)1427 static int list_drop_elem(list_t *simclist_restrict l, struct list_entry_s *tmp, unsigned int pos) {
1428 if (tmp == NULL) return -1;
1429
1430 /* fix mid pointer. This is wrt the PRE situation */
1431 if (l->numels % 2) { /* now odd */
1432 /* sort out the base case by hand */
1433 if (l->numels == 1) l->mid = NULL;
1434 else if (pos >= l->numels/2) l->mid = l->mid->prev;
1435 } else { /* now even */
1436 if (pos < l->numels/2) l->mid = l->mid->next;
1437 }
1438
1439 tmp->prev->next = tmp->next;
1440 tmp->next->prev = tmp->prev;
1441
1442 /* free what's to be freed */
1443 if (l->attrs.copy_data && tmp->data != NULL)
1444 free(tmp->data);
1445
1446 if (l->spareels != NULL && l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
1447 l->spareels[l->spareelsnum++] = tmp;
1448 } else {
1449 free(tmp);
1450 }
1451
1452 return 0;
1453 }
1454
1455 /* ready-made comparators and meters */
1456 #define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); }
1457
1458 SIMCLIST_NUMBER_COMPARATOR(int8_t)
SIMCLIST_NUMBER_COMPARATOR(int16_t)1459 SIMCLIST_NUMBER_COMPARATOR(int16_t)
1460 SIMCLIST_NUMBER_COMPARATOR(int32_t)
1461 SIMCLIST_NUMBER_COMPARATOR(int64_t)
1462
1463 SIMCLIST_NUMBER_COMPARATOR(uint8_t)
1464 SIMCLIST_NUMBER_COMPARATOR(uint16_t)
1465 SIMCLIST_NUMBER_COMPARATOR(uint32_t)
1466 SIMCLIST_NUMBER_COMPARATOR(uint64_t)
1467
1468 SIMCLIST_NUMBER_COMPARATOR(float)
1469 SIMCLIST_NUMBER_COMPARATOR(double)
1470
1471 int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); }
1472
1473 /* ready-made metric functions */
1474 #define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); }
1475
1476 SIMCLIST_METER(int8_t)
SIMCLIST_METER(int16_t)1477 SIMCLIST_METER(int16_t)
1478 SIMCLIST_METER(int32_t)
1479 SIMCLIST_METER(int64_t)
1480
1481 SIMCLIST_METER(uint8_t)
1482 SIMCLIST_METER(uint16_t)
1483 SIMCLIST_METER(uint32_t)
1484 SIMCLIST_METER(uint64_t)
1485
1486 SIMCLIST_METER(float)
1487 SIMCLIST_METER(double)
1488
1489 size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; }
1490
1491 /* ready-made hashing functions */
1492 #define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); }
1493
1494 SIMCLIST_HASHCOMPUTER(int8_t)
SIMCLIST_HASHCOMPUTER(int16_t)1495 SIMCLIST_HASHCOMPUTER(int16_t)
1496 SIMCLIST_HASHCOMPUTER(int32_t)
1497 SIMCLIST_HASHCOMPUTER(int64_t)
1498
1499 SIMCLIST_HASHCOMPUTER(uint8_t)
1500 SIMCLIST_HASHCOMPUTER(uint16_t)
1501 SIMCLIST_HASHCOMPUTER(uint32_t)
1502 SIMCLIST_HASHCOMPUTER(uint64_t)
1503
1504 SIMCLIST_HASHCOMPUTER(float)
1505 SIMCLIST_HASHCOMPUTER(double)
1506
1507 list_hash_t list_hashcomputer_string(const void *el) {
1508 size_t l;
1509 list_hash_t hash = 123;
1510 const char *str = (const char *)el;
1511 char plus;
1512
1513 for (l = 0; str[l] != '\0'; l++) {
1514 if (l) plus = hash ^ str[l];
1515 else plus = hash ^ (str[l] - str[0]);
1516 hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t))));
1517 }
1518
1519 return hash;
1520 }
1521
1522
1523 #ifndef NDEBUG
list_repOk(const list_t * simclist_restrict l)1524 static int list_repOk(const list_t *simclist_restrict l) {
1525 int ok, i;
1526 struct list_entry_s *s;
1527
1528 ok = (l != NULL) && (
1529 /* head/tail checks */
1530 (l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
1531 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
1532 /* empty list */
1533 (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
1534 /* spare elements checks */
1535 l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
1536 );
1537
1538 if (!ok) return 0;
1539
1540 if (l->numels >= 1) {
1541 /* correct referencing */
1542 for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
1543 if (s->next->prev != s) break;
1544 }
1545 ok = (i == (int)(l->numels-1)/2 && l->mid == s);
1546 if (!ok) return 0;
1547 for (; s->next != NULL; i++, s = s->next) {
1548 if (s->next->prev != s) break;
1549 }
1550 ok = (i == (int)l->numels && s == l->tail_sentinel);
1551 }
1552
1553 return ok;
1554 }
1555
list_attrOk(const list_t * simclist_restrict l)1556 static int list_attrOk(const list_t *simclist_restrict l) {
1557 int ok;
1558
1559 ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);
1560 return ok;
1561 }
1562
1563 #endif
1564
1565