src/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 */
 181 struct list_dump_header_s {
 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