pcsc-lite 1.7.2

simclist.c

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