1/* 2 * Copyright (c) 2003-2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24#include <stdlib.h> 25#include <string.h> 26#include <syslog.h> 27#include <sys/types.h> 28#include <os/assumes.h> 29#include "table.h" 30 31#define KEY_UNKNOWN 0 32#define KEY_INT 1 33#define KEY_STR_MINE 2 34#define KEY_STR_SHARED 3 35 36#define DEFAULT_SIZE 256 37 38typedef struct table_node_s 39{ 40 union 41 { 42 char *string; 43 const char *const_string; 44 uint64_t uint64; 45 } key; 46 void *datum; 47 struct table_node_s *next; 48} table_node_t; 49 50typedef struct __table_private 51{ 52 uint32_t type; 53 uint32_t bucket_count; 54 table_node_t **bucket; 55} table_private_t; 56 57typedef struct 58{ 59 uint32_t bucket_index; 60 table_node_t *node; 61} table_traverse_t; 62 63typedef struct __list_private 64{ 65 struct __list_private *prev; 66 struct __list_private *next; 67 uint32_t refcount; 68 void *data; 69} list_private_t; 70 71table_t * 72_nc_table_new(uint32_t n) 73{ 74 table_private_t *t; 75 76 t = (table_t *)malloc(sizeof(table_t)); 77 if (t == NULL) return NULL; 78 79 if (n == 0) n = DEFAULT_SIZE; 80 81 t->type = KEY_UNKNOWN; 82 t->bucket_count = n; 83 t->bucket = (table_node_t **)calloc(t->bucket_count, sizeof(table_node_t *)); 84 if (t->bucket == NULL) 85 { 86 free(t); 87 return NULL; 88 } 89 90 return (table_t *)t; 91} 92 93static uint32_t 94hash_key(int size, const char *key) 95{ 96 uint32_t v; 97 char *p; 98 99 if (key == NULL) return 0; 100 101 v = 0; 102 for (p = (char *)key; *p != '\0'; p++) 103 { 104 v = (v << 1) ^ (v ^ *p); 105 } 106 107 v %= size; 108 return v; 109} 110 111static uint32_t 112hash_nkey(uint32_t size, uint64_t key) 113{ 114 uint32_t x = key; 115 uint32_t y = key >> 32; 116 return ((x ^ y) % size); 117} 118 119void * 120_nc_table_find_get_key(table_t *tin, const char *key, const char **shared_key) 121{ 122 table_private_t *t; 123 table_node_t *n; 124 uint32_t b; 125 126 if (tin == NULL) return NULL; 127 if (key == NULL) return NULL; 128 129 if (shared_key != NULL) *shared_key = NULL; 130 131 t = (table_private_t *)tin; 132 b = hash_key(t->bucket_count, key); 133 134 for (n = t->bucket[b]; n != NULL; n = n->next) 135 { 136 if ((n->key.string != NULL) && (!strcmp(key, n->key.string))) 137 { 138 if (shared_key != NULL) *shared_key = n->key.const_string; 139 return n->datum; 140 } 141 } 142 143 return NULL; 144} 145 146void * 147_nc_table_find(table_t *tin, const char *key) 148{ 149 return _nc_table_find_get_key(tin, key, NULL); 150} 151 152void * 153_nc_table_find_64(table_t *tin, uint64_t key) 154{ 155 table_private_t *t; 156 table_node_t *n; 157 uint32_t b; 158 159 if (tin == NULL) return NULL; 160 161 t = (table_private_t *)tin; 162 b = hash_nkey(t->bucket_count, key); 163 164 for (n = t->bucket[b]; n != NULL; n = n->next) 165 { 166 if ((n->key.uint64 != (uint64_t)-1) && (key == n->key.uint64)) return n->datum; 167 } 168 169 return NULL; 170} 171 172void * 173_nc_table_find_n(table_t *tin, uint32_t key) 174{ 175 uint64_t n64 = key; 176 return _nc_table_find_64(tin, n64); 177} 178 179static void 180_nc_table_insert_type(table_t *tin, int type, char *key, const char *ckey, void *datum) 181{ 182 table_private_t *t; 183 table_node_t *n; 184 uint32_t b; 185 186 if (tin == NULL) return; 187 if ((key == NULL) && (ckey == NULL)) return; 188 if (datum == NULL) return; 189 190 t = (table_private_t *)tin; 191 if (t->type == KEY_UNKNOWN) t->type = type; 192 else os_assumes(t->type == type); 193 194 n = (table_node_t *)malloc(sizeof(table_node_t)); 195 196 if (key != NULL) 197 { 198 b = hash_key(t->bucket_count, key); 199 n->key.string = key; 200 } 201 else 202 { 203 b = hash_key(t->bucket_count, ckey); 204 n->key.const_string = ckey; 205 } 206 207 n->datum = datum; 208 n->next = t->bucket[b]; 209 t->bucket[b] = n; 210} 211 212void 213_nc_table_insert(table_t *tin, const char *key, void *datum) 214{ 215 char *dup; 216 217 if (tin == NULL) return; 218 if (key == NULL) return; 219 if (datum == NULL) return; 220 221 dup = strdup(key); 222 if (dup == NULL) return; 223 224 _nc_table_insert_type(tin, KEY_STR_MINE, dup, NULL, datum); 225} 226 227void 228_nc_table_insert_no_copy(table_t *tin, const char *key, void *datum) 229{ 230 if (tin == NULL) return; 231 if (key == NULL) return; 232 if (datum == NULL) return; 233 234 _nc_table_insert_type(tin, KEY_STR_SHARED, NULL, key, datum); 235} 236 237void 238_nc_table_insert_pass(table_t *tin, char *key, void *datum) 239{ 240 if (tin == NULL) return; 241 if (key == NULL) return; 242 if (datum == NULL) return; 243 244 _nc_table_insert_type(tin, KEY_STR_MINE, key, NULL, datum); 245} 246 247void 248_nc_table_insert_64(table_t *tin, uint64_t key, void *datum) 249{ 250 table_private_t *t; 251 table_node_t *n; 252 uint32_t b; 253 254 if (tin == NULL) return; 255 if (datum == NULL) return; 256 257 t = (table_private_t *)tin; 258 if (t->type == KEY_UNKNOWN) t->type = KEY_INT; 259 else os_assumes(t->type == KEY_INT); 260 261 b = hash_nkey(t->bucket_count, key); 262 n = (table_node_t *)malloc(sizeof(table_node_t)); 263 n->key.uint64 = key; 264 n->datum = datum; 265 n->next = t->bucket[b]; 266 t->bucket[b] = n; 267} 268 269void 270_nc_table_insert_n(table_t *tin, uint32_t key, void *datum) 271{ 272 uint64_t n64 = key; 273 _nc_table_insert_64(tin, n64, datum); 274} 275 276void 277_nc_table_delete(table_t *tin, const char *key) 278{ 279 table_private_t *t; 280 table_node_t *n, *p; 281 uint32_t b; 282 283 if (tin == NULL) return; 284 if (key == NULL) return; 285 286 t = (table_private_t *)tin; 287 os_assumes((t->type == KEY_STR_MINE) || (t->type == KEY_STR_SHARED)); 288 289 b = hash_key(t->bucket_count, key); 290 291 p = NULL; 292 for (n = t->bucket[b]; n != NULL; n = n->next) 293 { 294 if ((n->key.string != NULL) && (!strcmp(key, n->key.string))) 295 { 296 if (p == NULL) t->bucket[b] = n->next; 297 else p->next = n->next; 298 if (t->type == KEY_STR_MINE) free(n->key.string); 299 free(n); 300 return; 301 } 302 p = n; 303 } 304} 305 306void 307_nc_table_delete_64(table_t *tin, uint64_t key) 308{ 309 table_private_t *t; 310 table_node_t *n, *p; 311 uint32_t b; 312 313 if (tin == NULL) return; 314 315 t = (table_private_t *)tin; 316 os_assumes(t->type == KEY_INT); 317 318 b = hash_nkey(t->bucket_count, key); 319 320 p = NULL; 321 for (n = t->bucket[b]; n != NULL; n = n->next) 322 { 323 if ((n->key.uint64 != (uint64_t)-1) && (key == n->key.uint64)) 324 { 325 if (p == NULL) t->bucket[b] = n->next; 326 else p->next = n->next; 327 free(n); 328 return; 329 } 330 p = n; 331 } 332} 333 334void 335_nc_table_delete_n(table_t *tin, uint32_t key) 336{ 337 uint64_t n64 = key; 338 _nc_table_delete_64(tin, n64); 339} 340 341void * 342_nc_table_traverse_start(table_t *tin) 343{ 344 table_traverse_t *tt; 345 table_private_t *t; 346 uint32_t b; 347 348 if (tin == NULL) return NULL; 349 350 t = (table_private_t *)tin; 351 if (t->bucket_count == 0) return NULL; 352 353 for (b = 0; b < t->bucket_count; b++) 354 { 355 if (t->bucket[b] != NULL) 356 { 357 tt = (table_traverse_t *)malloc(sizeof(table_traverse_t)); 358 if (tt == NULL) return NULL; 359 tt->bucket_index = b; 360 tt->node = t->bucket[b]; 361 return (void *)tt; 362 } 363 } 364 365 return NULL; 366} 367 368void * 369_nc_table_traverse(table_t *tin, void *ttin) 370{ 371 table_private_t *t; 372 table_traverse_t *tt; 373 void *datum; 374 uint32_t b; 375 376 if (tin == NULL) return NULL; 377 if (ttin == NULL) return NULL; 378 379 t = (table_private_t *)tin; 380 tt = (table_traverse_t *)ttin; 381 382 if (tt->node == NULL) return NULL; 383 384 datum = tt->node->datum; 385 tt->node = tt->node->next; 386 if (tt->node != NULL) return datum; 387 388 for (b = tt->bucket_index + 1; b < t->bucket_count; b++) 389 { 390 if (t->bucket[b] != NULL) 391 { 392 tt->bucket_index = b; 393 tt->node = t->bucket[b]; 394 return datum; 395 } 396 } 397 398 tt->bucket_index = b; 399 tt->node = NULL; 400 401 return datum; 402} 403 404void 405_nc_table_traverse_end(table_t *tin, void *ttin) 406{ 407 if (ttin == NULL) return; 408 free(ttin); 409} 410 411void 412_nc_table_free(table_t *tin) 413{ 414 table_private_t *t; 415 table_node_t *n, *x; 416 uint32_t b; 417 418 if (tin == NULL) return; 419 420 t = (table_private_t *)tin; 421 422 for (b = 0; b < t->bucket_count; b++) 423 { 424 x = NULL; 425 for (n = t->bucket[b]; n != NULL; n = x) 426 { 427 x = n->next; 428 if (t->type == KEY_STR_MINE) free(n->key.string); 429 free(n); 430 } 431 } 432 433 free(t->bucket); 434 free(t); 435} 436 437/* Linked List */ 438 439/* 440 * Make a new node 441 */ 442list_t * 443_nc_list_new(void *d) 444{ 445 list_t *n; 446 447 n = (list_t *)calloc(1, sizeof(list_t)); 448 if (n == NULL) return NULL; 449 450 n->refcount = 1; 451 n->data = d; 452 return n; 453} 454 455/* 456 * Release a node 457 */ 458void 459_nc_list_release(list_t *l) 460{ 461 if (l == NULL) return; 462 l->refcount--; 463 if (l->refcount > 0) return; 464 465 free(l); 466} 467 468/* 469 * Retain a node 470 */ 471list_t * 472_nc_list_retain(list_t *l) 473{ 474 if (l == NULL) return NULL; 475 l->refcount++; 476 return l; 477} 478 479/* 480 * Retain a list 481 */ 482list_t * 483_nc_list_retain_list(list_t *l) 484{ 485 list_t *n; 486 487 for (n = l; n != NULL; n = n->next) n->refcount++; 488 return l; 489} 490 491/* 492 * Get previous node 493 */ 494list_t * 495_nc_list_prev(list_t *l) 496{ 497 if (l == NULL) return NULL; 498 return l->prev; 499} 500 501/* 502 * Get next node 503 */ 504list_t * 505_nc_list_next(list_t *l) 506{ 507 if (l == NULL) return NULL; 508 return l->next; 509} 510 511/* 512 * Get head (first node) of list 513 */ 514list_t * 515_nc_list_head(list_t *l) 516{ 517 list_t *p; 518 519 if (l == NULL) return NULL; 520 521 for (p = l; p->prev != NULL; p = p->prev); 522 523 return p; 524} 525 526/* 527 * Get tail (last node) of list 528 */ 529list_t * 530_nc_list_tail(list_t *l) 531{ 532 list_t *p; 533 534 if (l == NULL) return NULL; 535 536 for (p = l; p->next != NULL; p = p->next); 537 538 return p; 539} 540 541/* 542 * Insert a node in front of another node. 543 * Cuts list if n is NULL. 544 */ 545list_t * 546_nc_list_prepend(list_t *l, list_t *n) 547{ 548 if (l == NULL) return n; 549 550 if (n != NULL) 551 { 552 n->next = l; 553 n->prev = l->prev; 554 } 555 556 if (l->prev != NULL) l->prev->next = n; 557 l->prev = n; 558 559 return n; 560} 561 562/* 563 * Append a node after another node. 564 * Cuts list if n is NULL. 565 */ 566list_t * 567_nc_list_append(list_t *l, list_t *n) 568{ 569 if (l == NULL) return n; 570 571 if (n != NULL) 572 { 573 n->prev = l; 574 n->next = l->next; 575 } 576 577 if (l->next != NULL) n->next->prev = n; 578 l->next = n; 579 580 return n; 581} 582 583/* 584 * Set next pointer - use with care. 585 */ 586void 587_nc_list_set_next(list_t *l, list_t *n) 588{ 589 if (l == NULL) return; 590 l->next = n; 591} 592 593/* 594 * Set prev pointer - use with care. 595 */ 596void 597_nc_list_set_prev(list_t *l, list_t *p) 598{ 599 if (l == NULL) return; 600 l->prev = p; 601} 602 603/* 604 * Concatenate two lists. 605 * Returns new head. 606 */ 607list_t * 608_nc_list_concat(list_t *a, list_t *b) 609{ 610 list_t *p; 611 612 if (a == NULL) return b; 613 if (b == NULL) return a; 614 615 for (p = a; p->next != NULL; p = p->next); 616 617 p->next = b; 618 b->prev = p; 619 620 for (p = a; p->prev != NULL; p = p->prev); 621 622 return p; 623} 624 625uint32_t 626_nc_list_count(list_t *l) 627{ 628 uint32_t n; 629 list_t *p; 630 631 n = 0; 632 for (p = l; p != NULL; p = p->next) n++; 633 return n; 634} 635 636void * 637_nc_list_data(list_t *l) 638{ 639 if (l == NULL) return NULL; 640 return l->data; 641} 642 643void 644_nc_list_set_data(list_t *l, void *d) 645{ 646 if (l != NULL) l->data = d; 647} 648 649list_t * 650_nc_list_find(list_t *l, void *d) 651{ 652 list_t *p; 653 654 if (l == NULL) return NULL; 655 656 for (p = l; p != NULL; p = p->next) 657 { 658 if (p->data == d) return p; 659 } 660 661 return NULL; 662} 663 664list_t * 665_nc_list_find_release(list_t *l, void *d) 666{ 667 list_t *p; 668 669 if (l == NULL) return NULL; 670 671 if (l->data == d) 672 { 673 p = l->next; 674 if (p != NULL) p->prev = NULL; 675 _nc_list_release(l); 676 return p; 677 } 678 679 for (p = l->next; p != NULL; p = p->next) 680 { 681 if (p->data == d) 682 { 683 p->prev->next = p->next; 684 if (p->next != NULL) p->next->prev = p->prev; 685 _nc_list_release(p); 686 return l; 687 } 688 } 689 690 return l; 691} 692 693list_t * 694_nc_list_reverse(list_t *l) 695{ 696 list_t *x, *s, *r; 697 698 if (l == NULL) return NULL; 699 700 x = l->prev; 701 r = l; 702 s = l->next; 703 704 while (s != NULL) 705 { 706 s = r->next; 707 r->next = r->prev; 708 r->prev = s; 709 if (s != NULL) r = s; 710 } 711 712 if (x != NULL) 713 { 714 x->next = r; 715 r->prev = x; 716 } 717 718 return r; 719} 720 721list_t * 722_nc_list_extract(list_t *n) 723{ 724 if (n == NULL) return NULL; 725 726 if (n->prev != NULL) n->prev->next = n->next; 727 if (n->next != NULL) n->next->prev = n->prev; 728 729 n->prev = NULL; 730 n->next = NULL; 731 732 return n; 733} 734 735list_t * 736_nc_list_chop(list_t *l) 737{ 738 list_t *p; 739 740 if (l == NULL) return NULL; 741 p = l->next; 742 if (p != NULL) p->prev = NULL; 743 744 _nc_list_release(l); 745 return p; 746} 747 748void 749_nc_list_release_list(list_t *l) 750{ 751 list_t *p, *n; 752 753 if (l == NULL) return; 754 if (l->prev != NULL) l->prev->next = NULL; 755 756 p = l; 757 while (p != NULL) 758 { 759 n = p->next; 760 _nc_list_release(p); 761 p = n; 762 } 763} 764