27 #include <sys/types.h> 33 #ifndef SIMCLIST_NO_DUMPRESTORE 39 # include <arpa/inet.h> 41 # include <winsock2.h> 46 #ifndef SIMCLIST_DEBUG 56 #if defined(_MSC_VER) || defined(__MINGW32__) 58 int gettimeofday(
struct timeval *tp,
void *tzp) {
65 tp->tv_sec = t / 1000;
66 tp->tv_usec = t % 1000;
73 #if !defined(_WIN32) || !defined(_MSC_VER) 74 # include <inttypes.h> 77 typedef UINT8 uint8_t;
78 typedef UINT16 uint16_t;
79 typedef ULONG32 uint32_t;
80 typedef UINT64 uint64_t;
82 typedef INT16 int16_t;
83 typedef LONG32 int32_t;
84 typedef INT64 int64_t;
89 #ifndef SIMCLIST_NO_DUMPRESTORE 91 #define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \ 92 if (write(fd, msgbuf, msglen) < 0) return -1; \ 95 #define READ_ERRCHECK(fd, msgbuf, msglen) do { \ 96 if (read(fd, msgbuf, msglen) != msglen) { \ 107 ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \ 108 (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \ 109 (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \ 110 (((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \ 111 (((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \ 112 (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \ 113 (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \ 114 (((uint64_t)(x) & 0x00000000000000ffULL) << 56))) \ 118 #define ntoh64(x) (hton64(x)) 126 #ifdef SIMCLIST_WITH_THREADS 130 #define SIMCLIST_MAXTHREADS 2 157 #ifndef SIMCLIST_MAX_SPARE_ELEMS 158 #define SIMCLIST_MAX_SPARE_ELEMS 5 162 #ifdef SIMCLIST_WITH_THREADS 166 #include "simclist.h" 170 #define SIMCLIST_MINQUICKSORTELS 24 174 #define SIMCLIST_DUMPFORMAT_VERSION 1 176 #define SIMCLIST_DUMPFORMAT_HEADERLEN 30 181 int32_t timestamp_sec;
182 int32_t timestamp_usec;
194 static int list_drop_elem(
list_t *restrict l,
struct list_entry_s *tmp,
unsigned int pos);
197 static int list_attributes_setdefaults(
list_t *restrict l);
201 static int list_repOk(
const list_t *restrict l);
204 static int list_attrOk(
const list_t *restrict l);
208 static void list_sort_quicksort(
list_t *restrict l,
int versus,
212 static inline void list_sort_selectionsort(
list_t *restrict l,
int versus,
216 static void *list_get_minmax(
const list_t *restrict l,
int versus);
218 static inline struct list_entry_s *list_findpos(
const list_t *restrict l,
int posstart);
241 #ifdef SIMCLIST_SYSTEM_RNG 243 static unsigned random_seed = 0;
246 static inline void seed_random(
void) {
247 if (random_seed == 0)
248 random_seed = (unsigned)getpid() ^ (unsigned)time(NULL);
251 static inline long get_random(
void) {
252 random_seed = (1664525 * random_seed + 1013904223);
258 # define seed_random() 259 # define get_random() (rand()) 264 int list_init(
list_t *restrict l) {
265 if (l == NULL)
return -1;
267 memset(l, 0,
sizeof *l);
276 if (NULL == l->tail_sentinel || NULL == l->head_sentinel)
279 l->head_sentinel->next = l->tail_sentinel;
280 l->tail_sentinel->prev = l->head_sentinel;
281 l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL;
282 l->head_sentinel->data = l->tail_sentinel->data = NULL;
287 l->iter_curentry = NULL;
292 if (NULL == l->spareels)
295 #ifdef SIMCLIST_WITH_THREADS 299 if (list_attributes_setdefaults(l))
302 assert(list_repOk(l));
303 assert(list_attrOk(l));
308 void list_destroy(
list_t *restrict l) {
312 for (i = 0; i < l->spareelsnum; i++) {
313 free(l->spareels[i]);
316 free(l->head_sentinel);
317 free(l->tail_sentinel);
320 int list_attributes_setdefaults(
list_t *restrict l) {
321 l->attrs.comparator = NULL;
322 l->attrs.seeker = NULL;
325 l->attrs.meter = NULL;
326 l->attrs.copy_data = 0;
328 l->attrs.hasher = NULL;
331 l->attrs.serializer = NULL;
332 l->attrs.unserializer = NULL;
334 assert(list_attrOk(l));
340 int list_attributes_comparator(
list_t *restrict l, element_comparator comparator_fun) {
341 if (l == NULL)
return -1;
343 l->attrs.comparator = comparator_fun;
345 assert(list_attrOk(l));
350 int list_attributes_seeker(
list_t *restrict l, element_seeker seeker_fun) {
351 if (l == NULL)
return -1;
353 l->attrs.seeker = seeker_fun;
354 assert(list_attrOk(l));
359 int list_attributes_copy(
list_t *restrict l, element_meter metric_fun,
int copy_data) {
360 if (l == NULL || (metric_fun == NULL && copy_data != 0))
return -1;
362 l->attrs.meter = metric_fun;
363 l->attrs.copy_data = copy_data;
365 assert(list_attrOk(l));
370 int list_attributes_hash_computer(
list_t *restrict l, element_hash_computer hash_computer_fun) {
371 if (l == NULL)
return -1;
373 l->attrs.hasher = hash_computer_fun;
374 assert(list_attrOk(l));
378 int list_attributes_serializer(
list_t *restrict l, element_serializer serializer_fun) {
379 if (l == NULL)
return -1;
381 l->attrs.serializer = serializer_fun;
382 assert(list_attrOk(l));
386 int list_attributes_unserializer(
list_t *restrict l, element_unserializer unserializer_fun) {
387 if (l == NULL)
return -1;
389 l->attrs.unserializer = unserializer_fun;
390 assert(list_attrOk(l));
394 int list_append(
list_t *restrict l,
const void *data) {
395 return list_insert_at(l, data, l->numels);
398 int list_prepend(
list_t *restrict l,
const void *data) {
399 return list_insert_at(l, data, 0);
402 void *list_fetch(
list_t *restrict l) {
403 return list_extract_at(l, 0);
406 void *list_get_at(
const list_t *restrict l,
unsigned int pos) {
409 tmp = list_findpos(l, pos);
411 return (tmp != NULL ? tmp->data : NULL);
414 void *list_get_max(
const list_t *restrict l) {
415 return list_get_minmax(l, +1);
418 void *list_get_min(
const list_t *restrict l) {
419 return list_get_minmax(l, -1);
424 static void *list_get_minmax(
const list_t *restrict l,
int versus) {
428 if (l->attrs.comparator == NULL || l->numels == 0)
431 curminmax = l->head_sentinel->next->data;
432 for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) {
433 if (l->attrs.comparator(curminmax, s->data) * versus > 0)
441 static inline struct list_entry_s *list_findpos(
const list_t *restrict l,
int posstart) {
446 if (NULL == l->head_sentinel || NULL == l->tail_sentinel)
450 if (posstart < -1 || posstart > (
int)l->numels)
return NULL;
453 x = (float)(posstart+1) / l->numels;
458 for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++);
459 }
else if (x < 0.5) {
461 for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--);
462 }
else if (x <= 0.75) {
464 for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++);
467 for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--);
473 void *list_extract_at(
list_t *restrict l,
unsigned int pos) {
477 if (l->iter_active || pos >= l->numels)
return NULL;
479 tmp = list_findpos(l, pos);
486 list_drop_elem(l, tmp, pos);
489 assert(list_repOk(l));
494 int list_insert_at(
list_t *restrict l,
const void *data,
unsigned int pos) {
497 if (l->iter_active || pos > l->numels)
return -1;
500 if (l->spareelsnum > 0) {
501 lent = l->spareels[l->spareelsnum-1];
509 if (l->attrs.copy_data) {
511 size_t datalen = l->attrs.meter(data);
513 if (NULL == lent->data)
518 memcpy(lent->data, data, datalen);
520 lent->data = (
void*)data;
524 prec = list_findpos(l, pos-1);
541 if (l->numels == 1) {
543 }
else if (l->numels % 2) {
544 if (pos >= (l->numels-1)/2) l->mid = l->mid->next;
546 if (pos <= (l->numels-1)/2) l->mid = l->mid->prev;
549 assert(list_repOk(l));
554 int list_delete(
list_t *restrict l,
const void *data) {
557 pos = list_locate(l, data);
561 r = list_delete_at(l, pos);
565 assert(list_repOk(l));
570 int list_delete_at(
list_t *restrict l,
unsigned int pos) {
574 if (l->iter_active || pos >= l->numels)
return -1;
576 delendo = list_findpos(l, pos);
578 list_drop_elem(l, delendo, pos);
583 assert(list_repOk(l));
588 int list_delete_range(
list_t *restrict l,
unsigned int posstart,
unsigned int posend) {
590 unsigned int numdel, midposafter, i;
593 if (l->iter_active || posend < posstart || posend >= l->numels)
return -1;
595 numdel = posend - posstart + 1;
596 if (numdel == l->numels)
return list_clear(l);
598 tmp = list_findpos(l, posstart);
599 lastvalid = tmp->prev;
601 midposafter = (l->numels-1-numdel)/2;
603 midposafter = midposafter < posstart ? midposafter : midposafter+numdel;
604 movedx = midposafter - (l->numels-1)/2;
607 for (i = 0; i < (
unsigned int)movedx; l->mid = l->mid->next, i++);
610 for (i = 0; i < (
unsigned int)movedx; l->mid = l->mid->prev, i++);
613 assert(posstart == 0 || lastvalid != l->head_sentinel);
615 if (l->attrs.copy_data) {
617 for (; i <= posend; i++) {
620 if (tmp2->data != NULL) free(tmp2->data);
621 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
622 l->spareels[l->spareelsnum++] = tmp2;
629 for (; i <= posend; i++) {
632 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
633 l->spareels[l->spareelsnum++] = tmp2;
639 assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel));
641 lastvalid->next = tmp;
642 tmp->prev = lastvalid;
644 l->numels -= posend - posstart + 1;
646 assert(list_repOk(l));
651 int list_clear(
list_t *restrict l) {
658 if (l->iter_active)
return -1;
660 if (l->head_sentinel && l->tail_sentinel) {
661 if (l->attrs.copy_data) {
663 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
665 if (s->data != NULL) free(s->data);
666 l->spareels[l->spareelsnum++] = s;
668 while (s != l->tail_sentinel) {
670 if (s->data != NULL) free(s->data);
674 l->head_sentinel->next = l->tail_sentinel;
675 l->tail_sentinel->prev = l->head_sentinel;
678 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) {
680 l->spareels[l->spareelsnum++] = s;
682 while (s != l->tail_sentinel) {
687 l->head_sentinel->next = l->tail_sentinel;
688 l->tail_sentinel->prev = l->head_sentinel;
694 assert(list_repOk(l));
699 unsigned int list_size(
const list_t *restrict l) {
703 int list_empty(
const list_t *restrict l) {
704 return (l->numels == 0);
707 int list_locate(
const list_t *restrict l,
const void *data) {
711 if (NULL == l->head_sentinel || NULL == l->tail_sentinel)
714 if (l->attrs.comparator != NULL) {
716 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
717 if (l->attrs.comparator(data, el->data) == 0)
break;
721 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) {
722 if (el->data == data)
break;
725 if (el == l->tail_sentinel)
return -1;
730 void *list_seek(
list_t *restrict l,
const void *indicator) {
733 if (l->attrs.seeker == NULL)
return NULL;
735 if (NULL == l->head_sentinel || NULL == l->tail_sentinel)
738 for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) {
739 if (l->attrs.seeker(iter->data, indicator) != 0)
return iter->data;
745 int list_contains(
const list_t *restrict l,
const void *data) {
746 return (list_locate(l, data) >= 0);
755 if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest)
758 if (NULL == l1->head_sentinel || NULL == l1->tail_sentinel
759 || NULL == l2->head_sentinel || NULL == l2->tail_sentinel)
765 dest->numels = l1->numels + l2->numels;
766 if (dest->numels == 0)
770 srcel = l1->head_sentinel->next;
771 el = dest->head_sentinel;
772 while (srcel != l1->tail_sentinel) {
774 if (NULL == el->next)
778 el->data = srcel->data;
783 srcel = l2->head_sentinel->next;
784 while (srcel != l2->tail_sentinel) {
786 if (NULL == el->next)
790 el->data = srcel->data;
793 el->next = dest->tail_sentinel;
794 dest->tail_sentinel->prev = el;
797 err = l2->numels - l1->numels;
800 for (cnt = 0; cnt < (
unsigned int)err; cnt++) dest->mid = dest->mid->next;
801 }
else if (err/2 < 0) {
803 for (cnt = 0; cnt < (
unsigned int)err; cnt++) dest->mid = dest->mid->prev;
806 assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest));
811 int list_sort(
list_t *restrict l,
int versus) {
812 if (l->iter_active || l->attrs.comparator == NULL)
818 if (NULL == l->head_sentinel || NULL == l->tail_sentinel)
821 list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev);
822 assert(list_repOk(l));
826 #ifdef SIMCLIST_WITH_THREADS 827 struct list_sort_wrappedparams {
830 unsigned int first, last;
834 static void *list_sort_quicksort_threadwrapper(
void *wrapped_params) {
835 struct list_sort_wrappedparams *wp = (
struct list_sort_wrappedparams *)wrapped_params;
836 list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel);
843 static inline void list_sort_selectionsort(
list_t *restrict l,
int versus,
852 for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) {
854 for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next)
855 if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor;
856 if (toswap != firstunsorted) {
857 tmpdata = firstunsorted->data;
858 firstunsorted->data = toswap->data;
859 toswap->data = tmpdata;
864 static void list_sort_quicksort(
list_t *restrict l,
int versus,
867 unsigned int pivotid;
872 #ifdef SIMCLIST_WITH_THREADS 881 if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) {
882 list_sort_selectionsort(l, versus, first, fel, last, lel);
887 if (! (last > first))
return;
889 pivotid = (get_random() % (last - first + 1));
893 if (pivotid < (last - first + 1)/2) {
894 for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++);
896 for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--);
903 while (left != pivot && right != pivot) {
904 for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next);
906 for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev);
908 if (left != pivot && right != pivot) {
910 tmpdata = left->data;
911 left->data = right->data;
912 right->data = tmpdata;
920 if (right == pivot) {
921 while (left != pivot) {
922 if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) {
923 tmpdata = left->data;
924 left->data = pivot->prev->data;
925 pivot->prev->data = pivot->data;
926 pivot->data = tmpdata;
929 if (pivot == left)
break;
935 while (right != pivot) {
936 if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) {
938 tmpdata = right->data;
939 right->data = pivot->next->data;
940 pivot->next->data = pivot->data;
941 pivot->data = tmpdata;
944 if (pivot == right)
break;
953 #ifdef SIMCLIST_WITH_THREADS 957 if (l->threadcount < SIMCLIST_MAXTHREADS-1) {
958 struct list_sort_wrappedparams *wp = (
struct list_sort_wrappedparams *)malloc(
sizeof(
struct list_sort_wrappedparams));
967 wp->last = first+pivotid-1;
968 wp->lel = pivot->prev;
969 if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) {
972 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
975 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
978 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
980 pthread_join(tid, (
void **)NULL);
984 if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev);
985 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel);
989 int list_iterator_start(
list_t *restrict l) {
990 if (l->iter_active)
return 0;
991 if (NULL == l->head_sentinel)
995 l->iter_curentry = l->head_sentinel->next;
999 void *list_iterator_next(
list_t *restrict l) {
1002 if (! l->iter_active)
return NULL;
1004 toret = l->iter_curentry->data;
1005 l->iter_curentry = l->iter_curentry->next;
1011 int list_iterator_hasnext(
const list_t *restrict l) {
1012 if (! l->iter_active)
return 0;
1013 return (l->iter_pos < l->numels);
1016 int list_iterator_stop(
list_t *restrict l) {
1017 if (! l->iter_active)
return 0;
1023 int list_hash(
const list_t *restrict l, list_hash_t *restrict hash) {
1025 list_hash_t tmphash;
1027 assert(hash != NULL);
1029 tmphash = l->numels * 2 + 100;
1030 if (l->attrs.hasher == NULL) {
1031 #ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES 1033 #warning "Memlocation-based hash is consistent only for testing modification in the same program run." 1037 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1038 for (i = 0; i <
sizeof(x->data); i++) {
1039 tmphash += (tmphash ^ (uintptr_t)x->data);
1041 tmphash += tmphash % l->numels;
1048 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1049 tmphash += tmphash ^ l->attrs.hasher(x->data);
1050 tmphash += tmphash % l->numels;
1059 #ifndef SIMCLIST_NO_DUMPRESTORE 1060 int list_dump_getinfo_filedescriptor(
int fd,
list_dump_info_t *restrict info) {
1061 int32_t terminator_head, terminator_tail;
1067 READ_ERRCHECK(fd, & info->version,
sizeof(info->version));
1068 info->version = ntohs(info->version);
1069 if (info->version > SIMCLIST_DUMPFORMAT_VERSION) {
1075 READ_ERRCHECK(fd, & info->timestamp.tv_sec,
sizeof(info->timestamp.tv_sec));
1076 info->timestamp.tv_sec = ntohl(info->timestamp.tv_sec);
1077 READ_ERRCHECK(fd, & info->timestamp.tv_usec,
sizeof(info->timestamp.tv_usec));
1078 info->timestamp.tv_usec = ntohl(info->timestamp.tv_usec);
1081 READ_ERRCHECK(fd, & terminator_head,
sizeof(terminator_head));
1082 terminator_head = ntohl(terminator_head);
1085 READ_ERRCHECK(fd, & info->list_size,
sizeof(info->list_size));
1086 info->list_size = ntohl(info->list_size);
1089 READ_ERRCHECK(fd, & info->list_numels,
sizeof(info->list_numels));
1090 info->list_numels = ntohl(info->list_numels);
1093 READ_ERRCHECK(fd, & elemlen,
sizeof(elemlen));
1094 elemlen = ntohl(elemlen);
1097 READ_ERRCHECK(fd, & info->list_hash,
sizeof(info->list_hash));
1098 info->list_hash = ntohl(info->list_hash);
1103 hop = info->list_size;
1106 hop = info->list_size + elemlen*info->list_numels;
1108 if (lseek(fd, hop, SEEK_CUR) == -1) {
1113 READ_ERRCHECK(fd, & terminator_tail,
sizeof(terminator_tail));
1114 terminator_tail = ntohl(terminator_tail);
1116 if (terminator_head == terminator_tail)
1117 info->consistent = 1;
1119 info->consistent = 0;
1124 int list_dump_getinfo_file(
const char *restrict filename,
list_dump_info_t *restrict info) {
1127 fd = open(filename, O_RDONLY, 0);
1128 if (fd < 0)
return -1;
1130 ret = list_dump_getinfo_filedescriptor(fd, info);
1136 int list_dump_filedescriptor(
const list_t *restrict l,
int fd,
size_t *restrict len) {
1140 struct timeval timeofday;
1143 if (l->attrs.meter == NULL && l->attrs.serializer == NULL) {
1164 header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION );
1167 gettimeofday(&timeofday, NULL);
1168 header.timestamp_sec = htonl(timeofday.tv_sec);
1169 header.timestamp_usec = htonl(timeofday.tv_usec);
1171 header.rndterm = htonl((int32_t)get_random());
1176 header.numels = htonl(l->numels);
1179 if (l->attrs.hasher != NULL) {
1180 if (htonl(list_hash(l, & header.listhash)) != 0) {
1185 header.listhash = htonl(0);
1188 header.totlistlen = header.elemlen = 0;
1191 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
1197 if (l->numels > 0) {
1200 if (l->attrs.serializer != NULL) {
1202 ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen);
1205 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1206 ser_buf = l->attrs.serializer(x->data, &bufsize);
1207 header.totlistlen += bufsize;
1208 if (header.elemlen != 0) {
1209 if (header.elemlen != bufsize) {
1213 header.totlistlen = 0;
1214 x = l->head_sentinel;
1215 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) {
1223 WRITE_ERRCHECK(fd, ser_buf, bufsize);
1225 WRITE_ERRCHECK(fd, & bufsize,
sizeof(
size_t));
1226 WRITE_ERRCHECK(fd, ser_buf, bufsize);
1230 }
else if (l->attrs.meter != NULL) {
1231 header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data);
1234 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) {
1235 bufsize = l->attrs.meter(x->data);
1236 header.totlistlen += bufsize;
1237 if (header.elemlen != 0) {
1238 if (header.elemlen != bufsize) {
1241 header.totlistlen = 0;
1242 x = l->head_sentinel;
1246 WRITE_ERRCHECK(fd, x->data, bufsize);
1248 WRITE_ERRCHECK(fd, &bufsize,
sizeof(
size_t));
1249 WRITE_ERRCHECK(fd, x->data, bufsize);
1254 header.elemlen = htonl(header.elemlen);
1255 header.totlistlen = htonl(header.totlistlen);
1259 WRITE_ERRCHECK(fd, & header.rndterm,
sizeof(header.rndterm));
1263 lseek(fd, 0, SEEK_SET);
1265 WRITE_ERRCHECK(fd, & header.ver,
sizeof(header.ver));
1266 WRITE_ERRCHECK(fd, & header.timestamp_sec,
sizeof(header.timestamp_sec));
1267 WRITE_ERRCHECK(fd, & header.timestamp_usec,
sizeof(header.timestamp_usec));
1268 WRITE_ERRCHECK(fd, & header.rndterm,
sizeof(header.rndterm));
1270 WRITE_ERRCHECK(fd, & header.totlistlen,
sizeof(header.totlistlen));
1271 WRITE_ERRCHECK(fd, & header.numels,
sizeof(header.numels));
1272 WRITE_ERRCHECK(fd, & header.elemlen,
sizeof(header.elemlen));
1273 WRITE_ERRCHECK(fd, & header.listhash,
sizeof(header.listhash));
1278 *len =
sizeof(header) + ntohl(header.totlistlen);
1284 int list_restore_filedescriptor(
list_t *restrict l,
int fd,
size_t *restrict len) {
1288 uint32_t elsize, totreadlen, totmemorylen;
1290 memset(& header, 0,
sizeof(header));
1295 READ_ERRCHECK(fd, &header.ver,
sizeof(header.ver));
1296 header.ver = ntohs(header.ver);
1297 if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) {
1303 READ_ERRCHECK(fd, & header.timestamp_sec,
sizeof(header.timestamp_sec));
1304 header.timestamp_sec = ntohl(header.timestamp_sec);
1305 READ_ERRCHECK(fd, & header.timestamp_usec,
sizeof(header.timestamp_usec));
1306 header.timestamp_usec = ntohl(header.timestamp_usec);
1309 READ_ERRCHECK(fd, & header.rndterm,
sizeof(header.rndterm));
1311 header.rndterm = ntohl(header.rndterm);
1314 READ_ERRCHECK(fd, & header.totlistlen,
sizeof(header.totlistlen));
1315 header.totlistlen = ntohl(header.totlistlen);
1318 READ_ERRCHECK(fd, & header.numels,
sizeof(header.numels));
1319 header.numels = ntohl(header.numels);
1322 READ_ERRCHECK(fd, & header.elemlen,
sizeof(header.elemlen));
1323 header.elemlen = ntohl(header.elemlen);
1326 READ_ERRCHECK(fd, & header.listhash,
sizeof(header.listhash));
1327 header.listhash = ntohl(header.listhash);
1331 totreadlen = totmemorylen = 0;
1332 if (header.elemlen > 0) {
1334 if (l->attrs.unserializer != NULL) {
1336 buf = malloc(header.elemlen);
1339 for (cnt = 0; cnt < header.numels; cnt++) {
1340 READ_ERRCHECK(fd, buf, header.elemlen);
1341 list_append(l, l->attrs.unserializer(buf, & elsize));
1342 totmemorylen += elsize;
1346 for (cnt = 0; cnt < header.numels; cnt++) {
1347 buf = malloc(header.elemlen);
1350 READ_ERRCHECK(fd, buf, header.elemlen);
1351 list_append(l, buf);
1353 totmemorylen = header.numels * header.elemlen;
1355 totreadlen = header.numels * header.elemlen;
1358 if (l->attrs.unserializer != NULL) {
1360 for (cnt = 0; cnt < header.numels; cnt++) {
1361 READ_ERRCHECK(fd, & elsize,
sizeof(elsize));
1362 buf = malloc((
size_t)elsize);
1365 READ_ERRCHECK(fd, buf, elsize);
1366 totreadlen += elsize;
1367 list_append(l, l->attrs.unserializer(buf, & elsize));
1368 totmemorylen += elsize;
1372 for (cnt = 0; cnt < header.numels; cnt++) {
1373 READ_ERRCHECK(fd, & elsize,
sizeof(elsize));
1374 buf = malloc(elsize);
1377 READ_ERRCHECK(fd, buf, elsize);
1378 totreadlen += elsize;
1379 list_append(l, buf);
1381 totmemorylen = totreadlen;
1385 READ_ERRCHECK(fd, &elsize,
sizeof(elsize));
1386 elsize = ntohl(elsize);
1398 if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) {
1404 if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) {
1410 *len = totmemorylen;
1416 int list_dump_file(
const list_t *restrict l,
const char *restrict filename,
size_t *restrict len) {
1417 int fd, oflag, mode;
1420 oflag = O_RDWR | O_CREAT | O_TRUNC;
1421 mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH;
1423 oflag = _O_RDWR | _O_CREAT | _O_TRUNC;
1424 mode = _S_IRUSR | _S_IWUSR | _S_IRGRP | _S_IROTH;
1426 fd = open(filename, oflag, mode);
1427 if (fd < 0)
return -1;
1429 list_dump_filedescriptor(l, fd, len);
1435 int list_restore_file(
list_t *restrict l,
const char *restrict filename,
size_t *restrict len) {
1438 fd = open(filename, O_RDONLY, 0);
1439 if (fd < 0)
return -1;
1441 list_restore_filedescriptor(l, fd, len);
1449 static int list_drop_elem(
list_t *restrict l,
struct list_entry_s *tmp,
unsigned int pos) {
1450 if (tmp == NULL)
return -1;
1453 if (l->numels % 2) {
1455 if (l->numels == 1) l->mid = NULL;
1456 else if (pos >= l->numels/2) l->mid = l->mid->prev;
1458 if (pos < l->numels/2) l->mid = l->mid->next;
1461 tmp->prev->next = tmp->next;
1462 tmp->next->prev = tmp->prev;
1465 if (l->attrs.copy_data && tmp->data != NULL)
1468 if (l->spareels != NULL && l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) {
1469 l->spareels[l->spareelsnum++] = tmp;
1478 #define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); } 1480 SIMCLIST_NUMBER_COMPARATOR(int8_t)
1481 SIMCLIST_NUMBER_COMPARATOR(int16_t)
1482 SIMCLIST_NUMBER_COMPARATOR(int32_t)
1483 SIMCLIST_NUMBER_COMPARATOR(int64_t)
1485 SIMCLIST_NUMBER_COMPARATOR(uint8_t)
1486 SIMCLIST_NUMBER_COMPARATOR(uint16_t)
1487 SIMCLIST_NUMBER_COMPARATOR(uint32_t)
1488 SIMCLIST_NUMBER_COMPARATOR(uint64_t)
1490 SIMCLIST_NUMBER_COMPARATOR(
float)
1491 SIMCLIST_NUMBER_COMPARATOR(
double)
1493 int list_comparator_string(
const void *a,
const void *b) {
return strcmp((
const char *)b, (
const char *)a); }
1496 #define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { } return sizeof(type); } 1498 SIMCLIST_METER(int8_t)
1499 SIMCLIST_METER(int16_t)
1500 SIMCLIST_METER(int32_t)
1501 SIMCLIST_METER(int64_t)
1503 SIMCLIST_METER(uint8_t)
1504 SIMCLIST_METER(uint16_t)
1505 SIMCLIST_METER(uint32_t)
1506 SIMCLIST_METER(uint64_t)
1508 SIMCLIST_METER(
float)
1509 SIMCLIST_METER(
double)
1511 size_t list_meter_string(
const void *el) {
return strlen((
const char *)el) + 1; }
1514 #define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); } 1516 SIMCLIST_HASHCOMPUTER(int8_t)
1517 SIMCLIST_HASHCOMPUTER(int16_t)
1518 SIMCLIST_HASHCOMPUTER(int32_t)
1519 SIMCLIST_HASHCOMPUTER(int64_t)
1521 SIMCLIST_HASHCOMPUTER(uint8_t)
1522 SIMCLIST_HASHCOMPUTER(uint16_t)
1523 SIMCLIST_HASHCOMPUTER(uint32_t)
1524 SIMCLIST_HASHCOMPUTER(uint64_t)
1526 SIMCLIST_HASHCOMPUTER(
float)
1527 SIMCLIST_HASHCOMPUTER(
double)
1529 list_hash_t list_hashcomputer_string(
const void *el) {
1531 list_hash_t hash = 123;
1532 const char *str = (
const char *)el;
1535 for (l = 0; str[l] !=
'\0'; l++) {
1536 if (l) plus = hash ^ str[l];
1537 else plus = hash ^ (str[l] - str[0]);
1538 hash += (plus << (CHAR_BIT * (l %
sizeof(list_hash_t))));
1546 static int list_repOk(
const list_t *restrict l) {
1550 ok = (l != NULL) && (
1552 (l->head_sentinel != NULL && l->tail_sentinel != NULL) &&
1553 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) &&
1555 (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) &&
1557 l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS
1562 if (l->numels >= 1) {
1564 for (i = -1, s = l->head_sentinel; i < (
int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) {
1565 if (s->next->prev != s)
break;
1567 ok = (i == (int)(l->numels-1)/2 && l->mid == s);
1569 for (; s->next != NULL; i++, s = s->next) {
1570 if (s->next->prev != s)
break;
1572 ok = (i == (int)l->numels && s == l->tail_sentinel);
1578 static int list_attrOk(
const list_t *restrict l) {
1581 ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL);