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