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