1// Copyright 2014 The Android Open Source Project
2//
3// This software is licensed under the terms of the GNU General Public
4// License version 2, as published by the Free Software Foundation, and
5// may be copied, distributed, and modified under those terms.
6//
7// This program is distributed in the hope that it will be useful,
8// but WITHOUT ANY WARRANTY; without even the implied warranty of
9// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10// GNU General Public License for more details.
11
12#include <glib.h>
13
14#include <limits.h>
15#include <stdarg.h>
16#include <stdio.h>
17#include <stdlib.h>
18#include <stdint.h>
19#include <string.h>
20
21// Print a panic message then exit the program immediately.
22void g_critical(const char* fmt, ...) {
23  va_list args;
24  fprintf(stderr, "CRITICAL: ");
25  va_start(args, fmt);
26  vfprintf(stderr, fmt, args);
27  va_end(args);
28}
29
30void g_panic(const char* fmt, ...) {
31  va_list args;
32  fprintf(stderr, "PANIC: ");
33  va_start(args, fmt);
34  vfprintf(stderr, fmt, args);
35  va_end(args);
36  exit(1);
37}
38
39// Heap allocation.
40
41void* g_malloc(size_t size) {
42  if (size == 0)
43    return NULL;
44
45  void* ptr = malloc(size);
46  if (ptr == NULL)
47    g_panic("Can't allocate %zu bytes!\n", size);
48
49  return ptr;
50}
51
52
53void* g_malloc0(size_t size) {
54  void* ptr = g_malloc(size);
55  if (ptr == NULL)
56    return NULL;
57
58  memset(ptr, 0, size);
59  return ptr;
60}
61
62
63void* g_realloc(void* ptr, size_t size) {
64  if (size == 0) {
65    g_free(ptr);
66    return NULL;
67  }
68  void* new_ptr = realloc(ptr, size);
69  if (new_ptr == NULL)
70    g_panic("Can't reallocate pointer %p to %zu bytes!\n", ptr, size);
71
72  return new_ptr;
73}
74
75
76void g_free(void* ptr) {
77  if (ptr)
78    free(ptr);
79}
80
81// Strings.
82
83char* g_strdup(const char* str) {
84  if (str == NULL)
85    return NULL;
86
87  size_t len = strlen(str);
88  char* copy = g_malloc(len + 1);
89  memcpy(copy, str, len + 1);
90  return copy;
91}
92
93
94char* g_strndup(const char* str, size_t size) {
95  const char *end = memchr(str, 0, size);
96  char *copy;
97
98  if (end)
99    size = end - str;
100
101  copy = g_malloc(size + 1);
102  memcpy(copy, str, size);
103  copy[size] = 0;
104  return copy;
105}
106
107
108char* g_strdup_printf(const char* fmt, ...) {
109  char* result;
110  va_list args;
111  va_start(args, fmt);
112  g_vasprintf(&result, fmt, args);
113  va_end(args);
114  return result;
115}
116
117
118char* g_strdup_vprintf(const char* fmt, va_list args) {
119  char* result;
120  g_vasprintf(&result, fmt, args);
121  return result;
122}
123
124
125int g_vasprintf(char** str, const char* fmt, va_list args) {
126#ifdef _WIN32
127  // On Win32, vsnprintf() is broken and always returns -1 in case of truncation,
128  // so make an educated guess, and try again if that fails with a larger pool.
129  size_t capacity = 128;
130  char* buffer = g_malloc(capacity);
131  for (;;) {
132    va_list args2;
133    va_copy(args2, args);
134    int len = vsnprintf(buffer, capacity, fmt, args2);
135    if (len >= 0) {
136      *str = buffer;
137      return len;
138    }
139    va_end(args2);
140
141    capacity *= 2;
142    if (capacity > INT_MAX)
143      g_panic("Formatted string is too long!\n");
144
145    buffer = g_realloc(buffer, capacity);
146  }
147#else
148  // On other systems, vsnprintf() works properly and returns the size of the
149  // formatted string without truncation.
150  va_list args2;
151  va_copy(args2, args);
152  int len = vsnprintf(NULL, 0, fmt, args2);
153  va_end(args2);
154  if (len < 0)
155    g_panic("Can't format string!\n");
156
157  char* result = g_malloc(len + 1);
158  va_copy(args2, args);
159  vsnprintf(result, (size_t)len, fmt, args2);
160  va_end(args2);
161
162  *str = result;
163  return len;
164#endif
165}
166
167char** g_strsplit(const char* string, const char* delim, int max_tokens) {
168  // Sanity checks.
169  if (!string || !delim || !*delim)
170    return NULL;
171
172  if (max_tokens < 1)
173    max_tokens = INT_MAX;
174
175  // Create empty list of results.
176  GSList* string_list = NULL;
177  guint n = 0;
178
179  if (*string) {
180    // Input list is not empty, so try to split it.
181    const char* remainder = string;
182    const char* s = strstr(remainder, delim);
183    if (s) {
184      size_t delim_len = strlen(delim);
185      while (--max_tokens && s) {
186        size_t len = s - remainder;
187        string_list = g_slist_prepend(string_list, g_strndup(remainder, len));
188        n++;
189        remainder = s + delim_len;
190        s = strstr(remainder, delim);
191      }
192    }
193    n++;
194    string_list = g_slist_prepend(string_list, g_strdup(remainder));
195  }
196
197  // Convert list into NULL-terminated vector.
198  char** result = g_new(char*, n + 1);
199  result[n--] = NULL;
200  GSList* slist = string_list;
201  while (slist) {
202    result[n--] = slist->data;
203    slist = slist->next;
204  }
205  g_slist_free(string_list);
206
207  return result;
208}
209
210void g_strfreev(char** strings) {
211  guint n;
212  for (n = 0; strings[n]; ++n) {
213    g_free(strings[n]);
214  }
215  g_free(strings);
216}
217
218gboolean g_str_equal(const void* v1, const void* v2) {
219  return !strcmp((const char*)v1, (const char*)v2);
220}
221
222guint g_str_hash(const void* str) {
223  const signed char* p = str;
224  guint hash = 5381U;
225
226  for (; *p; ++p)
227    hash = (hash << 5) + hash + (guint)*p;
228
229  return hash;
230}
231
232// Single-linked list
233
234static GSList* _g_slist_alloc(void) {
235  return (GSList*) g_malloc(sizeof(GSList));
236}
237
238void g_slist_free(GSList* list) {
239  while (list) {
240    GSList* next = list->next;
241    g_free(list);
242    list = next;
243  }
244}
245
246GSList* g_slist_last(GSList* list) {
247  while (list && list->next)
248    list = list->next;
249  return list;
250}
251
252GSList* g_slist_find(GSList* list, const void* data) {
253  while (list) {
254    if (list->data == data)
255      break;
256    list = list->next;
257  }
258  return list;
259}
260
261GSList* g_slist_append(GSList* list, void* data) {
262  GSList* new_list = _g_slist_alloc();
263  new_list->data = data;
264  new_list->next = NULL;
265
266  if (!list)
267    return new_list;
268
269  GSList* last = g_slist_last(list);
270  last->next = new_list;
271  return list;
272}
273
274GSList* g_slist_prepend(GSList* list, void* data) {
275  GSList* new_list = _g_slist_alloc();
276  new_list->data = data;
277  new_list->next = list;
278  return new_list;
279}
280
281GSList* g_slist_remove(GSList* list, const void* data) {
282  GSList** pnode = &list;
283  for (;;) {
284    GSList* node = *pnode;
285    if (!node)
286      break;
287    if (node->data == data) {
288      *pnode = node->next;
289      g_slist_free(node);
290      break;
291    }
292    pnode = &node->next;
293  }
294  return list;
295}
296
297void g_slist_foreach(GSList* list, GFunc func, void* user_data) {
298  while (list) {
299    GSList* next = list->next;
300    (*func)(list->data, user_data);
301    list = next;
302  }
303}
304
305//
306static GSList* g_slist_sort_merge(GSList* l1,
307                                  GSList* l2,
308                                  GFunc compare_func,
309                                  void* user_data) {
310  GSList* list = NULL;
311  GSList** tail = &list;
312
313  while (l1 && l2) {
314    int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data);
315    if (cmp <= 0) {
316      *tail = l1;
317      tail = &l1->next;
318      l1 = l1->next;
319    } else {
320      *tail = l2;
321      tail = &l2->next;
322      l2 = l2->next;
323    }
324  }
325  *tail = l1 ? l1 : l2;
326
327  return list;
328}
329
330static GSList* g_slist_sort_real(GSList* list,
331                                 GFunc compare_func,
332                                 void* user_data) {
333
334  if (!list)
335    return NULL;
336  if (!list->next)
337    return list;
338
339  // Split list into two halves.
340  GSList* l1 = list;
341  GSList* l2 = list->next;
342
343  while (l2->next && l2->next->next) {
344    l2 = l2->next->next;
345    l1 = l1->next;
346  }
347  l2 = l1->next;
348  l1->next = NULL;
349
350  return g_slist_sort_merge(
351      g_slist_sort_real(list, compare_func, user_data),
352      g_slist_sort_real(l2, compare_func, user_data),
353      compare_func,
354      user_data);
355}
356
357GSList* g_slist_sort(GSList* list, GCompareFunc compare_func) {
358  return g_slist_sort_real(list, (GFunc) compare_func, NULL);
359}
360
361// Atomic operations
362
363#if !_WIN32
364// Note: Windows implementation in glib-mini-win32.c
365
366void g_atomic_int_inc(int volatile* atomic) {
367  __sync_fetch_and_add(atomic, 1);
368}
369
370gboolean g_atomic_int_dec_and_test(int volatile* atomic) {
371  return __sync_fetch_and_add(atomic, -1) == 1;
372}
373#endif  // !_WIN32
374
375// Hash Tables
376
377// This is a rather vanilla implementation, slightly simpler
378// than the GLib one, since QEMU doesn't require the full features:
379//
380// - Uses a single dynamic array of (key,value,hash) tuples.
381// - Array capacity is always 2^N
382// - No use of modulo primes for simplicity, we don't expect
383//   QEMU/QAPI to degenerate here.
384// - Dumb container only: doesn't own and free keys and values.
385// - No optimization for sets (i.e. when key == value for each entry).
386// - No iterators.
387//
388typedef struct {
389  gpointer key;
390  gpointer value;
391  guint    hash;
392} GHashEntry;
393
394#define HASH_UNUSED    0   // Must be 0, see _remove_all() below.
395#define HASH_TOMBSTONE 1
396#define HASH_IS_REAL(h)  ((h) >= 2)
397
398#define HASH_MIN_SHIFT  3
399#define HASH_MIN_CAPACITY  (1 << HASH_MIN_SHIFT)
400
401#define HASH_LOAD_SCALE 1024
402#define HASH_MIN_LOAD   256
403#define HASH_MAX_LOAD   768
404
405struct _GHashTable {
406  int ref_count;
407  int num_items;
408  int num_used;  // count of items + tombstones
409  int capacity;
410  GHashEntry* entries;
411  GHashFunc hash_func;
412  GEqualFunc key_equal_func;
413};
414
415// Default hash function for pointers.
416static guint _gpointer_hash(gconstpointer key) {
417    return (guint)(uintptr_t)key;
418}
419
420// Compute the hash value of a given key.
421static inline size_t
422_g_hash_table_hash(GHashTable* table, gconstpointer key) {
423  size_t hash = table->hash_func(key);
424  return HASH_IS_REAL(hash) ? hash : 2;
425}
426
427
428GHashTable* g_hash_table_new(GHashFunc hash_func,
429                             GEqualFunc key_equal_func) {
430  GHashTable* hash_table = g_new0(GHashTable, 1);
431
432  hash_table->ref_count = 1;
433  hash_table->num_items = 0;
434  hash_table->capacity = HASH_MIN_CAPACITY;
435  hash_table->entries = g_new0(GHashEntry, hash_table->capacity);
436  hash_table->hash_func = hash_func ? hash_func : &_gpointer_hash;
437  hash_table->key_equal_func = key_equal_func;
438
439  return hash_table;
440}
441
442
443static void _g_hash_table_remove_all(GHashTable* hash_table) {
444  // NOTE: This uses the fact that HASH_UNUSED is 0!
445  hash_table->num_items = 0;
446  memset(hash_table->entries,
447         0,
448         sizeof(hash_table->entries[0]) * hash_table->capacity);
449}
450
451
452GHashTable* g_hash_table_ref(GHashTable* hash_table) {
453  if (!hash_table)
454    return NULL;
455
456  g_atomic_int_inc(&hash_table->ref_count);
457  return hash_table;
458}
459
460
461void g_hash_table_unref(GHashTable* hash_table) {
462  if (!hash_table)
463    return;
464
465  if (!g_atomic_int_dec_and_test(&hash_table->ref_count))
466    return;
467
468  _g_hash_table_remove_all(hash_table);
469
470  g_free(hash_table->entries);
471  hash_table->capacity = 0;
472  hash_table->entries = NULL;
473
474  g_free(hash_table);
475}
476
477
478void g_hash_table_destroy(GHashTable* hash_table) {
479  if (!hash_table)
480    return;
481
482  _g_hash_table_remove_all(hash_table);
483  g_hash_table_unref(hash_table);
484}
485
486
487// Probe the hash table for |key|. If it is in the table, return the index
488// to the corresponding entry. Otherwise, return the index of an unused
489// or tombstone entry. Also sets |*key_hash| to the key hash value on
490// return.
491static guint _g_hash_table_lookup_index(GHashTable* hash_table,
492                                        gconstpointer key,
493                                        guint* key_hash) {
494  guint hash = _g_hash_table_hash(hash_table, key);
495  *key_hash = hash;
496
497  guint probe_mask = (hash_table->capacity - 1);
498  gint tombstone = -1;
499  guint probe_index = hash & probe_mask;
500  guint step = 0;
501
502  GHashEntry* probe = &hash_table->entries[probe_index];
503  while (probe->hash != HASH_UNUSED) {
504    if (probe->hash == hash) {
505      if (hash_table->key_equal_func) {
506        if (hash_table->key_equal_func(probe->key, key))
507          return probe_index;
508      } else if (probe->key == key) {
509        return probe_index;
510      }
511    } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) {
512      tombstone = (int)probe_index;
513    }
514
515    step++;
516    probe_index = (probe_index + step) & probe_mask;
517    probe = &hash_table->entries[probe_index];
518  }
519
520  if (tombstone >= 0)
521    return (guint)tombstone;
522
523  return probe_index;
524}
525
526
527void* g_hash_table_lookup(GHashTable* hash_table,
528                          const void* key) {
529  guint key_hash = HASH_UNUSED;
530  guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash);
531  GHashEntry* entry = &hash_table->entries[probe_index];
532
533  return HASH_IS_REAL(entry->hash) ? entry->value : NULL;
534}
535
536
537// Remove key/value pair at index position |i|.
538static void _g_hash_table_remove_index(GHashTable* hash_table,
539                                       int i) {
540  GHashEntry* entry = &hash_table->entries[i];
541  entry->hash = HASH_TOMBSTONE;
542  entry->key = NULL;
543  entry->value = NULL;
544}
545
546
547gboolean g_hash_table_remove(GHashTable* hash_table,
548                             const void* key) {
549  guint key_hash = HASH_UNUSED;
550  guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash);
551  GHashEntry* entry = &hash_table->entries[probe_index];
552  if (!HASH_IS_REAL(entry->hash))
553    return 0;
554
555  _g_hash_table_remove_index(hash_table, probe_index);
556  hash_table->num_items--;
557  return 1;
558}
559
560// Resize the hash table, this also gets rid of all tombstones.
561static void _g_hash_table_resize(GHashTable* hash_table) {
562  guint old_capacity = hash_table->capacity;
563
564  // Compute new capacity from new size
565  guint new_size = hash_table->num_items * 2;
566  guint new_capacity = HASH_MIN_CAPACITY;
567  while (new_capacity < new_size)
568    new_capacity <<= 1;
569
570  GHashEntry* new_entries = g_new0(GHashEntry, new_capacity);
571  guint n;
572  for (n = 0; n < old_capacity; ++n) {
573    GHashEntry* old_entry = &hash_table->entries[n];
574    guint old_hash = old_entry->hash;
575
576    if (!HASH_IS_REAL(old_hash))
577      continue;
578
579    guint probe_mask = (new_capacity - 1);
580    guint probe_n = old_hash & probe_mask;
581    GHashEntry* probe = &new_entries[probe_n];
582    guint step = 0;
583    while (probe->hash != HASH_UNUSED) {
584      step++;
585      probe_n = (probe_n + step) & probe_mask;
586      probe = &new_entries[probe_n];
587    }
588    probe[0] = old_entry[0];
589  }
590
591  g_free(hash_table->entries);
592  hash_table->entries = new_entries;
593  hash_table->capacity = new_capacity;
594  hash_table->num_used = hash_table->num_items;
595}
596
597// Resize the hash table if needed.
598static void _g_hash_table_maybe_resize(GHashTable* hash_table) {
599  guint count = hash_table->num_items;
600  guint capacity = hash_table->capacity;
601  // Computations explained.
602  //
603  // load < min_load i.e.
604  // => used / capacity < min_load
605  // => used < min_load * capacity
606  // => used * HASH_SCALE < HASH_MIN_LOAD * capacity
607  //
608  // load > max_load
609  // => used / capacity > max_load
610  // => used * HASH_SCALER > HASH_MAX_LOAD * capacity
611  uint64_t load = (uint64_t)count * HASH_LOAD_SCALE;
612  uint64_t min_load = (uint64_t)capacity * HASH_MIN_LOAD;
613  uint64_t max_load = (uint64_t)capacity * HASH_MAX_LOAD;
614  if (load < min_load || load > max_load) {
615    _g_hash_table_resize(hash_table);
616  }
617}
618
619static void _g_hash_table_insert_index(GHashTable* hash_table,
620                                       guint key_index,
621                                       guint new_key_hash,
622                                       gpointer new_key,
623                                       gpointer new_value) {
624  GHashEntry* entry = &hash_table->entries[key_index];
625  guint old_hash = entry->hash;
626
627  entry->key = new_key;
628  entry->value = new_value;
629  entry->hash = new_key_hash;
630
631  if (HASH_IS_REAL(old_hash)) {
632    // Simple replacement, exit immediately.
633    return;
634  }
635
636  hash_table->num_items++;
637  if (old_hash == HASH_TOMBSTONE) {
638    // No need to resize when replacing a tombstone.
639    return;
640  }
641
642  hash_table->num_used++;
643  _g_hash_table_maybe_resize(hash_table);
644}
645
646void g_hash_table_insert(GHashTable* hash_table,
647                         void* key,
648                         void* value) {
649  guint key_hash;
650  guint key_index =
651      _g_hash_table_lookup_index(hash_table, key, &key_hash);
652
653  _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value);
654}
655
656
657void g_hash_table_foreach(GHashTable* hash_table,
658                          GHFunc func,
659                          gpointer user_data) {
660  guint n;
661  for (n = 0; n < hash_table->capacity; ++n) {
662    GHashEntry* entry = &hash_table->entries[n];
663    if (HASH_IS_REAL(entry->hash))
664      (*func)(entry->key, entry->value, user_data);
665  }
666}
667
668
669gpointer g_hash_table_find(GHashTable* hash_table,
670                           GHRFunc predicate,
671                           gpointer user_data) {
672  guint n;
673  for (n = 0; n < hash_table->capacity; ++n) {
674    GHashEntry* entry = &hash_table->entries[n];
675    if (HASH_IS_REAL(entry->hash) &&
676        (*predicate)(entry->key, entry->value, user_data)) {
677      return entry->value;
678    }
679  }
680  return NULL;
681}
682
683
684guint g_hash_table_size(GHashTable* hash_table) {
685  return hash_table->num_items;
686}
687
688// Queues
689
690struct _GQueueNode {
691  void* data;
692  GQueueNode* next;
693  GQueueNode* prev;
694};
695
696static inline GQueueNode* _g_queue_node_alloc(void) {
697  return g_new0(GQueueNode, 1);
698}
699
700static void inline _g_queue_node_free(GQueueNode* node) {
701  g_free(node);
702}
703
704GQueue* g_queue_new(void) {
705  GQueue* queue = g_new0(GQueue, 1);
706  return queue;
707}
708
709void g_queue_free(GQueue* queue) {
710  GQueueNode* node = queue->head;
711  while (node) {
712    GQueueNode* next = node->next;
713    _g_queue_node_free(node);
714    node = next;
715  }
716  queue->head = queue->tail = NULL;
717  queue->length = 0;
718  g_free(queue);
719}
720
721gboolean g_queue_is_empty(GQueue* queue) {
722  return queue->head == NULL;
723}
724
725void g_queue_push_tail(GQueue* queue, void* data) {
726  GQueueNode* node = _g_queue_node_alloc();
727  node->data = data;
728  node->next = NULL;
729  node->prev = queue->tail;
730  queue->tail = node;
731  queue->length++;
732}
733
734void* g_queue_peek_head(GQueue* queue) {
735  return (queue->head) ? queue->head->data : NULL;
736}
737
738void* g_queue_peek_tail(GQueue* queue) {
739  return (queue->tail) ? queue->tail->data : NULL;
740}
741
742void* g_queue_pop_head(GQueue* queue) {
743  GQueueNode* head = queue->head;
744  if (!head)
745    return NULL;
746
747  void* result = head->data;
748
749  if (head->next) {
750    queue->head = head->next;
751    head->next->prev = NULL;
752  } else {
753    queue->head = NULL;
754    queue->tail = NULL;
755  }
756  queue->length--;
757
758  return result;
759}
760