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