pcsc-lite  1.8.3
simclist.c
00001 /*
00002  * Copyright (c) 2007,2008,2009,2010,2011 Mij <mij@bitchx.it>
00003  *
00004  * Permission to use, copy, modify, and distribute this software for any
00005  * purpose with or without fee is hereby granted, provided that the above
00006  * copyright notice and this permission notice appear in all copies.
00007  *
00008  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
00009  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
00010  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
00011  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00012  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
00013  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
00014  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00015  */
00016 
00017 
00018 /*
00019  * SimCList library. See http://mij.oltrelinux.com/devel/simclist
00020  */
00021 
00022 /* SimCList implementation, version 1.6 */
00023 
00024 #include <stdlib.h>
00025 #include <string.h>
00026 #include <errno.h>          /* for setting errno */
00027 #include <sys/types.h>
00028 #ifndef _WIN32
00029     /* not in Windows! */
00030 #   include <unistd.h>
00031 #   include <stdint.h>
00032 #endif
00033 #ifndef SIMCLIST_NO_DUMPRESTORE
00034     /* includes for dump/restore */
00035 #   include <time.h>
00036 #   include <sys/uio.h>     /* for READ_ERRCHECK() and write() */
00037 #   include <fcntl.h>       /* for open() etc */
00038 #   ifndef _WIN32
00039 #       include <arpa/inet.h>  /* for htons() on UNIX */
00040 #   else
00041 #       include <winsock2.h>  /* for htons() on Windows */
00042 #   endif
00043 #endif
00044 
00045 /* disable asserts */
00046 #ifndef SIMCLIST_DEBUG
00047 #define NDEBUG
00048 #endif
00049 
00050 #include <assert.h>
00051 
00052 
00053 #include <sys/stat.h>       /* for open()'s access modes S_IRUSR etc */
00054 #include <limits.h>
00055 
00056 #if defined(_MSC_VER) || defined(__MINGW32__)
00057 /* provide gettimeofday() missing in Windows */
00058 int gettimeofday(struct timeval *tp, void *tzp) {
00059     DWORD t;
00060 
00061     /* XSI says: "If tzp is not a null pointer, the behavior is unspecified" */
00062     assert(tzp == NULL);
00063 
00064     t = timeGetTime();
00065     tp->tv_sec = t / 1000;
00066     tp->tv_usec = t % 1000;
00067     return 0;
00068 }
00069 #endif
00070 
00071 
00072 /* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */
00073 #if !defined(_WIN32) || !defined(_MSC_VER)
00074 #   include <inttypes.h>   /* (u)int*_t */
00075 #else
00076 #   include <basetsd.h>
00077 typedef UINT8   uint8_t;
00078 typedef UINT16  uint16_t;
00079 typedef ULONG32 uint32_t;
00080 typedef UINT64  uint64_t;
00081 typedef INT8    int8_t;
00082 typedef INT16   int16_t;
00083 typedef LONG32  int32_t;
00084 typedef INT64   int64_t;
00085 #endif
00086 
00087 
00088 /* define some commodity macros for Dump/Restore functionality */
00089 #ifndef SIMCLIST_NO_DUMPRESTORE
00090 /* write() decorated with error checking logic */
00091 #define WRITE_ERRCHECK(fd, msgbuf, msglen)      do {                                                    \
00092                                                     if (write(fd, msgbuf, msglen) < 0) return -1;       \
00093                                                 } while (0);
00094 /* READ_ERRCHECK() decorated with error checking logic */
00095 #define READ_ERRCHECK(fd, msgbuf, msglen)      do {                                                     \
00096                                                     if (read(fd, msgbuf, msglen) != msglen) {           \
00097                                                         /*errno = EPROTO;*/                             \
00098                                                         return -1;                                      \
00099                                                     }                                                   \
00100                                                 } while (0);
00101 
00102 /* convert 64bit integers from host to network format */
00103 #define hton64(x)       (\
00104         htons(1) == 1 ?                                         \
00105             (uint64_t)x      /* big endian */                   \
00106         :       /* little endian */                             \
00107         ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
00108             (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
00109             (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
00110             (((uint64_t)(x) & 0x000000ff00000000ULL) >>  8) | \
00111             (((uint64_t)(x) & 0x00000000ff000000ULL) <<  8) | \
00112             (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
00113             (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
00114             (((uint64_t)(x) & 0x00000000000000ffULL) << 56)))   \
00115         )
00116 
00117 /* convert 64bit integers from network to host format */
00118 #define ntoh64(x)       (hton64(x))
00119 #endif
00120 
00121 /* some OSes don't have EPROTO (eg OpenBSD) */
00122 #ifndef EPROTO
00123 #define EPROTO  EIO
00124 #endif
00125 
00126 #ifdef SIMCLIST_WITH_THREADS
00127 /* limit (approx) to the number of threads running
00128  * for threaded operations. Only meant when
00129  * SIMCLIST_WITH_THREADS is defined */
00130 #define SIMCLIST_MAXTHREADS   2
00131 #endif
00132 
00133 /*
00134  * how many elems to keep as spare. During a deletion, an element
00135  * can be saved in a "free-list", not free()d immediately. When
00136  * latter insertions are performed, spare elems can be used instead
00137  * of malloc()ing new elems.
00138  *
00139  * about this param, some values for appending
00140  * 10 million elems into an empty list:
00141  * (#, time[sec], gain[%], gain/no[%])
00142  * 0    2,164   0,00    0,00    <-- feature disabled
00143  * 1    1,815   34,9    34,9
00144  * 2    1,446   71,8    35,9    <-- MAX gain/no
00145  * 3    1,347   81,7    27,23
00146  * 5    1,213   95,1    19,02
00147  * 8    1,064   110,0   13,75
00148  * 10   1,015   114,9   11,49   <-- MAX gain w/ likely sol
00149  * 15   1,019   114,5   7,63
00150  * 25   0,985   117,9   4,72
00151  * 50   1,088   107,6   2,15
00152  * 75   1,016   114,8   1,53
00153  * 100  0,988   117,6   1,18
00154  * 150  1,022   114,2   0,76
00155  * 200  0,939   122,5   0,61    <-- MIN time
00156  */
00157 #ifndef SIMCLIST_MAX_SPARE_ELEMS
00158 #define SIMCLIST_MAX_SPARE_ELEMS        5
00159 #endif
00160 
00161 
00162 #ifdef SIMCLIST_WITH_THREADS
00163 #include <pthread.h>
00164 #endif
00165 
00166 #include "simclist.h"
00167 
00168 
00169 /* minumum number of elements for sorting with quicksort instead of insertion */
00170 #define SIMCLIST_MINQUICKSORTELS        24
00171 
00172 
00173 /* list dump declarations */
00174 #define SIMCLIST_DUMPFORMAT_VERSION     1   /* (short integer) version of fileformat managed by _dump* and _restore* functions */
00175 
00176 #define SIMCLIST_DUMPFORMAT_HEADERLEN   30  /* length of the header */
00177 
00178 /* header for a list dump */
00179 struct list_dump_header_s {
00180     uint16_t ver;               /* version */
00181     int32_t timestamp_sec;      /* dump timestamp, seconds since UNIX Epoch */
00182     int32_t timestamp_usec;     /* dump timestamp, microseconds since timestamp_sec */
00183     int32_t rndterm;            /* random value terminator -- terminates the data sequence */
00184 
00185     uint32_t totlistlen;        /* sum of every element' size, bytes */
00186     uint32_t numels;            /* number of elements */
00187     uint32_t elemlen;           /* bytes length of an element, for constant-size lists, <= 0 otherwise */
00188     int32_t listhash;           /* hash of the list at the time of dumping, or 0 if to be ignored */
00189 };
00190 
00191 
00192 
00193 /* deletes tmp from list, with care wrt its position (head, tail, middle) */
00194 static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos);
00195 
00196 /* set default values for initialized lists */
00197 static int list_attributes_setdefaults(list_t *restrict l);
00198 
00199 #ifndef NDEBUG
00200 /* check whether the list internal REPresentation is valid -- Costs O(n) */
00201 static int list_repOk(const list_t *restrict l);
00202 
00203 /* check whether the list attribute set is valid -- Costs O(1) */
00204 static int list_attrOk(const list_t *restrict l);
00205 #endif
00206 
00207 /* do not inline, this is recursive */
00208 static void list_sort_quicksort(list_t *restrict l, int versus,
00209         unsigned int first, struct list_entry_s *fel,
00210         unsigned int last, struct list_entry_s *lel);
00211 
00212 static inline void list_sort_selectionsort(list_t *restrict l, int versus,
00213         unsigned int first, struct list_entry_s *fel,
00214         unsigned int last, struct list_entry_s *lel);
00215 
00216 static void *list_get_minmax(const list_t *restrict l, int versus);
00217 
00218 static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart);
00219 
00220 /*
00221  * Random Number Generator
00222  *
00223  * The user is expected to seed the RNG (ie call srand()) if
00224  * SIMCLIST_SYSTEM_RNG is defined.
00225  *
00226  * Otherwise, a self-contained RNG based on LCG is used; see
00227  * http://en.wikipedia.org/wiki/Linear_congruential_generator .
00228  *
00229  * Facts pro local RNG:
00230  * 1. no need for the user to call srand() on his own
00231  * 2. very fast, possibly faster than OS
00232  * 3. avoid interference with user's RNG
00233  *
00234  * Facts pro system RNG:
00235  * 1. may be more accurate (irrelevant for SimCList randno purposes)
00236  * 2. why reinvent the wheel
00237  *
00238  * Default to local RNG for user's ease of use.
00239  */
00240 
00241 #ifdef SIMCLIST_SYSTEM_RNG
00242 /* keep track whether we initialized already (non-0) or not (0) */
00243 static unsigned random_seed = 0;
00244 
00245 /* use local RNG */
00246 static inline void seed_random(void) {
00247     if (random_seed == 0)
00248         random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
00249 }
00250 
00251 static inline long get_random(void) {
00252     random_seed = (1664525 * random_seed + 1013904223);
00253     return random_seed;
00254 }
00255 
00256 #else
00257 /* use OS's random generator */
00258 #   define  seed_random()
00259 #   define  get_random()        (rand())
00260 #endif
00261 
00262 
00263 /* list initialization */
00264 int list_init(list_t *restrict l) {
00265     if (l == NULL) return -1;
00266 
00267     seed_random();
00268 
00269     l->numels = 0;
00270 
00271     /* head/tail sentinels and mid pointer */
00272     l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
00273     l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
00274     l->head_sentinel->next = l->tail_sentinel;
00275     l->tail_sentinel->prev = l->head_sentinel;
00276     l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
00277     l->head_sentinel->data = l->tail_sentinel->data = NULL;
00278 
00279     /* iteration attributes */
00280     l->iter_active = 0;
00281     l->iter_pos = 0;
00282     l->iter_curentry = NULL;
00283 
00284     /* free-list attributes */
00285     l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *));
00286     l->spareelsnum = 0;
00287 
00288 #ifdef SIMCLIST_WITH_THREADS
00289     l->threadcount = 0;
00290 #endif
00291 
00292     list_attributes_setdefaults(l);
00293 
00294     assert(list_repOk(l));
00295     assert(list_attrOk(l));
00296 
00297     return 0;
00298 }
00299 
00300 void list_destroy(list_t *restrict l) {
00301     unsigned int i;
00302 
00303     list_clear(l);
00304     for (i = 0; i < l->spareelsnum; i++) {
00305         free(l->spareels[i]);
00306     }
00307     free(l->spareels);
00308     free(l->head_sentinel);
00309     free(l->tail_sentinel);
00310 }
00311 
00312 int list_attributes_setdefaults(list_t *restrict l) {
00313     l->attrs.comparator = NULL;
00314     l->attrs.seeker = NULL;
00315 
00316     /* also free() element data when removing and element from the list */
00317     l->attrs.meter = NULL;
00318     l->attrs.copy_data = 0;
00319 
00320     l->attrs.hasher = NULL;
00321 
00322     /* serializer/unserializer */
00323     l->attrs.serializer = NULL;
00324     l->attrs.unserializer = NULL;
00325 
00326     assert(list_attrOk(l));
00327 
00328     return 0;
00329 }
00330 
00331 /* setting list properties */
00332 int list_attributes_comparator(list_t *restrict l, element_comparator comparator_fun) {
00333     if (l == NULL) return -1;
00334 
00335     l->attrs.comparator = comparator_fun;
00336 
00337     assert(list_attrOk(l));
00338 
00339     return 0;
00340 }
00341 
00342 int list_attributes_seeker(list_t *restrict l, element_seeker seeker_fun) {
00343     if (l == NULL) return -1;
00344 
00345     l->attrs.seeker = seeker_fun;
00346     assert(list_attrOk(l));
00347 
00348     return 0;
00349 }
00350 
00351 int list_attributes_copy(list_t *restrict l, element_meter metric_fun, int copy_data) {
00352     if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1;
00353 
00354     l->attrs.meter = metric_fun;
00355     l->attrs.copy_data = copy_data;
00356 
00357     assert(list_attrOk(l));
00358 
00359     return 0;
00360 }
00361 
00362 int list_attributes_hash_computer(list_t *restrict l, element_hash_computer hash_computer_fun) {
00363     if (l == NULL) return -1;
00364 
00365     l->attrs.hasher = hash_computer_fun;
00366     assert(list_attrOk(l));
00367     return 0;
00368 }
00369 
00370 int list_attributes_serializer(list_t *restrict l, element_serializer serializer_fun) {
00371     if (l == NULL) return -1;
00372 
00373     l->attrs.serializer = serializer_fun;
00374     assert(list_attrOk(l));
00375     return 0;
00376 }
00377 
00378 int list_attributes_unserializer(list_t *restrict l, element_unserializer unserializer_fun) {
00379     if (l == NULL) return -1;
00380 
00381     l->attrs.unserializer = unserializer_fun;
00382     assert(list_attrOk(l));
00383     return 0;
00384 }
00385 
00386 int list_append(list_t *restrict l, const void *data) {
00387     return list_insert_at(l, data, l->numels);
00388 }
00389 
00390 int list_prepend(list_t *restrict l, const void *data) {
00391     return list_insert_at(l, data, 0);
00392 }
00393 
00394 void *list_fetch(list_t *restrict l) {
00395     return list_extract_at(l, 0);
00396 }
00397 
00398 void *list_get_at(const list_t *restrict l, unsigned int pos) {
00399     struct list_entry_s *tmp;
00400 
00401     tmp = list_findpos(l, pos);
00402 
00403     return (tmp != NULL ? tmp->data : NULL);
00404 }
00405 
00406 void *list_get_max(const list_t *restrict l) {
00407     return list_get_minmax(l, +1);
00408 }
00409 
00410 void *list_get_min(const list_t *restrict l) {
00411     return list_get_minmax(l, -1);
00412 }
00413 
00414 /* REQUIRES {list->numels >= 1}
00415  * return the min (versus < 0) or max value (v > 0) in l */
00416 static void *list_get_minmax(const list_t *restrict l, int versus) {
00417     void *curminmax;
00418     struct list_entry_s *s;
00419 
00420     if (l->attrs.comparator == NULL || l->numels == 0)
00421         return NULL;
00422 
00423     curminmax = l->head_sentinel->next->data;
00424     for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
00425         if (l->attrs.comparator(curminmax, s->data) * versus > 0)
00426             curminmax = s->data;
00427     }
00428 
00429     return curminmax;
00430 }
00431 
00432 /* set tmp to point to element at index posstart in l */
00433 static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart) {
00434     struct list_entry_s *ptr;
00435     float x;
00436     int i;
00437 
00438     /* accept 1 slot overflow for fetching head and tail sentinels */
00439     if (posstart < -1 || posstart > (int)l->numels) return NULL;
00440 
00441     x = (float)(posstart+1) / l->numels;
00442     if (x <= 0.25) {
00443         /* first quarter: get to posstart from head */
00444         for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
00445     } else if (x < 0.5) {
00446         /* second quarter: get to posstart from mid */
00447         for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
00448     } else if (x <= 0.75) {
00449         /* third quarter: get to posstart from mid */
00450         for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
00451     } else {
00452         /* fourth quarter: get to posstart from tail */
00453         for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
00454     }
00455 
00456     return ptr;
00457 }
00458 
00459 void *list_extract_at(list_t *restrict l, unsigned int pos) {
00460     struct list_entry_s *tmp;
00461     void *data;
00462 
00463     if (l->iter_active || pos >= l->numels) return NULL;
00464 
00465     tmp = list_findpos(l, pos);
00466     data = tmp->data;
00467 
00468     tmp->data = NULL;   /* save data from list_drop_elem() free() */
00469     list_drop_elem(l, tmp, pos);
00470     l->numels--;
00471 
00472     assert(list_repOk(l));
00473 
00474     return data;
00475 }
00476 
00477 int list_insert_at(list_t *restrict l, const void *data, unsigned int pos) {
00478     struct list_entry_s *lent, *succ, *prec;
00479 
00480     if (l->iter_active || pos > l->numels) return -1;
00481 
00482     /* this code optimizes malloc() with a free-list */
00483     if (l->spareelsnum > 0) {
00484         lent = l->spareels[l->spareelsnum-1];
00485         l->spareelsnum--;
00486     } else {
00487         lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
00488         if (lent == NULL)
00489             return -1;
00490     }
00491 
00492     if (l->attrs.copy_data) {
00493         /* make room for user' data (has to be copied) */
00494         size_t datalen = l->attrs.meter(data);
00495         lent->data = (struct list_entry_s *)malloc(datalen);
00496         memcpy(lent->data, data, datalen);
00497     } else {
00498         lent->data = (void*)data;
00499     }
00500 
00501     /* actually append element */
00502     prec = list_findpos(l, pos-1);
00503     succ = prec->next;
00504 
00505     prec->next = lent;
00506     lent->prev = prec;
00507     lent->next = succ;
00508     succ->prev = lent;
00509 
00510     l->numels++;
00511 
00512     /* fix mid pointer */
00513     if (l->numels == 1) { /* first element, set pointer */
00514         l->mid = lent;
00515     } else if (l->numels % 2) {    /* now odd */
00516         if (pos >= (l->numels-1)/2) l->mid = l->mid->next;
00517     } else {                /* now even */
00518         if (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
00519     }
00520 
00521     assert(list_repOk(l));
00522 
00523     return 1;
00524 }
00525 
00526 int list_delete(list_t *restrict l, const void *data) {
00527     int pos, r;
00528 
00529     pos = list_locate(l, data);
00530     if (pos < 0)
00531         return -1;
00532 
00533     r = list_delete_at(l, pos);
00534     if (r < 0)
00535         return -1;
00536 
00537     assert(list_repOk(l));
00538 
00539     return 0;
00540 }
00541 
00542 int list_delete_at(list_t *restrict l, unsigned int pos) {
00543     struct list_entry_s *delendo;
00544 
00545 
00546     if (l->iter_active || pos >= l->numels) return -1;
00547 
00548     delendo = list_findpos(l, pos);
00549 
00550     list_drop_elem(l, delendo, pos);
00551 
00552     l->numels--;
00553 
00554 
00555     assert(list_repOk(l));
00556 
00557     return  0;
00558 }
00559 
00560 int list_delete_range(list_t *restrict l, unsigned int posstart, unsigned int posend) {
00561     struct list_entry_s *lastvalid, *tmp, *tmp2;
00562     unsigned int numdel, midposafter, i;
00563     int movedx;
00564 
00565     if (l->iter_active || posend < posstart || posend >= l->numels) return -1;
00566 
00567     numdel = posend - posstart + 1;
00568     if (numdel == l->numels) return list_clear(l);
00569 
00570     tmp = list_findpos(l, posstart);    /* first el to be deleted */
00571     lastvalid = tmp->prev;              /* last valid element */
00572 
00573     midposafter = (l->numels-1-numdel)/2;
00574 
00575     midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
00576     movedx = midposafter - (l->numels-1)/2;
00577 
00578     if (movedx > 0) { /* move right */
00579         for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++);
00580     } else {    /* move left */
00581         movedx = -movedx;
00582         for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++);
00583     }
00584 
00585     assert(posstart == 0 || lastvalid != l->head_sentinel);
00586     i = posstart;
00587     if (l->attrs.copy_data) {
00588         /* also free element data */
00589         for (; i <= posend; i++) {
00590             tmp2 = tmp;
00591             tmp = tmp->next;
00592             if (tmp2->data != NULL) free(tmp2->data);
00593             if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
00594                 l->spareels[l->spareelsnum++] = tmp2;
00595             } else {
00596                 free(tmp2);
00597             }
00598         }
00599     } else {
00600         /* only free containers */
00601         for (; i <= posend; i++) {
00602             tmp2 = tmp;
00603             tmp = tmp->next;
00604             if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
00605                 l->spareels[l->spareelsnum++] = tmp2;
00606             } else {
00607                 free(tmp2);
00608             }
00609         }
00610     }
00611     assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));
00612 
00613     lastvalid->next = tmp;
00614     tmp->prev = lastvalid;
00615 
00616     l->numels -= posend - posstart + 1;
00617 
00618     assert(list_repOk(l));
00619 
00620     return numdel;
00621 }
00622 
00623 int list_clear(list_t *restrict l) {
00624     struct list_entry_s *s;
00625     unsigned int numels;
00626 
00627     /* will be returned */
00628     numels = l->numels;
00629 
00630     if (l->iter_active) return -1;
00631 
00632     if (l->attrs.copy_data) {        /* also free user data */
00633         /* spare a loop conditional with two loops: spareing elems and freeing elems */
00634         for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
00635             /* move elements as spares as long as there is room */
00636             if (s->data != NULL) free(s->data);
00637             l->spareels[l->spareelsnum++] = s;
00638         }
00639         while (s != l->tail_sentinel) {
00640             /* free the remaining elems */
00641             if (s->data != NULL) free(s->data);
00642             s = s->next;
00643             free(s->prev);
00644         }
00645         l->head_sentinel->next = l->tail_sentinel;
00646         l->tail_sentinel->prev = l->head_sentinel;
00647     } else { /* only free element containers */
00648         /* spare a loop conditional with two loops: spareing elems and freeing elems */
00649         for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
00650             /* move elements as spares as long as there is room */
00651             l->spareels[l->spareelsnum++] = s;
00652         }
00653         while (s != l->tail_sentinel) {
00654             /* free the remaining elems */
00655             s = s->next;
00656             free(s->prev);
00657         }
00658         l->head_sentinel->next = l->tail_sentinel;
00659         l->tail_sentinel->prev = l->head_sentinel;
00660     }
00661     l->numels = 0;
00662     l->mid = NULL;
00663 
00664     assert(list_repOk(l));
00665 
00666     return numels;
00667 }
00668 
00669 unsigned int list_size(const list_t *restrict l) {
00670     return l->numels;
00671 }
00672 
00673 int list_empty(const list_t *restrict l) {
00674     return (l->numels == 0);
00675 }
00676 
00677 int list_locate(const list_t *restrict l, const void *data) {
00678     struct list_entry_s *el;
00679     int pos = 0;
00680 
00681     if (l->attrs.comparator != NULL) {
00682         /* use comparator */
00683         for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
00684             if (l->attrs.comparator(data, el->data) == 0) break;
00685         }
00686     } else {
00687         /* compare references */
00688         for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
00689             if (el->data == data) break;
00690         }
00691     }
00692     if (el == l->tail_sentinel) return -1;
00693 
00694     return pos;
00695 }
00696 
00697 void *list_seek(list_t *restrict l, const void *indicator) {
00698     const struct list_entry_s *iter;
00699 
00700     if (l->attrs.seeker == NULL) return NULL;
00701 
00702     for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
00703         if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data;
00704     }
00705 
00706     return NULL;
00707 }
00708 
00709 int list_contains(const list_t *restrict l, const void *data) {
00710     return (list_locate(l, data) >= 0);
00711 }
00712 
00713 int list_concat(const list_t *l1, const list_t *l2, list_t *restrict dest) {
00714     struct list_entry_s *el, *srcel;
00715     unsigned int cnt;
00716     int err;
00717 
00718 
00719     if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
00720         return -1;
00721 
00722     list_init(dest);
00723 
00724     dest->numels = l1->numels + l2->numels;
00725     if (dest->numels == 0)
00726         return 0;
00727 
00728     /* copy list1 */
00729     srcel = l1->head_sentinel->next;
00730     el = dest->head_sentinel;
00731     while (srcel != l1->tail_sentinel) {
00732         el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
00733         el->next->prev = el;
00734         el = el->next;
00735         el->data = srcel->data;
00736         srcel = srcel->next;
00737     }
00738     dest->mid = el;     /* approximate position (adjust later) */
00739     /* copy list 2 */
00740     srcel = l2->head_sentinel->next;
00741     while (srcel != l2->tail_sentinel) {
00742         el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
00743         el->next->prev = el;
00744         el = el->next;
00745         el->data = srcel->data;
00746         srcel = srcel->next;
00747     }
00748     el->next = dest->tail_sentinel;
00749     dest->tail_sentinel->prev = el;
00750 
00751     /* fix mid pointer */
00752     err = l2->numels - l1->numels;
00753     if ((err+1)/2 > 0) {        /* correct pos RIGHT (err-1)/2 moves */
00754         err = (err+1)/2;
00755         for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next;
00756     } else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */
00757         err = -err/2;
00758         for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev;
00759     }
00760 
00761     assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));
00762 
00763     return 0;
00764 }
00765 
00766 int list_sort(list_t *restrict l, int versus) {
00767     if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */
00768         return -1;
00769 
00770     if (l->numels <= 1)
00771         return 0;
00772     list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
00773     assert(list_repOk(l));
00774     return 0;
00775 }
00776 
00777 #ifdef SIMCLIST_WITH_THREADS
00778 struct list_sort_wrappedparams {
00779     list_t *restrict l;
00780     int versus;
00781     unsigned int first, last;
00782     struct list_entry_s *fel, *lel;
00783 };
00784 
00785 static void *list_sort_quicksort_threadwrapper(void *wrapped_params) {
00786     struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params;
00787     list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
00788     free(wp);
00789     pthread_exit(NULL);
00790     return NULL;
00791 }
00792 #endif
00793 
00794 static inline void list_sort_selectionsort(list_t *restrict l, int versus,
00795         unsigned int first, struct list_entry_s *fel,
00796         unsigned int last, struct list_entry_s *lel) {
00797     struct list_entry_s *cursor, *toswap, *firstunsorted;
00798     void *tmpdata;
00799 
00800     if (last <= first) /* <= 1-element lists are always sorted */
00801         return;
00802 
00803     for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
00804         /* find min or max in the remainder of the list */
00805         for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
00806             if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
00807         if (toswap != firstunsorted) { /* swap firstunsorted with toswap */
00808             tmpdata = firstunsorted->data;
00809             firstunsorted->data = toswap->data;
00810             toswap->data = tmpdata;
00811         }
00812     }
00813 }
00814 
00815 static void list_sort_quicksort(list_t *restrict l, int versus,
00816         unsigned int first, struct list_entry_s *fel,
00817         unsigned int last, struct list_entry_s *lel) {
00818     unsigned int pivotid;
00819     unsigned int i;
00820     register struct list_entry_s *pivot;
00821     struct list_entry_s *left, *right;
00822     void *tmpdata;
00823 #ifdef SIMCLIST_WITH_THREADS
00824     pthread_t tid;
00825     int traised;
00826 #endif
00827 
00828 
00829     if (last <= first)      /* <= 1-element lists are always sorted */
00830         return;
00831 
00832     if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
00833         list_sort_selectionsort(l, versus, first, fel, last, lel);
00834         return;
00835     }
00836 
00837     /* base of iteration: one element list */
00838     if (! (last > first)) return;
00839 
00840     pivotid = (get_random() % (last - first + 1));
00841     /* pivotid = (last - first + 1) / 2; */
00842 
00843     /* find pivot */
00844     if (pivotid < (last - first + 1)/2) {
00845         for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
00846     } else {
00847         for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
00848     }
00849 
00850     /* smaller PIVOT bigger */
00851     left = fel;
00852     right = lel;
00853     /* iterate     --- left ---> PIV <--- right --- */
00854     while (left != pivot && right != pivot) {
00855         for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
00856         /* left points to a smaller element, or to pivot */
00857         for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
00858         /* right points to a bigger element, or to pivot */
00859         if (left != pivot && right != pivot) {
00860             /* swap, then move iterators */
00861             tmpdata = left->data;
00862             left->data = right->data;
00863             right->data = tmpdata;
00864 
00865             left = left->next;
00866             right = right->prev;
00867         }
00868     }
00869 
00870     /* now either left points to pivot (end run), or right */
00871     if (right == pivot) {    /* left part longer */
00872         while (left != pivot) {
00873             if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
00874                 tmpdata = left->data;
00875                 left->data = pivot->prev->data;
00876                 pivot->prev->data = pivot->data;
00877                 pivot->data = tmpdata;
00878                 pivot = pivot->prev;
00879                 pivotid--;
00880                 if (pivot == left) break;
00881             } else {
00882                 left = left->next;
00883             }
00884         }
00885     } else {                /* right part longer */
00886         while (right != pivot) {
00887             if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
00888                 /* move current right before pivot */
00889                 tmpdata = right->data;
00890                 right->data = pivot->next->data;
00891                 pivot->next->data = pivot->data;
00892                 pivot->data = tmpdata;
00893                 pivot = pivot->next;
00894                 pivotid++;
00895                 if (pivot == right) break;
00896             } else {
00897                 right = right->prev;
00898             }
00899         }
00900     }
00901 
00902     /* sort sublists A and B :       |---A---| pivot |---B---| */
00903 
00904 #ifdef SIMCLIST_WITH_THREADS
00905     traised = 0;
00906     if (pivotid > 0) {
00907         /* prepare wrapped args, then start thread */
00908         if (l->threadcount < SIMCLIST_MAXTHREADS-1) {
00909             struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams));
00910             l->threadcount++;
00911             traised = 1;
00912             wp->l = l;
00913             wp->versus = versus;
00914             wp->first = first;
00915             wp->fel = fel;
00916             wp->last = first+pivotid-1;
00917             wp->lel = pivot->prev;
00918             if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
00919                 free(wp);
00920                 traised = 0;
00921                 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
00922             }
00923         } else {
00924             list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
00925         }
00926     }
00927     if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
00928     if (traised) {
00929         pthread_join(tid, (void **)NULL);
00930         l->threadcount--;
00931     }
00932 #else
00933     if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
00934     if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
00935 #endif
00936 }
00937 
00938 int list_iterator_start(list_t *restrict l) {
00939     if (l->iter_active) return 0;
00940     l->iter_pos = 0;
00941     l->iter_active = 1;
00942     l->iter_curentry = l->head_sentinel->next;
00943     return 1;
00944 }
00945 
00946 void *list_iterator_next(list_t *restrict l) {
00947     void *toret;
00948 
00949     if (! l->iter_active) return NULL;
00950 
00951     toret = l->iter_curentry->data;
00952     l->iter_curentry = l->iter_curentry->next;
00953     l->iter_pos++;
00954 
00955     return toret;
00956 }
00957 
00958 int list_iterator_hasnext(const list_t *restrict l) {
00959     if (! l->iter_active) return 0;
00960     return (l->iter_pos < l->numels);
00961 }
00962 
00963 int list_iterator_stop(list_t *restrict l) {
00964     if (! l->iter_active) return 0;
00965     l->iter_pos = 0;
00966     l->iter_active = 0;
00967     return 1;
00968 }
00969 
00970 int list_hash(const list_t *restrict l, list_hash_t *restrict hash) {
00971     struct list_entry_s *x;
00972     list_hash_t tmphash;
00973 
00974     assert(hash != NULL);
00975 
00976     tmphash = l->numels * 2 + 100;
00977     if (l->attrs.hasher == NULL) {
00978 #ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES
00979         /* ENABLE WITH CARE !! */
00980 #warning "Memlocation-based hash is consistent only for testing modification in the same program run."
00981         int i;
00982 
00983         /* only use element references */
00984         for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
00985             for (i = 0; i < sizeof(x->data); i++) {
00986                 tmphash += (tmphash ^ (uintptr_t)x->data);
00987             }
00988             tmphash += tmphash % l->numels;
00989         }
00990 #else
00991         return -1;
00992 #endif
00993     } else {
00994         /* hash each element with the user-given function */
00995         for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
00996             tmphash += tmphash ^ l->attrs.hasher(x->data);
00997             tmphash += tmphash % l->numels;
00998         }
00999     }
01000 
01001     *hash = tmphash;
01002 
01003     return 0;
01004 }
01005 
01006 #ifndef SIMCLIST_NO_DUMPRESTORE
01007 int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *restrict info) {
01008     int32_t terminator_head, terminator_tail;
01009     uint32_t elemlen;
01010     off_t hop;
01011 
01012 
01013     /* version */
01014     READ_ERRCHECK(fd, & info->version, sizeof(info->version));
01015     info->version = ntohs(info->version);
01016     if (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
01017         errno = EILSEQ;
01018         return -1;
01019     }
01020 
01021     /* timestamp.tv_sec and timestamp.tv_usec */
01022     READ_ERRCHECK(fd, & info->timestamp.tv_sec, sizeof(info->timestamp.tv_sec));
01023     info->timestamp.tv_sec = ntohl(info->timestamp.tv_sec);
01024     READ_ERRCHECK(fd, & info->timestamp.tv_usec, sizeof(info->timestamp.tv_usec));
01025     info->timestamp.tv_usec = ntohl(info->timestamp.tv_usec);
01026 
01027     /* list terminator (to check thereafter) */
01028     READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head));
01029     terminator_head = ntohl(terminator_head);
01030 
01031     /* list size */
01032     READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size));
01033     info->list_size = ntohl(info->list_size);
01034 
01035     /* number of elements */
01036     READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels));
01037     info->list_numels = ntohl(info->list_numels);
01038 
01039     /* length of each element (for checking for consistency) */
01040     READ_ERRCHECK(fd, & elemlen, sizeof(elemlen));
01041     elemlen = ntohl(elemlen);
01042 
01043     /* list hash */
01044     READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash));
01045     info->list_hash = ntohl(info->list_hash);
01046 
01047     /* check consistency */
01048     if (elemlen > 0) {
01049         /* constant length, hop by size only */
01050         hop = info->list_size;
01051     } else {
01052         /* non-constant length, hop by size + all element length blocks */
01053         hop = info->list_size + elemlen*info->list_numels;
01054     }
01055     if (lseek(fd, hop, SEEK_CUR) == -1) {
01056         return -1;
01057     }
01058 
01059     /* read the trailing value and compare with terminator_head */
01060     READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail));
01061     terminator_tail = ntohl(terminator_tail);
01062 
01063     if (terminator_head == terminator_tail)
01064         info->consistent = 1;
01065     else
01066         info->consistent = 0;
01067 
01068     return 0;
01069 }
01070 
01071 int list_dump_getinfo_file(const char *restrict filename, list_dump_info_t *restrict info) {
01072     int fd, ret;
01073 
01074     fd = open(filename, O_RDONLY, 0);
01075     if (fd < 0) return -1;
01076 
01077     ret = list_dump_getinfo_filedescriptor(fd, info);
01078     close(fd);
01079 
01080     return ret;
01081 }
01082 
01083 int list_dump_filedescriptor(const list_t *restrict l, int fd, size_t *restrict len) {
01084     struct list_entry_s *x;
01085     void *ser_buf;
01086     uint32_t bufsize;
01087     struct timeval timeofday;
01088     struct list_dump_header_s header;
01089 
01090     if (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
01091         errno = ENOTTY;
01092         return -1;
01093     }
01094 
01095     /****       DUMP FORMAT      ****
01096 
01097     [ ver   timestamp   |  totlen   numels  elemlen     hash    |   DATA ]
01098 
01099     where DATA can be:
01100     @ for constant-size list (element size is constant; elemlen > 0)
01101     [ elem    elem    ...    elem ]
01102     @ for other lists (element size dictated by element_meter each time; elemlen <= 0)
01103     [ size elem     size elem       ...     size elem ]
01104 
01105     all integers are encoded in NETWORK BYTE FORMAT
01106     *****/
01107 
01108 
01109     /* prepare HEADER */
01110     /* version */
01111     header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );
01112 
01113     /* timestamp */
01114     gettimeofday(&timeofday, NULL);
01115     header.timestamp_sec = htonl(timeofday.tv_sec);
01116     header.timestamp_usec = htonl(timeofday.tv_usec);
01117 
01118     header.rndterm = htonl((int32_t)get_random());
01119 
01120     /* total list size is postprocessed afterwards */
01121 
01122     /* number of elements */
01123     header.numels = htonl(l->numels);
01124 
01125     /* include an hash, if possible */
01126     if (l->attrs.hasher != NULL) {
01127         if (htonl(list_hash(l, & header.listhash)) != 0) {
01128             /* could not compute list hash! */
01129             return -1;
01130         }
01131     } else {
01132         header.listhash = htonl(0);
01133     }
01134 
01135     header.totlistlen = header.elemlen = 0;
01136 
01137     /* leave room for the header at the beginning of the file */
01138     if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
01139         /* errno set by lseek() */
01140         return -1;
01141     }
01142 
01143     /* write CONTENT */
01144     if (l->numels > 0) {
01145         /* SPECULATE that the list has constant element size */
01146 
01147         if (l->attrs.serializer != NULL) {  /* user user-specified serializer */
01148             /* get preliminary length of serialized element in header.elemlen */
01149             ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
01150             free(ser_buf);
01151             /* request custom serialization of each element */
01152             for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
01153                 ser_buf = l->attrs.serializer(x->data, &bufsize);
01154                 header.totlistlen += bufsize;
01155                 if (header.elemlen != 0) {      /* continue on speculation */
01156                     if (header.elemlen != bufsize) {
01157                         free(ser_buf);
01158                         /* constant element length speculation broken! */
01159                         header.elemlen = 0;
01160                         header.totlistlen = 0;
01161                         x = l->head_sentinel;
01162                         if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
01163                             /* errno set by lseek() */
01164                             return -1;
01165                         }
01166                         /* restart from the beginning */
01167                         continue;
01168                     }
01169                     /* speculation confirmed */
01170                     WRITE_ERRCHECK(fd, ser_buf, bufsize);
01171                 } else {                        /* speculation found broken */
01172                     WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t));
01173                     WRITE_ERRCHECK(fd, ser_buf, bufsize);
01174                 }
01175                 free(ser_buf);
01176             }
01177         } else if (l->attrs.meter != NULL) {
01178             header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);
01179 
01180             /* serialize the element straight from its data */
01181             for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
01182                 bufsize = l->attrs.meter(x->data);
01183                 header.totlistlen += bufsize;
01184                 if (header.elemlen != 0) {
01185                     if (header.elemlen != bufsize) {
01186                         /* constant element length speculation broken! */
01187                         header.elemlen = 0;
01188                         header.totlistlen = 0;
01189                         x = l->head_sentinel;
01190                         /* restart from the beginning */
01191                         continue;
01192                     }
01193                     WRITE_ERRCHECK(fd, x->data, bufsize);
01194                 } else {
01195                     WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t));
01196                     WRITE_ERRCHECK(fd, x->data, bufsize);
01197                 }
01198             }
01199         }
01200         /* adjust endianness */
01201         header.elemlen = htonl(header.elemlen);
01202         header.totlistlen = htonl(header.totlistlen);
01203     }
01204 
01205     /* write random terminator */
01206     WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));        /* list terminator */
01207 
01208 
01209     /* write header */
01210     lseek(fd, 0, SEEK_SET);
01211 
01212     WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver));                        /* version */
01213     WRITE_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec));    /* timestamp seconds */
01214     WRITE_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec));  /* timestamp microseconds */
01215     WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));                /* random terminator */
01216 
01217     WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));          /* total length of elements */
01218     WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels));                  /* number of elements */
01219     WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));                /* size of each element, or 0 for independent */
01220     WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));              /* list hash, or 0 for "ignore" */
01221 
01222 
01223     /* possibly store total written length in "len" */
01224     if (len != NULL) {
01225         *len = sizeof(header) + ntohl(header.totlistlen);
01226     }
01227 
01228     return 0;
01229 }
01230 
01231 int list_restore_filedescriptor(list_t *restrict l, int fd, size_t *restrict len) {
01232     struct list_dump_header_s header;
01233     unsigned long cnt;
01234     void *buf;
01235     uint32_t elsize, totreadlen, totmemorylen;
01236 
01237     memset(& header, 0, sizeof(header));
01238 
01239     /* read header */
01240 
01241     /* version */
01242     READ_ERRCHECK(fd, &header.ver, sizeof(header.ver));
01243     header.ver = ntohs(header.ver);
01244     if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
01245         errno = EILSEQ;
01246         return -1;
01247     }
01248 
01249     /* timestamp */
01250     READ_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec));
01251     header.timestamp_sec = ntohl(header.timestamp_sec);
01252     READ_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec));
01253     header.timestamp_usec = ntohl(header.timestamp_usec);
01254 
01255     /* list terminator */
01256     READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));
01257 
01258     header.rndterm = ntohl(header.rndterm);
01259 
01260     /* total list size */
01261     READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));
01262     header.totlistlen = ntohl(header.totlistlen);
01263 
01264     /* number of elements */
01265     READ_ERRCHECK(fd, & header.numels, sizeof(header.numels));
01266     header.numels = ntohl(header.numels);
01267 
01268     /* length of every element, or '0' = variable */
01269     READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));
01270     header.elemlen = ntohl(header.elemlen);
01271 
01272     /* list hash, or 0 = 'ignore' */
01273     READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));
01274     header.listhash = ntohl(header.listhash);
01275 
01276 
01277     /* read content */
01278     totreadlen = totmemorylen = 0;
01279     if (header.elemlen > 0) {
01280         /* elements have constant size = header.elemlen */
01281         if (l->attrs.unserializer != NULL) {
01282             /* use unserializer */
01283             buf = malloc(header.elemlen);
01284             for (cnt = 0; cnt < header.numels; cnt++) {
01285                 READ_ERRCHECK(fd, buf, header.elemlen);
01286                 list_append(l, l->attrs.unserializer(buf, & elsize));
01287                 totmemorylen += elsize;
01288             }
01289         } else {
01290             /* copy verbatim into memory */
01291             for (cnt = 0; cnt < header.numels; cnt++) {
01292                 buf = malloc(header.elemlen);
01293                 READ_ERRCHECK(fd, buf, header.elemlen);
01294                 list_append(l, buf);
01295             }
01296             totmemorylen = header.numels * header.elemlen;
01297         }
01298         totreadlen = header.numels * header.elemlen;
01299     } else {
01300         /* elements have variable size. Each element is preceded by its size */
01301         if (l->attrs.unserializer != NULL) {
01302             /* use unserializer */
01303             for (cnt = 0; cnt < header.numels; cnt++) {
01304                 READ_ERRCHECK(fd, & elsize, sizeof(elsize));
01305                 buf = malloc((size_t)elsize);
01306                 READ_ERRCHECK(fd, buf, elsize);
01307                 totreadlen += elsize;
01308                 list_append(l, l->attrs.unserializer(buf, & elsize));
01309                 totmemorylen += elsize;
01310             }
01311         } else {
01312             /* copy verbatim into memory */
01313             for (cnt = 0; cnt < header.numels; cnt++) {
01314                 READ_ERRCHECK(fd, & elsize, sizeof(elsize));
01315                 buf = malloc(elsize);
01316                 READ_ERRCHECK(fd, buf, elsize);
01317                 totreadlen += elsize;
01318                 list_append(l, buf);
01319             }
01320             totmemorylen = totreadlen;
01321         }
01322     }
01323 
01324     READ_ERRCHECK(fd, &elsize, sizeof(elsize));  /* read list terminator */
01325     elsize = ntohl(elsize);
01326 
01327     /* possibly verify the list consistency */
01328     /* wrt hash */
01329     /* don't do that
01330     if (header.listhash != 0 && header.listhash != list_hash(l)) {
01331         errno = ECANCELED;
01332         return -1;
01333     }
01334     */
01335 
01336     /* wrt header */
01337     if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
01338         errno = EPROTO;
01339         return -1;
01340     }
01341 
01342     /* wrt file */
01343     if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
01344         errno = EPROTO;
01345         return -1;
01346     }
01347 
01348     if (len != NULL) {
01349         *len = totmemorylen;
01350     }
01351 
01352     return 0;
01353 }
01354 
01355 int list_dump_file(const list_t *restrict l, const char *restrict filename, size_t *restrict len) {
01356     int fd, oflag, mode;
01357 
01358 #ifndef _WIN32
01359     oflag = O_RDWR | O_CREAT | O_TRUNC;
01360     mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;
01361 #else
01362     oflag = _O_RDWR | _O_CREAT | _O_TRUNC;
01363     mode = _S_IRUSR | _S_IWUSR | _S_IRGRP | _S_IROTH;
01364 #endif
01365     fd = open(filename, oflag, mode);
01366     if (fd < 0) return -1;
01367 
01368     list_dump_filedescriptor(l, fd, len);
01369     close(fd);
01370 
01371     return 0;
01372 }
01373 
01374 int list_restore_file(list_t *restrict l, const char *restrict filename, size_t *restrict len) {
01375     int fd;
01376 
01377     fd = open(filename, O_RDONLY, 0);
01378     if (fd < 0) return -1;
01379 
01380     list_restore_filedescriptor(l, fd, len);
01381     close(fd);
01382 
01383     return 0;
01384 }
01385 #endif /* ifndef SIMCLIST_NO_DUMPRESTORE */
01386 
01387 
01388 static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos) {
01389     if (tmp == NULL) return -1;
01390 
01391     /* fix mid pointer. This is wrt the PRE situation */
01392     if (l->numels % 2) {    /* now odd */
01393         /* sort out the base case by hand */
01394         if (l->numels == 1) l->mid = NULL;
01395         else if (pos >= l->numels/2) l->mid = l->mid->prev;
01396     } else {                /* now even */
01397         if (pos < l->numels/2) l->mid = l->mid->next;
01398     }
01399 
01400     tmp->prev->next = tmp->next;
01401     tmp->next->prev = tmp->prev;
01402 
01403     /* free what's to be freed */
01404     if (l->attrs.copy_data && tmp->data != NULL)
01405         free(tmp->data);
01406 
01407     if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
01408         l->spareels[l->spareelsnum++] = tmp;
01409     } else {
01410         free(tmp);
01411     }
01412 
01413     return 0;
01414 }
01415 
01416 /* ready-made comparators and meters */
01417 #define SIMCLIST_NUMBER_COMPARATOR(type)     int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); }
01418 
01419 SIMCLIST_NUMBER_COMPARATOR(int8_t)
01420 SIMCLIST_NUMBER_COMPARATOR(int16_t)
01421 SIMCLIST_NUMBER_COMPARATOR(int32_t)
01422 SIMCLIST_NUMBER_COMPARATOR(int64_t)
01423 
01424 SIMCLIST_NUMBER_COMPARATOR(uint8_t)
01425 SIMCLIST_NUMBER_COMPARATOR(uint16_t)
01426 SIMCLIST_NUMBER_COMPARATOR(uint32_t)
01427 SIMCLIST_NUMBER_COMPARATOR(uint64_t)
01428 
01429 SIMCLIST_NUMBER_COMPARATOR(float)
01430 SIMCLIST_NUMBER_COMPARATOR(double)
01431 
01432 int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); }
01433 
01434 /* ready-made metric functions */
01435 #define SIMCLIST_METER(type)        size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); }
01436 
01437 SIMCLIST_METER(int8_t)
01438 SIMCLIST_METER(int16_t)
01439 SIMCLIST_METER(int32_t)
01440 SIMCLIST_METER(int64_t)
01441 
01442 SIMCLIST_METER(uint8_t)
01443 SIMCLIST_METER(uint16_t)
01444 SIMCLIST_METER(uint32_t)
01445 SIMCLIST_METER(uint64_t)
01446 
01447 SIMCLIST_METER(float)
01448 SIMCLIST_METER(double)
01449 
01450 size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; }
01451 
01452 /* ready-made hashing functions */
01453 #define SIMCLIST_HASHCOMPUTER(type)    list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); }
01454 
01455 SIMCLIST_HASHCOMPUTER(int8_t)
01456 SIMCLIST_HASHCOMPUTER(int16_t)
01457 SIMCLIST_HASHCOMPUTER(int32_t)
01458 SIMCLIST_HASHCOMPUTER(int64_t)
01459 
01460 SIMCLIST_HASHCOMPUTER(uint8_t)
01461 SIMCLIST_HASHCOMPUTER(uint16_t)
01462 SIMCLIST_HASHCOMPUTER(uint32_t)
01463 SIMCLIST_HASHCOMPUTER(uint64_t)
01464 
01465 SIMCLIST_HASHCOMPUTER(float)
01466 SIMCLIST_HASHCOMPUTER(double)
01467 
01468 list_hash_t list_hashcomputer_string(const void *el) {
01469     size_t l;
01470     list_hash_t hash = 123;
01471     const char *str = (const char *)el;
01472     char plus;
01473 
01474     for (l = 0; str[l] != '\0'; l++) {
01475         if (l) plus = hash ^ str[l];
01476         else plus = hash ^ (str[l] - str[0]);
01477         hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t))));
01478     }
01479 
01480     return hash;
01481 }
01482 
01483 
01484 #ifndef NDEBUG
01485 static int list_repOk(const list_t *restrict l) {
01486     int ok, i;
01487     struct list_entry_s *s;
01488 
01489     ok = (l != NULL) && (
01490             /* head/tail checks */
01491             (l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
01492                 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
01493             /* empty list */
01494             (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
01495             /* spare elements checks */
01496             l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
01497          );
01498 
01499     if (!ok) return 0;
01500 
01501     if (l->numels >= 1) {
01502         /* correct referencing */
01503         for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
01504             if (s->next->prev != s) break;
01505         }
01506         ok = (i == (int)(l->numels-1)/2 && l->mid == s);
01507         if (!ok) return 0;
01508         for (; s->next != NULL; i++, s = s->next) {
01509             if (s->next->prev != s) break;
01510         }
01511         ok = (i == (int)l->numels && s == l->tail_sentinel);
01512     }
01513 
01514     return ok;
01515 }
01516 
01517 static int list_attrOk(const list_t *restrict l) {
01518     int ok;
01519 
01520     ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);
01521     return ok;
01522 }
01523 
01524 #endif
01525