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