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