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