|
Packit |
9f0df5 |
/*
|
|
Packit |
9f0df5 |
* Copyright (c) 2007,2008,2009,2010,2011 Mij <mij@bitchx.it>
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* Permission to use, copy, modify, and distribute this software for any
|
|
Packit |
9f0df5 |
* purpose with or without fee is hereby granted, provided that the above
|
|
Packit |
9f0df5 |
* copyright notice and this permission notice appear in all copies.
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
|
|
Packit |
9f0df5 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
|
|
Packit |
9f0df5 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
|
|
Packit |
9f0df5 |
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
|
|
Packit |
9f0df5 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
|
|
Packit |
9f0df5 |
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
|
|
Packit |
9f0df5 |
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
|
|
Packit |
9f0df5 |
*/
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/*
|
|
Packit |
9f0df5 |
* SimCList library. See http://mij.oltrelinux.com/devel/simclist
|
|
Packit |
9f0df5 |
*/
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* SimCList implementation, version 1.6 */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#include <stdlib.h>
|
|
Packit |
9f0df5 |
#include <string.h>
|
|
Packit |
9f0df5 |
#include <errno.h> /* for setting errno */
|
|
Packit |
9f0df5 |
#include <sys/types.h>
|
|
Packit |
9f0df5 |
#ifndef _WIN32
|
|
Packit |
9f0df5 |
/* not in Windows! */
|
|
Packit |
9f0df5 |
# include <unistd.h>
|
|
Packit |
9f0df5 |
# include <stdint.h>
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
#ifndef SIMCLIST_NO_DUMPRESTORE
|
|
Packit |
9f0df5 |
/* includes for dump/restore */
|
|
Packit |
9f0df5 |
# include <time.h>
|
|
Packit |
9f0df5 |
# include <sys/uio.h> /* for READ_ERRCHECK() and write() */
|
|
Packit |
9f0df5 |
# include <fcntl.h> /* for open() etc */
|
|
Packit |
9f0df5 |
# ifndef _WIN32
|
|
Packit |
9f0df5 |
# include <arpa/inet.h> /* for htons() on UNIX */
|
|
Packit |
9f0df5 |
# else
|
|
Packit |
9f0df5 |
# include <winsock2.h> /* for htons() on Windows */
|
|
Packit |
9f0df5 |
# endif
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* disable asserts */
|
|
Packit |
9f0df5 |
#ifndef SIMCLIST_DEBUG
|
|
Packit |
9f0df5 |
#define NDEBUG
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#include <assert.h>
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#include <sys/stat.h> /* for open()'s access modes S_IRUSR etc */
|
|
Packit |
9f0df5 |
#include <limits.h>
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#if defined(_MSC_VER) || defined(__MINGW32__)
|
|
Packit |
9f0df5 |
/* provide gettimeofday() missing in Windows */
|
|
Packit |
9f0df5 |
int gettimeofday(struct timeval *tp, void *tzp) {
|
|
Packit |
9f0df5 |
DWORD t;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* XSI says: "If tzp is not a null pointer, the behavior is unspecified" */
|
|
Packit |
9f0df5 |
assert(tzp == NULL);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
t = timeGetTime();
|
|
Packit |
9f0df5 |
tp->tv_sec = t / 1000;
|
|
Packit |
9f0df5 |
tp->tv_usec = t % 1000;
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */
|
|
Packit |
9f0df5 |
#if !defined(_WIN32) || !defined(_MSC_VER)
|
|
Packit |
9f0df5 |
# include <inttypes.h> /* (u)int*_t */
|
|
Packit |
9f0df5 |
#else
|
|
Packit |
9f0df5 |
# include <basetsd.h>
|
|
Packit |
9f0df5 |
typedef UINT8 uint8_t;
|
|
Packit |
9f0df5 |
typedef UINT16 uint16_t;
|
|
Packit |
9f0df5 |
typedef ULONG32 uint32_t;
|
|
Packit |
9f0df5 |
typedef UINT64 uint64_t;
|
|
Packit |
9f0df5 |
typedef INT8 int8_t;
|
|
Packit |
9f0df5 |
typedef INT16 int16_t;
|
|
Packit |
9f0df5 |
typedef LONG32 int32_t;
|
|
Packit |
9f0df5 |
typedef INT64 int64_t;
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* define some commodity macros for Dump/Restore functionality */
|
|
Packit |
9f0df5 |
#ifndef SIMCLIST_NO_DUMPRESTORE
|
|
Packit |
9f0df5 |
/* write() decorated with error checking logic */
|
|
Packit |
9f0df5 |
#define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \
|
|
Packit |
9f0df5 |
if (write(fd, msgbuf, msglen) < 0) return -1; \
|
|
Packit |
9f0df5 |
} while (0);
|
|
Packit |
9f0df5 |
/* READ_ERRCHECK() decorated with error checking logic */
|
|
Packit |
9f0df5 |
#define READ_ERRCHECK(fd, msgbuf, msglen) do { \
|
|
Packit |
9f0df5 |
if (read(fd, msgbuf, msglen) != msglen) { \
|
|
Packit |
9f0df5 |
/*errno = EPROTO;*/ \
|
|
Packit |
9f0df5 |
return -1; \
|
|
Packit |
9f0df5 |
} \
|
|
Packit |
9f0df5 |
} while (0);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* convert 64bit integers from host to network format */
|
|
Packit |
9f0df5 |
#define hton64(x) (\
|
|
Packit |
9f0df5 |
htons(1) == 1 ? \
|
|
Packit |
9f0df5 |
(uint64_t)x /* big endian */ \
|
|
Packit |
9f0df5 |
: /* little endian */ \
|
|
Packit |
9f0df5 |
((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
|
|
Packit |
9f0df5 |
(((uint64_t)(x) & 0x00000000000000ffULL) << 56))) \
|
|
Packit |
9f0df5 |
)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* convert 64bit integers from network to host format */
|
|
Packit |
9f0df5 |
#define ntoh64(x) (hton64(x))
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* some OSes don't have EPROTO (eg OpenBSD) */
|
|
Packit |
9f0df5 |
#ifndef EPROTO
|
|
Packit |
9f0df5 |
#define EPROTO EIO
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
/* limit (approx) to the number of threads running
|
|
Packit |
9f0df5 |
* for threaded operations. Only meant when
|
|
Packit |
9f0df5 |
* SIMCLIST_WITH_THREADS is defined */
|
|
Packit |
9f0df5 |
#define SIMCLIST_MAXTHREADS 2
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/*
|
|
Packit |
9f0df5 |
* how many elems to keep as spare. During a deletion, an element
|
|
Packit |
9f0df5 |
* can be saved in a "free-list", not free()d immediately. When
|
|
Packit |
9f0df5 |
* latter insertions are performed, spare elems can be used instead
|
|
Packit |
9f0df5 |
* of malloc()ing new elems.
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* about this param, some values for appending
|
|
Packit |
9f0df5 |
* 10 million elems into an empty list:
|
|
Packit |
9f0df5 |
* (#, time[sec], gain[%], gain/no[%])
|
|
Packit |
9f0df5 |
* 0 2,164 0,00 0,00 <-- feature disabled
|
|
Packit |
9f0df5 |
* 1 1,815 34,9 34,9
|
|
Packit |
9f0df5 |
* 2 1,446 71,8 35,9 <-- MAX gain/no
|
|
Packit |
9f0df5 |
* 3 1,347 81,7 27,23
|
|
Packit |
9f0df5 |
* 5 1,213 95,1 19,02
|
|
Packit |
9f0df5 |
* 8 1,064 110,0 13,75
|
|
Packit |
9f0df5 |
* 10 1,015 114,9 11,49 <-- MAX gain w/ likely sol
|
|
Packit |
9f0df5 |
* 15 1,019 114,5 7,63
|
|
Packit |
9f0df5 |
* 25 0,985 117,9 4,72
|
|
Packit |
9f0df5 |
* 50 1,088 107,6 2,15
|
|
Packit |
9f0df5 |
* 75 1,016 114,8 1,53
|
|
Packit |
9f0df5 |
* 100 0,988 117,6 1,18
|
|
Packit |
9f0df5 |
* 150 1,022 114,2 0,76
|
|
Packit |
9f0df5 |
* 200 0,939 122,5 0,61 <-- MIN time
|
|
Packit |
9f0df5 |
*/
|
|
Packit |
9f0df5 |
#ifndef SIMCLIST_MAX_SPARE_ELEMS
|
|
Packit |
9f0df5 |
#define SIMCLIST_MAX_SPARE_ELEMS 5
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
#include <pthread.h>
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#include "simclist.h"
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* minumum number of elements for sorting with quicksort instead of insertion */
|
|
Packit |
9f0df5 |
#define SIMCLIST_MINQUICKSORTELS 24
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list dump declarations */
|
|
Packit |
9f0df5 |
#define SIMCLIST_DUMPFORMAT_VERSION 1 /* (short integer) version of fileformat managed by _dump* and _restore* functions */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#define SIMCLIST_DUMPFORMAT_HEADERLEN 30 /* length of the header */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* header for a list dump */
|
|
Packit |
9f0df5 |
struct list_dump_header_s {
|
|
Packit |
9f0df5 |
uint16_t ver; /* version */
|
|
Packit |
9f0df5 |
int32_t timestamp_sec; /* dump timestamp, seconds since UNIX Epoch */
|
|
Packit |
9f0df5 |
int32_t timestamp_usec; /* dump timestamp, microseconds since timestamp_sec */
|
|
Packit |
9f0df5 |
int32_t rndterm; /* random value terminator -- terminates the data sequence */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
uint32_t totlistlen; /* sum of every element' size, bytes */
|
|
Packit |
9f0df5 |
uint32_t numels; /* number of elements */
|
|
Packit |
9f0df5 |
uint32_t elemlen; /* bytes length of an element, for constant-size lists, <= 0 otherwise */
|
|
Packit |
9f0df5 |
int32_t listhash; /* hash of the list at the time of dumping, or 0 if to be ignored */
|
|
Packit |
9f0df5 |
};
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* deletes tmp from list, with care wrt its position (head, tail, middle) */
|
|
Packit |
9f0df5 |
static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* set default values for initialized lists */
|
|
Packit |
9f0df5 |
static int list_attributes_setdefaults(list_t *restrict l);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifndef NDEBUG
|
|
Packit |
9f0df5 |
/* check whether the list internal REPresentation is valid -- Costs O(n) */
|
|
Packit |
9f0df5 |
static int list_repOk(const list_t *restrict l);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* check whether the list attribute set is valid -- Costs O(1) */
|
|
Packit |
9f0df5 |
static int list_attrOk(const list_t *restrict l);
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* do not inline, this is recursive */
|
|
Packit |
9f0df5 |
static void list_sort_quicksort(list_t *restrict l, int versus,
|
|
Packit |
9f0df5 |
unsigned int first, struct list_entry_s *fel,
|
|
Packit |
9f0df5 |
unsigned int last, struct list_entry_s *lel);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static inline void list_sort_selectionsort(list_t *restrict l, int versus,
|
|
Packit |
9f0df5 |
unsigned int first, struct list_entry_s *fel,
|
|
Packit |
9f0df5 |
unsigned int last, struct list_entry_s *lel);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static void *list_get_minmax(const list_t *restrict l, int versus);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/*
|
|
Packit |
9f0df5 |
* Random Number Generator
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* The user is expected to seed the RNG (ie call srand()) if
|
|
Packit |
9f0df5 |
* SIMCLIST_SYSTEM_RNG is defined.
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* Otherwise, a self-contained RNG based on LCG is used; see
|
|
Packit |
9f0df5 |
* http://en.wikipedia.org/wiki/Linear_congruential_generator .
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* Facts pro local RNG:
|
|
Packit |
9f0df5 |
* 1. no need for the user to call srand() on his own
|
|
Packit |
9f0df5 |
* 2. very fast, possibly faster than OS
|
|
Packit |
9f0df5 |
* 3. avoid interference with user's RNG
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* Facts pro system RNG:
|
|
Packit |
9f0df5 |
* 1. may be more accurate (irrelevant for SimCList randno purposes)
|
|
Packit |
9f0df5 |
* 2. why reinvent the wheel
|
|
Packit |
9f0df5 |
*
|
|
Packit |
9f0df5 |
* Default to local RNG for user's ease of use.
|
|
Packit |
9f0df5 |
*/
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_SYSTEM_RNG
|
|
Packit |
9f0df5 |
/* keep track whether we initialized already (non-0) or not (0) */
|
|
Packit |
9f0df5 |
static unsigned random_seed = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* use local RNG */
|
|
Packit |
9f0df5 |
static inline void seed_random(void) {
|
|
Packit |
9f0df5 |
if (random_seed == 0)
|
|
Packit |
9f0df5 |
random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static inline long get_random(void) {
|
|
Packit |
9f0df5 |
random_seed = (1664525 * random_seed + 1013904223);
|
|
Packit |
9f0df5 |
return random_seed;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#else
|
|
Packit |
9f0df5 |
/* use OS's random generator */
|
|
Packit |
9f0df5 |
# define seed_random()
|
|
Packit |
9f0df5 |
# define get_random() (rand())
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list initialization */
|
|
Packit |
9f0df5 |
int list_init(list_t *restrict l) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
seed_random();
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->numels = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* head/tail sentinels and mid pointer */
|
|
Packit |
9f0df5 |
l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
|
|
Packit |
9f0df5 |
l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
|
|
Packit |
9f0df5 |
l->head_sentinel->next = l->tail_sentinel;
|
|
Packit |
9f0df5 |
l->tail_sentinel->prev = l->head_sentinel;
|
|
Packit |
9f0df5 |
l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
|
|
Packit |
9f0df5 |
l->head_sentinel->data = l->tail_sentinel->data = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* iteration attributes */
|
|
Packit |
9f0df5 |
l->iter_active = 0;
|
|
Packit |
9f0df5 |
l->iter_pos = 0;
|
|
Packit |
9f0df5 |
l->iter_curentry = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* free-list attributes */
|
|
Packit |
9f0df5 |
l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *));
|
|
Packit |
9f0df5 |
l->spareelsnum = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
l->threadcount = 0;
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_attributes_setdefaults(l);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void list_destroy(list_t *restrict l) {
|
|
Packit |
9f0df5 |
unsigned int i;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_clear(l);
|
|
Packit |
9f0df5 |
for (i = 0; i < l->spareelsnum; i++) {
|
|
Packit |
9f0df5 |
free(l->spareels[i]);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
free(l->spareels);
|
|
Packit |
9f0df5 |
free(l->head_sentinel);
|
|
Packit |
9f0df5 |
free(l->tail_sentinel);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_setdefaults(list_t *restrict l) {
|
|
Packit |
9f0df5 |
l->attrs.comparator = NULL;
|
|
Packit |
9f0df5 |
l->attrs.seeker = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* also free() element data when removing and element from the list */
|
|
Packit |
9f0df5 |
l->attrs.meter = NULL;
|
|
Packit |
9f0df5 |
l->attrs.copy_data = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.hasher = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* serializer/unserializer */
|
|
Packit |
9f0df5 |
l->attrs.serializer = NULL;
|
|
Packit |
9f0df5 |
l->attrs.unserializer = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* setting list properties */
|
|
Packit |
9f0df5 |
int list_attributes_comparator(list_t *restrict l, element_comparator comparator_fun) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.comparator = comparator_fun;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_seeker(list_t *restrict l, element_seeker seeker_fun) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.seeker = seeker_fun;
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_copy(list_t *restrict l, element_meter metric_fun, int copy_data) {
|
|
Packit |
9f0df5 |
if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.meter = metric_fun;
|
|
Packit |
9f0df5 |
l->attrs.copy_data = copy_data;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_hash_computer(list_t *restrict l, element_hash_computer hash_computer_fun) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.hasher = hash_computer_fun;
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_serializer(list_t *restrict l, element_serializer serializer_fun) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.serializer = serializer_fun;
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_attributes_unserializer(list_t *restrict l, element_unserializer unserializer_fun) {
|
|
Packit |
9f0df5 |
if (l == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->attrs.unserializer = unserializer_fun;
|
|
Packit |
9f0df5 |
assert(list_attrOk(l));
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_append(list_t *restrict l, const void *data) {
|
|
Packit |
9f0df5 |
return list_insert_at(l, data, l->numels);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_prepend(list_t *restrict l, const void *data) {
|
|
Packit |
9f0df5 |
return list_insert_at(l, data, 0);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_fetch(list_t *restrict l) {
|
|
Packit |
9f0df5 |
return list_extract_at(l, 0);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_get_at(const list_t *restrict l, unsigned int pos) {
|
|
Packit |
9f0df5 |
struct list_entry_s *tmp;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmp = list_findpos(l, pos);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return (tmp != NULL ? tmp->data : NULL);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_get_max(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
return list_get_minmax(l, +1);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_get_min(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
return list_get_minmax(l, -1);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* REQUIRES {list->numels >= 1}
|
|
Packit |
9f0df5 |
* return the min (versus < 0) or max value (v > 0) in l */
|
|
Packit |
9f0df5 |
static void *list_get_minmax(const list_t *restrict l, int versus) {
|
|
Packit |
9f0df5 |
void *curminmax;
|
|
Packit |
9f0df5 |
struct list_entry_s *s;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.comparator == NULL || l->numels == 0)
|
|
Packit |
9f0df5 |
return NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
curminmax = l->head_sentinel->next->data;
|
|
Packit |
9f0df5 |
for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
|
|
Packit |
9f0df5 |
if (l->attrs.comparator(curminmax, s->data) * versus > 0)
|
|
Packit |
9f0df5 |
curminmax = s->data;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return curminmax;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* set tmp to point to element at index posstart in l */
|
|
Packit |
9f0df5 |
static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart) {
|
|
Packit |
9f0df5 |
struct list_entry_s *ptr;
|
|
Packit |
9f0df5 |
float x;
|
|
Packit |
9f0df5 |
int i;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* accept 1 slot overflow for fetching head and tail sentinels */
|
|
Packit |
9f0df5 |
if (posstart < -1 || posstart > (int)l->numels) return NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
x = (float)(posstart+1) / l->numels;
|
|
Packit |
9f0df5 |
if (x <= 0.25) {
|
|
Packit |
9f0df5 |
/* first quarter: get to posstart from head */
|
|
Packit |
9f0df5 |
for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
|
|
Packit |
9f0df5 |
} else if (x < 0.5) {
|
|
Packit |
9f0df5 |
/* second quarter: get to posstart from mid */
|
|
Packit |
9f0df5 |
for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
|
|
Packit |
9f0df5 |
} else if (x <= 0.75) {
|
|
Packit |
9f0df5 |
/* third quarter: get to posstart from mid */
|
|
Packit |
9f0df5 |
for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* fourth quarter: get to posstart from tail */
|
|
Packit |
9f0df5 |
for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return ptr;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_extract_at(list_t *restrict l, unsigned int pos) {
|
|
Packit |
9f0df5 |
struct list_entry_s *tmp;
|
|
Packit |
9f0df5 |
void *data;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->iter_active || pos >= l->numels) return NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmp = list_findpos(l, pos);
|
|
Packit |
9f0df5 |
data = tmp->data;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmp->data = NULL; /* save data from list_drop_elem() free() */
|
|
Packit |
9f0df5 |
list_drop_elem(l, tmp, pos);
|
|
Packit |
9f0df5 |
l->numels--;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return data;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_insert_at(list_t *restrict l, const void *data, unsigned int pos) {
|
|
Packit |
9f0df5 |
struct list_entry_s *lent, *succ, *prec;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->iter_active || pos > l->numels) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* this code optimizes malloc() with a free-list */
|
|
Packit |
9f0df5 |
if (l->spareelsnum > 0) {
|
|
Packit |
9f0df5 |
lent = l->spareels[l->spareelsnum-1];
|
|
Packit |
9f0df5 |
l->spareelsnum--;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
|
|
Packit |
9f0df5 |
if (lent == NULL)
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.copy_data) {
|
|
Packit |
9f0df5 |
/* make room for user' data (has to be copied) */
|
|
Packit |
9f0df5 |
size_t datalen = l->attrs.meter(data);
|
|
Packit |
9f0df5 |
lent->data = (struct list_entry_s *)malloc(datalen);
|
|
Packit |
9f0df5 |
memcpy(lent->data, data, datalen);
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
lent->data = (void*)data;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* actually append element */
|
|
Packit |
9f0df5 |
prec = list_findpos(l, pos-1);
|
|
Packit |
9f0df5 |
succ = prec->next;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
prec->next = lent;
|
|
Packit |
9f0df5 |
lent->prev = prec;
|
|
Packit |
9f0df5 |
lent->next = succ;
|
|
Packit |
9f0df5 |
succ->prev = lent;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->numels++;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* fix mid pointer */
|
|
Packit |
9f0df5 |
if (l->numels == 1) { /* first element, set pointer */
|
|
Packit |
9f0df5 |
l->mid = lent;
|
|
Packit |
9f0df5 |
} else if (l->numels % 2) { /* now odd */
|
|
Packit |
9f0df5 |
if (pos >= (l->numels-1)/2) l->mid = l->mid->next;
|
|
Packit |
9f0df5 |
} else { /* now even */
|
|
Packit |
9f0df5 |
if (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_delete(list_t *restrict l, const void *data) {
|
|
Packit |
9f0df5 |
int pos, r;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
pos = list_locate(l, data);
|
|
Packit |
9f0df5 |
if (pos < 0)
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
r = list_delete_at(l, pos);
|
|
Packit |
9f0df5 |
if (r < 0)
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_delete_at(list_t *restrict l, unsigned int pos) {
|
|
Packit |
9f0df5 |
struct list_entry_s *delendo;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->iter_active || pos >= l->numels) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
delendo = list_findpos(l, pos);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_drop_elem(l, delendo, pos);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->numels--;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_delete_range(list_t *restrict l, unsigned int posstart, unsigned int posend) {
|
|
Packit |
9f0df5 |
struct list_entry_s *lastvalid, *tmp, *tmp2;
|
|
Packit |
9f0df5 |
unsigned int numdel, midposafter, i;
|
|
Packit |
9f0df5 |
int movedx;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->iter_active || posend < posstart || posend >= l->numels) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
numdel = posend - posstart + 1;
|
|
Packit |
9f0df5 |
if (numdel == l->numels) return list_clear(l);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmp = list_findpos(l, posstart); /* first el to be deleted */
|
|
Packit |
9f0df5 |
lastvalid = tmp->prev; /* last valid element */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
midposafter = (l->numels-1-numdel)/2;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
|
|
Packit |
9f0df5 |
movedx = midposafter - (l->numels-1)/2;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (movedx > 0) { /* move right */
|
|
Packit |
9f0df5 |
for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++);
|
|
Packit |
9f0df5 |
} else { /* move left */
|
|
Packit |
9f0df5 |
movedx = -movedx;
|
|
Packit |
9f0df5 |
for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(posstart == 0 || lastvalid != l->head_sentinel);
|
|
Packit |
9f0df5 |
i = posstart;
|
|
Packit |
9f0df5 |
if (l->attrs.copy_data) {
|
|
Packit |
9f0df5 |
/* also free element data */
|
|
Packit |
9f0df5 |
for (; i <= posend; i++) {
|
|
Packit |
9f0df5 |
tmp2 = tmp;
|
|
Packit |
9f0df5 |
tmp = tmp->next;
|
|
Packit |
9f0df5 |
if (tmp2->data != NULL) free(tmp2->data);
|
|
Packit |
9f0df5 |
if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
|
|
Packit |
9f0df5 |
l->spareels[l->spareelsnum++] = tmp2;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
free(tmp2);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* only free containers */
|
|
Packit |
9f0df5 |
for (; i <= posend; i++) {
|
|
Packit |
9f0df5 |
tmp2 = tmp;
|
|
Packit |
9f0df5 |
tmp = tmp->next;
|
|
Packit |
9f0df5 |
if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
|
|
Packit |
9f0df5 |
l->spareels[l->spareelsnum++] = tmp2;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
free(tmp2);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
lastvalid->next = tmp;
|
|
Packit |
9f0df5 |
tmp->prev = lastvalid;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
l->numels -= posend - posstart + 1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return numdel;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_clear(list_t *restrict l) {
|
|
Packit |
9f0df5 |
struct list_entry_s *s;
|
|
Packit |
9f0df5 |
unsigned int numels;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* will be returned */
|
|
Packit |
9f0df5 |
numels = l->numels;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->iter_active) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.copy_data) { /* also free user data */
|
|
Packit |
9f0df5 |
/* spare a loop conditional with two loops: spareing elems and freeing elems */
|
|
Packit |
9f0df5 |
for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
|
|
Packit |
9f0df5 |
/* move elements as spares as long as there is room */
|
|
Packit |
9f0df5 |
if (s->data != NULL) free(s->data);
|
|
Packit |
9f0df5 |
l->spareels[l->spareelsnum++] = s;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
while (s != l->tail_sentinel) {
|
|
Packit |
9f0df5 |
/* free the remaining elems */
|
|
Packit |
9f0df5 |
if (s->data != NULL) free(s->data);
|
|
Packit |
9f0df5 |
s = s->next;
|
|
Packit |
9f0df5 |
free(s->prev);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
l->head_sentinel->next = l->tail_sentinel;
|
|
Packit |
9f0df5 |
l->tail_sentinel->prev = l->head_sentinel;
|
|
Packit |
9f0df5 |
} else { /* only free element containers */
|
|
Packit |
9f0df5 |
/* spare a loop conditional with two loops: spareing elems and freeing elems */
|
|
Packit |
9f0df5 |
for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
|
|
Packit |
9f0df5 |
/* move elements as spares as long as there is room */
|
|
Packit |
9f0df5 |
l->spareels[l->spareelsnum++] = s;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
while (s != l->tail_sentinel) {
|
|
Packit |
9f0df5 |
/* free the remaining elems */
|
|
Packit |
9f0df5 |
s = s->next;
|
|
Packit |
9f0df5 |
free(s->prev);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
l->head_sentinel->next = l->tail_sentinel;
|
|
Packit |
9f0df5 |
l->tail_sentinel->prev = l->head_sentinel;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
l->numels = 0;
|
|
Packit |
9f0df5 |
l->mid = NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return numels;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
unsigned int list_size(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
return l->numels;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_empty(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
return (l->numels == 0);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_locate(const list_t *restrict l, const void *data) {
|
|
Packit |
9f0df5 |
struct list_entry_s *el;
|
|
Packit |
9f0df5 |
int pos = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.comparator != NULL) {
|
|
Packit |
9f0df5 |
/* use comparator */
|
|
Packit |
9f0df5 |
for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
|
|
Packit |
9f0df5 |
if (l->attrs.comparator(data, el->data) == 0) break;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* compare references */
|
|
Packit |
9f0df5 |
for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
|
|
Packit |
9f0df5 |
if (el->data == data) break;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
if (el == l->tail_sentinel) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return pos;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_seek(list_t *restrict l, const void *indicator) {
|
|
Packit |
9f0df5 |
const struct list_entry_s *iter;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.seeker == NULL) return NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
|
|
Packit |
9f0df5 |
if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return NULL;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_contains(const list_t *restrict l, const void *data) {
|
|
Packit |
9f0df5 |
return (list_locate(l, data) >= 0);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_concat(const list_t *l1, const list_t *l2, list_t *restrict dest) {
|
|
Packit |
9f0df5 |
struct list_entry_s *el, *srcel;
|
|
Packit |
9f0df5 |
unsigned int cnt;
|
|
Packit |
9f0df5 |
int err;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_init(dest);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
dest->numels = l1->numels + l2->numels;
|
|
Packit |
9f0df5 |
if (dest->numels == 0)
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* copy list1 */
|
|
Packit |
9f0df5 |
srcel = l1->head_sentinel->next;
|
|
Packit |
9f0df5 |
el = dest->head_sentinel;
|
|
Packit |
9f0df5 |
while (srcel != l1->tail_sentinel) {
|
|
Packit |
9f0df5 |
el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
|
|
Packit |
9f0df5 |
el->next->prev = el;
|
|
Packit |
9f0df5 |
el = el->next;
|
|
Packit |
9f0df5 |
el->data = srcel->data;
|
|
Packit |
9f0df5 |
srcel = srcel->next;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
dest->mid = el; /* approximate position (adjust later) */
|
|
Packit |
9f0df5 |
/* copy list 2 */
|
|
Packit |
9f0df5 |
srcel = l2->head_sentinel->next;
|
|
Packit |
9f0df5 |
while (srcel != l2->tail_sentinel) {
|
|
Packit |
9f0df5 |
el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s));
|
|
Packit |
9f0df5 |
el->next->prev = el;
|
|
Packit |
9f0df5 |
el = el->next;
|
|
Packit |
9f0df5 |
el->data = srcel->data;
|
|
Packit |
9f0df5 |
srcel = srcel->next;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
el->next = dest->tail_sentinel;
|
|
Packit |
9f0df5 |
dest->tail_sentinel->prev = el;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* fix mid pointer */
|
|
Packit |
9f0df5 |
err = l2->numels - l1->numels;
|
|
Packit |
9f0df5 |
if ((err+1)/2 > 0) { /* correct pos RIGHT (err-1)/2 moves */
|
|
Packit |
9f0df5 |
err = (err+1)/2;
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next;
|
|
Packit |
9f0df5 |
} else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */
|
|
Packit |
9f0df5 |
err = -err/2;
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_sort(list_t *restrict l, int versus) {
|
|
Packit |
9f0df5 |
if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->numels <= 1)
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
|
|
Packit |
9f0df5 |
assert(list_repOk(l));
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
struct list_sort_wrappedparams {
|
|
Packit |
9f0df5 |
list_t *restrict l;
|
|
Packit |
9f0df5 |
int versus;
|
|
Packit |
9f0df5 |
unsigned int first, last;
|
|
Packit |
9f0df5 |
struct list_entry_s *fel, *lel;
|
|
Packit |
9f0df5 |
};
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static void *list_sort_quicksort_threadwrapper(void *wrapped_params) {
|
|
Packit |
9f0df5 |
struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params;
|
|
Packit |
9f0df5 |
list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
|
|
Packit |
9f0df5 |
free(wp);
|
|
Packit |
9f0df5 |
pthread_exit(NULL);
|
|
Packit |
9f0df5 |
return NULL;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static inline void list_sort_selectionsort(list_t *restrict l, int versus,
|
|
Packit |
9f0df5 |
unsigned int first, struct list_entry_s *fel,
|
|
Packit |
9f0df5 |
unsigned int last, struct list_entry_s *lel) {
|
|
Packit |
9f0df5 |
struct list_entry_s *cursor, *toswap, *firstunsorted;
|
|
Packit |
9f0df5 |
void *tmpdata;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (last <= first) /* <= 1-element lists are always sorted */
|
|
Packit |
9f0df5 |
return;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
|
|
Packit |
9f0df5 |
/* find min or max in the remainder of the list */
|
|
Packit |
9f0df5 |
for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
|
|
Packit |
9f0df5 |
if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
|
|
Packit |
9f0df5 |
if (toswap != firstunsorted) { /* swap firstunsorted with toswap */
|
|
Packit |
9f0df5 |
tmpdata = firstunsorted->data;
|
|
Packit |
9f0df5 |
firstunsorted->data = toswap->data;
|
|
Packit |
9f0df5 |
toswap->data = tmpdata;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static void list_sort_quicksort(list_t *restrict l, int versus,
|
|
Packit |
9f0df5 |
unsigned int first, struct list_entry_s *fel,
|
|
Packit |
9f0df5 |
unsigned int last, struct list_entry_s *lel) {
|
|
Packit |
9f0df5 |
unsigned int pivotid;
|
|
Packit |
9f0df5 |
unsigned int i;
|
|
Packit |
9f0df5 |
register struct list_entry_s *pivot;
|
|
Packit |
9f0df5 |
struct list_entry_s *left, *right;
|
|
Packit |
9f0df5 |
void *tmpdata;
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
pthread_t tid;
|
|
Packit |
9f0df5 |
int traised;
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (last <= first) /* <= 1-element lists are always sorted */
|
|
Packit |
9f0df5 |
return;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
|
|
Packit |
9f0df5 |
list_sort_selectionsort(l, versus, first, fel, last, lel);
|
|
Packit |
9f0df5 |
return;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* base of iteration: one element list */
|
|
Packit |
9f0df5 |
if (! (last > first)) return;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
pivotid = (get_random() % (last - first + 1));
|
|
Packit |
9f0df5 |
/* pivotid = (last - first + 1) / 2; */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* find pivot */
|
|
Packit |
9f0df5 |
if (pivotid < (last - first + 1)/2) {
|
|
Packit |
9f0df5 |
for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* smaller PIVOT bigger */
|
|
Packit |
9f0df5 |
left = fel;
|
|
Packit |
9f0df5 |
right = lel;
|
|
Packit |
9f0df5 |
/* iterate --- left ---> PIV <--- right --- */
|
|
Packit |
9f0df5 |
while (left != pivot && right != pivot) {
|
|
Packit |
9f0df5 |
for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
|
|
Packit |
9f0df5 |
/* left points to a smaller element, or to pivot */
|
|
Packit |
9f0df5 |
for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
|
|
Packit |
9f0df5 |
/* right points to a bigger element, or to pivot */
|
|
Packit |
9f0df5 |
if (left != pivot && right != pivot) {
|
|
Packit |
9f0df5 |
/* swap, then move iterators */
|
|
Packit |
9f0df5 |
tmpdata = left->data;
|
|
Packit |
9f0df5 |
left->data = right->data;
|
|
Packit |
9f0df5 |
right->data = tmpdata;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
left = left->next;
|
|
Packit |
9f0df5 |
right = right->prev;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* now either left points to pivot (end run), or right */
|
|
Packit |
9f0df5 |
if (right == pivot) { /* left part longer */
|
|
Packit |
9f0df5 |
while (left != pivot) {
|
|
Packit |
9f0df5 |
if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
|
|
Packit |
9f0df5 |
tmpdata = left->data;
|
|
Packit |
9f0df5 |
left->data = pivot->prev->data;
|
|
Packit |
9f0df5 |
pivot->prev->data = pivot->data;
|
|
Packit |
9f0df5 |
pivot->data = tmpdata;
|
|
Packit |
9f0df5 |
pivot = pivot->prev;
|
|
Packit |
9f0df5 |
pivotid--;
|
|
Packit |
9f0df5 |
if (pivot == left) break;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
left = left->next;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else { /* right part longer */
|
|
Packit |
9f0df5 |
while (right != pivot) {
|
|
Packit |
9f0df5 |
if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
|
|
Packit |
9f0df5 |
/* move current right before pivot */
|
|
Packit |
9f0df5 |
tmpdata = right->data;
|
|
Packit |
9f0df5 |
right->data = pivot->next->data;
|
|
Packit |
9f0df5 |
pivot->next->data = pivot->data;
|
|
Packit |
9f0df5 |
pivot->data = tmpdata;
|
|
Packit |
9f0df5 |
pivot = pivot->next;
|
|
Packit |
9f0df5 |
pivotid++;
|
|
Packit |
9f0df5 |
if (pivot == right) break;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
right = right->prev;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* sort sublists A and B : |---A---| pivot |---B---| */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_WITH_THREADS
|
|
Packit |
9f0df5 |
traised = 0;
|
|
Packit |
9f0df5 |
if (pivotid > 0) {
|
|
Packit |
9f0df5 |
/* prepare wrapped args, then start thread */
|
|
Packit |
9f0df5 |
if (l->threadcount < SIMCLIST_MAXTHREADS-1) {
|
|
Packit |
9f0df5 |
struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams));
|
|
Packit |
9f0df5 |
l->threadcount++;
|
|
Packit |
9f0df5 |
traised = 1;
|
|
Packit |
9f0df5 |
wp->l = l;
|
|
Packit |
9f0df5 |
wp->versus = versus;
|
|
Packit |
9f0df5 |
wp->first = first;
|
|
Packit |
9f0df5 |
wp->fel = fel;
|
|
Packit |
9f0df5 |
wp->last = first+pivotid-1;
|
|
Packit |
9f0df5 |
wp->lel = pivot->prev;
|
|
Packit |
9f0df5 |
if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
|
|
Packit |
9f0df5 |
free(wp);
|
|
Packit |
9f0df5 |
traised = 0;
|
|
Packit |
9f0df5 |
list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
|
|
Packit |
9f0df5 |
if (traised) {
|
|
Packit |
9f0df5 |
pthread_join(tid, (void **)NULL);
|
|
Packit |
9f0df5 |
l->threadcount--;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
#else
|
|
Packit |
9f0df5 |
if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
|
|
Packit |
9f0df5 |
if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_iterator_start(list_t *restrict l) {
|
|
Packit |
9f0df5 |
if (l->iter_active) return 0;
|
|
Packit |
9f0df5 |
l->iter_pos = 0;
|
|
Packit |
9f0df5 |
l->iter_active = 1;
|
|
Packit |
9f0df5 |
l->iter_curentry = l->head_sentinel->next;
|
|
Packit |
9f0df5 |
return 1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
void *list_iterator_next(list_t *restrict l) {
|
|
Packit |
9f0df5 |
void *toret;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (! l->iter_active) return NULL;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
toret = l->iter_curentry->data;
|
|
Packit |
9f0df5 |
l->iter_curentry = l->iter_curentry->next;
|
|
Packit |
9f0df5 |
l->iter_pos++;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return toret;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_iterator_hasnext(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
if (! l->iter_active) return 0;
|
|
Packit |
9f0df5 |
return (l->iter_pos < l->numels);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_iterator_stop(list_t *restrict l) {
|
|
Packit |
9f0df5 |
if (! l->iter_active) return 0;
|
|
Packit |
9f0df5 |
l->iter_pos = 0;
|
|
Packit |
9f0df5 |
l->iter_active = 0;
|
|
Packit |
9f0df5 |
return 1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_hash(const list_t *restrict l, list_hash_t *restrict hash) {
|
|
Packit |
9f0df5 |
struct list_entry_s *x;
|
|
Packit |
9f0df5 |
list_hash_t tmphash;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
assert(hash != NULL);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmphash = l->numels * 2 + 100;
|
|
Packit |
9f0df5 |
if (l->attrs.hasher == NULL) {
|
|
Packit |
9f0df5 |
#ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES
|
|
Packit |
9f0df5 |
/* ENABLE WITH CARE !! */
|
|
Packit |
9f0df5 |
#warning "Memlocation-based hash is consistent only for testing modification in the same program run."
|
|
Packit |
9f0df5 |
int i;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* only use element references */
|
|
Packit |
9f0df5 |
for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
|
|
Packit |
9f0df5 |
for (i = 0; i < sizeof(x->data); i++) {
|
|
Packit |
9f0df5 |
tmphash += (tmphash ^ (uintptr_t)x->data);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
tmphash += tmphash % l->numels;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
#else
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* hash each element with the user-given function */
|
|
Packit |
9f0df5 |
for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
|
|
Packit |
9f0df5 |
tmphash += tmphash ^ l->attrs.hasher(x->data);
|
|
Packit |
9f0df5 |
tmphash += tmphash % l->numels;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
*hash = tmphash;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifndef SIMCLIST_NO_DUMPRESTORE
|
|
Packit |
9f0df5 |
int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *restrict info) {
|
|
Packit |
9f0df5 |
int32_t terminator_head, terminator_tail;
|
|
Packit |
9f0df5 |
uint32_t elemlen;
|
|
Packit |
9f0df5 |
off_t hop;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* version */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->version, sizeof(info->version));
|
|
Packit |
9f0df5 |
info->version = ntohs(info->version);
|
|
Packit |
9f0df5 |
if (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
|
|
Packit |
9f0df5 |
errno = EILSEQ;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* timestamp.tv_sec and timestamp.tv_usec */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->timestamp.tv_sec, sizeof(info->timestamp.tv_sec));
|
|
Packit |
9f0df5 |
info->timestamp.tv_sec = ntohl(info->timestamp.tv_sec);
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->timestamp.tv_usec, sizeof(info->timestamp.tv_usec));
|
|
Packit |
9f0df5 |
info->timestamp.tv_usec = ntohl(info->timestamp.tv_usec);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list terminator (to check thereafter) */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head));
|
|
Packit |
9f0df5 |
terminator_head = ntohl(terminator_head);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list size */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size));
|
|
Packit |
9f0df5 |
info->list_size = ntohl(info->list_size);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* number of elements */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels));
|
|
Packit |
9f0df5 |
info->list_numels = ntohl(info->list_numels);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* length of each element (for checking for consistency) */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & elemlen, sizeof(elemlen));
|
|
Packit |
9f0df5 |
elemlen = ntohl(elemlen);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list hash */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash));
|
|
Packit |
9f0df5 |
info->list_hash = ntohl(info->list_hash);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* check consistency */
|
|
Packit |
9f0df5 |
if (elemlen > 0) {
|
|
Packit |
9f0df5 |
/* constant length, hop by size only */
|
|
Packit |
9f0df5 |
hop = info->list_size;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* non-constant length, hop by size + all element length blocks */
|
|
Packit |
9f0df5 |
hop = info->list_size + elemlen*info->list_numels;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
if (lseek(fd, hop, SEEK_CUR) == -1) {
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* read the trailing value and compare with terminator_head */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail));
|
|
Packit |
9f0df5 |
terminator_tail = ntohl(terminator_tail);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (terminator_head == terminator_tail)
|
|
Packit |
9f0df5 |
info->consistent = 1;
|
|
Packit |
9f0df5 |
else
|
|
Packit |
9f0df5 |
info->consistent = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_dump_getinfo_file(const char *restrict filename, list_dump_info_t *restrict info) {
|
|
Packit |
9f0df5 |
int fd, ret;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
fd = open(filename, O_RDONLY, 0);
|
|
Packit |
9f0df5 |
if (fd < 0) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
ret = list_dump_getinfo_filedescriptor(fd, info);
|
|
Packit |
9f0df5 |
close(fd);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return ret;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_dump_filedescriptor(const list_t *restrict l, int fd, size_t *restrict len) {
|
|
Packit |
9f0df5 |
struct list_entry_s *x;
|
|
Packit |
9f0df5 |
void *ser_buf;
|
|
Packit |
9f0df5 |
uint32_t bufsize;
|
|
Packit |
9f0df5 |
struct timeval timeofday;
|
|
Packit |
9f0df5 |
struct list_dump_header_s header;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
|
|
Packit |
9f0df5 |
errno = ENOTTY;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/**** DUMP FORMAT ****
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
[ ver timestamp | totlen numels elemlen hash | DATA ]
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
where DATA can be:
|
|
Packit |
9f0df5 |
@ for constant-size list (element size is constant; elemlen > 0)
|
|
Packit |
9f0df5 |
[ elem elem ... elem ]
|
|
Packit |
9f0df5 |
@ for other lists (element size dictated by element_meter each time; elemlen <= 0)
|
|
Packit |
9f0df5 |
[ size elem size elem ... size elem ]
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
all integers are encoded in NETWORK BYTE FORMAT
|
|
Packit |
9f0df5 |
*****/
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* prepare HEADER */
|
|
Packit |
9f0df5 |
/* version */
|
|
Packit |
9f0df5 |
header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* timestamp */
|
|
Packit |
9f0df5 |
gettimeofday(&timeofday, NULL);
|
|
Packit |
9f0df5 |
header.timestamp_sec = htonl(timeofday.tv_sec);
|
|
Packit |
9f0df5 |
header.timestamp_usec = htonl(timeofday.tv_usec);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
header.rndterm = htonl((int32_t)get_random());
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* total list size is postprocessed afterwards */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* number of elements */
|
|
Packit |
9f0df5 |
header.numels = htonl(l->numels);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* include an hash, if possible */
|
|
Packit |
9f0df5 |
if (l->attrs.hasher != NULL) {
|
|
Packit |
9f0df5 |
if (htonl(list_hash(l, & header.listhash)) != 0) {
|
|
Packit |
9f0df5 |
/* could not compute list hash! */
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
header.listhash = htonl(0);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
header.totlistlen = header.elemlen = 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* leave room for the header at the beginning of the file */
|
|
Packit |
9f0df5 |
if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
|
|
Packit |
9f0df5 |
/* errno set by lseek() */
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* write CONTENT */
|
|
Packit |
9f0df5 |
if (l->numels > 0) {
|
|
Packit |
9f0df5 |
/* SPECULATE that the list has constant element size */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->attrs.serializer != NULL) { /* user user-specified serializer */
|
|
Packit |
9f0df5 |
/* get preliminary length of serialized element in header.elemlen */
|
|
Packit |
9f0df5 |
ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
|
|
Packit |
9f0df5 |
free(ser_buf);
|
|
Packit |
9f0df5 |
/* request custom serialization of each element */
|
|
Packit |
9f0df5 |
for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
|
|
Packit |
9f0df5 |
ser_buf = l->attrs.serializer(x->data, &bufsize);
|
|
Packit |
9f0df5 |
header.totlistlen += bufsize;
|
|
Packit |
9f0df5 |
if (header.elemlen != 0) { /* continue on speculation */
|
|
Packit |
9f0df5 |
if (header.elemlen != bufsize) {
|
|
Packit |
9f0df5 |
free(ser_buf);
|
|
Packit |
9f0df5 |
/* constant element length speculation broken! */
|
|
Packit |
9f0df5 |
header.elemlen = 0;
|
|
Packit |
9f0df5 |
header.totlistlen = 0;
|
|
Packit |
9f0df5 |
x = l->head_sentinel;
|
|
Packit |
9f0df5 |
if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
|
|
Packit |
9f0df5 |
/* errno set by lseek() */
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
/* restart from the beginning */
|
|
Packit |
9f0df5 |
continue;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
/* speculation confirmed */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, ser_buf, bufsize);
|
|
Packit |
9f0df5 |
} else { /* speculation found broken */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t));
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, ser_buf, bufsize);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
free(ser_buf);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else if (l->attrs.meter != NULL) {
|
|
Packit |
9f0df5 |
header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* serialize the element straight from its data */
|
|
Packit |
9f0df5 |
for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
|
|
Packit |
9f0df5 |
bufsize = l->attrs.meter(x->data);
|
|
Packit |
9f0df5 |
header.totlistlen += bufsize;
|
|
Packit |
9f0df5 |
if (header.elemlen != 0) {
|
|
Packit |
9f0df5 |
if (header.elemlen != bufsize) {
|
|
Packit |
9f0df5 |
/* constant element length speculation broken! */
|
|
Packit |
9f0df5 |
header.elemlen = 0;
|
|
Packit |
9f0df5 |
header.totlistlen = 0;
|
|
Packit |
9f0df5 |
x = l->head_sentinel;
|
|
Packit |
9f0df5 |
/* restart from the beginning */
|
|
Packit |
9f0df5 |
continue;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, x->data, bufsize);
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t));
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, x->data, bufsize);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
/* adjust endianness */
|
|
Packit |
9f0df5 |
header.elemlen = htonl(header.elemlen);
|
|
Packit |
9f0df5 |
header.totlistlen = htonl(header.totlistlen);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* write random terminator */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* list terminator */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* write header */
|
|
Packit |
9f0df5 |
lseek(fd, 0, SEEK_SET);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver)); /* version */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec)); /* timestamp seconds */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec)); /* timestamp microseconds */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* random terminator */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); /* total length of elements */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels)); /* number of elements */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); /* size of each element, or 0 for independent */
|
|
Packit |
9f0df5 |
WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); /* list hash, or 0 for "ignore" */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* possibly store total written length in "len" */
|
|
Packit |
9f0df5 |
if (len != NULL) {
|
|
Packit |
9f0df5 |
*len = sizeof(header) + ntohl(header.totlistlen);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_restore_filedescriptor(list_t *restrict l, int fd, size_t *restrict len) {
|
|
Packit |
9f0df5 |
struct list_dump_header_s header;
|
|
Packit |
9f0df5 |
unsigned long cnt;
|
|
Packit |
9f0df5 |
void *buf;
|
|
Packit |
9f0df5 |
uint32_t elsize, totreadlen, totmemorylen;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
memset(& header, 0, sizeof(header));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* read header */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* version */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, &header.ver, sizeof(header.ver));
|
|
Packit |
9f0df5 |
header.ver = ntohs(header.ver);
|
|
Packit |
9f0df5 |
if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
|
|
Packit |
9f0df5 |
errno = EILSEQ;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* timestamp */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec));
|
|
Packit |
9f0df5 |
header.timestamp_sec = ntohl(header.timestamp_sec);
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec));
|
|
Packit |
9f0df5 |
header.timestamp_usec = ntohl(header.timestamp_usec);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list terminator */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm));
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
header.rndterm = ntohl(header.rndterm);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* total list size */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen));
|
|
Packit |
9f0df5 |
header.totlistlen = ntohl(header.totlistlen);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* number of elements */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.numels, sizeof(header.numels));
|
|
Packit |
9f0df5 |
header.numels = ntohl(header.numels);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* length of every element, or '0' = variable */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen));
|
|
Packit |
9f0df5 |
header.elemlen = ntohl(header.elemlen);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* list hash, or 0 = 'ignore' */
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash));
|
|
Packit |
9f0df5 |
header.listhash = ntohl(header.listhash);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* read content */
|
|
Packit |
9f0df5 |
totreadlen = totmemorylen = 0;
|
|
Packit |
9f0df5 |
if (header.elemlen > 0) {
|
|
Packit |
9f0df5 |
/* elements have constant size = header.elemlen */
|
|
Packit |
9f0df5 |
if (l->attrs.unserializer != NULL) {
|
|
Packit |
9f0df5 |
/* use unserializer */
|
|
Packit |
9f0df5 |
buf = malloc(header.elemlen);
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < header.numels; cnt++) {
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, buf, header.elemlen);
|
|
Packit |
9f0df5 |
list_append(l, l->attrs.unserializer(buf, & elsize));
|
|
Packit |
9f0df5 |
totmemorylen += elsize;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* copy verbatim into memory */
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < header.numels; cnt++) {
|
|
Packit |
9f0df5 |
buf = malloc(header.elemlen);
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, buf, header.elemlen);
|
|
Packit |
9f0df5 |
list_append(l, buf);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
totmemorylen = header.numels * header.elemlen;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
totreadlen = header.numels * header.elemlen;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* elements have variable size. Each element is preceded by its size */
|
|
Packit |
9f0df5 |
if (l->attrs.unserializer != NULL) {
|
|
Packit |
9f0df5 |
/* use unserializer */
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < header.numels; cnt++) {
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & elsize, sizeof(elsize));
|
|
Packit |
9f0df5 |
buf = malloc((size_t)elsize);
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, buf, elsize);
|
|
Packit |
9f0df5 |
totreadlen += elsize;
|
|
Packit |
9f0df5 |
list_append(l, l->attrs.unserializer(buf, & elsize));
|
|
Packit |
9f0df5 |
totmemorylen += elsize;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
/* copy verbatim into memory */
|
|
Packit |
9f0df5 |
for (cnt = 0; cnt < header.numels; cnt++) {
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, & elsize, sizeof(elsize));
|
|
Packit |
9f0df5 |
buf = malloc(elsize);
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, buf, elsize);
|
|
Packit |
9f0df5 |
totreadlen += elsize;
|
|
Packit |
9f0df5 |
list_append(l, buf);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
totmemorylen = totreadlen;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
READ_ERRCHECK(fd, &elsize, sizeof(elsize)); /* read list terminator */
|
|
Packit |
9f0df5 |
elsize = ntohl(elsize);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* possibly verify the list consistency */
|
|
Packit |
9f0df5 |
/* wrt hash */
|
|
Packit |
9f0df5 |
/* don't do that
|
|
Packit |
9f0df5 |
if (header.listhash != 0 && header.listhash != list_hash(l)) {
|
|
Packit |
9f0df5 |
errno = ECANCELED;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
*/
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* wrt header */
|
|
Packit |
9f0df5 |
if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
|
|
Packit |
9f0df5 |
errno = EPROTO;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* wrt file */
|
|
Packit |
9f0df5 |
if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
|
|
Packit |
9f0df5 |
errno = EPROTO;
|
|
Packit |
9f0df5 |
return -1;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (len != NULL) {
|
|
Packit |
9f0df5 |
*len = totmemorylen;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_dump_file(const list_t *restrict l, const char *restrict filename, size_t *restrict len) {
|
|
Packit |
9f0df5 |
int fd, oflag, mode;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifndef _WIN32
|
|
Packit |
9f0df5 |
oflag = O_RDWR | O_CREAT | O_TRUNC;
|
|
Packit |
9f0df5 |
mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;
|
|
Packit |
9f0df5 |
#else
|
|
Packit |
9f0df5 |
oflag = _O_RDWR | _O_CREAT | _O_TRUNC;
|
|
Packit |
9f0df5 |
mode = _S_IRUSR | _S_IWUSR | _S_IRGRP | _S_IROTH;
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
fd = open(filename, oflag, mode);
|
|
Packit |
9f0df5 |
if (fd < 0) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_dump_filedescriptor(l, fd, len);
|
|
Packit |
9f0df5 |
close(fd);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_restore_file(list_t *restrict l, const char *restrict filename, size_t *restrict len) {
|
|
Packit |
9f0df5 |
int fd;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
fd = open(filename, O_RDONLY, 0);
|
|
Packit |
9f0df5 |
if (fd < 0) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_restore_filedescriptor(l, fd, len);
|
|
Packit |
9f0df5 |
close(fd);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
#endif /* ifndef SIMCLIST_NO_DUMPRESTORE */
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos) {
|
|
Packit |
9f0df5 |
if (tmp == NULL) return -1;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* fix mid pointer. This is wrt the PRE situation */
|
|
Packit |
9f0df5 |
if (l->numels % 2) { /* now odd */
|
|
Packit |
9f0df5 |
/* sort out the base case by hand */
|
|
Packit |
9f0df5 |
if (l->numels == 1) l->mid = NULL;
|
|
Packit |
9f0df5 |
else if (pos >= l->numels/2) l->mid = l->mid->prev;
|
|
Packit |
9f0df5 |
} else { /* now even */
|
|
Packit |
9f0df5 |
if (pos < l->numels/2) l->mid = l->mid->next;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
tmp->prev->next = tmp->next;
|
|
Packit |
9f0df5 |
tmp->next->prev = tmp->prev;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* free what's to be freed */
|
|
Packit |
9f0df5 |
if (l->attrs.copy_data && tmp->data != NULL)
|
|
Packit |
9f0df5 |
free(tmp->data);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
|
|
Packit |
9f0df5 |
l->spareels[l->spareelsnum++] = tmp;
|
|
Packit |
9f0df5 |
} else {
|
|
Packit |
9f0df5 |
free(tmp);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return 0;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* ready-made comparators and meters */
|
|
Packit |
9f0df5 |
#define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); }
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(int8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(int16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(int32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(int64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(uint8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(uint16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(uint32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(uint64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(float)
|
|
Packit |
9f0df5 |
SIMCLIST_NUMBER_COMPARATOR(double)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); }
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* ready-made metric functions */
|
|
Packit |
9f0df5 |
#define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); }
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_METER(int8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(int16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(int32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(int64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_METER(uint8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(uint16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(uint32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(uint64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_METER(float)
|
|
Packit |
9f0df5 |
SIMCLIST_METER(double)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; }
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
/* ready-made hashing functions */
|
|
Packit |
9f0df5 |
#define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); }
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(int8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(int16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(int32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(int64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(uint8_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(uint16_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(uint32_t)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(uint64_t)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(float)
|
|
Packit |
9f0df5 |
SIMCLIST_HASHCOMPUTER(double)
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
list_hash_t list_hashcomputer_string(const void *el) {
|
|
Packit |
9f0df5 |
size_t l;
|
|
Packit |
9f0df5 |
list_hash_t hash = 123;
|
|
Packit |
9f0df5 |
const char *str = (const char *)el;
|
|
Packit |
9f0df5 |
char plus;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
for (l = 0; str[l] != '\0'; l++) {
|
|
Packit |
9f0df5 |
if (l) plus = hash ^ str[l];
|
|
Packit |
9f0df5 |
else plus = hash ^ (str[l] - str[0]);
|
|
Packit |
9f0df5 |
hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t))));
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return hash;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#ifndef NDEBUG
|
|
Packit |
9f0df5 |
static int list_repOk(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
int ok, i;
|
|
Packit |
9f0df5 |
struct list_entry_s *s;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
ok = (l != NULL) && (
|
|
Packit |
9f0df5 |
/* head/tail checks */
|
|
Packit |
9f0df5 |
(l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
|
|
Packit |
9f0df5 |
(l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
|
|
Packit |
9f0df5 |
/* empty list */
|
|
Packit |
9f0df5 |
(l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
|
|
Packit |
9f0df5 |
/* spare elements checks */
|
|
Packit |
9f0df5 |
l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
|
|
Packit |
9f0df5 |
);
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (!ok) return 0;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
if (l->numels >= 1) {
|
|
Packit |
9f0df5 |
/* correct referencing */
|
|
Packit |
9f0df5 |
for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
|
|
Packit |
9f0df5 |
if (s->next->prev != s) break;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
ok = (i == (int)(l->numels-1)/2 && l->mid == s);
|
|
Packit |
9f0df5 |
if (!ok) return 0;
|
|
Packit |
9f0df5 |
for (; s->next != NULL; i++, s = s->next) {
|
|
Packit |
9f0df5 |
if (s->next->prev != s) break;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
ok = (i == (int)l->numels && s == l->tail_sentinel);
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
return ok;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
static int list_attrOk(const list_t *restrict l) {
|
|
Packit |
9f0df5 |
int ok;
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);
|
|
Packit |
9f0df5 |
return ok;
|
|
Packit |
9f0df5 |
}
|
|
Packit |
9f0df5 |
|
|
Packit |
9f0df5 |
#endif
|
|
Packit |
9f0df5 |
|