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