/*

 * Copyright (c) 2007,2008,2009,2010,2011 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.6 */

#include <stdlib.h>

#include <string.h>

#include <errno.h>          /* for setting errno */

#include <sys/types.h>

#ifndef _WIN32

    /* not in Windows! */

#   include <unistd.h>

#   include <stdint.h>

#endif

#ifndef SIMCLIST_NO_DUMPRESTORE

    /* includes for dump/restore */

#   include <time.h>

#   include <sys/uio.h>     /* for READ_ERRCHECK() and write() */

#   include <fcntl.h>       /* for open() etc */

#   ifndef _WIN32

#       include <arpa/inet.h>  /* for htons() on UNIX */

#   else

#       include <winsock2.h>  /* for htons() on Windows */

#   endif

#endif

/* disable asserts */

#ifndef SIMCLIST_DEBUG

#define NDEBUG

#endif

#include <assert.h>

#include <sys/stat.h>       /* for open()'s access modes S_IRUSR etc */

#include <limits.h>

#if defined(_MSC_VER) || defined(__MINGW32__)

/* provide gettimeofday() missing in Windows */

int gettimeofday(struct timeval *tp, void *tzp) {

    DWORD t;

    /* XSI says: "If tzp is not a null pointer, the behavior is unspecified" */

    assert(tzp == NULL);

    t = timeGetTime();

    tp->tv_sec = t / 1000;

    tp->tv_usec = t % 1000;

    return 0;

}

#endif

/* 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

/* define some commodity macros for Dump/Restore functionality */

#ifndef SIMCLIST_NO_DUMPRESTORE

/* 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);

/* 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

#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 */

    int32_t timestamp_sec;      /* dump timestamp, seconds since UNIX Epoch */

    int32_t timestamp_usec;     /* dump timestamp, microseconds since timestamp_sec */

    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);

/*

 * 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(void) {

    if (random_seed == 0)

        random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);

}

static inline long get_random(void) {

    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 numdel, midposafter, i;

    int movedx;

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

    numdel = posend - posstart + 1;

    if (numdel == l->numels) return list_clear(l);

    tmp = list_findpos(l, posstart);    /* first el to be deleted */

    lastvalid = tmp->prev;              /* last valid element */

    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 numdel;

}

int list_clear(list_t *restrict l) {

    struct list_entry_s *s;

    unsigned int numels;

    /* will be returned */

    numels = l->numels;

    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 numels;

}

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;