1 /*
2 glib_compat.c replacement functionality for glib code used in qemu
3 Copyright (C) 2016 Chris Eagle cseagle at gmail dot com
4
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either version 2
8 of the License, or (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 */
19
20 // Part of this code was lifted from glib-2.28.0.
21 // Glib license is available in COPYING_GLIB file in root directory.
22
23 #ifndef _GNU_SOURCE
24 #define _GNU_SOURCE
25 #endif
26
27 #include <string.h>
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <limits.h>
31
32 #include "glib_compat.h"
33
34 #define MAX(a, b) (((a) > (b)) ? (a) : (b))
35 #ifndef _WIN64
36 #define GPOINTER_TO_UINT(p) ((guint)(uintptr_t)(p))
37 #else
38 #define GPOINTER_TO_UINT(p) ((guint) (guint64) (p))
39 #endif
40 #define G_MAXINT INT_MAX
41
42 /* All functions below added to eliminate GLIB dependency */
43
44 /* hashing and equality functions */
45 // Hash functions lifted glib-2.28.0/glib/ghash.c
46
47 /**
48 * g_direct_hash:
49 * @v: a #gpointer key
50 *
51 * Converts a gpointer to a hash value.
52 * It can be passed to g_hash_table_new() as the @hash_func parameter,
53 * when using pointers as keys in a #GHashTable.
54 *
55 * Returns: a hash value corresponding to the key.
56 */
g_direct_hash(gconstpointer v)57 static guint g_direct_hash (gconstpointer v)
58 {
59 return GPOINTER_TO_UINT (v);
60 }
61
62 // g_str_hash() is lifted glib-2.28.0/glib/gstring.c
63 /**
64 * g_str_hash:
65 * @v: a string key
66 *
67 * Converts a string to a hash value.
68 *
69 * This function implements the widely used "djb" hash apparently posted
70 * by Daniel Bernstein to comp.lang.c some time ago. The 32 bit
71 * unsigned hash value starts at 5381 and for each byte 'c' in the
72 * string, is updated: <literal>hash = hash * 33 + c</literal>. This
73 * function uses the signed value of each byte.
74 *
75 * It can be passed to g_hash_table_new() as the @hash_func parameter,
76 * when using strings as keys in a #GHashTable.
77 *
78 * Returns: a hash value corresponding to the key
79 **/
g_str_hash(gconstpointer v)80 guint g_str_hash (gconstpointer v)
81 {
82 const signed char *p;
83 guint32 h = 5381;
84
85 for (p = v; *p != '\0'; p++)
86 h = (h << 5) + h + *p;
87
88 return h;
89 }
90
g_str_equal(gconstpointer v1,gconstpointer v2)91 gboolean g_str_equal(gconstpointer v1, gconstpointer v2)
92 {
93 return strcmp((const char*)v1, (const char*)v2) == 0;
94 }
95
96 // g_int_hash() is lifted from glib-2.28.0/glib/gutils.c
97 /**
98 * g_int_hash:
99 * @v: a pointer to a #gint key
100 *
101 * Converts a pointer to a #gint to a hash value.
102 * It can be passed to g_hash_table_new() as the @hash_func parameter,
103 * when using pointers to integers values as keys in a #GHashTable.
104 *
105 * Returns: a hash value corresponding to the key.
106 */
g_int_hash(gconstpointer v)107 guint g_int_hash (gconstpointer v)
108 {
109 return *(const gint*) v;
110 }
111
g_int_equal(gconstpointer v1,gconstpointer v2)112 gboolean g_int_equal(gconstpointer v1, gconstpointer v2)
113 {
114 return *((const gint*)v1) == *((const gint*)v2);
115 }
116
117 /* Doubly-linked list */
118
g_list_first(GList * list)119 GList *g_list_first(GList *list)
120 {
121 if (list == NULL) return NULL;
122 while (list->prev) list = list->prev;
123 return list;
124 }
125
g_list_foreach(GList * list,GFunc func,gpointer user_data)126 void g_list_foreach(GList *list, GFunc func, gpointer user_data)
127 {
128 GList *lp;
129 for (lp = list; lp; lp = lp->next) {
130 (*func)(lp->data, user_data);
131 }
132 }
133
g_list_free(GList * list)134 void g_list_free(GList *list)
135 {
136 GList *lp, *next, *prev = NULL;
137 if (list) prev = list->prev;
138 for (lp = list; lp; lp = next) {
139 next = lp->next;
140 free(lp);
141 }
142 for (lp = prev; lp; lp = prev) {
143 prev = lp->prev;
144 free(lp);
145 }
146 }
147
g_list_insert_sorted(GList * list,gpointer data,GCompareFunc compare)148 GList *g_list_insert_sorted(GList *list, gpointer data, GCompareFunc compare)
149 {
150 GList *i;
151 GList *n = (GList*)g_malloc(sizeof(GList));
152 n->data = data;
153 if (list == NULL) {
154 n->next = n->prev = NULL;
155 return n;
156 }
157 for (i = list; i; i = i->next) {
158 n->prev = i->prev;
159 if ((*compare)(data, i->data) <= 0) {
160 n->next = i;
161 i->prev = n;
162 if (i == list) return n;
163 else return list;
164 }
165 }
166 n->prev = n->prev->next;
167 n->next = NULL;
168 n->prev->next = n;
169 return list;
170 }
171
g_list_prepend(GList * list,gpointer data)172 GList *g_list_prepend(GList *list, gpointer data)
173 {
174 GList *n = (GList*)g_malloc(sizeof(GList));
175 n->next = list;
176 n->prev = NULL;
177 n->data = data;
178 return n;
179 }
180
g_list_remove_link(GList * list,GList * llink)181 GList *g_list_remove_link(GList *list, GList *llink)
182 {
183 if (llink) {
184 if (llink == list) list = list->next;
185 if (llink->prev) llink->prev->next = llink->next;
186 if (llink->next) llink->next->prev = llink->prev;
187 }
188 return list;
189 }
190
191 // code copied from glib/glist.c, version 2.28.0
g_list_sort_merge(GList * l1,GList * l2,GFunc compare_func,gpointer user_data)192 static GList *g_list_sort_merge(GList *l1,
193 GList *l2,
194 GFunc compare_func,
195 gpointer user_data)
196 {
197 GList list, *l, *lprev;
198 gint cmp;
199
200 l = &list;
201 lprev = NULL;
202
203 while (l1 && l2)
204 {
205 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
206
207 if (cmp <= 0)
208 {
209 l->next = l1;
210 l1 = l1->next;
211 }
212 else
213 {
214 l->next = l2;
215 l2 = l2->next;
216 }
217 l = l->next;
218 l->prev = lprev;
219 lprev = l;
220 }
221 l->next = l1 ? l1 : l2;
222 l->next->prev = l;
223
224 return list.next;
225 }
226
g_list_sort_real(GList * list,GFunc compare_func,gpointer user_data)227 static GList *g_list_sort_real(GList *list,
228 GFunc compare_func,
229 gpointer user_data)
230 {
231 GList *l1, *l2;
232
233 if (!list)
234 return NULL;
235 if (!list->next)
236 return list;
237
238 l1 = list;
239 l2 = list->next;
240
241 while ((l2 = l2->next) != NULL)
242 {
243 if ((l2 = l2->next) == NULL)
244 break;
245 l1 = l1->next;
246 }
247 l2 = l1->next;
248 l1->next = NULL;
249
250 return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
251 g_list_sort_real (l2, compare_func, user_data),
252 compare_func,
253 user_data);
254 }
255
256 /**
257 * g_list_sort:
258 * @list: a #GList
259 * @compare_func: the comparison function used to sort the #GList.
260 * This function is passed the data from 2 elements of the #GList
261 * and should return 0 if they are equal, a negative value if the
262 * first element comes before the second, or a positive value if
263 * the first element comes after the second.
264 *
265 * Sorts a #GList using the given comparison function.
266 *
267 * Returns: the start of the sorted #GList
268 */
269 /**
270 * GCompareFunc:
271 * @a: a value.
272 * @b: a value to compare with.
273 * @Returns: negative value if @a < @b; zero if @a = @b; positive
274 * value if @a > @b.
275 *
276 * Specifies the type of a comparison function used to compare two
277 * values. The function should return a negative integer if the first
278 * value comes before the second, 0 if they are equal, or a positive
279 * integer if the first value comes after the second.
280 **/
g_list_sort(GList * list,GCompareFunc compare_func)281 GList *g_list_sort (GList *list, GCompareFunc compare_func)
282 {
283 return g_list_sort_real (list, (GFunc) compare_func, NULL);
284 }
285
286 /* END of g_list related functions */
287
288 /* Singly-linked list */
289
g_slist_append(GSList * list,gpointer data)290 GSList *g_slist_append(GSList *list, gpointer data)
291 {
292 GSList *head = list;
293 if (list) {
294 while (list->next) list = list->next;
295 list->next = (GSList*)g_malloc(sizeof(GSList));
296 list = list->next;
297 } else {
298 head = list = (GSList*)g_malloc(sizeof(GSList));
299 }
300 list->data = data;
301 list->next = NULL;
302 return head;
303 }
304
g_slist_foreach(GSList * list,GFunc func,gpointer user_data)305 void g_slist_foreach(GSList *list, GFunc func, gpointer user_data)
306 {
307 GSList *lp;
308 for (lp = list; lp; lp = lp->next) {
309 (*func)(lp->data, user_data);
310 }
311 }
312
g_slist_free(GSList * list)313 void g_slist_free(GSList *list)
314 {
315 GSList *lp, *next;
316 for (lp = list; lp; lp = next) {
317 next = lp->next;
318 free(lp);
319 }
320 }
321
g_slist_prepend(GSList * list,gpointer data)322 GSList *g_slist_prepend(GSList *list, gpointer data)
323 {
324 GSList *head = (GSList*)g_malloc(sizeof(GSList));
325 head->next = list;
326 head->data = data;
327 return head;
328 }
329
g_slist_sort_merge(GSList * l1,GSList * l2,GFunc compare_func,gpointer user_data)330 static GSList *g_slist_sort_merge (GSList *l1,
331 GSList *l2,
332 GFunc compare_func,
333 gpointer user_data)
334 {
335 GSList list, *l;
336 gint cmp;
337
338 l=&list;
339
340 while (l1 && l2)
341 {
342 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
343
344 if (cmp <= 0)
345 {
346 l=l->next=l1;
347 l1=l1->next;
348 }
349 else
350 {
351 l=l->next=l2;
352 l2=l2->next;
353 }
354 }
355 l->next= l1 ? l1 : l2;
356
357 return list.next;
358 }
359
g_slist_sort_real(GSList * list,GFunc compare_func,gpointer user_data)360 static GSList *g_slist_sort_real (GSList *list,
361 GFunc compare_func,
362 gpointer user_data)
363 {
364 GSList *l1, *l2;
365
366 if (!list)
367 return NULL;
368 if (!list->next)
369 return list;
370
371 l1 = list;
372 l2 = list->next;
373
374 while ((l2 = l2->next) != NULL)
375 {
376 if ((l2 = l2->next) == NULL)
377 break;
378 l1=l1->next;
379 }
380 l2 = l1->next;
381 l1->next = NULL;
382
383 return g_slist_sort_merge (g_slist_sort_real (list, compare_func, user_data),
384 g_slist_sort_real (l2, compare_func, user_data),
385 compare_func,
386 user_data);
387 }
388
389 /**
390 * g_slist_sort:
391 * @list: a #GSList
392 * @compare_func: the comparison function used to sort the #GSList.
393 * This function is passed the data from 2 elements of the #GSList
394 * and should return 0 if they are equal, a negative value if the
395 * first element comes before the second, or a positive value if
396 * the first element comes after the second.
397 *
398 * Sorts a #GSList using the given comparison function.
399 *
400 * Returns: the start of the sorted #GSList
401 */
g_slist_sort(GSList * list,GCompareFunc compare_func)402 GSList *g_slist_sort (GSList *list,
403 GCompareFunc compare_func)
404 {
405 return g_slist_sort_real (list, (GFunc) compare_func, NULL);
406 }
407
408 /* END of g_slist related functions */
409
410 // Hash functions lifted glib-2.28.0/glib/ghash.c
411
412 #define HASH_TABLE_MIN_SHIFT 3 /* 1 << 3 == 8 buckets */
413
414 typedef struct _GHashNode GHashNode;
415
416 struct _GHashNode {
417 gpointer key;
418 gpointer value;
419
420 /* If key_hash == 0, node is not in use
421 * If key_hash == 1, node is a tombstone
422 * If key_hash >= 2, node contains data */
423 guint key_hash;
424 };
425
426 struct _GHashTable {
427 gint size;
428 gint mod;
429 guint mask;
430 gint nnodes;
431 gint noccupied; /* nnodes + tombstones */
432 GHashNode *nodes;
433 GHashFunc hash_func;
434 GEqualFunc key_equal_func;
435 volatile gint ref_count;
436 GDestroyNotify key_destroy_func;
437 GDestroyNotify value_destroy_func;
438 };
439
440 /**
441 * g_hash_table_destroy:
442 * @hash_table: a #GHashTable.
443 *
444 * Destroys all keys and values in the #GHashTable and decrements its
445 * reference count by 1. If keys and/or values are dynamically allocated,
446 * you should either free them first or create the #GHashTable with destroy
447 * notifiers using g_hash_table_new_full(). In the latter case the destroy
448 * functions you supplied will be called on all keys and values during the
449 * destruction phase.
450 **/
g_hash_table_destroy(GHashTable * hash_table)451 void g_hash_table_destroy (GHashTable *hash_table)
452 {
453 if (hash_table == NULL) return;
454 if (hash_table->ref_count == 0) return;
455
456 g_hash_table_remove_all (hash_table);
457 g_hash_table_unref (hash_table);
458 }
459
460 /**
461 * g_hash_table_find:
462 * @hash_table: a #GHashTable.
463 * @predicate: function to test the key/value pairs for a certain property.
464 * @user_data: user data to pass to the function.
465 *
466 * Calls the given function for key/value pairs in the #GHashTable until
467 * @predicate returns %TRUE. The function is passed the key and value of
468 * each pair, and the given @user_data parameter. The hash table may not
469 * be modified while iterating over it (you can't add/remove items).
470 *
471 * Note, that hash tables are really only optimized for forward lookups,
472 * i.e. g_hash_table_lookup().
473 * So code that frequently issues g_hash_table_find() or
474 * g_hash_table_foreach() (e.g. in the order of once per every entry in a
475 * hash table) should probably be reworked to use additional or different
476 * data structures for reverse lookups (keep in mind that an O(n) find/foreach
477 * operation issued for all n values in a hash table ends up needing O(n*n)
478 * operations).
479 *
480 * Return value: The value of the first key/value pair is returned, for which
481 * func evaluates to %TRUE. If no pair with the requested property is found,
482 * %NULL is returned.
483 *
484 * Since: 2.4
485 **/
g_hash_table_find(GHashTable * hash_table,GHRFunc predicate,gpointer user_data)486 gpointer g_hash_table_find (GHashTable *hash_table,
487 GHRFunc predicate,
488 gpointer user_data)
489 {
490 gint i;
491
492 if (hash_table == NULL) return NULL;
493 if (predicate == NULL) return NULL;
494
495 for (i = 0; i < hash_table->size; i++)
496 {
497 GHashNode *node = &hash_table->nodes [i];
498
499 if (node->key_hash > 1 && predicate (node->key, node->value, user_data))
500 return node->value;
501 }
502
503 return NULL;
504 }
505
506 /**
507 * g_hash_table_foreach:
508 * @hash_table: a #GHashTable.
509 * @func: the function to call for each key/value pair.
510 * @user_data: user data to pass to the function.
511 *
512 * Calls the given function for each of the key/value pairs in the
513 * #GHashTable. The function is passed the key and value of each
514 * pair, and the given @user_data parameter. The hash table may not
515 * be modified while iterating over it (you can't add/remove
516 * items). To remove all items matching a predicate, use
517 * g_hash_table_foreach_remove().
518 *
519 * See g_hash_table_find() for performance caveats for linear
520 * order searches in contrast to g_hash_table_lookup().
521 **/
g_hash_table_foreach(GHashTable * hash_table,GHFunc func,gpointer user_data)522 void g_hash_table_foreach (GHashTable *hash_table,
523 GHFunc func,
524 gpointer user_data)
525 {
526 gint i;
527
528 if (hash_table == NULL) return;
529 if (func == NULL) return;
530
531 for (i = 0; i < hash_table->size; i++)
532 {
533 GHashNode *node = &hash_table->nodes [i];
534
535 if (node->key_hash > 1)
536 (* func) (node->key, node->value, user_data);
537 }
538 }
539
540 /*
541 * g_hash_table_lookup_node_for_insertion:
542 * @hash_table: our #GHashTable
543 * @key: the key to lookup against
544 * @hash_return: key hash return location
545 * Return value: index of the described #GHashNode
546 *
547 * Performs a lookup in the hash table, preserving extra information
548 * usually needed for insertion.
549 *
550 * This function first computes the hash value of the key using the
551 * user's hash function.
552 *
553 * If an entry in the table matching @key is found then this function
554 * returns the index of that entry in the table, and if not, the
555 * index of an unused node (empty or tombstone) where the key can be
556 * inserted.
557 *
558 * The computed hash value is returned in the variable pointed to
559 * by @hash_return. This is to save insertions from having to compute
560 * the hash record again for the new record.
561 */
g_hash_table_lookup_node_for_insertion(GHashTable * hash_table,gconstpointer key,guint * hash_return)562 static inline guint g_hash_table_lookup_node_for_insertion (GHashTable *hash_table,
563 gconstpointer key,
564 guint *hash_return)
565 {
566 GHashNode *node;
567 guint node_index;
568 guint hash_value;
569 guint first_tombstone = 0;
570 gboolean have_tombstone = FALSE;
571 guint step = 0;
572
573 /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.
574 * We need to make sure our hash value is not one of these. */
575
576 hash_value = (* hash_table->hash_func) (key);
577 if (hash_value <= 1)
578 hash_value = 2;
579
580 *hash_return = hash_value;
581
582 node_index = hash_value % hash_table->mod;
583 node = &hash_table->nodes [node_index];
584
585 while (node->key_hash)
586 {
587 /* We first check if our full hash values
588 * are equal so we can avoid calling the full-blown
589 * key equality function in most cases.
590 */
591
592 if (node->key_hash == hash_value)
593 {
594 if (hash_table->key_equal_func)
595 {
596 if (hash_table->key_equal_func (node->key, key))
597 return node_index;
598 }
599 else if (node->key == key)
600 {
601 return node_index;
602 }
603 }
604 else if (node->key_hash == 1 && !have_tombstone)
605 {
606 first_tombstone = node_index;
607 have_tombstone = TRUE;
608 }
609
610 step++;
611 node_index += step;
612 node_index &= hash_table->mask;
613 node = &hash_table->nodes [node_index];
614 }
615
616 if (have_tombstone)
617 return first_tombstone;
618
619 return node_index;
620 }
621
622 /* Each table size has an associated prime modulo (the first prime
623 * lower than the table size) used to find the initial bucket. Probing
624 * then works modulo 2^n. The prime modulo is necessary to get a
625 * good distribution with poor hash functions. */
626 static const gint prime_mod [] = {
627 1, /* For 1 << 0 */
628 2,
629 3,
630 7,
631 13,
632 31,
633 61,
634 127,
635 251,
636 509,
637 1021,
638 2039,
639 4093,
640 8191,
641 16381,
642 32749,
643 65521, /* For 1 << 16 */
644 131071,
645 262139,
646 524287,
647 1048573,
648 2097143,
649 4194301,
650 8388593,
651 16777213,
652 33554393,
653 67108859,
654 134217689,
655 268435399,
656 536870909,
657 1073741789,
658 2147483647 /* For 1 << 31 */
659 };
660
g_hash_table_set_shift(GHashTable * hash_table,gint shift)661 static void g_hash_table_set_shift (GHashTable *hash_table, gint shift)
662 {
663 gint i;
664 guint mask = 0;
665
666 hash_table->size = 1 << shift;
667 hash_table->mod = prime_mod [shift];
668
669 for (i = 0; i < shift; i++)
670 {
671 mask <<= 1;
672 mask |= 1;
673 }
674
675 hash_table->mask = mask;
676 }
677
g_hash_table_find_closest_shift(gint n)678 static gint g_hash_table_find_closest_shift (gint n)
679 {
680 gint i;
681
682 for (i = 0; n; i++)
683 n >>= 1;
684
685 return i;
686 }
687
g_hash_table_set_shift_from_size(GHashTable * hash_table,gint size)688 static void g_hash_table_set_shift_from_size (GHashTable *hash_table, gint size)
689 {
690 gint shift;
691
692 shift = g_hash_table_find_closest_shift (size);
693 shift = MAX (shift, HASH_TABLE_MIN_SHIFT);
694
695 g_hash_table_set_shift (hash_table, shift);
696 }
697
698 /*
699 * g_hash_table_resize:
700 * @hash_table: our #GHashTable
701 *
702 * Resizes the hash table to the optimal size based on the number of
703 * nodes currently held. If you call this function then a resize will
704 * occur, even if one does not need to occur. Use
705 * g_hash_table_maybe_resize() instead.
706 *
707 * This function may "resize" the hash table to its current size, with
708 * the side effect of cleaning up tombstones and otherwise optimizing
709 * the probe sequences.
710 */
g_hash_table_resize(GHashTable * hash_table)711 static void g_hash_table_resize (GHashTable *hash_table)
712 {
713 GHashNode *new_nodes;
714 gint old_size;
715 gint i;
716
717 old_size = hash_table->size;
718 g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);
719
720 new_nodes = g_new0 (GHashNode, hash_table->size);
721
722 for (i = 0; i < old_size; i++)
723 {
724 GHashNode *node = &hash_table->nodes [i];
725 GHashNode *new_node;
726 guint hash_val;
727 guint step = 0;
728
729 if (node->key_hash <= 1)
730 continue;
731
732 hash_val = node->key_hash % hash_table->mod;
733 new_node = &new_nodes [hash_val];
734
735 while (new_node->key_hash)
736 {
737 step++;
738 hash_val += step;
739 hash_val &= hash_table->mask; new_node = &new_nodes [hash_val];
740 }
741
742 *new_node = *node;
743 }
744
745 g_free (hash_table->nodes);
746 hash_table->nodes = new_nodes;
747 hash_table->noccupied = hash_table->nnodes;
748 }
749
750 /*
751 * g_hash_table_maybe_resize:
752 * @hash_table: our #GHashTable
753 *
754 * Resizes the hash table, if needed.
755 *
756 * Essentially, calls g_hash_table_resize() if the table has strayed
757 * too far from its ideal size for its number of nodes.
758 */
g_hash_table_maybe_resize(GHashTable * hash_table)759 static inline void g_hash_table_maybe_resize (GHashTable *hash_table)
760 {
761 gint noccupied = hash_table->noccupied;
762 gint size = hash_table->size;
763
764 if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
765 (size <= noccupied + (noccupied / 16)))
766 g_hash_table_resize (hash_table);
767 }
768
769 /*
770 * g_hash_table_insert_internal:
771 * @hash_table: our #GHashTable
772 * @key: the key to insert
773 * @value: the value to insert
774 * @keep_new_key: if %TRUE and this key already exists in the table
775 * then call the destroy notify function on the old key. If %FALSE
776 * then call the destroy notify function on the new key.
777 *
778 * Implements the common logic for the g_hash_table_insert() and
779 * g_hash_table_replace() functions.
780 *
781 * Do a lookup of @key. If it is found, replace it with the new
782 * @value (and perhaps the new @key). If it is not found, create a
783 * new node.
784 */
g_hash_table_insert_internal(GHashTable * hash_table,gpointer key,gpointer value,gboolean keep_new_key)785 static void g_hash_table_insert_internal (GHashTable *hash_table,
786 gpointer key,
787 gpointer value,
788 gboolean keep_new_key)
789 {
790 GHashNode *node;
791 guint node_index;
792 guint key_hash;
793 guint old_hash;
794
795 if (hash_table == NULL) return;
796 if (hash_table->ref_count == 0) return;
797
798 node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash);
799 node = &hash_table->nodes [node_index];
800
801 old_hash = node->key_hash;
802
803 if (old_hash > 1)
804 {
805 if (keep_new_key)
806 {
807 if (hash_table->key_destroy_func)
808 hash_table->key_destroy_func (node->key);
809 node->key = key;
810 }
811 else
812 {
813 if (hash_table->key_destroy_func)
814 hash_table->key_destroy_func (key);
815 }
816
817 if (hash_table->value_destroy_func)
818 hash_table->value_destroy_func (node->value);
819
820 node->value = value;
821 }
822 else
823 {
824 node->key = key;
825 node->value = value;
826 node->key_hash = key_hash;
827
828 hash_table->nnodes++;
829
830 if (old_hash == 0)
831 {
832 /* We replaced an empty node, and not a tombstone */
833 hash_table->noccupied++;
834 g_hash_table_maybe_resize (hash_table);
835 }
836 }
837 }
838
839 /**
840 * g_hash_table_insert:
841 * @hash_table: a #GHashTable.
842 * @key: a key to insert.
843 * @value: the value to associate with the key.
844 *
845 * Inserts a new key and value into a #GHashTable.
846 *
847 * If the key already exists in the #GHashTable its current value is replaced
848 * with the new value. If you supplied a @value_destroy_func when creating the
849 * #GHashTable, the old value is freed using that function. If you supplied
850 * a @key_destroy_func when creating the #GHashTable, the passed key is freed
851 * using that function.
852 **/
g_hash_table_insert(GHashTable * hash_table,gpointer key,gpointer value)853 void g_hash_table_insert (GHashTable *hash_table,
854 gpointer key,
855 gpointer value)
856 {
857 g_hash_table_insert_internal (hash_table, key, value, FALSE);
858 }
859
860 /*
861 * g_hash_table_lookup_node:
862 * @hash_table: our #GHashTable
863 * @key: the key to lookup against
864 * @hash_return: optional key hash return location
865 * Return value: index of the described #GHashNode
866 *
867 * Performs a lookup in the hash table. Virtually all hash operations
868 * will use this function internally.
869 *
870 * This function first computes the hash value of the key using the
871 * user's hash function.
872 *
873 * If an entry in the table matching @key is found then this function
874 * returns the index of that entry in the table, and if not, the
875 * index of an empty node (never a tombstone).
876 */
g_hash_table_lookup_node(GHashTable * hash_table,gconstpointer key)877 static inline guint g_hash_table_lookup_node (GHashTable *hash_table,
878 gconstpointer key)
879 {
880 GHashNode *node;
881 guint node_index;
882 guint hash_value;
883 guint step = 0;
884
885 /* Empty buckets have hash_value set to 0, and for tombstones, it's 1.
886 * We need to make sure our hash value is not one of these. */
887
888 hash_value = (* hash_table->hash_func) (key);
889 if (hash_value <= 1)
890 hash_value = 2;
891
892 node_index = hash_value % hash_table->mod;
893 node = &hash_table->nodes [node_index];
894
895 while (node->key_hash)
896 {
897 /* We first check if our full hash values
898 * are equal so we can avoid calling the full-blown
899 * key equality function in most cases.
900 */
901
902 if (node->key_hash == hash_value)
903 {
904 if (hash_table->key_equal_func)
905 {
906 if (hash_table->key_equal_func (node->key, key))
907 break;
908 }
909 else if (node->key == key)
910 {
911 break;
912 }
913 }
914
915 step++;
916 node_index += step;
917 node_index &= hash_table->mask;
918 node = &hash_table->nodes [node_index];
919 }
920
921 return node_index;
922 }
923
924 /**
925 * g_hash_table_lookup:
926 * @hash_table: a #GHashTable.
927 * @key: the key to look up.
928 *
929 * Looks up a key in a #GHashTable. Note that this function cannot
930 * distinguish between a key that is not present and one which is present
931 * and has the value %NULL. If you need this distinction, use
932 * g_hash_table_lookup_extended().
933 *
934 * Return value: the associated value, or %NULL if the key is not found.
935 **/
g_hash_table_lookup(GHashTable * hash_table,gconstpointer key)936 gpointer g_hash_table_lookup (GHashTable *hash_table,
937 gconstpointer key)
938 {
939 GHashNode *node;
940 guint node_index;
941
942 if (hash_table == NULL) return NULL;
943
944 node_index = g_hash_table_lookup_node (hash_table, key);
945 node = &hash_table->nodes [node_index];
946
947 return node->key_hash ? node->value : NULL;
948 }
949
950 /**
951 * g_hash_table_new:
952 * @hash_func: a function to create a hash value from a key.
953 * Hash values are used to determine where keys are stored within the
954 * #GHashTable data structure. The g_direct_hash(), g_int_hash(),
955 * g_int64_hash(), g_double_hash() and g_str_hash() functions are provided
956 * for some common types of keys.
957 * If hash_func is %NULL, g_direct_hash() is used.
958 * @key_equal_func: a function to check two keys for equality. This is
959 * used when looking up keys in the #GHashTable. The g_direct_equal(),
960 * g_int_equal(), g_int64_equal(), g_double_equal() and g_str_equal()
961 * functions are provided for the most common types of keys.
962 * If @key_equal_func is %NULL, keys are compared directly in a similar
963 * fashion to g_direct_equal(), but without the overhead of a function call.
964 *
965 * Creates a new #GHashTable with a reference count of 1.
966 *
967 * Return value: a new #GHashTable.
968 **/
g_hash_table_new(GHashFunc hash_func,GEqualFunc key_equal_func)969 GHashTable *g_hash_table_new(GHashFunc hash_func, GEqualFunc key_equal_func)
970 {
971 return g_hash_table_new_full(hash_func, key_equal_func, NULL, NULL);
972 }
973
974 /**
975 * g_hash_table_new_full:
976 * @hash_func: a function to create a hash value from a key.
977 * @key_equal_func: a function to check two keys for equality.
978 * @key_destroy_func: a function to free the memory allocated for the key
979 * used when removing the entry from the #GHashTable or %NULL if you
980 * don't want to supply such a function.
981 * @value_destroy_func: a function to free the memory allocated for the
982 * value used when removing the entry from the #GHashTable or %NULL if
983 * you don't want to supply such a function.
984 *
985 * Creates a new #GHashTable like g_hash_table_new() with a reference count
986 * of 1 and allows to specify functions to free the memory allocated for the
987 * key and value that get called when removing the entry from the #GHashTable.
988 *
989 * Return value: a new #GHashTable.
990 **/
g_hash_table_new_full(GHashFunc hash_func,GEqualFunc key_equal_func,GDestroyNotify key_destroy_func,GDestroyNotify value_destroy_func)991 GHashTable* g_hash_table_new_full (GHashFunc hash_func,
992 GEqualFunc key_equal_func,
993 GDestroyNotify key_destroy_func,
994 GDestroyNotify value_destroy_func)
995 {
996 GHashTable *hash_table;
997
998 hash_table = (GHashTable*)g_malloc(sizeof(GHashTable));
999 //hash_table = g_slice_new (GHashTable);
1000 g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);
1001 hash_table->nnodes = 0;
1002 hash_table->noccupied = 0;
1003 hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
1004 hash_table->key_equal_func = key_equal_func;
1005 hash_table->ref_count = 1;
1006 hash_table->key_destroy_func = key_destroy_func;
1007 hash_table->value_destroy_func = value_destroy_func;
1008 hash_table->nodes = g_new0 (GHashNode, hash_table->size);
1009
1010 return hash_table;
1011 }
1012
1013 /*
1014 * g_hash_table_remove_all_nodes:
1015 * @hash_table: our #GHashTable
1016 * @notify: %TRUE if the destroy notify handlers are to be called
1017 *
1018 * Removes all nodes from the table. Since this may be a precursor to
1019 * freeing the table entirely, no resize is performed.
1020 *
1021 * If @notify is %TRUE then the destroy notify functions are called
1022 * for the key and value of the hash node.
1023 */
g_hash_table_remove_all_nodes(GHashTable * hash_table,gboolean notify)1024 static void g_hash_table_remove_all_nodes (GHashTable *hash_table,
1025 gboolean notify)
1026 {
1027 int i;
1028
1029 for (i = 0; i < hash_table->size; i++)
1030 {
1031 GHashNode *node = &hash_table->nodes [i];
1032
1033 if (node->key_hash > 1)
1034 {
1035 if (notify && hash_table->key_destroy_func)
1036 hash_table->key_destroy_func (node->key);
1037
1038 if (notify && hash_table->value_destroy_func)
1039 hash_table->value_destroy_func (node->value);
1040 }
1041 }
1042
1043 /* We need to set node->key_hash = 0 for all nodes - might as well be GC
1044 * friendly and clear everything */
1045 memset (hash_table->nodes, 0, hash_table->size * sizeof (GHashNode));
1046
1047 hash_table->nnodes = 0;
1048 hash_table->noccupied = 0;
1049 }
1050
1051 /**
1052 * g_hash_table_remove_all:
1053 * @hash_table: a #GHashTable
1054 *
1055 * Removes all keys and their associated values from a #GHashTable.
1056 *
1057 * If the #GHashTable was created using g_hash_table_new_full(), the keys
1058 * and values are freed using the supplied destroy functions, otherwise you
1059 * have to make sure that any dynamically allocated values are freed
1060 * yourself.
1061 *
1062 * Since: 2.12
1063 **/
g_hash_table_remove_all(GHashTable * hash_table)1064 void g_hash_table_remove_all (GHashTable *hash_table)
1065 {
1066 if (hash_table == NULL) return;
1067
1068 g_hash_table_remove_all_nodes (hash_table, TRUE);
1069 g_hash_table_maybe_resize (hash_table);
1070 }
1071
1072 /*
1073 * g_hash_table_remove_node:
1074 * @hash_table: our #GHashTable
1075 * @node: pointer to node to remove
1076 * @notify: %TRUE if the destroy notify handlers are to be called
1077 *
1078 * Removes a node from the hash table and updates the node count.
1079 * The node is replaced by a tombstone. No table resize is performed.
1080 *
1081 * If @notify is %TRUE then the destroy notify functions are called
1082 * for the key and value of the hash node.
1083 */
g_hash_table_remove_node(GHashTable * hash_table,GHashNode * node,gboolean notify)1084 static void g_hash_table_remove_node (GHashTable *hash_table,
1085 GHashNode *node,
1086 gboolean notify)
1087 {
1088 if (notify && hash_table->key_destroy_func)
1089 hash_table->key_destroy_func (node->key);
1090
1091 if (notify && hash_table->value_destroy_func)
1092 hash_table->value_destroy_func (node->value);
1093
1094 /* Erect tombstone */
1095 node->key_hash = 1;
1096
1097 /* Be GC friendly */
1098 node->key = NULL;
1099 node->value = NULL;
1100
1101 hash_table->nnodes--;
1102 }
1103 /*
1104 * g_hash_table_remove_internal:
1105 * @hash_table: our #GHashTable
1106 * @key: the key to remove
1107 * @notify: %TRUE if the destroy notify handlers are to be called
1108 * Return value: %TRUE if a node was found and removed, else %FALSE
1109 *
1110 * Implements the common logic for the g_hash_table_remove() and
1111 * g_hash_table_steal() functions.
1112 *
1113 * Do a lookup of @key and remove it if it is found, calling the
1114 * destroy notify handlers only if @notify is %TRUE.
1115 */
g_hash_table_remove_internal(GHashTable * hash_table,gconstpointer key,gboolean notify)1116 static gboolean g_hash_table_remove_internal (GHashTable *hash_table,
1117 gconstpointer key,
1118 gboolean notify)
1119 {
1120 GHashNode *node;
1121 guint node_index;
1122
1123 if (hash_table == NULL) return FALSE;
1124
1125 node_index = g_hash_table_lookup_node (hash_table, key);
1126 node = &hash_table->nodes [node_index];
1127
1128 /* g_hash_table_lookup_node() never returns a tombstone, so this is safe */
1129 if (!node->key_hash)
1130 return FALSE;
1131
1132 g_hash_table_remove_node (hash_table, node, notify);
1133 g_hash_table_maybe_resize (hash_table);
1134
1135 return TRUE;
1136 }
1137 /**
1138 * g_hash_table_remove:
1139 * @hash_table: a #GHashTable.
1140 * @key: the key to remove.
1141 *
1142 * Removes a key and its associated value from a #GHashTable.
1143 *
1144 * If the #GHashTable was created using g_hash_table_new_full(), the
1145 * key and value are freed using the supplied destroy functions, otherwise
1146 * you have to make sure that any dynamically allocated values are freed
1147 * yourself.
1148 *
1149 * Return value: %TRUE if the key was found and removed from the #GHashTable.
1150 **/
g_hash_table_remove(GHashTable * hash_table,gconstpointer key)1151 gboolean g_hash_table_remove (GHashTable *hash_table,
1152 gconstpointer key)
1153 {
1154 return g_hash_table_remove_internal (hash_table, key, TRUE);
1155 }
1156
1157 /**
1158 * g_hash_table_unref:
1159 * @hash_table: a valid #GHashTable.
1160 *
1161 * Atomically decrements the reference count of @hash_table by one.
1162 * If the reference count drops to 0, all keys and values will be
1163 * destroyed, and all memory allocated by the hash table is released.
1164 * This function is MT-safe and may be called from any thread.
1165 *
1166 * Since: 2.10
1167 **/
g_hash_table_unref(GHashTable * hash_table)1168 void g_hash_table_unref (GHashTable *hash_table)
1169 {
1170 if (hash_table == NULL) return;
1171 if (hash_table->ref_count == 0) return;
1172
1173 hash_table->ref_count--;
1174 if (hash_table->ref_count == 0) {
1175 g_hash_table_remove_all_nodes (hash_table, TRUE);
1176 g_free (hash_table->nodes);
1177 g_free (hash_table);
1178 }
1179 }
1180
1181 /**
1182 * g_hash_table_ref:
1183 * @hash_table: a valid #GHashTable.
1184 *
1185 * Atomically increments the reference count of @hash_table by one.
1186 * This function is MT-safe and may be called from any thread.
1187 *
1188 * Return value: the passed in #GHashTable.
1189 *
1190 * Since: 2.10
1191 **/
g_hash_table_ref(GHashTable * hash_table)1192 GHashTable *g_hash_table_ref (GHashTable *hash_table)
1193 {
1194 if (hash_table == NULL) return NULL;
1195 if (hash_table->ref_count == 0) return hash_table;
1196
1197 //g_atomic_int_add (&hash_table->ref_count, 1);
1198 hash_table->ref_count++;
1199 return hash_table;
1200 }
1201
g_hash_table_size(GHashTable * hash_table)1202 guint g_hash_table_size(GHashTable *hash_table)
1203 {
1204 if (hash_table == NULL) return 0;
1205
1206 return hash_table->nnodes;
1207 }
1208
1209 /* END of g_hash_table related functions */
1210
1211 /* general g_XXX substitutes */
1212
g_free(gpointer ptr)1213 void g_free(gpointer ptr)
1214 {
1215 free(ptr);
1216 }
1217
g_malloc(size_t size)1218 gpointer g_malloc(size_t size)
1219 {
1220 void *res;
1221 if (size == 0) return NULL;
1222 res = malloc(size);
1223 if (res == NULL) exit(1);
1224 return res;
1225 }
1226
g_malloc0(size_t size)1227 gpointer g_malloc0(size_t size)
1228 {
1229 void *res;
1230 if (size == 0) return NULL;
1231 res = calloc(size, 1);
1232 if (res == NULL) exit(1);
1233 return res;
1234 }
1235
g_try_malloc0(size_t size)1236 gpointer g_try_malloc0(size_t size)
1237 {
1238 if (size == 0) return NULL;
1239 return calloc(size, 1);
1240 }
1241
g_realloc(gpointer ptr,size_t size)1242 gpointer g_realloc(gpointer ptr, size_t size)
1243 {
1244 void *res;
1245 if (size == 0) {
1246 free(ptr);
1247 return NULL;
1248 }
1249 res = realloc(ptr, size);
1250 if (res == NULL) exit(1);
1251 return res;
1252 }
1253
g_strdup(const char * str)1254 char *g_strdup(const char *str)
1255 {
1256 #ifdef _MSC_VER
1257 return str ? _strdup(str) : NULL;
1258 #else
1259 return str ? strdup(str) : NULL;
1260 #endif
1261 }
1262
g_strdup_printf(const char * format,...)1263 char *g_strdup_printf(const char *format, ...)
1264 {
1265 va_list ap;
1266 char *res;
1267 va_start(ap, format);
1268 res = g_strdup_vprintf(format, ap);
1269 va_end(ap);
1270 return res;
1271 }
1272
g_strdup_vprintf(const char * format,va_list ap)1273 char *g_strdup_vprintf(const char *format, va_list ap)
1274 {
1275 char *str_res = NULL;
1276 #ifdef _MSC_VER
1277 int len = _vscprintf(format, ap);
1278 if( len < 0 )
1279 return NULL;
1280 str_res = (char *)malloc(len+1);
1281 if(str_res==NULL)
1282 return NULL;
1283 vsnprintf(str_res, len+1, format, ap);
1284 #else
1285 int ret = vasprintf(&str_res, format, ap);
1286 if (ret == -1) {
1287 return NULL;
1288 }
1289 #endif
1290 return str_res;
1291 }
1292
g_strndup(const char * str,size_t n)1293 char *g_strndup(const char *str, size_t n)
1294 {
1295 /* try to mimic glib's g_strndup */
1296 char *res = calloc(n + 1, 1);
1297 strncpy(res, str, n);
1298 return res;
1299 }
1300
g_strfreev(char ** str_array)1301 void g_strfreev(char **str_array)
1302 {
1303 char **p = str_array;
1304 if (p) {
1305 while (*p) {
1306 free(*p++);
1307 }
1308 }
1309 free(str_array);
1310 }
1311
g_memdup(gconstpointer mem,size_t byte_size)1312 gpointer g_memdup(gconstpointer mem, size_t byte_size)
1313 {
1314 if (mem) {
1315 void *res = g_malloc(byte_size);
1316 memcpy(res, mem, byte_size);
1317 return res;
1318 }
1319 return NULL;
1320 }
1321
g_new_(size_t sz,size_t n_structs)1322 gpointer g_new_(size_t sz, size_t n_structs)
1323 {
1324 size_t need = sz * n_structs;
1325 if ((need / sz) != n_structs) return NULL;
1326 return g_malloc(need);
1327 }
1328
g_new0_(size_t sz,size_t n_structs)1329 gpointer g_new0_(size_t sz, size_t n_structs)
1330 {
1331 size_t need = sz * n_structs;
1332 if ((need / sz) != n_structs) return NULL;
1333 return g_malloc0(need);
1334 }
1335
g_renew_(size_t sz,gpointer mem,size_t n_structs)1336 gpointer g_renew_(size_t sz, gpointer mem, size_t n_structs)
1337 {
1338 size_t need = sz * n_structs;
1339 if ((need / sz) != n_structs) return NULL;
1340 return g_realloc(mem, need);
1341 }
1342
1343 /**
1344 * g_strconcat:
1345 * @string1: the first string to add, which must not be %NULL
1346 * @Varargs: a %NULL-terminated list of strings to append to the string
1347 *
1348 * Concatenates all of the given strings into one long string.
1349 * The returned string should be freed with g_free() when no longer needed.
1350 *
1351 * Note that this function is usually not the right function to use to
1352 * assemble a translated message from pieces, since proper translation
1353 * often requires the pieces to be reordered.
1354 *
1355 * <warning><para>The variable argument list <emphasis>must</emphasis> end
1356 * with %NULL. If you forget the %NULL, g_strconcat() will start appending
1357 * random memory junk to your string.</para></warning>
1358 *
1359 * Returns: a newly-allocated string containing all the string arguments
1360 */
g_strconcat(const gchar * string1,...)1361 gchar* g_strconcat (const gchar *string1, ...)
1362 {
1363 va_list ap;
1364 char *res;
1365 size_t sz = strlen(string1);
1366 va_start(ap, string1);
1367 while (1) {
1368 char *arg = va_arg(ap, char*);
1369 if (arg == NULL) break;
1370 sz += strlen(arg);
1371 }
1372 va_end(ap);
1373 res = g_malloc(sz + 1);
1374 strcpy(res, string1);
1375 va_start(ap, string1);
1376 while (1) {
1377 char *arg = va_arg(ap, char*);
1378 if (arg == NULL) break;
1379 strcat(res, arg);
1380 }
1381 va_end(ap);
1382 return res;
1383 }
1384
1385 /**
1386 * g_strsplit:
1387 * @string: a string to split.
1388 * @delimiter: a string which specifies the places at which to split the string.
1389 * The delimiter is not included in any of the resulting strings, unless
1390 * @max_tokens is reached.
1391 * @max_tokens: the maximum number of pieces to split @string into. If this is
1392 * less than 1, the string is split completely.
1393 *
1394 * Splits a string into a maximum of @max_tokens pieces, using the given
1395 * @delimiter. If @max_tokens is reached, the remainder of @string is appended
1396 * to the last token.
1397 *
1398 * As a special case, the result of splitting the empty string "" is an empty
1399 * vector, not a vector containing a single string. The reason for this
1400 * special case is that being able to represent a empty vector is typically
1401 * more useful than consistent handling of empty elements. If you do need
1402 * to represent empty elements, you'll need to check for the empty string
1403 * before calling g_strsplit().
1404 *
1405 * Return value: a newly-allocated %NULL-terminated array of strings. Use
1406 * g_strfreev() to free it.
1407 **/
g_strsplit(const gchar * string,const gchar * delimiter,gint max_tokens)1408 gchar** g_strsplit (const gchar *string,
1409 const gchar *delimiter,
1410 gint max_tokens)
1411 {
1412 GSList *string_list = NULL, *slist;
1413 gchar **str_array, *s;
1414 guint n = 0;
1415 const gchar *remainder;
1416
1417 if (string == NULL) return NULL;
1418 if (delimiter == NULL) return NULL;
1419 if (delimiter[0] == '\0') return NULL;
1420
1421 if (max_tokens < 1)
1422 max_tokens = G_MAXINT;
1423
1424 remainder = string;
1425 s = strstr (remainder, delimiter);
1426 if (s)
1427 {
1428 gsize delimiter_len = strlen (delimiter);
1429
1430 while (--max_tokens && s)
1431 {
1432 gsize len;
1433
1434 len = s - remainder;
1435 string_list = g_slist_prepend (string_list,
1436 g_strndup (remainder, len));
1437 n++;
1438 remainder = s + delimiter_len;
1439 s = strstr (remainder, delimiter);
1440 }
1441 }
1442 if (*string)
1443 {
1444 n++;
1445 string_list = g_slist_prepend (string_list, g_strdup (remainder));
1446 }
1447
1448 str_array = g_new (gchar*, n + 1);
1449
1450 str_array[n--] = NULL;
1451 for (slist = string_list; slist; slist = slist->next)
1452 str_array[n--] = slist->data;
1453
1454 g_slist_free (string_list);
1455
1456 return str_array;
1457 }
1458