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