1/* 2 * Copyright (c) 2007,2008,2009,2010,2011 Mij <mij@bitchx.it> 3 * 4 * Permission to use, copy, modify, and distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 18/* 19 * SimCList library. See http://mij.oltrelinux.com/devel/simclist 20 */ 21 22/* SimCList implementation, version 1.6 */ 23 24#include <stdlib.h> 25#include <string.h> 26#include <errno.h> /* for setting errno */ 27#include <sys/types.h> 28#ifndef _WIN32 29 /* not in Windows! */ 30# include <unistd.h> 31# include <stdint.h> 32#endif 33#ifndef SIMCLIST_NO_DUMPRESTORE 34 /* includes for dump/restore */ 35# include <time.h> 36# include <sys/uio.h> /* for READ_ERRCHECK() and write() */ 37# include <fcntl.h> /* for open() etc */ 38# ifndef _WIN32 39# include <arpa/inet.h> /* for htons() on UNIX */ 40# else 41# include <winsock2.h> /* for htons() on Windows */ 42# endif 43#endif 44 45/* disable asserts */ 46#ifndef SIMCLIST_DEBUG 47#define NDEBUG 48#endif 49 50#include <assert.h> 51 52 53#include <sys/stat.h> /* for open()'s access modes S_IRUSR etc */ 54#include <limits.h> 55 56#if defined(_MSC_VER) || defined(__MINGW32__) 57/* provide gettimeofday() missing in Windows */ 58int gettimeofday(struct timeval *tp, void *tzp) { 59 DWORD t; 60 61 /* XSI says: "If tzp is not a null pointer, the behavior is unspecified" */ 62 assert(tzp == NULL); 63 64 t = timeGetTime(); 65 tp->tv_sec = t / 1000; 66 tp->tv_usec = t % 1000; 67 return 0; 68} 69#endif 70 71 72/* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */ 73#if !defined(_WIN32) || !defined(_MSC_VER) 74# include <inttypes.h> /* (u)int*_t */ 75#else 76# include <basetsd.h> 77typedef UINT8 uint8_t; 78typedef UINT16 uint16_t; 79typedef ULONG32 uint32_t; 80typedef UINT64 uint64_t; 81typedef INT8 int8_t; 82typedef INT16 int16_t; 83typedef LONG32 int32_t; 84typedef INT64 int64_t; 85#endif 86 87 88/* define some commodity macros for Dump/Restore functionality */ 89#ifndef SIMCLIST_NO_DUMPRESTORE 90/* write() decorated with error checking logic */ 91#define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \ 92 if (write(fd, msgbuf, msglen) < 0) return -1; \ 93 } while (0); 94/* READ_ERRCHECK() decorated with error checking logic */ 95#define READ_ERRCHECK(fd, msgbuf, msglen) do { \ 96 if (read(fd, msgbuf, msglen) != msglen) { \ 97 /*errno = EPROTO;*/ \ 98 return -1; \ 99 } \ 100 } while (0); 101 102/* convert 64bit integers from host to network format */ 103#define hton64(x) (\ 104 htons(1) == 1 ? \ 105 (uint64_t)x /* big endian */ \ 106 : /* little endian */ \ 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))) \ 115 ) 116 117/* convert 64bit integers from network to host format */ 118#define ntoh64(x) (hton64(x)) 119#endif 120 121/* some OSes don't have EPROTO (eg OpenBSD) */ 122#ifndef EPROTO 123#define EPROTO EIO 124#endif 125 126#ifdef SIMCLIST_WITH_THREADS 127/* limit (approx) to the number of threads running 128 * for threaded operations. Only meant when 129 * SIMCLIST_WITH_THREADS is defined */ 130#define SIMCLIST_MAXTHREADS 2 131#endif 132 133/* 134 * how many elems to keep as spare. During a deletion, an element 135 * can be saved in a "free-list", not free()d immediately. When 136 * latter insertions are performed, spare elems can be used instead 137 * of malloc()ing new elems. 138 * 139 * about this param, some values for appending 140 * 10 million elems into an empty list: 141 * (#, time[sec], gain[%], gain/no[%]) 142 * 0 2,164 0,00 0,00 <-- feature disabled 143 * 1 1,815 34,9 34,9 144 * 2 1,446 71,8 35,9 <-- MAX gain/no 145 * 3 1,347 81,7 27,23 146 * 5 1,213 95,1 19,02 147 * 8 1,064 110,0 13,75 148 * 10 1,015 114,9 11,49 <-- MAX gain w/ likely sol 149 * 15 1,019 114,5 7,63 150 * 25 0,985 117,9 4,72 151 * 50 1,088 107,6 2,15 152 * 75 1,016 114,8 1,53 153 * 100 0,988 117,6 1,18 154 * 150 1,022 114,2 0,76 155 * 200 0,939 122,5 0,61 <-- MIN time 156 */ 157#ifndef SIMCLIST_MAX_SPARE_ELEMS 158#define SIMCLIST_MAX_SPARE_ELEMS 5 159#endif 160 161 162#ifdef SIMCLIST_WITH_THREADS 163#include <pthread.h> 164#endif 165 166#include "simclist.h" 167 168 169/* minumum number of elements for sorting with quicksort instead of insertion */ 170#define SIMCLIST_MINQUICKSORTELS 24 171 172 173/* list dump declarations */ 174#define SIMCLIST_DUMPFORMAT_VERSION 1 /* (short integer) version of fileformat managed by _dump* and _restore* functions */ 175 176#define SIMCLIST_DUMPFORMAT_HEADERLEN 30 /* length of the header */ 177 178/* header for a list dump */ 179struct list_dump_header_s { 180 uint16_t ver; /* version */ 181 int32_t timestamp_sec; /* dump timestamp, seconds since UNIX Epoch */ 182 int32_t timestamp_usec; /* dump timestamp, microseconds since timestamp_sec */ 183 int32_t rndterm; /* random value terminator -- terminates the data sequence */ 184 185 uint32_t totlistlen; /* sum of every element' size, bytes */ 186 uint32_t numels; /* number of elements */ 187 uint32_t elemlen; /* bytes length of an element, for constant-size lists, <= 0 otherwise */ 188 int32_t listhash; /* hash of the list at the time of dumping, or 0 if to be ignored */ 189}; 190 191 192 193/* deletes tmp from list, with care wrt its position (head, tail, middle) */ 194static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos); 195 196/* set default values for initialized lists */ 197static int list_attributes_setdefaults(list_t *restrict l); 198 199#ifndef NDEBUG 200/* check whether the list internal REPresentation is valid -- Costs O(n) */ 201static int list_repOk(const list_t *restrict l); 202 203/* check whether the list attribute set is valid -- Costs O(1) */ 204static int list_attrOk(const list_t *restrict l); 205#endif 206 207/* do not inline, this is recursive */ 208static void list_sort_quicksort(list_t *restrict l, int versus, 209 unsigned int first, struct list_entry_s *fel, 210 unsigned int last, struct list_entry_s *lel); 211 212static inline void list_sort_selectionsort(list_t *restrict l, int versus, 213 unsigned int first, struct list_entry_s *fel, 214 unsigned int last, struct list_entry_s *lel); 215 216static void *list_get_minmax(const list_t *restrict l, int versus); 217 218static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart); 219 220/* 221 * Random Number Generator 222 * 223 * The user is expected to seed the RNG (ie call srand()) if 224 * SIMCLIST_SYSTEM_RNG is defined. 225 * 226 * Otherwise, a self-contained RNG based on LCG is used; see 227 * http://en.wikipedia.org/wiki/Linear_congruential_generator . 228 * 229 * Facts pro local RNG: 230 * 1. no need for the user to call srand() on his own 231 * 2. very fast, possibly faster than OS 232 * 3. avoid interference with user's RNG 233 * 234 * Facts pro system RNG: 235 * 1. may be more accurate (irrelevant for SimCList randno purposes) 236 * 2. why reinvent the wheel 237 * 238 * Default to local RNG for user's ease of use. 239 */ 240 241#ifdef SIMCLIST_SYSTEM_RNG 242/* keep track whether we initialized already (non-0) or not (0) */ 243static unsigned random_seed = 0; 244 245/* use local RNG */ 246static inline void seed_random(void) { 247 if (random_seed == 0) 248 random_seed = (unsigned)getpid() ^ (unsigned)time(NULL); 249} 250 251static inline long get_random(void) { 252 random_seed = (1664525 * random_seed + 1013904223); 253 return random_seed; 254} 255 256#else 257/* use OS's random generator */ 258# define seed_random() 259# define get_random() (rand()) 260#endif 261 262 263/* list initialization */ 264int list_init(list_t *restrict l) { 265 if (l == NULL) return -1; 266 267 seed_random(); 268 269 l->numels = 0; 270 271 /* head/tail sentinels and mid pointer */ 272 l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 273 l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 274 l->head_sentinel->next = l->tail_sentinel; 275 l->tail_sentinel->prev = l->head_sentinel; 276 l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL; 277 l->head_sentinel->data = l->tail_sentinel->data = NULL; 278 279 /* iteration attributes */ 280 l->iter_active = 0; 281 l->iter_pos = 0; 282 l->iter_curentry = NULL; 283 284 /* free-list attributes */ 285 l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *)); 286 l->spareelsnum = 0; 287 288#ifdef SIMCLIST_WITH_THREADS 289 l->threadcount = 0; 290#endif 291 292 list_attributes_setdefaults(l); 293 294 assert(list_repOk(l)); 295 assert(list_attrOk(l)); 296 297 return 0; 298} 299 300void list_destroy(list_t *restrict l) { 301 unsigned int i; 302 303 list_clear(l); 304 for (i = 0; i < l->spareelsnum; i++) { 305 free(l->spareels[i]); 306 } 307 free(l->spareels); 308 free(l->head_sentinel); 309 free(l->tail_sentinel); 310} 311 312int list_attributes_setdefaults(list_t *restrict l) { 313 l->attrs.comparator = NULL; 314 l->attrs.seeker = NULL; 315 316 /* also free() element data when removing and element from the list */ 317 l->attrs.meter = NULL; 318 l->attrs.copy_data = 0; 319 320 l->attrs.hasher = NULL; 321 322 /* serializer/unserializer */ 323 l->attrs.serializer = NULL; 324 l->attrs.unserializer = NULL; 325 326 assert(list_attrOk(l)); 327 328 return 0; 329} 330 331/* setting list properties */ 332int list_attributes_comparator(list_t *restrict l, element_comparator comparator_fun) { 333 if (l == NULL) return -1; 334 335 l->attrs.comparator = comparator_fun; 336 337 assert(list_attrOk(l)); 338 339 return 0; 340} 341 342int list_attributes_seeker(list_t *restrict l, element_seeker seeker_fun) { 343 if (l == NULL) return -1; 344 345 l->attrs.seeker = seeker_fun; 346 assert(list_attrOk(l)); 347 348 return 0; 349} 350 351int list_attributes_copy(list_t *restrict l, element_meter metric_fun, int copy_data) { 352 if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1; 353 354 l->attrs.meter = metric_fun; 355 l->attrs.copy_data = copy_data; 356 357 assert(list_attrOk(l)); 358 359 return 0; 360} 361 362int list_attributes_hash_computer(list_t *restrict l, element_hash_computer hash_computer_fun) { 363 if (l == NULL) return -1; 364 365 l->attrs.hasher = hash_computer_fun; 366 assert(list_attrOk(l)); 367 return 0; 368} 369 370int list_attributes_serializer(list_t *restrict l, element_serializer serializer_fun) { 371 if (l == NULL) return -1; 372 373 l->attrs.serializer = serializer_fun; 374 assert(list_attrOk(l)); 375 return 0; 376} 377 378int list_attributes_unserializer(list_t *restrict l, element_unserializer unserializer_fun) { 379 if (l == NULL) return -1; 380 381 l->attrs.unserializer = unserializer_fun; 382 assert(list_attrOk(l)); 383 return 0; 384} 385 386int list_append(list_t *restrict l, const void *data) { 387 return list_insert_at(l, data, l->numels); 388} 389 390int list_prepend(list_t *restrict l, const void *data) { 391 return list_insert_at(l, data, 0); 392} 393 394void *list_fetch(list_t *restrict l) { 395 return list_extract_at(l, 0); 396} 397 398void *list_get_at(const list_t *restrict l, unsigned int pos) { 399 struct list_entry_s *tmp; 400 401 tmp = list_findpos(l, pos); 402 403 return (tmp != NULL ? tmp->data : NULL); 404} 405 406void *list_get_max(const list_t *restrict l) { 407 return list_get_minmax(l, +1); 408} 409 410void *list_get_min(const list_t *restrict l) { 411 return list_get_minmax(l, -1); 412} 413 414/* REQUIRES {list->numels >= 1} 415 * return the min (versus < 0) or max value (v > 0) in l */ 416static void *list_get_minmax(const list_t *restrict l, int versus) { 417 void *curminmax; 418 struct list_entry_s *s; 419 420 if (l->attrs.comparator == NULL || l->numels == 0) 421 return NULL; 422 423 curminmax = l->head_sentinel->next->data; 424 for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) { 425 if (l->attrs.comparator(curminmax, s->data) * versus > 0) 426 curminmax = s->data; 427 } 428 429 return curminmax; 430} 431 432/* set tmp to point to element at index posstart in l */ 433static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart) { 434 struct list_entry_s *ptr; 435 float x; 436 int i; 437 438 /* accept 1 slot overflow for fetching head and tail sentinels */ 439 if (posstart < -1 || posstart > (int)l->numels) return NULL; 440 441 x = (float)(posstart+1) / l->numels; 442 if (x <= 0.25) { 443 /* first quarter: get to posstart from head */ 444 for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++); 445 } else if (x < 0.5) { 446 /* second quarter: get to posstart from mid */ 447 for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--); 448 } else if (x <= 0.75) { 449 /* third quarter: get to posstart from mid */ 450 for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++); 451 } else { 452 /* fourth quarter: get to posstart from tail */ 453 for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--); 454 } 455 456 return ptr; 457} 458 459void *list_extract_at(list_t *restrict l, unsigned int pos) { 460 struct list_entry_s *tmp; 461 void *data; 462 463 if (l->iter_active || pos >= l->numels) return NULL; 464 465 tmp = list_findpos(l, pos); 466 data = tmp->data; 467 468 tmp->data = NULL; /* save data from list_drop_elem() free() */ 469 list_drop_elem(l, tmp, pos); 470 l->numels--; 471 472 assert(list_repOk(l)); 473 474 return data; 475} 476 477int list_insert_at(list_t *restrict l, const void *data, unsigned int pos) { 478 struct list_entry_s *lent, *succ, *prec; 479 480 if (l->iter_active || pos > l->numels) return -1; 481 482 /* this code optimizes malloc() with a free-list */ 483 if (l->spareelsnum > 0) { 484 lent = l->spareels[l->spareelsnum-1]; 485 l->spareelsnum--; 486 } else { 487 lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 488 if (lent == NULL) 489 return -1; 490 } 491 492 if (l->attrs.copy_data) { 493 /* make room for user' data (has to be copied) */ 494 size_t datalen = l->attrs.meter(data); 495 lent->data = (struct list_entry_s *)malloc(datalen); 496 memcpy(lent->data, data, datalen); 497 } else { 498 lent->data = (void*)data; 499 } 500 501 /* actually append element */ 502 prec = list_findpos(l, pos-1); 503 succ = prec->next; 504 505 prec->next = lent; 506 lent->prev = prec; 507 lent->next = succ; 508 succ->prev = lent; 509 510 l->numels++; 511 512 /* fix mid pointer */ 513 if (l->numels == 1) { /* first element, set pointer */ 514 l->mid = lent; 515 } else if (l->numels % 2) { /* now odd */ 516 if (pos >= (l->numels-1)/2) l->mid = l->mid->next; 517 } else { /* now even */ 518 if (pos <= (l->numels-1)/2) l->mid = l->mid->prev; 519 } 520 521 assert(list_repOk(l)); 522 523 return 1; 524} 525 526int list_delete(list_t *restrict l, const void *data) { 527 int pos, r; 528 529 pos = list_locate(l, data); 530 if (pos < 0) 531 return -1; 532 533 r = list_delete_at(l, pos); 534 if (r < 0) 535 return -1; 536 537 assert(list_repOk(l)); 538 539 return 0; 540} 541 542int list_delete_at(list_t *restrict l, unsigned int pos) { 543 struct list_entry_s *delendo; 544 545 546 if (l->iter_active || pos >= l->numels) return -1; 547 548 delendo = list_findpos(l, pos); 549 550 list_drop_elem(l, delendo, pos); 551 552 l->numels--; 553 554 555 assert(list_repOk(l)); 556 557 return 0; 558} 559 560int list_delete_range(list_t *restrict l, unsigned int posstart, unsigned int posend) { 561 struct list_entry_s *lastvalid, *tmp, *tmp2; 562 unsigned int numdel, midposafter, i; 563 int movedx; 564 565 if (l->iter_active || posend < posstart || posend >= l->numels) return -1; 566 567 numdel = posend - posstart + 1; 568 if (numdel == l->numels) return list_clear(l); 569 570 tmp = list_findpos(l, posstart); /* first el to be deleted */ 571 lastvalid = tmp->prev; /* last valid element */ 572 573 midposafter = (l->numels-1-numdel)/2; 574 575 midposafter = midposafter < posstart ? midposafter : midposafter+numdel; 576 movedx = midposafter - (l->numels-1)/2; 577 578 if (movedx > 0) { /* move right */ 579 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++); 580 } else { /* move left */ 581 movedx = -movedx; 582 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++); 583 } 584 585 assert(posstart == 0 || lastvalid != l->head_sentinel); 586 i = posstart; 587 if (l->attrs.copy_data) { 588 /* also free element data */ 589 for (; i <= posend; i++) { 590 tmp2 = tmp; 591 tmp = tmp->next; 592 if (tmp2->data != NULL) free(tmp2->data); 593 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 594 l->spareels[l->spareelsnum++] = tmp2; 595 } else { 596 free(tmp2); 597 } 598 } 599 } else { 600 /* only free containers */ 601 for (; i <= posend; i++) { 602 tmp2 = tmp; 603 tmp = tmp->next; 604 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 605 l->spareels[l->spareelsnum++] = tmp2; 606 } else { 607 free(tmp2); 608 } 609 } 610 } 611 assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel)); 612 613 lastvalid->next = tmp; 614 tmp->prev = lastvalid; 615 616 l->numels -= posend - posstart + 1; 617 618 assert(list_repOk(l)); 619 620 return numdel; 621} 622 623int list_clear(list_t *restrict l) { 624 struct list_entry_s *s; 625 unsigned int numels; 626 627 /* will be returned */ 628 numels = l->numels; 629 630 if (l->iter_active) return -1; 631 632 if (l->attrs.copy_data) { /* also free user data */ 633 /* spare a loop conditional with two loops: spareing elems and freeing elems */ 634 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) { 635 /* move elements as spares as long as there is room */ 636 if (s->data != NULL) free(s->data); 637 l->spareels[l->spareelsnum++] = s; 638 } 639 while (s != l->tail_sentinel) { 640 /* free the remaining elems */ 641 if (s->data != NULL) free(s->data); 642 s = s->next; 643 free(s->prev); 644 } 645 l->head_sentinel->next = l->tail_sentinel; 646 l->tail_sentinel->prev = l->head_sentinel; 647 } else { /* only free element containers */ 648 /* spare a loop conditional with two loops: spareing elems and freeing elems */ 649 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) { 650 /* move elements as spares as long as there is room */ 651 l->spareels[l->spareelsnum++] = s; 652 } 653 while (s != l->tail_sentinel) { 654 /* free the remaining elems */ 655 s = s->next; 656 free(s->prev); 657 } 658 l->head_sentinel->next = l->tail_sentinel; 659 l->tail_sentinel->prev = l->head_sentinel; 660 } 661 l->numels = 0; 662 l->mid = NULL; 663 664 assert(list_repOk(l)); 665 666 return numels; 667} 668 669unsigned int list_size(const list_t *restrict l) { 670 return l->numels; 671} 672 673int list_empty(const list_t *restrict l) { 674 return (l->numels == 0); 675} 676 677int list_locate(const list_t *restrict l, const void *data) { 678 struct list_entry_s *el; 679 int pos = 0; 680 681 if (l->attrs.comparator != NULL) { 682 /* use comparator */ 683 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) { 684 if (l->attrs.comparator(data, el->data) == 0) break; 685 } 686 } else { 687 /* compare references */ 688 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) { 689 if (el->data == data) break; 690 } 691 } 692 if (el == l->tail_sentinel) return -1; 693 694 return pos; 695} 696 697void *list_seek(list_t *restrict l, const void *indicator) { 698 const struct list_entry_s *iter; 699 700 if (l->attrs.seeker == NULL) return NULL; 701 702 for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) { 703 if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data; 704 } 705 706 return NULL; 707} 708 709int list_contains(const list_t *restrict l, const void *data) { 710 return (list_locate(l, data) >= 0); 711} 712 713int list_concat(const list_t *l1, const list_t *l2, list_t *restrict dest) { 714 struct list_entry_s *el, *srcel; 715 unsigned int cnt; 716 int err; 717 718 719 if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest) 720 return -1; 721 722 list_init(dest); 723 724 dest->numels = l1->numels + l2->numels; 725 if (dest->numels == 0) 726 return 0; 727 728 /* copy list1 */ 729 srcel = l1->head_sentinel->next; 730 el = dest->head_sentinel; 731 while (srcel != l1->tail_sentinel) { 732 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 733 el->next->prev = el; 734 el = el->next; 735 el->data = srcel->data; 736 srcel = srcel->next; 737 } 738 dest->mid = el; /* approximate position (adjust later) */ 739 /* copy list 2 */ 740 srcel = l2->head_sentinel->next; 741 while (srcel != l2->tail_sentinel) { 742 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 743 el->next->prev = el; 744 el = el->next; 745 el->data = srcel->data; 746 srcel = srcel->next; 747 } 748 el->next = dest->tail_sentinel; 749 dest->tail_sentinel->prev = el; 750 751 /* fix mid pointer */ 752 err = l2->numels - l1->numels; 753 if ((err+1)/2 > 0) { /* correct pos RIGHT (err-1)/2 moves */ 754 err = (err+1)/2; 755 for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next; 756 } else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */ 757 err = -err/2; 758 for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev; 759 } 760 761 assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest)); 762 763 return 0; 764} 765 766int list_sort(list_t *restrict l, int versus) { 767 if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */ 768 return -1; 769 770 if (l->numels <= 1) 771 return 0; 772 list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev); 773 assert(list_repOk(l)); 774 return 0; 775} 776 777#ifdef SIMCLIST_WITH_THREADS 778struct list_sort_wrappedparams { 779 list_t *restrict l; 780 int versus; 781 unsigned int first, last; 782 struct list_entry_s *fel, *lel; 783}; 784 785static void *list_sort_quicksort_threadwrapper(void *wrapped_params) { 786 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params; 787 list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel); 788 free(wp); 789 pthread_exit(NULL); 790 return NULL; 791} 792#endif 793 794static inline void list_sort_selectionsort(list_t *restrict l, int versus, 795 unsigned int first, struct list_entry_s *fel, 796 unsigned int last, struct list_entry_s *lel) { 797 struct list_entry_s *cursor, *toswap, *firstunsorted; 798 void *tmpdata; 799 800 if (last <= first) /* <= 1-element lists are always sorted */ 801 return; 802 803 for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) { 804 /* find min or max in the remainder of the list */ 805 for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next) 806 if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor; 807 if (toswap != firstunsorted) { /* swap firstunsorted with toswap */ 808 tmpdata = firstunsorted->data; 809 firstunsorted->data = toswap->data; 810 toswap->data = tmpdata; 811 } 812 } 813} 814 815static void list_sort_quicksort(list_t *restrict l, int versus, 816 unsigned int first, struct list_entry_s *fel, 817 unsigned int last, struct list_entry_s *lel) { 818 unsigned int pivotid; 819 unsigned int i; 820 register struct list_entry_s *pivot; 821 struct list_entry_s *left, *right; 822 void *tmpdata; 823#ifdef SIMCLIST_WITH_THREADS 824 pthread_t tid; 825 int traised; 826#endif 827 828 829 if (last <= first) /* <= 1-element lists are always sorted */ 830 return; 831 832 if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) { 833 list_sort_selectionsort(l, versus, first, fel, last, lel); 834 return; 835 } 836 837 /* base of iteration: one element list */ 838 if (! (last > first)) return; 839 840 pivotid = (get_random() % (last - first + 1)); 841 /* pivotid = (last - first + 1) / 2; */ 842 843 /* find pivot */ 844 if (pivotid < (last - first + 1)/2) { 845 for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++); 846 } else { 847 for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--); 848 } 849 850 /* smaller PIVOT bigger */ 851 left = fel; 852 right = lel; 853 /* iterate --- left ---> PIV <--- right --- */ 854 while (left != pivot && right != pivot) { 855 for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next); 856 /* left points to a smaller element, or to pivot */ 857 for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev); 858 /* right points to a bigger element, or to pivot */ 859 if (left != pivot && right != pivot) { 860 /* swap, then move iterators */ 861 tmpdata = left->data; 862 left->data = right->data; 863 right->data = tmpdata; 864 865 left = left->next; 866 right = right->prev; 867 } 868 } 869 870 /* now either left points to pivot (end run), or right */ 871 if (right == pivot) { /* left part longer */ 872 while (left != pivot) { 873 if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) { 874 tmpdata = left->data; 875 left->data = pivot->prev->data; 876 pivot->prev->data = pivot->data; 877 pivot->data = tmpdata; 878 pivot = pivot->prev; 879 pivotid--; 880 if (pivot == left) break; 881 } else { 882 left = left->next; 883 } 884 } 885 } else { /* right part longer */ 886 while (right != pivot) { 887 if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) { 888 /* move current right before pivot */ 889 tmpdata = right->data; 890 right->data = pivot->next->data; 891 pivot->next->data = pivot->data; 892 pivot->data = tmpdata; 893 pivot = pivot->next; 894 pivotid++; 895 if (pivot == right) break; 896 } else { 897 right = right->prev; 898 } 899 } 900 } 901 902 /* sort sublists A and B : |---A---| pivot |---B---| */ 903 904#ifdef SIMCLIST_WITH_THREADS 905 traised = 0; 906 if (pivotid > 0) { 907 /* prepare wrapped args, then start thread */ 908 if (l->threadcount < SIMCLIST_MAXTHREADS-1) { 909 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams)); 910 l->threadcount++; 911 traised = 1; 912 wp->l = l; 913 wp->versus = versus; 914 wp->first = first; 915 wp->fel = fel; 916 wp->last = first+pivotid-1; 917 wp->lel = pivot->prev; 918 if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) { 919 free(wp); 920 traised = 0; 921 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 922 } 923 } else { 924 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 925 } 926 } 927 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel); 928 if (traised) { 929 pthread_join(tid, (void **)NULL); 930 l->threadcount--; 931 } 932#else 933 if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 934 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel); 935#endif 936} 937 938int list_iterator_start(list_t *restrict l) { 939 if (l->iter_active) return 0; 940 l->iter_pos = 0; 941 l->iter_active = 1; 942 l->iter_curentry = l->head_sentinel->next; 943 return 1; 944} 945 946void *list_iterator_next(list_t *restrict l) { 947 void *toret; 948 949 if (! l->iter_active) return NULL; 950 951 toret = l->iter_curentry->data; 952 l->iter_curentry = l->iter_curentry->next; 953 l->iter_pos++; 954 955 return toret; 956} 957 958int list_iterator_hasnext(const list_t *restrict l) { 959 if (! l->iter_active) return 0; 960 return (l->iter_pos < l->numels); 961} 962 963int list_iterator_stop(list_t *restrict l) { 964 if (! l->iter_active) return 0; 965 l->iter_pos = 0; 966 l->iter_active = 0; 967 return 1; 968} 969 970int list_hash(const list_t *restrict l, list_hash_t *restrict hash) { 971 struct list_entry_s *x; 972 list_hash_t tmphash; 973 974 assert(hash != NULL); 975 976 tmphash = l->numels * 2 + 100; 977 if (l->attrs.hasher == NULL) { 978#ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES 979 /* ENABLE WITH CARE !! */ 980#warning "Memlocation-based hash is consistent only for testing modification in the same program run." 981 int i; 982 983 /* only use element references */ 984 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 985 for (i = 0; i < sizeof(x->data); i++) { 986 tmphash += (tmphash ^ (uintptr_t)x->data); 987 } 988 tmphash += tmphash % l->numels; 989 } 990#else 991 return -1; 992#endif 993 } else { 994 /* hash each element with the user-given function */ 995 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 996 tmphash += tmphash ^ l->attrs.hasher(x->data); 997 tmphash += tmphash % l->numels; 998 } 999 } 1000 1001 *hash = tmphash; 1002 1003 return 0; 1004} 1005 1006#ifndef SIMCLIST_NO_DUMPRESTORE 1007int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *restrict info) { 1008 int32_t terminator_head, terminator_tail; 1009 uint32_t elemlen; 1010 off_t hop; 1011 1012 1013 /* version */ 1014 READ_ERRCHECK(fd, & info->version, sizeof(info->version)); 1015 info->version = ntohs(info->version); 1016 if (info->version > SIMCLIST_DUMPFORMAT_VERSION) { 1017 errno = EILSEQ; 1018 return -1; 1019 } 1020 1021 /* timestamp.tv_sec and timestamp.tv_usec */ 1022 READ_ERRCHECK(fd, & info->timestamp.tv_sec, sizeof(info->timestamp.tv_sec)); 1023 info->timestamp.tv_sec = ntohl(info->timestamp.tv_sec); 1024 READ_ERRCHECK(fd, & info->timestamp.tv_usec, sizeof(info->timestamp.tv_usec)); 1025 info->timestamp.tv_usec = ntohl(info->timestamp.tv_usec); 1026 1027 /* list terminator (to check thereafter) */ 1028 READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head)); 1029 terminator_head = ntohl(terminator_head); 1030 1031 /* list size */ 1032 READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size)); 1033 info->list_size = ntohl(info->list_size); 1034 1035 /* number of elements */ 1036 READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels)); 1037 info->list_numels = ntohl(info->list_numels); 1038 1039 /* length of each element (for checking for consistency) */ 1040 READ_ERRCHECK(fd, & elemlen, sizeof(elemlen)); 1041 elemlen = ntohl(elemlen); 1042 1043 /* list hash */ 1044 READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash)); 1045 info->list_hash = ntohl(info->list_hash); 1046 1047 /* check consistency */ 1048 if (elemlen > 0) { 1049 /* constant length, hop by size only */ 1050 hop = info->list_size; 1051 } else { 1052 /* non-constant length, hop by size + all element length blocks */ 1053 hop = info->list_size + elemlen*info->list_numels; 1054 } 1055 if (lseek(fd, hop, SEEK_CUR) == -1) { 1056 return -1; 1057 } 1058 1059 /* read the trailing value and compare with terminator_head */ 1060 READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail)); 1061 terminator_tail = ntohl(terminator_tail); 1062 1063 if (terminator_head == terminator_tail) 1064 info->consistent = 1; 1065 else 1066 info->consistent = 0; 1067 1068 return 0; 1069} 1070 1071int list_dump_getinfo_file(const char *restrict filename, list_dump_info_t *restrict info) { 1072 int fd, ret; 1073 1074 fd = open(filename, O_RDONLY, 0); 1075 if (fd < 0) return -1; 1076 1077 ret = list_dump_getinfo_filedescriptor(fd, info); 1078 close(fd); 1079 1080 return ret; 1081} 1082 1083int list_dump_filedescriptor(const list_t *restrict l, int fd, size_t *restrict len) { 1084 struct list_entry_s *x; 1085 void *ser_buf; 1086 uint32_t bufsize; 1087 struct timeval timeofday; 1088 struct list_dump_header_s header; 1089 1090 if (l->attrs.meter == NULL && l->attrs.serializer == NULL) { 1091 errno = ENOTTY; 1092 return -1; 1093 } 1094 1095 /**** DUMP FORMAT **** 1096 1097 [ ver timestamp | totlen numels elemlen hash | DATA ] 1098 1099 where DATA can be: 1100 @ for constant-size list (element size is constant; elemlen > 0) 1101 [ elem elem ... elem ] 1102 @ for other lists (element size dictated by element_meter each time; elemlen <= 0) 1103 [ size elem size elem ... size elem ] 1104 1105 all integers are encoded in NETWORK BYTE FORMAT 1106 *****/ 1107 1108 1109 /* prepare HEADER */ 1110 /* version */ 1111 header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION ); 1112 1113 /* timestamp */ 1114 gettimeofday(&timeofday, NULL); 1115 header.timestamp_sec = htonl(timeofday.tv_sec); 1116 header.timestamp_usec = htonl(timeofday.tv_usec); 1117 1118 header.rndterm = htonl((int32_t)get_random()); 1119 1120 /* total list size is postprocessed afterwards */ 1121 1122 /* number of elements */ 1123 header.numels = htonl(l->numels); 1124 1125 /* include an hash, if possible */ 1126 if (l->attrs.hasher != NULL) { 1127 if (htonl(list_hash(l, & header.listhash)) != 0) { 1128 /* could not compute list hash! */ 1129 return -1; 1130 } 1131 } else { 1132 header.listhash = htonl(0); 1133 } 1134 1135 header.totlistlen = header.elemlen = 0; 1136 1137 /* leave room for the header at the beginning of the file */ 1138 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) { 1139 /* errno set by lseek() */ 1140 return -1; 1141 } 1142 1143 /* write CONTENT */ 1144 if (l->numels > 0) { 1145 /* SPECULATE that the list has constant element size */ 1146 1147 if (l->attrs.serializer != NULL) { /* user user-specified serializer */ 1148 /* get preliminary length of serialized element in header.elemlen */ 1149 ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen); 1150 free(ser_buf); 1151 /* request custom serialization of each element */ 1152 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 1153 ser_buf = l->attrs.serializer(x->data, &bufsize); 1154 header.totlistlen += bufsize; 1155 if (header.elemlen != 0) { /* continue on speculation */ 1156 if (header.elemlen != bufsize) { 1157 free(ser_buf); 1158 /* constant element length speculation broken! */ 1159 header.elemlen = 0; 1160 header.totlistlen = 0; 1161 x = l->head_sentinel; 1162 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) { 1163 /* errno set by lseek() */ 1164 return -1; 1165 } 1166 /* restart from the beginning */ 1167 continue; 1168 } 1169 /* speculation confirmed */ 1170 WRITE_ERRCHECK(fd, ser_buf, bufsize); 1171 } else { /* speculation found broken */ 1172 WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t)); 1173 WRITE_ERRCHECK(fd, ser_buf, bufsize); 1174 } 1175 free(ser_buf); 1176 } 1177 } else if (l->attrs.meter != NULL) { 1178 header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data); 1179 1180 /* serialize the element straight from its data */ 1181 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 1182 bufsize = l->attrs.meter(x->data); 1183 header.totlistlen += bufsize; 1184 if (header.elemlen != 0) { 1185 if (header.elemlen != bufsize) { 1186 /* constant element length speculation broken! */ 1187 header.elemlen = 0; 1188 header.totlistlen = 0; 1189 x = l->head_sentinel; 1190 /* restart from the beginning */ 1191 continue; 1192 } 1193 WRITE_ERRCHECK(fd, x->data, bufsize); 1194 } else { 1195 WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t)); 1196 WRITE_ERRCHECK(fd, x->data, bufsize); 1197 } 1198 } 1199 } 1200 /* adjust endianness */ 1201 header.elemlen = htonl(header.elemlen); 1202 header.totlistlen = htonl(header.totlistlen); 1203 } 1204 1205 /* write random terminator */ 1206 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* list terminator */ 1207 1208 1209 /* write header */ 1210 lseek(fd, 0, SEEK_SET); 1211 1212 WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver)); /* version */ 1213 WRITE_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec)); /* timestamp seconds */ 1214 WRITE_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec)); /* timestamp microseconds */ 1215 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* random terminator */ 1216 1217 WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); /* total length of elements */ 1218 WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels)); /* number of elements */ 1219 WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); /* size of each element, or 0 for independent */ 1220 WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); /* list hash, or 0 for "ignore" */ 1221 1222 1223 /* possibly store total written length in "len" */ 1224 if (len != NULL) { 1225 *len = sizeof(header) + ntohl(header.totlistlen); 1226 } 1227 1228 return 0; 1229} 1230 1231int list_restore_filedescriptor(list_t *restrict l, int fd, size_t *restrict len) { 1232 struct list_dump_header_s header; 1233 unsigned long cnt; 1234 void *buf; 1235 uint32_t elsize, totreadlen, totmemorylen; 1236 1237 memset(& header, 0, sizeof(header)); 1238 1239 /* read header */ 1240 1241 /* version */ 1242 READ_ERRCHECK(fd, &header.ver, sizeof(header.ver)); 1243 header.ver = ntohs(header.ver); 1244 if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) { 1245 errno = EILSEQ; 1246 return -1; 1247 } 1248 1249 /* timestamp */ 1250 READ_ERRCHECK(fd, & header.timestamp_sec, sizeof(header.timestamp_sec)); 1251 header.timestamp_sec = ntohl(header.timestamp_sec); 1252 READ_ERRCHECK(fd, & header.timestamp_usec, sizeof(header.timestamp_usec)); 1253 header.timestamp_usec = ntohl(header.timestamp_usec); 1254 1255 /* list terminator */ 1256 READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); 1257 1258 header.rndterm = ntohl(header.rndterm); 1259 1260 /* total list size */ 1261 READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); 1262 header.totlistlen = ntohl(header.totlistlen); 1263 1264 /* number of elements */ 1265 READ_ERRCHECK(fd, & header.numels, sizeof(header.numels)); 1266 header.numels = ntohl(header.numels); 1267 1268 /* length of every element, or '0' = variable */ 1269 READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); 1270 header.elemlen = ntohl(header.elemlen); 1271 1272 /* list hash, or 0 = 'ignore' */ 1273 READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); 1274 header.listhash = ntohl(header.listhash); 1275 1276 1277 /* read content */ 1278 totreadlen = totmemorylen = 0; 1279 if (header.elemlen > 0) { 1280 /* elements have constant size = header.elemlen */ 1281 if (l->attrs.unserializer != NULL) { 1282 /* use unserializer */ 1283 buf = malloc(header.elemlen); 1284 for (cnt = 0; cnt < header.numels; cnt++) { 1285 READ_ERRCHECK(fd, buf, header.elemlen); 1286 list_append(l, l->attrs.unserializer(buf, & elsize)); 1287 totmemorylen += elsize; 1288 } 1289 } else { 1290 /* copy verbatim into memory */ 1291 for (cnt = 0; cnt < header.numels; cnt++) { 1292 buf = malloc(header.elemlen); 1293 READ_ERRCHECK(fd, buf, header.elemlen); 1294 list_append(l, buf); 1295 } 1296 totmemorylen = header.numels * header.elemlen; 1297 } 1298 totreadlen = header.numels * header.elemlen; 1299 } else { 1300 /* elements have variable size. Each element is preceded by its size */ 1301 if (l->attrs.unserializer != NULL) { 1302 /* use unserializer */ 1303 for (cnt = 0; cnt < header.numels; cnt++) { 1304 READ_ERRCHECK(fd, & elsize, sizeof(elsize)); 1305 buf = malloc((size_t)elsize); 1306 READ_ERRCHECK(fd, buf, elsize); 1307 totreadlen += elsize; 1308 list_append(l, l->attrs.unserializer(buf, & elsize)); 1309 totmemorylen += elsize; 1310 } 1311 } else { 1312 /* copy verbatim into memory */ 1313 for (cnt = 0; cnt < header.numels; cnt++) { 1314 READ_ERRCHECK(fd, & elsize, sizeof(elsize)); 1315 buf = malloc(elsize); 1316 READ_ERRCHECK(fd, buf, elsize); 1317 totreadlen += elsize; 1318 list_append(l, buf); 1319 } 1320 totmemorylen = totreadlen; 1321 } 1322 } 1323 1324 READ_ERRCHECK(fd, &elsize, sizeof(elsize)); /* read list terminator */ 1325 elsize = ntohl(elsize); 1326 1327 /* possibly verify the list consistency */ 1328 /* wrt hash */ 1329 /* don't do that 1330 if (header.listhash != 0 && header.listhash != list_hash(l)) { 1331 errno = ECANCELED; 1332 return -1; 1333 } 1334 */ 1335 1336 /* wrt header */ 1337 if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) { 1338 errno = EPROTO; 1339 return -1; 1340 } 1341 1342 /* wrt file */ 1343 if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) { 1344 errno = EPROTO; 1345 return -1; 1346 } 1347 1348 if (len != NULL) { 1349 *len = totmemorylen; 1350 } 1351 1352 return 0; 1353} 1354 1355int list_dump_file(const list_t *restrict l, const char *restrict filename, size_t *restrict len) { 1356 int fd, oflag, mode; 1357 1358#ifndef _WIN32 1359 oflag = O_RDWR | O_CREAT | O_TRUNC; 1360 mode = S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH; 1361#else 1362 oflag = _O_RDWR | _O_CREAT | _O_TRUNC; 1363 mode = _S_IRUSR | _S_IWUSR | _S_IRGRP | _S_IROTH; 1364#endif 1365 fd = open(filename, oflag, mode); 1366 if (fd < 0) return -1; 1367 1368 list_dump_filedescriptor(l, fd, len); 1369 close(fd); 1370 1371 return 0; 1372} 1373 1374int list_restore_file(list_t *restrict l, const char *restrict filename, size_t *restrict len) { 1375 int fd; 1376 1377 fd = open(filename, O_RDONLY, 0); 1378 if (fd < 0) return -1; 1379 1380 list_restore_filedescriptor(l, fd, len); 1381 close(fd); 1382 1383 return 0; 1384} 1385#endif /* ifndef SIMCLIST_NO_DUMPRESTORE */ 1386 1387 1388static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos) { 1389 if (tmp == NULL) return -1; 1390 1391 /* fix mid pointer. This is wrt the PRE situation */ 1392 if (l->numels % 2) { /* now odd */ 1393 /* sort out the base case by hand */ 1394 if (l->numels == 1) l->mid = NULL; 1395 else if (pos >= l->numels/2) l->mid = l->mid->prev; 1396 } else { /* now even */ 1397 if (pos < l->numels/2) l->mid = l->mid->next; 1398 } 1399 1400 tmp->prev->next = tmp->next; 1401 tmp->next->prev = tmp->prev; 1402 1403 /* free what's to be freed */ 1404 if (l->attrs.copy_data && tmp->data != NULL) 1405 free(tmp->data); 1406 1407 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 1408 l->spareels[l->spareelsnum++] = tmp; 1409 } else { 1410 free(tmp); 1411 } 1412 1413 return 0; 1414} 1415 1416/* ready-made comparators and meters */ 1417#define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); } 1418 1419SIMCLIST_NUMBER_COMPARATOR(int8_t) 1420SIMCLIST_NUMBER_COMPARATOR(int16_t) 1421SIMCLIST_NUMBER_COMPARATOR(int32_t) 1422SIMCLIST_NUMBER_COMPARATOR(int64_t) 1423 1424SIMCLIST_NUMBER_COMPARATOR(uint8_t) 1425SIMCLIST_NUMBER_COMPARATOR(uint16_t) 1426SIMCLIST_NUMBER_COMPARATOR(uint32_t) 1427SIMCLIST_NUMBER_COMPARATOR(uint64_t) 1428 1429SIMCLIST_NUMBER_COMPARATOR(float) 1430SIMCLIST_NUMBER_COMPARATOR(double) 1431 1432int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); } 1433 1434/* ready-made metric functions */ 1435#define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); } 1436 1437SIMCLIST_METER(int8_t) 1438SIMCLIST_METER(int16_t) 1439SIMCLIST_METER(int32_t) 1440SIMCLIST_METER(int64_t) 1441 1442SIMCLIST_METER(uint8_t) 1443SIMCLIST_METER(uint16_t) 1444SIMCLIST_METER(uint32_t) 1445SIMCLIST_METER(uint64_t) 1446 1447SIMCLIST_METER(float) 1448SIMCLIST_METER(double) 1449 1450size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; } 1451 1452/* ready-made hashing functions */ 1453#define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); } 1454 1455SIMCLIST_HASHCOMPUTER(int8_t) 1456SIMCLIST_HASHCOMPUTER(int16_t) 1457SIMCLIST_HASHCOMPUTER(int32_t) 1458SIMCLIST_HASHCOMPUTER(int64_t) 1459 1460SIMCLIST_HASHCOMPUTER(uint8_t) 1461SIMCLIST_HASHCOMPUTER(uint16_t) 1462SIMCLIST_HASHCOMPUTER(uint32_t) 1463SIMCLIST_HASHCOMPUTER(uint64_t) 1464 1465SIMCLIST_HASHCOMPUTER(float) 1466SIMCLIST_HASHCOMPUTER(double) 1467 1468list_hash_t list_hashcomputer_string(const void *el) { 1469 size_t l; 1470 list_hash_t hash = 123; 1471 const char *str = (const char *)el; 1472 char plus; 1473 1474 for (l = 0; str[l] != '\0'; l++) { 1475 if (l) plus = hash ^ str[l]; 1476 else plus = hash ^ (str[l] - str[0]); 1477 hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t)))); 1478 } 1479 1480 return hash; 1481} 1482 1483 1484#ifndef NDEBUG 1485static int list_repOk(const list_t *restrict l) { 1486 int ok, i; 1487 struct list_entry_s *s; 1488 1489 ok = (l != NULL) && ( 1490 /* head/tail checks */ 1491 (l->head_sentinel != NULL && l->tail_sentinel != NULL) && 1492 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) && 1493 /* empty list */ 1494 (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) && 1495 /* spare elements checks */ 1496 l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS 1497 ); 1498 1499 if (!ok) return 0; 1500 1501 if (l->numels >= 1) { 1502 /* correct referencing */ 1503 for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) { 1504 if (s->next->prev != s) break; 1505 } 1506 ok = (i == (int)(l->numels-1)/2 && l->mid == s); 1507 if (!ok) return 0; 1508 for (; s->next != NULL; i++, s = s->next) { 1509 if (s->next->prev != s) break; 1510 } 1511 ok = (i == (int)l->numels && s == l->tail_sentinel); 1512 } 1513 1514 return ok; 1515} 1516 1517static int list_attrOk(const list_t *restrict l) { 1518 int ok; 1519 1520 ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL); 1521 return ok; 1522} 1523 1524#endif 1525 1526