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