pcsc-lite
1.7.4
|
00001 /* 00002 * Copyright (c) 2007,2008,2009,2010 Mij <mij@bitchx.it> 00003 * 00004 * Permission to use, copy, modify, and distribute this software for any 00005 * purpose with or without fee is hereby granted, provided that the above 00006 * copyright notice and this permission notice appear in all copies. 00007 * 00008 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 00009 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 00010 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 00011 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 00012 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 00013 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 00014 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 00015 */ 00016 00017 00018 /* 00019 * SimCList library. See http://mij.oltrelinux.com/devel/simclist 00020 */ 00021 00022 /* SimCList implementation, version 1.5 */ 00023 00024 #include <stdlib.h> 00025 #include <string.h> 00026 #include <errno.h> /* for setting errno */ 00027 #include <sys/types.h> 00028 #include <sys/uio.h> /* for READ_ERRCHECK() and write() */ 00029 #include <fcntl.h> /* for open() etc */ 00030 #include <arpa/inet.h> /* for htons() */ 00031 #include <unistd.h> 00032 #include <time.h> /* for time() for random seed */ 00033 #include <sys/time.h> /* for gettimeofday() */ 00034 #include <sys/stat.h> /* for open()'s access modes S_IRUSR etc */ 00035 #include <limits.h> 00036 #include <stdint.h> 00037 00038 00039 /* work around lack of inttypes.h support in broken Microsoft Visual Studio compilers */ 00040 #if !defined(WIN32) || !defined(_MSC_VER) 00041 # include <inttypes.h> /* (u)int*_t */ 00042 #else 00043 # include <basetsd.h> 00044 typedef UINT8 uint8_t; 00045 typedef UINT16 uint16_t; 00046 typedef ULONG32 uint32_t; 00047 typedef UINT64 uint64_t; 00048 typedef INT8 int8_t; 00049 typedef INT16 int16_t; 00050 typedef LONG32 int32_t; 00051 typedef INT64 int64_t; 00052 #endif 00053 00054 00055 00056 #ifndef SIMCLIST_NO_DUMPRESTORE 00057 /* convert 64bit integers from host to network format */ 00058 #define hton64(x) (\ 00059 htons(1) == 1 ? \ 00060 (uint64_t)x /* big endian */ \ 00061 : /* little endian */ \ 00062 ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \ 00063 (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \ 00064 (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \ 00065 (((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \ 00066 (((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \ 00067 (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \ 00068 (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \ 00069 (((uint64_t)(x) & 0x00000000000000ffULL) << 56))) \ 00070 ) 00071 00072 /* convert 64bit integers from network to host format */ 00073 #define ntoh64(x) (hton64(x)) 00074 #endif 00075 00076 /* some OSes don't have EPROTO (eg OpenBSD) */ 00077 #ifndef EPROTO 00078 #define EPROTO EIO 00079 #endif 00080 00081 /* disable asserts */ 00082 #ifndef SIMCLIST_DEBUG 00083 #define NDEBUG 00084 #endif 00085 00086 #include <assert.h> 00087 00088 #ifdef SIMCLIST_WITH_THREADS 00089 /* limit (approx) to the number of threads running 00090 * for threaded operations. Only meant when 00091 * SIMCLIST_WITH_THREADS is defined */ 00092 #define SIMCLIST_MAXTHREADS 2 00093 #endif 00094 00095 /* 00096 * how many elems to keep as spare. During a deletion, an element 00097 * can be saved in a "free-list", not free()d immediately. When 00098 * latter insertions are performed, spare elems can be used instead 00099 * of malloc()ing new elems. 00100 * 00101 * about this param, some values for appending 00102 * 10 million elems into an empty list: 00103 * (#, time[sec], gain[%], gain/no[%]) 00104 * 0 2,164 0,00 0,00 <-- feature disabled 00105 * 1 1,815 34,9 34,9 00106 * 2 1,446 71,8 35,9 <-- MAX gain/no 00107 * 3 1,347 81,7 27,23 00108 * 5 1,213 95,1 19,02 00109 * 8 1,064 110,0 13,75 00110 * 10 1,015 114,9 11,49 <-- MAX gain w/ likely sol 00111 * 15 1,019 114,5 7,63 00112 * 25 0,985 117,9 4,72 00113 * 50 1,088 107,6 2,15 00114 * 75 1,016 114,8 1,53 00115 * 100 0,988 117,6 1,18 00116 * 150 1,022 114,2 0,76 00117 * 200 0,939 122,5 0,61 <-- MIN time 00118 */ 00119 #ifndef SIMCLIST_MAX_SPARE_ELEMS 00120 #define SIMCLIST_MAX_SPARE_ELEMS 5 00121 #endif 00122 00123 00124 #ifdef SIMCLIST_WITH_THREADS 00125 #include <pthread.h> 00126 #endif 00127 00128 #include "simclist.h" 00129 00130 00131 /* minumum number of elements for sorting with quicksort instead of insertion */ 00132 #define SIMCLIST_MINQUICKSORTELS 24 00133 00134 00135 /* list dump declarations */ 00136 #define SIMCLIST_DUMPFORMAT_VERSION 1 /* (short integer) version of fileformat managed by _dump* and _restore* functions */ 00137 00138 #define SIMCLIST_DUMPFORMAT_HEADERLEN 30 /* length of the header */ 00139 00140 /* header for a list dump */ 00141 struct list_dump_header_s { 00142 uint16_t ver; /* version */ 00143 int64_t timestamp; /* dump timestamp */ 00144 int32_t rndterm; /* random value terminator -- terminates the data sequence */ 00145 00146 uint32_t totlistlen; /* sum of every element' size, bytes */ 00147 uint32_t numels; /* number of elements */ 00148 uint32_t elemlen; /* bytes length of an element, for constant-size lists, <= 0 otherwise */ 00149 int32_t listhash; /* hash of the list at the time of dumping, or 0 if to be ignored */ 00150 }; 00151 00152 00153 00154 /* deletes tmp from list, with care wrt its position (head, tail, middle) */ 00155 static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos); 00156 00157 /* set default values for initialized lists */ 00158 static int list_attributes_setdefaults(list_t *restrict l); 00159 00160 #ifndef NDEBUG 00161 /* check whether the list internal REPresentation is valid -- Costs O(n) */ 00162 static int list_repOk(const list_t *restrict l); 00163 00164 /* check whether the list attribute set is valid -- Costs O(1) */ 00165 static int list_attrOk(const list_t *restrict l); 00166 #endif 00167 00168 /* do not inline, this is recursive */ 00169 static void list_sort_quicksort(list_t *restrict l, int versus, 00170 unsigned int first, struct list_entry_s *fel, 00171 unsigned int last, struct list_entry_s *lel); 00172 00173 static inline void list_sort_selectionsort(list_t *restrict l, int versus, 00174 unsigned int first, struct list_entry_s *fel, 00175 unsigned int last, struct list_entry_s *lel); 00176 00177 static void *list_get_minmax(const list_t *restrict l, int versus); 00178 00179 static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart); 00180 00181 /* write() decorated with error checking logic */ 00182 #define WRITE_ERRCHECK(fd, msgbuf, msglen) do { \ 00183 if (write(fd, msgbuf, msglen) < 0) return -1; \ 00184 } while (0); 00185 /* READ_ERRCHECK() decorated with error checking logic */ 00186 #define READ_ERRCHECK(fd, msgbuf, msglen) do { \ 00187 if (read(fd, msgbuf, msglen) != msglen) { \ 00188 /*errno = EPROTO;*/ \ 00189 return -1; \ 00190 } \ 00191 } while (0); 00192 00193 /* 00194 * Random Number Generator 00195 * 00196 * The user is expected to seed the RNG (ie call srand()) if 00197 * SIMCLIST_SYSTEM_RNG is defined. 00198 * 00199 * Otherwise, a self-contained RNG based on LCG is used; see 00200 * http://en.wikipedia.org/wiki/Linear_congruential_generator . 00201 * 00202 * Facts pro local RNG: 00203 * 1. no need for the user to call srand() on his own 00204 * 2. very fast, possibly faster than OS 00205 * 3. avoid interference with user's RNG 00206 * 00207 * Facts pro system RNG: 00208 * 1. may be more accurate (irrelevant for SimCList randno purposes) 00209 * 2. why reinvent the wheel 00210 * 00211 * Default to local RNG for user's ease of use. 00212 */ 00213 00214 #ifdef SIMCLIST_SYSTEM_RNG 00215 /* keep track whether we initialized already (non-0) or not (0) */ 00216 static unsigned random_seed = 0; 00217 00218 /* use local RNG */ 00219 static inline void seed_random() { 00220 if (random_seed == 0) 00221 random_seed = (unsigned)getpid() ^ (unsigned)time(NULL); 00222 } 00223 00224 static inline long get_random() { 00225 random_seed = (1664525 * random_seed + 1013904223); 00226 return random_seed; 00227 } 00228 00229 #else 00230 /* use OS's random generator */ 00231 # define seed_random() 00232 # define get_random() (rand()) 00233 #endif 00234 00235 00236 /* list initialization */ 00237 int list_init(list_t *restrict l) { 00238 if (l == NULL) return -1; 00239 00240 seed_random(); 00241 00242 l->numels = 0; 00243 00244 /* head/tail sentinels and mid pointer */ 00245 l->head_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 00246 l->tail_sentinel = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 00247 l->head_sentinel->next = l->tail_sentinel; 00248 l->tail_sentinel->prev = l->head_sentinel; 00249 l->head_sentinel->prev = l->tail_sentinel->next = l->mid = NULL; 00250 l->head_sentinel->data = l->tail_sentinel->data = NULL; 00251 00252 /* iteration attributes */ 00253 l->iter_active = 0; 00254 l->iter_pos = 0; 00255 l->iter_curentry = NULL; 00256 00257 /* free-list attributes */ 00258 l->spareels = (struct list_entry_s **)malloc(SIMCLIST_MAX_SPARE_ELEMS * sizeof(struct list_entry_s *)); 00259 l->spareelsnum = 0; 00260 00261 #ifdef SIMCLIST_WITH_THREADS 00262 l->threadcount = 0; 00263 #endif 00264 00265 list_attributes_setdefaults(l); 00266 00267 assert(list_repOk(l)); 00268 assert(list_attrOk(l)); 00269 00270 return 0; 00271 } 00272 00273 void list_destroy(list_t *restrict l) { 00274 unsigned int i; 00275 00276 list_clear(l); 00277 for (i = 0; i < l->spareelsnum; i++) { 00278 free(l->spareels[i]); 00279 } 00280 free(l->spareels); 00281 free(l->head_sentinel); 00282 free(l->tail_sentinel); 00283 } 00284 00285 int list_attributes_setdefaults(list_t *restrict l) { 00286 l->attrs.comparator = NULL; 00287 l->attrs.seeker = NULL; 00288 00289 /* also free() element data when removing and element from the list */ 00290 l->attrs.meter = NULL; 00291 l->attrs.copy_data = 0; 00292 00293 l->attrs.hasher = NULL; 00294 00295 /* serializer/unserializer */ 00296 l->attrs.serializer = NULL; 00297 l->attrs.unserializer = NULL; 00298 00299 assert(list_attrOk(l)); 00300 00301 return 0; 00302 } 00303 00304 /* setting list properties */ 00305 int list_attributes_comparator(list_t *restrict l, element_comparator comparator_fun) { 00306 if (l == NULL) return -1; 00307 00308 l->attrs.comparator = comparator_fun; 00309 00310 assert(list_attrOk(l)); 00311 00312 return 0; 00313 } 00314 00315 int list_attributes_seeker(list_t *restrict l, element_seeker seeker_fun) { 00316 if (l == NULL) return -1; 00317 00318 l->attrs.seeker = seeker_fun; 00319 assert(list_attrOk(l)); 00320 00321 return 0; 00322 } 00323 00324 int list_attributes_copy(list_t *restrict l, element_meter metric_fun, int copy_data) { 00325 if (l == NULL || (metric_fun == NULL && copy_data != 0)) return -1; 00326 00327 l->attrs.meter = metric_fun; 00328 l->attrs.copy_data = copy_data; 00329 00330 assert(list_attrOk(l)); 00331 00332 return 0; 00333 } 00334 00335 int list_attributes_hash_computer(list_t *restrict l, element_hash_computer hash_computer_fun) { 00336 if (l == NULL) return -1; 00337 00338 l->attrs.hasher = hash_computer_fun; 00339 assert(list_attrOk(l)); 00340 return 0; 00341 } 00342 00343 int list_attributes_serializer(list_t *restrict l, element_serializer serializer_fun) { 00344 if (l == NULL) return -1; 00345 00346 l->attrs.serializer = serializer_fun; 00347 assert(list_attrOk(l)); 00348 return 0; 00349 } 00350 00351 int list_attributes_unserializer(list_t *restrict l, element_unserializer unserializer_fun) { 00352 if (l == NULL) return -1; 00353 00354 l->attrs.unserializer = unserializer_fun; 00355 assert(list_attrOk(l)); 00356 return 0; 00357 } 00358 00359 int list_append(list_t *restrict l, const void *data) { 00360 return list_insert_at(l, data, l->numels); 00361 } 00362 00363 int list_prepend(list_t *restrict l, const void *data) { 00364 return list_insert_at(l, data, 0); 00365 } 00366 00367 void *list_fetch(list_t *restrict l) { 00368 return list_extract_at(l, 0); 00369 } 00370 00371 void *list_get_at(const list_t *restrict l, unsigned int pos) { 00372 struct list_entry_s *tmp; 00373 00374 tmp = list_findpos(l, pos); 00375 00376 return (tmp != NULL ? tmp->data : NULL); 00377 } 00378 00379 void *list_get_max(const list_t *restrict l) { 00380 return list_get_minmax(l, +1); 00381 } 00382 00383 void *list_get_min(const list_t *restrict l) { 00384 return list_get_minmax(l, -1); 00385 } 00386 00387 /* REQUIRES {list->numels >= 1} 00388 * return the min (versus < 0) or max value (v > 0) in l */ 00389 static void *list_get_minmax(const list_t *restrict l, int versus) { 00390 void *curminmax; 00391 struct list_entry_s *s; 00392 00393 if (l->attrs.comparator == NULL || l->numels == 0) 00394 return NULL; 00395 00396 curminmax = l->head_sentinel->next->data; 00397 for (s = l->head_sentinel->next->next; s != l->tail_sentinel; s = s->next) { 00398 if (l->attrs.comparator(curminmax, s->data) * versus > 0) 00399 curminmax = s->data; 00400 } 00401 00402 return curminmax; 00403 } 00404 00405 /* set tmp to point to element at index posstart in l */ 00406 static inline struct list_entry_s *list_findpos(const list_t *restrict l, int posstart) { 00407 struct list_entry_s *ptr; 00408 float x; 00409 int i; 00410 00411 /* accept 1 slot overflow for fetching head and tail sentinels */ 00412 if (posstart < -1 || posstart > (int)l->numels) return NULL; 00413 00414 00415 if (0 == l->numels) 00416 x = 0; 00417 else 00418 x = (float)(posstart+1) / l->numels; 00419 if (x <= 0.25) { 00420 /* first quarter: get to posstart from head */ 00421 for (i = -1, ptr = l->head_sentinel; i < posstart; ptr = ptr->next, i++); 00422 } else if (x < 0.5) { 00423 /* second quarter: get to posstart from mid */ 00424 for (i = (l->numels-1)/2, ptr = l->mid; i > posstart; ptr = ptr->prev, i--); 00425 } else if (x <= 0.75) { 00426 /* third quarter: get to posstart from mid */ 00427 for (i = (l->numels-1)/2, ptr = l->mid; i < posstart; ptr = ptr->next, i++); 00428 } else { 00429 /* fourth quarter: get to posstart from tail */ 00430 for (i = l->numels, ptr = l->tail_sentinel; i > posstart; ptr = ptr->prev, i--); 00431 } 00432 00433 return ptr; 00434 } 00435 00436 void *list_extract_at(list_t *restrict l, unsigned int pos) { 00437 struct list_entry_s *tmp; 00438 void *data; 00439 00440 if (l->iter_active || pos >= l->numels) return NULL; 00441 00442 tmp = list_findpos(l, pos); 00443 data = tmp->data; 00444 00445 tmp->data = NULL; /* save data from list_drop_elem() free() */ 00446 list_drop_elem(l, tmp, pos); 00447 l->numels--; 00448 00449 assert(list_repOk(l)); 00450 00451 return data; 00452 } 00453 00454 int list_insert_at(list_t *restrict l, const void *data, unsigned int pos) { 00455 struct list_entry_s *lent, *succ, *prec; 00456 00457 if (l->iter_active || pos > l->numels) return -1; 00458 00459 /* this code optimizes malloc() with a free-list */ 00460 if (l->spareelsnum > 0) { 00461 lent = l->spareels[l->spareelsnum-1]; 00462 l->spareelsnum--; 00463 } else { 00464 lent = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 00465 if (lent == NULL) 00466 return -1; 00467 } 00468 00469 if (l->attrs.copy_data) { 00470 /* make room for user' data (has to be copied) */ 00471 size_t datalen = l->attrs.meter(data); 00472 lent->data = (struct list_entry_s *)malloc(datalen); 00473 memcpy(lent->data, data, datalen); 00474 } else { 00475 lent->data = (void*)data; 00476 } 00477 00478 /* actually append element */ 00479 prec = list_findpos(l, pos-1); 00480 succ = prec->next; 00481 00482 prec->next = lent; 00483 lent->prev = prec; 00484 lent->next = succ; 00485 succ->prev = lent; 00486 00487 l->numels++; 00488 00489 /* fix mid pointer */ 00490 if (l->numels == 1) { /* first element, set pointer */ 00491 l->mid = lent; 00492 } else if (l->numels % 2) { /* now odd */ 00493 if (pos >= (l->numels-1)/2) l->mid = l->mid->next; 00494 } else { /* now even */ 00495 if (pos <= (l->numels-1)/2) l->mid = l->mid->prev; 00496 } 00497 00498 assert(list_repOk(l)); 00499 00500 return 1; 00501 } 00502 00503 int list_delete(list_t *restrict l, const void *data) { 00504 int pos, r; 00505 00506 pos = list_locate(l, data); 00507 if (pos < 0) 00508 return -1; 00509 00510 r = list_delete_at(l, pos); 00511 if (r < 0) 00512 return -1; 00513 00514 assert(list_repOk(l)); 00515 00516 return 0; 00517 } 00518 00519 int list_delete_at(list_t *restrict l, unsigned int pos) { 00520 struct list_entry_s *delendo; 00521 00522 00523 if (l->iter_active || pos >= l->numels) return -1; 00524 00525 delendo = list_findpos(l, pos); 00526 00527 list_drop_elem(l, delendo, pos); 00528 00529 l->numels--; 00530 00531 00532 assert(list_repOk(l)); 00533 00534 return 0; 00535 } 00536 00537 int list_delete_range(list_t *restrict l, unsigned int posstart, unsigned int posend) { 00538 struct list_entry_s *lastvalid, *tmp, *tmp2; 00539 unsigned int i; 00540 int movedx; 00541 unsigned int numdel, midposafter; 00542 00543 if (l->iter_active || posend < posstart || posend >= l->numels) return -1; 00544 00545 tmp = list_findpos(l, posstart); /* first el to be deleted */ 00546 lastvalid = tmp->prev; /* last valid element */ 00547 00548 numdel = posend - posstart + 1; 00549 midposafter = (l->numels-1-numdel)/2; 00550 00551 midposafter = midposafter < posstart ? midposafter : midposafter+numdel; 00552 movedx = midposafter - (l->numels-1)/2; 00553 00554 if (movedx > 0) { /* move right */ 00555 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->next, i++); 00556 } else { /* move left */ 00557 movedx = -movedx; 00558 for (i = 0; i < (unsigned int)movedx; l->mid = l->mid->prev, i++); 00559 } 00560 00561 assert(posstart == 0 || lastvalid != l->head_sentinel); 00562 i = posstart; 00563 if (l->attrs.copy_data) { 00564 /* also free element data */ 00565 for (; i <= posend; i++) { 00566 tmp2 = tmp; 00567 tmp = tmp->next; 00568 if (tmp2->data != NULL) free(tmp2->data); 00569 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 00570 l->spareels[l->spareelsnum++] = tmp2; 00571 } else { 00572 free(tmp2); 00573 } 00574 } 00575 } else { 00576 /* only free containers */ 00577 for (; i <= posend; i++) { 00578 tmp2 = tmp; 00579 tmp = tmp->next; 00580 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 00581 l->spareels[l->spareelsnum++] = tmp2; 00582 } else { 00583 free(tmp2); 00584 } 00585 } 00586 } 00587 assert(i == posend+1 && (posend != l->numels || tmp == l->tail_sentinel)); 00588 00589 lastvalid->next = tmp; 00590 tmp->prev = lastvalid; 00591 00592 l->numels -= posend - posstart + 1; 00593 00594 assert(list_repOk(l)); 00595 00596 return 0; 00597 } 00598 00599 int list_clear(list_t *restrict l) { 00600 struct list_entry_s *s; 00601 00602 if (l->iter_active) return -1; 00603 00604 if (l->attrs.copy_data) { /* also free user data */ 00605 /* spare a loop conditional with two loops: spareing elems and freeing elems */ 00606 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) { 00607 /* move elements as spares as long as there is room */ 00608 if (s->data != NULL) free(s->data); 00609 l->spareels[l->spareelsnum++] = s; 00610 } 00611 while (s != l->tail_sentinel) { 00612 /* free the remaining elems */ 00613 if (s->data != NULL) free(s->data); 00614 s = s->next; 00615 free(s->prev); 00616 } 00617 l->head_sentinel->next = l->tail_sentinel; 00618 l->tail_sentinel->prev = l->head_sentinel; 00619 } else { /* only free element containers */ 00620 /* spare a loop conditional with two loops: spareing elems and freeing elems */ 00621 for (s = l->head_sentinel->next; l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS && s != l->tail_sentinel; s = s->next) { 00622 /* move elements as spares as long as there is room */ 00623 l->spareels[l->spareelsnum++] = s; 00624 } 00625 while (s != l->tail_sentinel) { 00626 /* free the remaining elems */ 00627 s = s->next; 00628 free(s->prev); 00629 } 00630 l->head_sentinel->next = l->tail_sentinel; 00631 l->tail_sentinel->prev = l->head_sentinel; 00632 } 00633 l->numels = 0; 00634 l->mid = NULL; 00635 00636 assert(list_repOk(l)); 00637 00638 return 0; 00639 } 00640 00641 unsigned int list_size(const list_t *restrict l) { 00642 return l->numels; 00643 } 00644 00645 int list_empty(const list_t *restrict l) { 00646 return (l->numels == 0); 00647 } 00648 00649 int list_locate(const list_t *restrict l, const void *data) { 00650 struct list_entry_s *el; 00651 int pos = 0; 00652 00653 if (l->attrs.comparator != NULL) { 00654 /* use comparator */ 00655 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) { 00656 if (l->attrs.comparator(data, el->data) == 0) break; 00657 } 00658 } else { 00659 /* compare references */ 00660 for (el = l->head_sentinel->next; el != l->tail_sentinel; el = el->next, pos++) { 00661 if (el->data == data) break; 00662 } 00663 } 00664 if (el == l->tail_sentinel) return -1; 00665 00666 return pos; 00667 } 00668 00669 void *list_seek(list_t *restrict l, const void *indicator) { 00670 const struct list_entry_s *iter; 00671 00672 if (l->attrs.seeker == NULL) return NULL; 00673 00674 for (iter = l->head_sentinel->next; iter != l->tail_sentinel; iter = iter->next) { 00675 if (l->attrs.seeker(iter->data, indicator) != 0) return iter->data; 00676 } 00677 00678 return NULL; 00679 } 00680 00681 int list_contains(const list_t *restrict l, const void *data) { 00682 return (list_locate(l, data) >= 0); 00683 } 00684 00685 int list_concat(const list_t *l1, const list_t *l2, list_t *restrict dest) { 00686 struct list_entry_s *el, *srcel; 00687 unsigned int cnt; 00688 int err; 00689 00690 00691 if (l1 == NULL || l2 == NULL || dest == NULL || l1 == dest || l2 == dest) 00692 return -1; 00693 00694 list_init(dest); 00695 00696 dest->numels = l1->numels + l2->numels; 00697 if (dest->numels == 0) 00698 return 0; 00699 00700 /* copy list1 */ 00701 srcel = l1->head_sentinel->next; 00702 el = dest->head_sentinel; 00703 while (srcel != l1->tail_sentinel) { 00704 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 00705 el->next->prev = el; 00706 el = el->next; 00707 el->data = srcel->data; 00708 srcel = srcel->next; 00709 } 00710 dest->mid = el; /* approximate position (adjust later) */ 00711 /* copy list 2 */ 00712 srcel = l2->head_sentinel->next; 00713 while (srcel != l2->tail_sentinel) { 00714 el->next = (struct list_entry_s *)malloc(sizeof(struct list_entry_s)); 00715 el->next->prev = el; 00716 el = el->next; 00717 el->data = srcel->data; 00718 srcel = srcel->next; 00719 } 00720 el->next = dest->tail_sentinel; 00721 dest->tail_sentinel->prev = el; 00722 00723 /* fix mid pointer */ 00724 err = l2->numels - l1->numels; 00725 if ((err+1)/2 > 0) { /* correct pos RIGHT (err-1)/2 moves */ 00726 err = (err+1)/2; 00727 for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->next; 00728 } else if (err/2 < 0) { /* correct pos LEFT (err/2)-1 moves */ 00729 err = -err/2; 00730 for (cnt = 0; cnt < (unsigned int)err; cnt++) dest->mid = dest->mid->prev; 00731 } 00732 00733 assert(!(list_repOk(l1) && list_repOk(l2)) || list_repOk(dest)); 00734 00735 return 0; 00736 } 00737 00738 int list_sort(list_t *restrict l, int versus) { 00739 if (l->iter_active || l->attrs.comparator == NULL) /* cannot modify list in the middle of an iteration */ 00740 return -1; 00741 00742 if (l->numels <= 1) 00743 return 0; 00744 list_sort_quicksort(l, versus, 0, l->head_sentinel->next, l->numels-1, l->tail_sentinel->prev); 00745 assert(list_repOk(l)); 00746 return 0; 00747 } 00748 00749 #ifdef SIMCLIST_WITH_THREADS 00750 struct list_sort_wrappedparams { 00751 list_t *restrict l; 00752 int versus; 00753 unsigned int first, last; 00754 struct list_entry_s *fel, *lel; 00755 }; 00756 00757 static void *list_sort_quicksort_threadwrapper(void *wrapped_params) { 00758 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)wrapped_params; 00759 list_sort_quicksort(wp->l, wp->versus, wp->first, wp->fel, wp->last, wp->lel); 00760 free(wp); 00761 pthread_exit(NULL); 00762 return NULL; 00763 } 00764 #endif 00765 00766 static inline void list_sort_selectionsort(list_t *restrict l, int versus, 00767 unsigned int first, struct list_entry_s *fel, 00768 unsigned int last, struct list_entry_s *lel) { 00769 struct list_entry_s *cursor, *toswap, *firstunsorted; 00770 void *tmpdata; 00771 00772 if (last <= first) /* <= 1-element lists are always sorted */ 00773 return; 00774 00775 for (firstunsorted = fel; firstunsorted != lel; firstunsorted = firstunsorted->next) { 00776 /* find min or max in the remainder of the list */ 00777 for (toswap = firstunsorted, cursor = firstunsorted->next; cursor != lel->next; cursor = cursor->next) 00778 if (l->attrs.comparator(toswap->data, cursor->data) * -versus > 0) toswap = cursor; 00779 if (toswap != firstunsorted) { /* swap firstunsorted with toswap */ 00780 tmpdata = firstunsorted->data; 00781 firstunsorted->data = toswap->data; 00782 toswap->data = tmpdata; 00783 } 00784 } 00785 } 00786 00787 static void list_sort_quicksort(list_t *restrict l, int versus, 00788 unsigned int first, struct list_entry_s *fel, 00789 unsigned int last, struct list_entry_s *lel) { 00790 unsigned int pivotid; 00791 unsigned int i; 00792 register struct list_entry_s *pivot; 00793 struct list_entry_s *left, *right; 00794 void *tmpdata; 00795 #ifdef SIMCLIST_WITH_THREADS 00796 pthread_t tid; 00797 int traised; 00798 #endif 00799 00800 00801 if (last <= first) /* <= 1-element lists are always sorted */ 00802 return; 00803 00804 if (last - first+1 <= SIMCLIST_MINQUICKSORTELS) { 00805 list_sort_selectionsort(l, versus, first, fel, last, lel); 00806 return; 00807 } 00808 00809 /* base of iteration: one element list */ 00810 if (! (last > first)) return; 00811 00812 pivotid = (get_random() % (last - first + 1)); 00813 /* pivotid = (last - first + 1) / 2; */ 00814 00815 /* find pivot */ 00816 if (pivotid < (last - first + 1)/2) { 00817 for (i = 0, pivot = fel; i < pivotid; pivot = pivot->next, i++); 00818 } else { 00819 for (i = last - first, pivot = lel; i > pivotid; pivot = pivot->prev, i--); 00820 } 00821 00822 /* smaller PIVOT bigger */ 00823 left = fel; 00824 right = lel; 00825 /* iterate --- left ---> PIV <--- right --- */ 00826 while (left != pivot && right != pivot) { 00827 for (; left != pivot && (l->attrs.comparator(left->data, pivot->data) * -versus <= 0); left = left->next); 00828 /* left points to a smaller element, or to pivot */ 00829 for (; right != pivot && (l->attrs.comparator(right->data, pivot->data) * -versus >= 0); right = right->prev); 00830 /* right points to a bigger element, or to pivot */ 00831 if (left != pivot && right != pivot) { 00832 /* swap, then move iterators */ 00833 tmpdata = left->data; 00834 left->data = right->data; 00835 right->data = tmpdata; 00836 00837 left = left->next; 00838 right = right->prev; 00839 } 00840 } 00841 00842 /* now either left points to pivot (end run), or right */ 00843 if (right == pivot) { /* left part longer */ 00844 while (left != pivot) { 00845 if (l->attrs.comparator(left->data, pivot->data) * -versus > 0) { 00846 tmpdata = left->data; 00847 left->data = pivot->prev->data; 00848 pivot->prev->data = pivot->data; 00849 pivot->data = tmpdata; 00850 pivot = pivot->prev; 00851 pivotid--; 00852 if (pivot == left) break; 00853 } else { 00854 left = left->next; 00855 } 00856 } 00857 } else { /* right part longer */ 00858 while (right != pivot) { 00859 if (l->attrs.comparator(right->data, pivot->data) * -versus < 0) { 00860 /* move current right before pivot */ 00861 tmpdata = right->data; 00862 right->data = pivot->next->data; 00863 pivot->next->data = pivot->data; 00864 pivot->data = tmpdata; 00865 pivot = pivot->next; 00866 pivotid++; 00867 if (pivot == right) break; 00868 } else { 00869 right = right->prev; 00870 } 00871 } 00872 } 00873 00874 /* sort sublists A and B : |---A---| pivot |---B---| */ 00875 00876 #ifdef SIMCLIST_WITH_THREADS 00877 traised = 0; 00878 if (pivotid > 0) { 00879 /* prepare wrapped args, then start thread */ 00880 if (l->threadcount < SIMCLIST_MAXTHREADS-1) { 00881 struct list_sort_wrappedparams *wp = (struct list_sort_wrappedparams *)malloc(sizeof(struct list_sort_wrappedparams)); 00882 l->threadcount++; 00883 traised = 1; 00884 wp->l = l; 00885 wp->versus = versus; 00886 wp->first = first; 00887 wp->fel = fel; 00888 wp->last = first+pivotid-1; 00889 wp->lel = pivot->prev; 00890 if (pthread_create(&tid, NULL, list_sort_quicksort_threadwrapper, wp) != 0) { 00891 free(wp); 00892 traised = 0; 00893 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 00894 } 00895 } else { 00896 list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 00897 } 00898 } 00899 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel); 00900 if (traised) { 00901 pthread_join(tid, (void **)NULL); 00902 l->threadcount--; 00903 } 00904 #else 00905 if (pivotid > 0) list_sort_quicksort(l, versus, first, fel, first+pivotid-1, pivot->prev); 00906 if (first + pivotid < last) list_sort_quicksort(l, versus, first+pivotid+1, pivot->next, last, lel); 00907 #endif 00908 } 00909 00910 int list_iterator_start(list_t *restrict l) { 00911 if (l->iter_active) return 0; 00912 l->iter_pos = 0; 00913 l->iter_active = 1; 00914 l->iter_curentry = l->head_sentinel->next; 00915 return 1; 00916 } 00917 00918 void *list_iterator_next(list_t *restrict l) { 00919 void *toret; 00920 00921 if (! l->iter_active) return NULL; 00922 00923 toret = l->iter_curentry->data; 00924 l->iter_curentry = l->iter_curentry->next; 00925 l->iter_pos++; 00926 00927 return toret; 00928 } 00929 00930 int list_iterator_hasnext(const list_t *restrict l) { 00931 if (! l->iter_active) return 0; 00932 return (l->iter_pos < l->numels); 00933 } 00934 00935 int list_iterator_stop(list_t *restrict l) { 00936 if (! l->iter_active) return 0; 00937 l->iter_pos = 0; 00938 l->iter_active = 0; 00939 return 1; 00940 } 00941 00942 int list_hash(const list_t *restrict l, list_hash_t *restrict hash) { 00943 struct list_entry_s *x; 00944 list_hash_t tmphash; 00945 00946 assert(hash != NULL); 00947 00948 tmphash = l->numels * 2 + 100; 00949 if (l->attrs.hasher == NULL) { 00950 #ifdef SIMCLIST_ALLOW_LOCATIONBASED_HASHES 00951 /* ENABLE WITH CARE !! */ 00952 #warning "Memlocation-based hash is consistent only for testing modification in the same program run." 00953 int i; 00954 00955 /* only use element references */ 00956 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 00957 for (i = 0; i < sizeof(x->data); i++) { 00958 tmphash += (tmphash ^ (uintptr_t)x->data); 00959 } 00960 tmphash += tmphash % l->numels; 00961 } 00962 #else 00963 return -1; 00964 #endif 00965 } else { 00966 /* hash each element with the user-given function */ 00967 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 00968 tmphash += tmphash ^ l->attrs.hasher(x->data); 00969 tmphash +=* hash % l->numels; 00970 } 00971 } 00972 00973 *hash = tmphash; 00974 00975 return 0; 00976 } 00977 00978 #ifndef SIMCLIST_NO_DUMPRESTORE 00979 int list_dump_getinfo_filedescriptor(int fd, list_dump_info_t *restrict info) { 00980 int32_t terminator_head, terminator_tail; 00981 uint32_t elemlen; 00982 off_t hop; 00983 00984 00985 /* version */ 00986 READ_ERRCHECK(fd, & info->version, sizeof(info->version)); 00987 info->version = ntohs(info->version); 00988 if (info->version > SIMCLIST_DUMPFORMAT_VERSION) { 00989 errno = EILSEQ; 00990 return -1; 00991 } 00992 00993 /* timestamp */ 00994 READ_ERRCHECK(fd, & info->timestamp, sizeof(info->timestamp)); 00995 info->timestamp = hton64(info->timestamp); 00996 00997 /* list terminator (to check thereafter) */ 00998 READ_ERRCHECK(fd, & terminator_head, sizeof(terminator_head)); 00999 terminator_head = ntohl(terminator_head); 01000 01001 /* list size */ 01002 READ_ERRCHECK(fd, & info->list_size, sizeof(info->list_size)); 01003 info->list_size = ntohl(info->list_size); 01004 01005 /* number of elements */ 01006 READ_ERRCHECK(fd, & info->list_numels, sizeof(info->list_numels)); 01007 info->list_numels = ntohl(info->list_numels); 01008 01009 /* length of each element (for checking for consistency) */ 01010 READ_ERRCHECK(fd, & elemlen, sizeof(elemlen)); 01011 elemlen = ntohl(elemlen); 01012 01013 /* list hash */ 01014 READ_ERRCHECK(fd, & info->list_hash, sizeof(info->list_hash)); 01015 info->list_hash = ntohl(info->list_hash); 01016 01017 /* check consistency */ 01018 if (elemlen > 0) { 01019 /* constant length, hop by size only */ 01020 hop = info->list_size; 01021 } else { 01022 /* non-constant length, hop by size + all element length blocks */ 01023 hop = info->list_size + elemlen*info->list_numels; 01024 } 01025 if (lseek(fd, hop, SEEK_CUR) == -1) { 01026 return -1; 01027 } 01028 01029 /* read the trailing value and compare with terminator_head */ 01030 READ_ERRCHECK(fd, & terminator_tail, sizeof(terminator_tail)); 01031 terminator_tail = ntohl(terminator_tail); 01032 01033 if (terminator_head == terminator_tail) 01034 info->consistent = 1; 01035 else 01036 info->consistent = 0; 01037 01038 return 0; 01039 } 01040 01041 int list_dump_getinfo_file(const char *restrict filename, list_dump_info_t *restrict info) { 01042 int fd, ret; 01043 01044 fd = open(filename, O_RDONLY, 0); 01045 if (fd < 0) return -1; 01046 01047 ret = list_dump_getinfo_filedescriptor(fd, info); 01048 close(fd); 01049 01050 return ret; 01051 } 01052 01053 int list_dump_filedescriptor(const list_t *restrict l, int fd, size_t *restrict len) { 01054 struct list_entry_s *x; 01055 void *ser_buf; 01056 uint32_t bufsize; 01057 struct timeval timeofday; 01058 struct list_dump_header_s header; 01059 01060 if (l->attrs.meter == NULL && l->attrs.serializer == NULL) { 01061 errno = ENOTTY; 01062 return -1; 01063 } 01064 01065 /**** DUMP FORMAT **** 01066 01067 [ ver timestamp | totlen numels elemlen hash | DATA ] 01068 01069 where DATA can be: 01070 @ for constant-size list (element size is constant; elemlen > 0) 01071 [ elem elem ... elem ] 01072 @ for other lists (element size dictated by element_meter each time; elemlen <= 0) 01073 [ size elem size elem ... size elem ] 01074 01075 all integers are encoded in NETWORK BYTE FORMAT 01076 *****/ 01077 01078 01079 /* prepare HEADER */ 01080 /* version */ 01081 header.ver = htons( SIMCLIST_DUMPFORMAT_VERSION ); 01082 01083 /* timestamp */ 01084 gettimeofday(&timeofday, NULL); 01085 header.timestamp = (int64_t)timeofday.tv_sec * 1000000 + (int64_t)timeofday.tv_usec; 01086 header.timestamp = hton64(header.timestamp); 01087 01088 header.rndterm = htonl((int32_t)get_random()); 01089 01090 /* total list size is postprocessed afterwards */ 01091 01092 /* number of elements */ 01093 header.numels = htonl(l->numels); 01094 01095 /* include an hash, if possible */ 01096 if (l->attrs.hasher != NULL) { 01097 if (htonl(list_hash(l, & header.listhash)) != 0) { 01098 /* could not compute list hash! */ 01099 return -1; 01100 } 01101 } else { 01102 header.listhash = htonl(0); 01103 } 01104 01105 header.totlistlen = header.elemlen = 0; 01106 01107 /* leave room for the header at the beginning of the file */ 01108 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) { 01109 /* errno set by lseek() */ 01110 return -1; 01111 } 01112 01113 /* write CONTENT */ 01114 if (l->numels > 0) { 01115 /* SPECULATE that the list has constant element size */ 01116 01117 if (l->attrs.serializer != NULL) { /* user user-specified serializer */ 01118 /* get preliminary length of serialized element in header.elemlen */ 01119 ser_buf = l->attrs.serializer(l->head_sentinel->next->data, & header.elemlen); 01120 free(ser_buf); 01121 /* request custom serialization of each element */ 01122 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 01123 ser_buf = l->attrs.serializer(x->data, &bufsize); 01124 header.totlistlen += bufsize; 01125 if (header.elemlen != 0) { /* continue on speculation */ 01126 if (header.elemlen != bufsize) { 01127 free(ser_buf); 01128 /* constant element length speculation broken! */ 01129 header.elemlen = 0; 01130 header.totlistlen = 0; 01131 x = l->head_sentinel; 01132 if (lseek(fd, SIMCLIST_DUMPFORMAT_HEADERLEN, SEEK_SET) < 0) { 01133 /* errno set by lseek() */ 01134 return -1; 01135 } 01136 /* restart from the beginning */ 01137 continue; 01138 } 01139 /* speculation confirmed */ 01140 WRITE_ERRCHECK(fd, ser_buf, bufsize); 01141 } else { /* speculation found broken */ 01142 WRITE_ERRCHECK(fd, & bufsize, sizeof(size_t)); 01143 WRITE_ERRCHECK(fd, ser_buf, bufsize); 01144 } 01145 free(ser_buf); 01146 } 01147 } else if (l->attrs.meter != NULL) { 01148 header.elemlen = (uint32_t)l->attrs.meter(l->head_sentinel->next->data); 01149 01150 /* serialize the element straight from its data */ 01151 for (x = l->head_sentinel->next; x != l->tail_sentinel; x = x->next) { 01152 bufsize = l->attrs.meter(x->data); 01153 header.totlistlen += bufsize; 01154 if (header.elemlen != 0) { 01155 if (header.elemlen != bufsize) { 01156 /* constant element length speculation broken! */ 01157 header.elemlen = 0; 01158 header.totlistlen = 0; 01159 x = l->head_sentinel; 01160 /* restart from the beginning */ 01161 continue; 01162 } 01163 WRITE_ERRCHECK(fd, x->data, bufsize); 01164 } else { 01165 WRITE_ERRCHECK(fd, &bufsize, sizeof(size_t)); 01166 WRITE_ERRCHECK(fd, x->data, bufsize); 01167 } 01168 } 01169 } 01170 /* adjust endianness */ 01171 header.elemlen = htonl(header.elemlen); 01172 header.totlistlen = htonl(header.totlistlen); 01173 } 01174 01175 /* write random terminator */ 01176 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* list terminator */ 01177 01178 01179 /* write header */ 01180 lseek(fd, 0, SEEK_SET); 01181 01182 WRITE_ERRCHECK(fd, & header.ver, sizeof(header.ver)); /* version */ 01183 WRITE_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp)); /* timestamp */ 01184 WRITE_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); /* random terminator */ 01185 01186 WRITE_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); /* total length of elements */ 01187 WRITE_ERRCHECK(fd, & header.numels, sizeof(header.numels)); /* number of elements */ 01188 WRITE_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); /* size of each element, or 0 for independent */ 01189 WRITE_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); /* list hash, or 0 for "ignore" */ 01190 01191 01192 /* possibly store total written length in "len" */ 01193 if (len != NULL) { 01194 *len = sizeof(header) + ntohl(header.totlistlen); 01195 } 01196 01197 return 0; 01198 } 01199 01200 int list_restore_filedescriptor(list_t *restrict l, int fd, size_t *restrict len) { 01201 struct list_dump_header_s header; 01202 unsigned long cnt; 01203 void *buf; 01204 uint32_t elsize, totreadlen, totmemorylen; 01205 01206 memset(& header, 0, sizeof(header)); 01207 01208 /* read header */ 01209 01210 /* version */ 01211 READ_ERRCHECK(fd, &header.ver, sizeof(header.ver)); 01212 header.ver = ntohs(header.ver); 01213 if (header.ver != SIMCLIST_DUMPFORMAT_VERSION) { 01214 errno = EILSEQ; 01215 return -1; 01216 } 01217 01218 /* timestamp */ 01219 READ_ERRCHECK(fd, & header.timestamp, sizeof(header.timestamp)); 01220 01221 /* list terminator */ 01222 READ_ERRCHECK(fd, & header.rndterm, sizeof(header.rndterm)); 01223 01224 header.rndterm = ntohl(header.rndterm); 01225 01226 /* total list size */ 01227 READ_ERRCHECK(fd, & header.totlistlen, sizeof(header.totlistlen)); 01228 header.totlistlen = ntohl(header.totlistlen); 01229 01230 /* number of elements */ 01231 READ_ERRCHECK(fd, & header.numels, sizeof(header.numels)); 01232 header.numels = ntohl(header.numels); 01233 01234 /* length of every element, or '0' = variable */ 01235 READ_ERRCHECK(fd, & header.elemlen, sizeof(header.elemlen)); 01236 header.elemlen = ntohl(header.elemlen); 01237 01238 /* list hash, or 0 = 'ignore' */ 01239 READ_ERRCHECK(fd, & header.listhash, sizeof(header.listhash)); 01240 header.listhash = ntohl(header.listhash); 01241 01242 01243 /* read content */ 01244 totreadlen = totmemorylen = 0; 01245 if (header.elemlen > 0) { 01246 /* elements have constant size = header.elemlen */ 01247 if (l->attrs.unserializer != NULL) { 01248 /* use unserializer */ 01249 buf = malloc(header.elemlen); 01250 for (cnt = 0; cnt < header.numels; cnt++) { 01251 READ_ERRCHECK(fd, buf, header.elemlen); 01252 list_append(l, l->attrs.unserializer(buf, & elsize)); 01253 totmemorylen += elsize; 01254 } 01255 } else { 01256 /* copy verbatim into memory */ 01257 for (cnt = 0; cnt < header.numels; cnt++) { 01258 buf = malloc(header.elemlen); 01259 READ_ERRCHECK(fd, buf, header.elemlen); 01260 list_append(l, buf); 01261 } 01262 totmemorylen = header.numels * header.elemlen; 01263 } 01264 totreadlen = header.numels * header.elemlen; 01265 } else { 01266 /* elements have variable size. Each element is preceded by its size */ 01267 if (l->attrs.unserializer != NULL) { 01268 /* use unserializer */ 01269 for (cnt = 0; cnt < header.numels; cnt++) { 01270 READ_ERRCHECK(fd, & elsize, sizeof(elsize)); 01271 buf = malloc((size_t)elsize); 01272 READ_ERRCHECK(fd, buf, elsize); 01273 totreadlen += elsize; 01274 list_append(l, l->attrs.unserializer(buf, & elsize)); 01275 totmemorylen += elsize; 01276 } 01277 } else { 01278 /* copy verbatim into memory */ 01279 for (cnt = 0; cnt < header.numels; cnt++) { 01280 READ_ERRCHECK(fd, & elsize, sizeof(elsize)); 01281 buf = malloc(elsize); 01282 READ_ERRCHECK(fd, buf, elsize); 01283 totreadlen += elsize; 01284 list_append(l, buf); 01285 } 01286 totmemorylen = totreadlen; 01287 } 01288 } 01289 01290 READ_ERRCHECK(fd, &elsize, sizeof(elsize)); /* read list terminator */ 01291 elsize = ntohl(elsize); 01292 01293 /* possibly verify the list consistency */ 01294 /* wrt hash */ 01295 /* don't do that 01296 if (header.listhash != 0 && header.listhash != list_hash(l)) { 01297 errno = ECANCELED; 01298 return -1; 01299 } 01300 */ 01301 01302 /* wrt header */ 01303 if (totreadlen != header.totlistlen && (int32_t)elsize == header.rndterm) { 01304 errno = EPROTO; 01305 return -1; 01306 } 01307 01308 /* wrt file */ 01309 if (lseek(fd, 0, SEEK_CUR) != lseek(fd, 0, SEEK_END)) { 01310 errno = EPROTO; 01311 return -1; 01312 } 01313 01314 if (len != NULL) { 01315 *len = totmemorylen; 01316 } 01317 01318 return 0; 01319 } 01320 01321 int list_dump_file(const list_t *restrict l, const char *restrict filename, size_t *restrict len) { 01322 int fd; 01323 size_t sizetoret; 01324 01325 fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH); 01326 if (fd < 0) return -1; 01327 01328 sizetoret = list_dump_filedescriptor(l, fd, len); 01329 close(fd); 01330 01331 return sizetoret; 01332 } 01333 01334 int list_restore_file(list_t *restrict l, const char *restrict filename, size_t *restrict len) { 01335 int fd; 01336 size_t totdata; 01337 01338 fd = open(filename, O_RDONLY, 0); 01339 if (fd < 0) return -1; 01340 01341 totdata = list_restore_filedescriptor(l, fd, len); 01342 close(fd); 01343 01344 return totdata; 01345 } 01346 #endif /* ifndef SIMCLIST_NO_DUMPRESTORE */ 01347 01348 01349 static int list_drop_elem(list_t *restrict l, struct list_entry_s *tmp, unsigned int pos) { 01350 if (tmp == NULL) return -1; 01351 01352 /* fix mid pointer. This is wrt the PRE situation */ 01353 if (l->numels % 2) { /* now odd */ 01354 /* sort out the base case by hand */ 01355 if (l->numels == 1) l->mid = NULL; 01356 else if (pos >= l->numels/2) l->mid = l->mid->prev; 01357 } else { /* now even */ 01358 if (pos < l->numels/2) l->mid = l->mid->next; 01359 } 01360 01361 tmp->prev->next = tmp->next; 01362 tmp->next->prev = tmp->prev; 01363 01364 /* free what's to be freed */ 01365 if (l->attrs.copy_data && tmp->data != NULL) 01366 free(tmp->data); 01367 01368 if (l->spareelsnum < SIMCLIST_MAX_SPARE_ELEMS) { 01369 l->spareels[l->spareelsnum++] = tmp; 01370 } else { 01371 free(tmp); 01372 } 01373 01374 return 0; 01375 } 01376 01377 /* ready-made comparators and meters */ 01378 #define SIMCLIST_NUMBER_COMPARATOR(type) int list_comparator_##type(const void *a, const void *b) { return( *(type *)a < *(type *)b) - (*(type *)a > *(type *)b); } 01379 01380 SIMCLIST_NUMBER_COMPARATOR(int8_t) 01381 SIMCLIST_NUMBER_COMPARATOR(int16_t) 01382 SIMCLIST_NUMBER_COMPARATOR(int32_t) 01383 SIMCLIST_NUMBER_COMPARATOR(int64_t) 01384 01385 SIMCLIST_NUMBER_COMPARATOR(uint8_t) 01386 SIMCLIST_NUMBER_COMPARATOR(uint16_t) 01387 SIMCLIST_NUMBER_COMPARATOR(uint32_t) 01388 SIMCLIST_NUMBER_COMPARATOR(uint64_t) 01389 01390 SIMCLIST_NUMBER_COMPARATOR(float) 01391 SIMCLIST_NUMBER_COMPARATOR(double) 01392 01393 int list_comparator_string(const void *a, const void *b) { return strcmp((const char *)b, (const char *)a); } 01394 01395 /* ready-made metric functions */ 01396 #define SIMCLIST_METER(type) size_t list_meter_##type(const void *el) { if (el) { /* kill compiler whinge */ } return sizeof(type); } 01397 01398 SIMCLIST_METER(int8_t) 01399 SIMCLIST_METER(int16_t) 01400 SIMCLIST_METER(int32_t) 01401 SIMCLIST_METER(int64_t) 01402 01403 SIMCLIST_METER(uint8_t) 01404 SIMCLIST_METER(uint16_t) 01405 SIMCLIST_METER(uint32_t) 01406 SIMCLIST_METER(uint64_t) 01407 01408 SIMCLIST_METER(float) 01409 SIMCLIST_METER(double) 01410 01411 size_t list_meter_string(const void *el) { return strlen((const char *)el) + 1; } 01412 01413 /* ready-made hashing functions */ 01414 #define SIMCLIST_HASHCOMPUTER(type) list_hash_t list_hashcomputer_##type(const void *el) { return (list_hash_t)(*(type *)el); } 01415 01416 SIMCLIST_HASHCOMPUTER(int8_t) 01417 SIMCLIST_HASHCOMPUTER(int16_t) 01418 SIMCLIST_HASHCOMPUTER(int32_t) 01419 SIMCLIST_HASHCOMPUTER(int64_t) 01420 01421 SIMCLIST_HASHCOMPUTER(uint8_t) 01422 SIMCLIST_HASHCOMPUTER(uint16_t) 01423 SIMCLIST_HASHCOMPUTER(uint32_t) 01424 SIMCLIST_HASHCOMPUTER(uint64_t) 01425 01426 SIMCLIST_HASHCOMPUTER(float) 01427 SIMCLIST_HASHCOMPUTER(double) 01428 01429 list_hash_t list_hashcomputer_string(const void *el) { 01430 size_t l; 01431 list_hash_t hash = 123; 01432 const char *str = (const char *)el; 01433 char plus; 01434 01435 for (l = 0; str[l] != '\0'; l++) { 01436 if (l) plus = hash ^ str[l]; 01437 else plus = hash ^ (str[l] - str[0]); 01438 hash += (plus << (CHAR_BIT * (l % sizeof(list_hash_t)))); 01439 } 01440 01441 return hash; 01442 } 01443 01444 01445 #ifndef NDEBUG 01446 static int list_repOk(const list_t *restrict l) { 01447 int ok, i; 01448 struct list_entry_s *s; 01449 01450 ok = (l != NULL) && ( 01451 /* head/tail checks */ 01452 (l->head_sentinel != NULL && l->tail_sentinel != NULL) && 01453 (l->head_sentinel != l->tail_sentinel) && (l->head_sentinel->prev == NULL && l->tail_sentinel->next == NULL) && 01454 /* empty list */ 01455 (l->numels > 0 || (l->mid == NULL && l->head_sentinel->next == l->tail_sentinel && l->tail_sentinel->prev == l->head_sentinel)) && 01456 /* spare elements checks */ 01457 l->spareelsnum <= SIMCLIST_MAX_SPARE_ELEMS 01458 ); 01459 01460 if (!ok) return 0; 01461 01462 if (l->numels >= 1) { 01463 /* correct referencing */ 01464 for (i = -1, s = l->head_sentinel; i < (int)(l->numels-1)/2 && s->next != NULL; i++, s = s->next) { 01465 if (s->next->prev != s) break; 01466 } 01467 ok = (i == (int)(l->numels-1)/2 && l->mid == s); 01468 if (!ok) return 0; 01469 for (; s->next != NULL; i++, s = s->next) { 01470 if (s->next->prev != s) break; 01471 } 01472 ok = (i == (int)l->numels && s == l->tail_sentinel); 01473 } 01474 01475 return ok; 01476 } 01477 01478 static int list_attrOk(const list_t *restrict l) { 01479 int ok; 01480 01481 ok = (l->attrs.copy_data == 0 || l->attrs.meter != NULL); 01482 return ok; 01483 } 01484 01485 #endif 01486