simclist.c

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