Agronode_feeder/simclist.c

/*
 * Copyright (c) 2007,2008,2009,2010 Mij <mij@bitchx.it>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */


/*
 * SimCList library. See http://mij.oltrelinux.com/devel/simclist
 */

/* SimCList implementation, version 1.5 */

#include <stdlib.h>
#include <string.h>
#include <errno.h>      /* for setting errno */
#include <sys/types.h>
#include <sys/uio.h>    /* for READ_ERRCHECK() and write() */
#include <fcntl.h>      /* for open() etc */
#include <arpa/inet.h>  /* for htons() */
#include <unistd.h>
#include <time.h>       /* for time() for random seed */
#include <sys/time.h>   /* for gettimeofday() */
#include <sys/stat.h>   /* for open()'s access modes S_IRUSR etc */
#include <limits.h>
#include <stdint.h>


/* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */
#if !defined(WIN32) || !defined(_MSC_VER)
#   include <inttypes.h>   /* (u)int*_t */
#else
#   include <basetsd.h>
typedef UINT8   uint8_t;
typedef UINT16  uint16_t;
typedef ULONG32 uint32_t;
typedef UINT64  uint64_t;
typedef INT8    int8_t;
typedef INT16   int16_t;
typedef LONG32  int32_t;
typedef INT64   int64_t;
#endif
 


#ifndef SIMCLIST_NO_DUMPRESTORE
/* convert 64bit integers from host to network format */
#define hton64(x)       (\
        htons(1) == 1 ?                                         \
            (uint64_t)x      /* big endian */                   \
        :       /* little endian */                             \
        ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
            (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
            (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
            (((uint64_t)(x) & 0x000000ff00000000ULL) >>  8) | \
            (((uint64_t)(x) & 0x00000000ff000000ULL) <<  8) | \
            (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
            (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
            (((uint64_t)(x) & 0x00000000000000ffULL) << 56)))   \
        )

/* convert 64bit integers from network to host format */
#define ntoh64(x)       (hton64(x))
#endif

/* some OSes don't have EPROTO (eg OpenBSD) */
#ifndef EPROTO
#define EPROTO  EIO
#endif

/* disable asserts */
#ifndef SIMCLIST_DEBUG
#define NDEBUG
#endif

#include <assert.h>

#ifdef SIMCLIST_WITH_THREADS
/* limit (approx) to the number of threads running
 * for threaded operations. Only meant when
 * SIMCLIST_WITH_THREADS is defined */
#define SIMCLIST_MAXTHREADS   2
#endif

/*
 * how many elems to keep as spare. During a deletion, an element
 * can be saved in a "free-list", not free()d immediately. When
 * latter insertions are performed, spare elems can be used instead
 * of malloc()ing new elems.
 *
 * about this param, some values for appending
 * 10 million elems into an empty list:
 * (#, time[sec], gain[%], gain/no[%])
 * 0    2,164   0,00    0,00    <-- feature disabled
 * 1    1,815   34,9    34,9
 * 2    1,446   71,8    35,9    <-- MAX gain/no
 * 3    1,347   81,7    27,23
 * 5    1,213   95,1    19,02
 * 8    1,064   110,0   13,75
 * 10   1,015   114,9   11,49   <-- MAX gain w/ likely sol
 * 15   1,019   114,5   7,63
 * 25   0,985   117,9   4,72
 * 50   1,088   107,6   2,15
 * 75   1,016   114,8   1,53
 * 100  0,988   117,6   1,18
 * 150  1,022   114,2   0,76
 * 200  0,939   122,5   0,61    <-- MIN time
 */
#ifndef SIMCLIST_MAX_SPARE_ELEMS
#define SIMCLIST_MAX_SPARE_ELEMS        5
#endif


#ifdef SIMCLIST_WITH_THREADS
#include <pthread.h>
#endif

#include "simclist.h"


/* minumum number of elements for sorting with quicksort instead of insertion */
#define SIMCLIST_MINQUICKSORTELS        24


/* list dump declarations */
#define SIMCLIST_DUMPFORMAT_VERSION     1   /* (short integer) version of fileformat managed by _dump* and _restore* functions */

#define SIMCLIST_DUMPFORMAT_HEADERLEN   30  /* length of the header */

/* header for a list dump */
struct list_dump_header_s {
    uint16_t ver;               /* version */
    int64_t timestamp;          /* dump timestamp */
    int32_t rndterm;            /* random value terminator -- terminates the data sequence */

    uint32_t totlistlen;        /* sum of every element' size, bytes */
    uint32_t numels;            /* number of elements */
    uint32_t elemlen;           /* bytes length of an element, for constant-size lists, <= 0 otherwise */
    int32_t listhash;           /* hash of the list at the time of dumping, or 0 if to be ignored */
};



/* deletes tmp from list, with care wrt its position (head, tail, middle) */
static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos);

/* set default values for initialized lists */
static int list_attributes_setdefaults(list_t *restrict l);

#ifndef NDEBUG
/* check whether the list internal REPresentation is valid -- Costs O(n) */
static int list_repOk(const list_t *restrict l);

/* check whether the list attribute set is valid -- Costs O(1) */
static int list_attrOk(const list_t *restrict l);
#endif

/* do not inline, this is recursive */
static void list_sort_quicksort(list_t *restrict l, int versus, 
        unsigned int first, struct list_entry_s *fel,
        unsigned int last, struct list_entry_s *lel);

static inline void list_sort_selectionsort(list_t *restrict l, int versus, 
        unsigned int first, struct list_entry_s *fel,
        unsigned int last, struct list_entry_s *lel);

static void *list_get_minmax(const list_t *restrict l, int versus);

static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart);

/* write() decorated with error checking logic */
#define WRITE_ERRCHECK(fd, msgbuf, msglen)      do {                                                    \
                                                    if (write(fd, msgbuf, msglen) < 0) return -1;       \
                                                } while (0);
/* READ_ERRCHECK() decorated with error checking logic */
#define READ_ERRCHECK(fd, msgbuf, msglen)      do {                                                     \
                                                    if (read(fd, msgbuf, msglen) != msglen) {           \
                                                        /*errno = EPROTO;*/                             \
                                                        return -1;                                      \
                                                    }                                                   \
                                                } while (0);

/*
 * Random Number Generator
 * 
 * The user is expected to seed the RNG (ie call srand()) if 
 * SIMCLIST_SYSTEM_RNG is defined.
 *
 * Otherwise, a self-contained RNG based on LCG is used; see
 * http://en.wikipedia.org/wiki/Linear_congruential_generator .
 *
 * Facts pro local RNG:
 * 1. no need for the user to call srand() on his own
 * 2. very fast, possibly faster than OS
 * 3. avoid interference with user's RNG
 *
 * Facts pro system RNG:
 * 1. may be more accurate (irrelevant for SimCList randno purposes)
 * 2. why reinvent the wheel
 *
 * Default to local RNG for user's ease of use.
 */

#ifdef SIMCLIST_SYSTEM_RNG
/* keep track whether we initialized already (non-0) or not (0) */
static unsigned random_seed = 0;

/* use local RNG */
static inline void seed_random() {
    if (random_seed == 0)
        random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
}

static inline long get_random() {
    random_seed = (1664525 * random_seed + 1013904223);
    return random_seed;
}

#else
/* use OS's random generator */
#   define  seed_random()
#   define  get_random()        (rand())
#endif


/* list initialization */
int list_init(list_t *restrict l) {
    if (l == NULL) return -1;

    seed_random();

    l->numels = 0;

    /* head/tail sentinels and mid pointer */
    l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
    l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
    l->head_sentinel->next = l->tail_sentinel;
    l->tail_sentinel->prev = l->head_sentinel;
    l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
    l->head_sentinel->data = l->tail_sentinel->data = NULL;

    /* iteration attributes */
    l->iter_active = 0;
    l->iter_pos = 0;
    l->iter_curentry = NULL;

    /* free-list attributes */
    l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *));
    l->spareelsnum = 0;

#ifdef SIMCLIST_WITH_THREADS
    l->threadcount = 0;
#endif

    list_attributes_setdefaults(l);

    assert(list_repOk(l));
    assert(list_attrOk(l));

    return 0;
}

void list_destroy(list_t *restrict l) {
    unsigned int i;

    list_clear(l);
    for (i = 0; i < l->spareelsnum; i++) {
        free(l->spareels[i]);
    }
    free(l->spareels);
    free(l->head_sentinel);
    free(l->tail_sentinel);
}

int list_attributes_setdefaults(list_t *restrict l) {
    l->attrs.comparator = NULL;
    l->attrs.seeker = NULL;

    /* also free() element data when removing and element from the list */
    l->attrs.meter = NULL;
    l->attrs.copy_data = 0;

    l->attrs.hasher = NULL;

    /* serializer/unserializer */
    l->attrs.serializer = NULL;
    l->attrs.unserializer = NULL;

    assert(list_attrOk(l));
    
    return 0;
}

/* setting list properties */
int list_attributes_comparator(list_t *restrict l, element_comparator comparator_fun) {
    if (l == NULL) return -1;

    l->attrs.comparator = comparator_fun;

    assert(list_attrOk(l));
    
    return 0;
}

int list_attributes_seeker(list_t *restrict l, element_seeker seeker_fun) {
    if (l == NULL) return -1;

    l->attrs.seeker = seeker_fun;
    assert(list_attrOk(l));

    return 0;
}

int list_attributes_copy(list_t *restrict l, element_meter metric_fun, int copy_data) {
    if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1;

    l->attrs.meter = metric_fun;
    l->attrs.copy_data = copy_data;

    assert(list_attrOk(l));

    return 0;
}

int list_attributes_hash_computer(list_t *restrict l, element_hash_computer hash_computer_fun) {
    if (l == NULL) return -1;

    l->attrs.hasher = hash_computer_fun;
    assert(list_attrOk(l));
    return 0;
}

int list_attributes_serializer(list_t *restrict l, element_serializer serializer_fun) {
    if (l == NULL) return -1;

    l->attrs.serializer = serializer_fun;
    assert(list_attrOk(l));
    return 0;
}

int list_attributes_unserializer(list_t *restrict l, element_unserializer unserializer_fun) {
    if (l == NULL) return -1;

    l->attrs.unserializer = unserializer_fun;
    assert(list_attrOk(l));
    return 0;
}

int list_append(list_t *restrict l, const void *data) {
    return list_insert_at(l, data, l->numels);
}

int list_prepend(list_t *restrict l, const void *data) {
    return list_insert_at(l, data, 0);
}

void *list_fetch(list_t *restrict l) {
    return list_extract_at(l, 0);
}

void *list_get_at(const list_t *restrict l, unsigned int pos) {
    struct list_entry_s *tmp;

    tmp = list_findpos(l, pos);

    return (tmp != NULL ? tmp->data : NULL);
}

void *list_get_max(const list_t *restrict l) {
    return list_get_minmax(l, +1);
}

void *list_get_min(const list_t *restrict l) {
    return list_get_minmax(l, -1);
}

/* REQUIRES {list->numels >= 1}
 * return the min (versus < 0) or max value (v > 0) in l */
static void *list_get_minmax(const list_t *restrict l, int versus) {
    void *curminmax;
    struct list_entry_s *s;

    if (l->attrs.comparator == NULL || l->numels == 0)
        return NULL;
    
    curminmax = l->head_sentinel->next->data;
    for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
        if (l->attrs.comparator(curminmax, s->data) * versus > 0)
            curminmax = s->data;
    }

    return curminmax;
}

/* set tmp to point to element at index posstart in l */
static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart) {
    struct list_entry_s *ptr;
    float x;
    int i;

    /* accept 1 slot overflow for fetching head and tail sentinels */
    if (posstart < -1 || posstart > (int)l->numels) return NULL;

    x = (float)(posstart+1) / l->numels;
    if (x <= 0.25) {
        /* first quarter: get to posstart from head */
        for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
    } else if (x < 0.5) {
        /* second quarter: get to posstart from mid */
        for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
    } else if (x <= 0.75) {
        /* third quarter: get to posstart from mid */
        for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
    } else {
        /* fourth quarter: get to posstart from tail */
        for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
    }

    return ptr;
}

void *list_extract_at(list_t *restrict l, unsigned int pos) {
    struct list_entry_s *tmp;
    void *data;
    
    if (l->iter_active || pos >= l->numels) return NULL;

    tmp = list_findpos(l, pos);
    data = tmp->data;

    tmp->data = NULL;   /* save data from list_drop_elem() free() */
    list_drop_elem(l, tmp, pos);
    l->numels--;
    
    assert(list_repOk(l));

    return data;
}

int list_insert_at(list_t *restrict l, const void *data, unsigned int pos) {
    struct list_entry_s *lent, *succ, *prec;
    
    if (l->iter_active || pos > l->numels) return -1;
    
    /* this code optimizes malloc() with a free-list */
    if (l->spareelsnum > 0) {
        lent = l->spareels[l->spareelsnum-1];
        l->spareelsnum--;
    } else {
        lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
        if (lent == NULL)
            return -1;
    }

    if (l->attrs.copy_data) {
        /* make room for user' data (has to be copied) */
        size_t datalen = l->attrs.meter(data);
        lent->data = (struct list_entry_s *)malloc(datalen);
        memcpy(lent->data, data, datalen);
    } else {
        lent->data = (void*)data;
    }

    /* actually append element */
    prec = list_findpos(l, pos-1);
    succ = prec->next;
    
    prec->next = lent;
    lent->prev = prec;
    lent->next = succ;
    succ->prev = lent;

    l->numels++;

    /* fix mid pointer */
    if (l->numels == 1) { /* first element, set pointer */
        l->mid = lent;
    } else if (l->numels % 2) {    /* now odd */
        if (pos >= (l->numels-1)/2) l->mid = l->mid->next;
    } else {                /* now even */
        if (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
    }

    assert(list_repOk(l));

    return 1;
}

int list_delete(list_t *restrict l, const void *data) {
	int pos, r;

	pos = list_locate(l, data);
	if (pos < 0)
		return -1;

	r = list_delete_at(l, pos);
	if (r < 0)
		return -1;

    assert(list_repOk(l));

	return 0;
}

int list_delete_at(list_t *restrict l, unsigned int pos) {
    struct list_entry_s *delendo;


    if (l->iter_active || pos >= l->numels) return -1;

    delendo = list_findpos(l, pos);

    list_drop_elem(l, delendo, pos);

    l->numels--;


    assert(list_repOk(l));

    return  0;
}

int list_delete_range(list_t *restrict l, unsigned int posstart, unsigned int posend) {
    struct list_entry_s *lastvalid, *tmp, *tmp2;
    unsigned int i;
    int movedx;
    unsigned int numdel, midposafter;

    if (l->iter_active || posend < posstart || posend >= l->numels) return -1;

    tmp = list_findpos(l, posstart);    /* first el to be deleted */
    lastvalid = tmp->prev;              /* last valid element */

    numdel = posend - posstart + 1;
    midposafter = (l->numels-1-numdel)/2;

    midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
    movedx = midposafter - (l->numels-1)/2;

    if (movedx > 0) { /* move right */
        for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++);
    } else {    /* move left */
        movedx = -movedx;
        for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++);
    }

    assert(posstart == 0 || lastvalid != l->head_sentinel);
    i = posstart;
    if (l->attrs.copy_data) {
        /* also free element data */
        for (; i <= posend; i++) {
            tmp2 = tmp;
            tmp = tmp->next;
            if (tmp2->data != NULL) free(tmp2->data);
            if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
                l->spareels[l->spareelsnum++] = tmp2;
            } else {
                free(tmp2);
            }
        }
    } else {
        /* only free containers */
        for (; i <= posend; i++) {
            tmp2 = tmp;
            tmp = tmp->next;
            if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
                l->spareels[l->spareelsnum++] = tmp2;
            } else {
                free(tmp2);
            }
        }
    }
    assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));

    lastvalid->next = tmp;
    tmp->prev = lastvalid;

    l->numels -= posend - posstart + 1;

    assert(list_repOk(l));

    return 0;
}

int list_clear(list_t *restrict l) {
    struct list_entry_s *s;

    if (l->iter_active) return -1;
    
    if (l->attrs.copy_data) {        /* also free user data */
        /* spare a loop conditional with two loops: spareing elems and freeing elems */
        for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
            /* move elements as spares as long as there is room */
            if (s->data != NULL) free(s->data);
            l->spareels[l->spareelsnum++] = s;
        }
        while (s != l->tail_sentinel) {
            /* free the remaining elems */
            if (s->data != NULL) free(s->data);
            s = s->next;
            free(s->prev);
        }
        l->head_sentinel->next = l->tail_sentinel;
        l->tail_sentinel->prev = l->head_sentinel;
    } else { /* only free element containers */
        /* spare a loop conditional with two loops: spareing elems and freeing elems */
        for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
            /* move elements as spares as long as there is room */
            l->spareels[l->spareelsnum++] = s;
        }
        while (s != l->tail_sentinel) {
            /* free the remaining elems */
            s = s->next;
            free(s->prev);
        }
        l->head_sentinel->next = l->tail_sentinel;
        l->tail_sentinel->prev = l->head_sentinel;
    }
    l->numels = 0;
    l->mid = NULL;

    assert(list_repOk(l));

    return 0;
}

unsigned int list_size(const list_t *restrict l) {
    return l->numels;
}

int list_empty(const list_t *restrict l) {
    return (l->numels == 0);
}

int list_locate(const list_t *restrict l, const void *data) {
    struct list_entry_s *el;
    int pos = 0;
    
    if (l->attrs.comparator != NULL) {
        /* use comparator */
        for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
            if (l->attrs.comparator(data, el->data) == 0) break;
        }
    } else {
        /* compare references */
        for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
            if (el->data == data) break;
        }
    }
    if (el == l->tail_sentinel) return -1;

    return pos;
}

void *list_seek(list_t *restrict l, const void *indicator) {
    const struct list_entry_s *iter;

    if (l->attrs.seeker == NULL) return NULL;

    for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
        if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data;
    }

    return NULL;
}

int list_contains(const list_t *restrict l, const void *data) {
    return (list_locate(l, data) >= 0);
}

int list_concat(const list_t *l1, const list_t *l2, list_t *restrict dest) {
    struct list_entry_s *el, *srcel;
    unsigned int cnt;
    int err;


    if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
        return -1;

    list_init(dest);

    dest->numels = l1->numels + l2->numels;
    if (dest->numels == 0)
        return 0;

    /* copy list1 */
    srcel = l1->head_sentinel->next;
    el = dest->head_sentinel;
    while (srcel != l1->tail_sentinel) {
        el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
        el->next->prev = el;
        el = el->next;
        el->data = srcel->data;
        srcel = srcel->next;
    }
    dest->mid = el;     /* approximate position (adjust later) */
    /* copy list 2 */
    srcel = l2->head_sentinel->next;
    while (srcel != l2->tail_sentinel) {
        el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
        el->next->prev = el;
        el = el->next;
        el->data = srcel->data;
        srcel = srcel->next;
    }
    el->next = dest->tail_sentinel;
    dest->tail_sentinel->prev = el;
    
    /* fix mid pointer */
    err = l2->numels - l1->numels;
    if ((err+1)/2 > 0) {        /* correct pos RIGHT (err-1)/2 moves */
        err = (err+1)/2;
        for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next;
    } else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */
        err = -err/2;
        for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev;
    }
 
    assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));

    return 0;
}

int list_sort(list_t *restrict l, int versus) {
    if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */
        return -1;

    if (l->numels <= 1)
        return 0;
    list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
    assert(list_repOk(l));
    return 0;
}

#ifdef SIMCLIST_WITH_THREADS
struct list_sort_wrappedparams {
    list_t *restrict l;
    int versus;
    unsigned int first, last;
    struct list_entry_s *fel, *lel;
};

static void *list_sort_quicksort_threadwrapper(void *wrapped_params) {
    struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params;
    list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
    free(wp);
    pthread_exit(NULL);
    return NULL;
}
#endif

static inline void list_sort_selectionsort(list_t *restrict l, int versus, 
        unsigned int first, struct list_entry_s *fel,
        unsigned int last, struct list_entry_s *lel) {
    struct list_entry_s *cursor, *toswap, *firstunsorted;
    void *tmpdata;

    if (last <= first) /* <= 1-element lists are always sorted */
        return;
    
    for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
        /* find min or max in the remainder of the list */
        for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
            if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
        if (toswap != firstunsorted) { /* swap firstunsorted with toswap */
            tmpdata = firstunsorted->data;
            firstunsorted->data = toswap->data;
            toswap->data = tmpdata;
        }
    }
}

static void list_sort_quicksort(list_t *restrict l, int versus, 
        unsigned int first, struct list_entry_s *fel,
        unsigned int last, struct list_entry_s *lel) {
    unsigned int pivotid;
    unsigned int i;
    register struct list_entry_s *pivot;
    struct list_entry_s *left, *right;
    void *tmpdata;
#ifdef SIMCLIST_WITH_THREADS
    pthread_t tid;
    int traised;
#endif


    if (last <= first)      /* <= 1-element lists are always sorted */
        return;
    
    if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
        list_sort_selectionsort(l, versus, first, fel, last, lel);
        return;
    }
    
    /* base of iteration: one element list */
    if (! (last > first)) return;

    pivotid = (get_random() % (last - first + 1));
    /* pivotid = (last - first + 1) / 2; */

    /* find pivot */
    if (pivotid < (last - first + 1)/2) {
        for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
    } else {
        for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
    }

    /* smaller PIVOT bigger */
    left = fel;
    right = lel;
    /* iterate     --- left ---> PIV <--- right --- */
    while (left != pivot && right != pivot) {
        for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
        /* left points to a smaller element, or to pivot */
        for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
        /* right points to a bigger element, or to pivot */
        if (left != pivot && right != pivot) {
            /* swap, then move iterators */
            tmpdata = left->data;
            left->data = right->data;
            right->data = tmpdata;

            left = left->next;
            right = right->prev;
        }
    }

    /* now either left points to pivot (end run), or right */
    if (right == pivot) {    /* left part longer */
        while (left != pivot) {
            if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
                tmpdata = left->data;
                left->data = pivot->prev->data;
                pivot->prev->data = pivot->data;
                pivot->data = tmpdata;
                pivot = pivot->prev;
                pivotid--;
                if (pivot == left) break;
            } else {
                left = left->next;
            }
        }
    } else {                /* right part longer */
        while (right != pivot) {
            if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
                /* move current right before pivot */
                tmpdata = right->data;
                right->data = pivot->next->data;
                pivot->next->data = pivot->data;
                pivot->data = tmpdata;
                pivot = pivot->next;
                pivotid++;
                if (pivot == right) break;
            } else {
                right = right->prev;
            }
        }
    }

    /* sort sublists A and B :       |---A---| pivot |---B---| */

#ifdef SIMCLIST_WITH_THREADS
    traised = 0;
    if (pivotid > 0) {
        /* prepare wrapped args, then start thread */
        if (l->threadcount < SIMCLIST_MAXTHREADS-1) {
            struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams));
            l->threadcount++;
            traised = 1;
            wp->l = l;
            wp->versus = versus;
            wp->first = first;
            wp->fel = fel;
            wp->last = first+pivotid-1;
            wp->lel = pivot->prev;
            if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
                free(wp);
                traised = 0;
                list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
            }
        } else {
            list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
        }
    }
    if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
    if (traised) {
        pthread_join(tid, (void **)NULL);
        l->threadcount--;
    }
#else
    if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
    if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
#endif
}

int list_iterator_start(list_t *restrict l) {
    if (l->iter_active) return 0;
    l->iter_pos = 0;
    l->iter_active = 1;
    l->iter_curentry = l->head_sentinel->next;
    return 1;
}

void *list_iterator_next(list_t *restrict l) {
    void *toret;

    if (! l->iter_active) return NULL;

    toret = l->iter_curentry->data;
    l->iter_curentry = l->iter_curentry->next;
    l->iter_pos++;

    return toret;
}

int list_iterator_hasnext(const list_t *restrict l) {
    if (! l->iter_active) return 0;
    return (l->iter_pos < l->numels);
}

int list_iterator_stop(list_t *restrict l) {
    if (! l->iter_active) return 0;
    l->iter_pos = 0;
    l->iter_active = 0;
    return 1;
}

int list_hash(const list_t *restrict l, list_hash_t *restrict hash) {
    struct list_entry_s *x;
    list_hash_t tmphash;
    
    assert(hash != NULL);

    tmphash = l->numels * 2 + 100;
    if (l->attrs.hasher == NULL) {
#ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES
        /* ENABLE WITH CARE !! */
#warning "Memlocation-based hash is consistent only for testing modification in the same program run."
        int i;

        /* only use element references */
        for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
            for (i = 0; i < sizeof(x->data); i++) {
                tmphash += (tmphash ^ (uintptr_t)x->data);
            }
            tmphash += tmphash % l->numels;
        }
#else
        return -1;
#endif
    } else {
        /* hash each element with the user-given function */
        for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
            tmphash += tmphash ^ l->attrs.hasher(x->data);
            tmphash +=* hash % l->numels;
        }
    }

    *hash = tmphash;

    return 0;
}

#ifndef SIMCLIST_NO_DUMPRESTORE
int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *restrict info) {
    int32_t terminator_head, terminator_tail;
    uint32_t elemlen;
    off_t hop;


    /* version */
    READ_ERRCHECK(fd, & info->version, sizeof(info->version));
    info->version = ntohs(info->version);
    if (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
        errno = EILSEQ;
        return -1;
    }

    /* timestamp */
    READ_ERRCHECK(fd, & info->timestamp, sizeof(info->timestamp));
    info->timestamp = hton64(info->timestamp);

    /* list terminator (to check thereafter) */
    READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head));
    terminator_head = ntohl(terminator_head);

    /* list size */
    READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size));
    info->list_size = ntohl(info->list_size);

    /* number of elements */
    READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels));
    info->list_numels = ntohl(info->list_numels);

    /* length of each element (for checking for consistency) */
    READ_ERRCHECK(fd, & elemlen, sizeof(elemlen));
    elemlen = ntohl(elemlen);

    /* list hash */
    READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash));
    info->list_hash = ntohl(info->list_hash);

    /* check consistency */
    if (elemlen > 0) {
        /* constant length, hop by size only */
        hop = info->list_size;
    } else {
        /* non-constant length, hop by size + all element length blocks */
        hop = info->list_size + elemlen*info->list_numels;
    }
    if (lseek(fd, hop, SEEK_CUR) == -1) {
        return -1;
    }

    /* read the trailing value and compare with terminator_head */
    READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail));
    terminator_tail = ntohl(terminator_tail);

    if (terminator_head == terminator_tail)
        info->consistent = 1;
    else
        info->consistent = 0;

    return 0;
}

int list_dump_getinfo_file(const char *restrict filename, list_dump_info_t *restrict info) {
    int fd, ret;

    fd = open(filename, O_RDONLY, 0);
    if (fd < 0) return -1;

    ret = list_dump_getinfo_filedescriptor(fd, info);
    close(fd);

    return ret;
}

int list_dump_filedescriptor(const list_t *restrict l, int fd, size_t *restrict len) {
    struct list_entry_s *x;
    void *ser_buf;
    uint32_t bufsize;
    struct timeval timeofday;
    struct list_dump_header_s header;

    if (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
        errno = ENOTTY;
        return -1;
    }

    /****       DUMP FORMAT      ****

    [ ver   timestamp   |  totlen   numels  elemlen     hash    |   DATA ]
    
    where DATA can be:
    @ for constant-size list (element size is constant; elemlen > 0)
    [ elem    elem    ...    elem ]
    @ for other lists (element size dictated by element_meter each time; elemlen <= 0)
    [ size elem     size elem       ...     size elem ]
    
    all integers are encoded in NETWORK BYTE FORMAT
    *****/


    /* prepare HEADER */
    /* version */
    header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );

    /* timestamp */
    gettimeofday(&timeofday, NULL);
    header.timestamp = (int64_t)timeofday.tv_sec * 1000000 + (int64_t)timeofday.tv_usec;
    header.timestamp = hton64(header.timestamp);

    header.rndterm = htonl((int32_t)get_random());

    /* total list size is postprocessed afterwards */

    /* number of elements */
    header.numels = htonl(l->numels);

    /* include an hash, if possible */
    if (l->attrs.hasher != NULL) {
        if (htonl(list_hash(l, & header.listhash)) != 0) {
            /* could not compute list hash! */
            return -1;
        }
    } else {
        header.listhash = htonl(0);
    }

    header.totlistlen = header.elemlen = 0;

    /* leave room for the header at the beginning of the file */
    if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
        /* errno set by lseek() */
        return -1;
    }

    /* write CONTENT */
    if (l->numels > 0) {
        /* SPECULATE that the list has constant element size */
        
        if (l->attrs.serializer != NULL) {  /* user user-specified serializer */
            /* get preliminary length of serialized element in header.elemlen */
            ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
            free(ser_buf);
            /* request custom serialization of each element */
            for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
                ser_buf = l->attrs.serializer(x->data, &bufsize);
                header.totlistlen += bufsize;
                if (header.elemlen != 0) {      /* continue on speculation */
                    if (header.elemlen != bufsize) {
                        free(ser_buf);
                        /* constant element length speculation broken! */
                        header.elemlen = 0;
                        header.totlistlen = 0;
                        x = l->head_sentinel;
                        if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
                            /* errno set by lseek() */
                            return -1;
                        }
                        /* restart from the beginning */
                        continue;
                    }
                    /* speculation confirmed */
                    WRITE_ERRCHECK(fd, ser_buf, bufsize);
                } else {                        /* speculation found broken */
                    WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t));
                    WRITE_ERRCHECK(fd, ser_buf, bufsize);
                }
                free(ser_buf);
            }
        } else if (l->attrs.meter != NULL) {
            header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);

            /* serialize the element straight from its data */
            for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
                bufsize = l->attrs.meter(x->data);
                header.totlistlen += bufsize;
                if (header.elemlen != 0) {
                    if (header.elemlen != bufsize) {
                        /* constant element length speculation broken! */
                        header.elemlen = 0;
                        header.totlistlen = 0;
                        x = l->head_sentinel;
                        /* restart from the beginning */
                        continue;
                    }
                    WRITE_ERRCHECK(fd, x->data, bufsize);
                } else {
                    WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t));
                    WRITE_ERRCHECK(fd, x->data, bufsize);
                }
            }
        }
        /* adjust endianness */
        header.elemlen = htonl(header.elemlen);
        header.totlistlen = htonl(header.totlistlen);
    }

    /* write random terminator */
    WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));        /* list terminator */


    /* write header */
    lseek(fd, 0, SEEK_SET);

    WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver));                        /* version */
    WRITE_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp));            /* timestamp */
    WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));                /* random terminator */

    WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));          /* total length of elements */
    WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels));                  /* number of elements */
    WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));                /* size of each element, or 0 for independent */
    WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));             /* list hash, or 0 for "ignore" */


    /* possibly store total written length in "len" */
    if (len != NULL) {
        *len = sizeof(header) + ntohl(header.totlistlen);
    }

    return 0;
}

int list_restore_filedescriptor(list_t *restrict l, int fd, size_t *restrict len) {
    struct list_dump_header_s header;
    unsigned long cnt;
    void *buf;
    uint32_t elsize, totreadlen, totmemorylen;

    memset(& header, 0, sizeof(header));

    /* read header */
    
    /* version */
    READ_ERRCHECK(fd, &header.ver, sizeof(header.ver));
    header.ver = ntohs(header.ver);
    if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
        errno = EILSEQ;
        return -1;
    }

    /* timestamp */
    READ_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp));

    /* list terminator */
    READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));

    header.rndterm = ntohl(header.rndterm);

    /* total list size */
    READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));
    header.totlistlen = ntohl(header.totlistlen);

    /* number of elements */
    READ_ERRCHECK(fd, & header.numels, sizeof(header.numels));
    header.numels = ntohl(header.numels);

    /* length of every element, or '0' = variable */
    READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));
    header.elemlen = ntohl(header.elemlen);

    /* list hash, or 0 = 'ignore' */
    READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));
    header.listhash = ntohl(header.listhash);


    /* read content */
    totreadlen = totmemorylen = 0;
    if (header.elemlen > 0) {   
        /* elements have constant size = header.elemlen */
        if (l->attrs.unserializer != NULL) {
            /* use unserializer */
            buf = malloc(header.elemlen);
            for (cnt = 0; cnt < header.numels; cnt++) {
                READ_ERRCHECK(fd, buf, header.elemlen);
                list_append(l, l->attrs.unserializer(buf, & elsize));
                totmemorylen += elsize;
            }
        } else {
            /* copy verbatim into memory */
            for (cnt = 0; cnt < header.numels; cnt++) {
                buf = malloc(header.elemlen);
                READ_ERRCHECK(fd, buf, header.elemlen);
                list_append(l, buf);
            }
            totmemorylen = header.numels * header.elemlen;
        }
        totreadlen = header.numels * header.elemlen;
    } else {
        /* elements have variable size. Each element is preceded by its size */
        if (l->attrs.unserializer != NULL) {
            /* use unserializer */
            for (cnt = 0; cnt < header.numels; cnt++) {
                READ_ERRCHECK(fd, & elsize, sizeof(elsize));
                buf = malloc((size_t)elsize);
                READ_ERRCHECK(fd, buf, elsize);
                totreadlen += elsize;
                list_append(l, l->attrs.unserializer(buf, & elsize));
                totmemorylen += elsize;
            }
        } else {
            /* copy verbatim into memory */
            for (cnt = 0; cnt < header.numels; cnt++) {
                READ_ERRCHECK(fd, & elsize, sizeof(elsize));
                buf = malloc(elsize);
                READ_ERRCHECK(fd, buf, elsize);
                totreadlen += elsize;
                list_append(l, buf);
            }
            totmemorylen = totreadlen;
        }
    }

    READ_ERRCHECK(fd, &elsize, sizeof(elsize));  /* read list terminator */
    elsize = ntohl(elsize);

    /* possibly verify the list consistency */
    /* wrt hash */
    /* don't do that
    if (header.listhash != 0 && header.listhash != list_hash(l)) {
        errno = ECANCELED;
        return -1;
    }
    */

    /* wrt header */
    if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
        errno = EPROTO;
        return -1;
    }

    /* wrt file */
    if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
        errno = EPROTO;
        return -1;
    }

    if (len != NULL) {
        *len = totmemorylen;
    }

    return 0;
}

int list_dump_file(const list_t *restrict l, const char *restrict filename, size_t *restrict len) {
    int fd;
    size_t sizetoret;

    fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
    if (fd < 0) return -1;

    sizetoret = list_dump_filedescriptor(l, fd, len);
    close(fd);

    return sizetoret;
}

int list_restore_file(list_t *restrict l, const char *restrict filename, size_t *restrict len) {
    int fd;
    size_t totdata;

    fd = open(filename, O_RDONLY, 0);
    if (fd < 0) return -1;

    totdata = list_restore_filedescriptor(l, fd, len);
    close(fd);

    return totdata;
}
#endif /* ifndef SIMCLIST_NO_DUMPRESTORE */


static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos) {
    if (tmp == NULL) return -1;

    /* fix mid pointer. This is wrt the PRE situation */
    if (l->numels % 2) {    /* now odd */
        /* sort out the base case by hand */
        if (l->numels == 1) l->mid = NULL;
        else if (pos >= l->numels/2) l->mid = l->mid->prev;
    } else {                /* now even */
        if (pos < l->numels/2) l->mid = l->mid->next;
    }
    
    tmp->prev->next = tmp->next;
    tmp->next->prev = tmp->prev;

    /* free what's to be freed */
    if (l->attrs.copy_data && tmp->data != NULL)
        free(tmp->data);

    if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
        l->spareels[l->spareelsnum++] = tmp;
    } else {
        free(tmp);
    }

    return 0;
}

/* ready-made comparators and meters */
#define SIMCLIST_NUMBER_COMPARATOR(type)     int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); } 

SIMCLIST_NUMBER_COMPARATOR(int8_t)
SIMCLIST_NUMBER_COMPARATOR(int16_t)
SIMCLIST_NUMBER_COMPARATOR(int32_t)
SIMCLIST_NUMBER_COMPARATOR(int64_t)

SIMCLIST_NUMBER_COMPARATOR(uint8_t)
SIMCLIST_NUMBER_COMPARATOR(uint16_t)
SIMCLIST_NUMBER_COMPARATOR(uint32_t)
SIMCLIST_NUMBER_COMPARATOR(uint64_t)

SIMCLIST_NUMBER_COMPARATOR(float)
SIMCLIST_NUMBER_COMPARATOR(double)

int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); }

/* ready-made metric functions */
#define SIMCLIST_METER(type)        size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); }

SIMCLIST_METER(int8_t)
SIMCLIST_METER(int16_t)
SIMCLIST_METER(int32_t)
SIMCLIST_METER(int64_t)

SIMCLIST_METER(uint8_t)
SIMCLIST_METER(uint16_t)
SIMCLIST_METER(uint32_t)
SIMCLIST_METER(uint64_t)

SIMCLIST_METER(float)
SIMCLIST_METER(double)

size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; }

/* ready-made hashing functions */
#define SIMCLIST_HASHCOMPUTER(type)    list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); }

SIMCLIST_HASHCOMPUTER(int8_t)
SIMCLIST_HASHCOMPUTER(int16_t)
SIMCLIST_HASHCOMPUTER(int32_t)
SIMCLIST_HASHCOMPUTER(int64_t)

SIMCLIST_HASHCOMPUTER(uint8_t)
SIMCLIST_HASHCOMPUTER(uint16_t)
SIMCLIST_HASHCOMPUTER(uint32_t)
SIMCLIST_HASHCOMPUTER(uint64_t)

SIMCLIST_HASHCOMPUTER(float)
SIMCLIST_HASHCOMPUTER(double)

list_hash_t list_hashcomputer_string(const void *el) {
    size_t l;
    list_hash_t hash = 123;
    const char *str = (const char *)el;
    char plus;

    for (l = 0; str[l] != '\0'; l++) {
        if (l) plus = hash ^ str[l];
        else plus = hash ^ (str[l] - str[0]);
        hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t))));
    }

    return hash;
}


#ifndef NDEBUG
static int list_repOk(const list_t *restrict l) {
    int ok, i;
    struct list_entry_s *s;

    ok = (l != NULL) && (
            /* head/tail checks */
            (l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
                (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
            /* empty list */
            (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
            /* spare elements checks */
            l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
         );
    
    if (!ok) return 0;

    if (l->numels >= 1) {
        /* correct referencing */
        for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
            if (s->next->prev != s) break;
        }
        ok = (i == (int)(l->numels-1)/2 && l->mid == s);
        if (!ok) return 0;
        for (; s->next != NULL; i++, s = s->next) {
            if (s->next->prev != s) break;
        }
        ok = (i == (int)l->numels && s == l->tail_sentinel);
    }

    return ok;
}

static int list_attrOk(const list_t *restrict l) {
    int ok;

    ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);
    return ok;
}

#endif