mini-glib/src/glib-mini.c

// Copyright 2014 The Android Open Source Project
//
// This software is licensed under the terms of the GNU General Public
// License version 2, as published by the Free Software Foundation, and
// may be copied, distributed, and modified under those terms.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#include <glib.h>

#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Print a panic message then exit the program immediately.
void g_panic(const char* fmt, ...) {
  va_list args;
  fprintf(stderr, "MiniGLib:PANIC: ");
  va_start(args, fmt);
  vfprintf(stderr, fmt, args);
  va_end(args);
  exit(1);
}


// Heap allocation.

void* g_malloc(size_t size) {
  if (size == 0)
    return NULL;

  void* ptr = malloc(size);
  if (ptr == NULL)
    g_panic("Can't allocate %zu bytes!\n", size);

  return ptr;
}


void* g_malloc0(size_t size) {
  void* ptr = g_malloc(size);
  if (ptr == NULL)
    return NULL;

  memset(ptr, 0, size);
  return ptr;
}


void* g_realloc(void* ptr, size_t size) {
  if (size == 0) {
    g_free(ptr);
    return NULL;
  }
  void* new_ptr = realloc(ptr, size);
  if (new_ptr == NULL)
    g_panic("Can't reallocate pointer %p to %zu bytes!\n", ptr, size);

  return new_ptr;
}


void g_free(void* ptr) {
  if (ptr)
    free(ptr);
}

// Strings.

char* g_strdup(const char* str) {
  if (str == NULL)
    return NULL;

  size_t len = strlen(str);
  char* copy = g_malloc(len + 1);
  memcpy(copy, str, len + 1);
  return copy;
}


char* g_strndup(const char* str, size_t size) {
  const char *end = memchr(str, 0, size);
  char *copy;

  if (end)
    size = end - str;

  copy = g_malloc(size + 1);
  memcpy(copy, str, size);
  copy[size] = 0;
  return copy;
}


char* g_strdup_printf(const char* fmt, ...) {
  char* result;
  va_list args;
  va_start(args, fmt);
  g_vasprintf(&result, fmt, args);
  va_end(args);
  return result;
}


char* g_strdup_vprintf(const char* fmt, va_list args) {
  char* result;
  g_vasprintf(&result, fmt, args);
  return result;
}


int g_vasprintf(char** str, const char* fmt, va_list args) {
#ifdef _WIN32
  // On Win32, vsnprintf() is broken and always returns -1 in case of truncation,
  // so make an educated guess, and try again if that fails with a larger pool.
  size_t capacity = 128;
  char* buffer = g_malloc(capacity);
  for (;;) {
    va_list args2;
    va_copy(args2, args);
    int len = vsnprintf(buffer, capacity, fmt, args2);
    if (len >= 0) {
      *str = buffer;
      return len;
    }
    va_end(args2);

    capacity *= 2;
    if (capacity > INT_MAX)
      g_panic("Formatted string is too long!\n");

    buffer = g_realloc(buffer, capacity);
  }
#else
  // On other systems, vsnprintf() works properly and returns the size of the
  // formatted string without truncation.
  va_list args2;
  va_copy(args2, args);
  int len = vsnprintf(NULL, 0, fmt, args2);
  va_end(args2);
  if (len < 0)
    g_panic("Can't format string!\n");

  char* result = g_malloc(len + 1);
  va_copy(args2, args);
  vsnprintf(result, (size_t)len, fmt, args2);
  va_end(args2);

  *str = result;
  return len;
#endif
}

gboolean g_str_equal(const void* v1, const void* v2) {
  return !strcmp((const char*)v1, (const char*)v2);
}

guint g_str_hash(const void* str) {
  const signed char* p = str;
  guint hash = 5381U;

  for (; *p; ++p)
    hash = (hash << 5) + hash + (guint)*p;

  return hash;
}

// Single-linked list

static GSList* _g_slist_alloc(void) {
  return (GSList*) g_malloc(sizeof(GSList));
}

void g_slist_free(GSList* list) {
  while (list) {
    GSList* next = list->next;
    g_free(list);
    list = next;
  }
}

GSList* g_slist_last(GSList* list) {
  while (list && list->next)
    list = list->next;
  return list;
}

GSList* g_slist_find(GSList* list, const void* data) {
  while (list) {
    if (list->data == data)
      break;
    list = list->next;
  }
  return list;
}

GSList* g_slist_append(GSList* list, void* data) {
  GSList* new_list = _g_slist_alloc();
  new_list->data = data;
  new_list->next = NULL;

  if (!list)
    return new_list;

  GSList* last = g_slist_last(list);
  last->next = new_list;
  return list;
}

GSList* g_slist_prepend(GSList* list, void* data) {
  GSList* new_list = _g_slist_alloc();
  new_list->data = data;
  new_list->next = list;
  return new_list;
}

GSList* g_slist_remove(GSList* list, const void* data) {
  GSList** pnode = &list;
  for (;;) {
    GSList* node = *pnode;
    if (!node)
      break;
    if (node->data == data) {
      *pnode = node->next;
      g_slist_free(node);
      break;
    }
    pnode = &node->next;
  }
  return list;
}

void g_slist_foreach(GSList* list, GFunc func, void* user_data) {
  while (list) {
    GSList* next = list->next;
    (*func)(list->data, user_data);
    list = next;
  }
}

//
static GSList* g_slist_sort_merge(GSList* l1,
                                  GSList* l2,
                                  GFunc compare_func,
                                  void* user_data) {
  GSList* list = NULL;
  GSList** tail = &list;

  while (l1 && l2) {
    int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data);
    if (cmp <= 0) {
      *tail = l1;
      tail = &l1->next;
      l1 = l1->next;
    } else {
      *tail = l2;
      tail = &l2->next;
      l2 = l2->next;
    }
  }
  *tail = l1 ? l1 : l2;

  return list;
}

static GSList* g_slist_sort_real(GSList* list,
                                 GFunc compare_func,
                                 void* user_data) {

  if (!list)
    return NULL;
  if (!list->next)
    return list;

  // Split list into two halves.
  GSList* l1 = list;
  GSList* l2 = list->next;

  while (l2->next && l2->next->next) {
    l2 = l2->next->next;
    l1 = l1->next;
  }
  l2 = l1->next;
  l1->next = NULL;

  return g_slist_sort_merge(
      g_slist_sort_real(list, compare_func, user_data),
      g_slist_sort_real(l2, compare_func, user_data),
      compare_func,
      user_data);
}

GSList* g_slist_sort(GSList* list, GCompareFunc compare_func) {
  return g_slist_sort_real(list, (GFunc) compare_func, NULL);
}

// Atomic operations

#if !_WIN32
// Note: Windows implementation in glib-mini-win32.c

void g_atomic_int_inc(int volatile* atomic) {
  __sync_fetch_and_add(atomic, 1);
}

gboolean g_atomic_int_dec_and_test(int volatile* atomic) {
  return __sync_fetch_and_add(atomic, -1) == 1;
}
#endif  // !_WIN32

// Hash Tables

// This is a rather vanilla implementation, slightly simpler
// than the GLib one, since QEMU doesn't require the full features:
//
// - Uses a single dynamic array of (key,value,hash) tuples.
// - Array capacity is always 2^N
// - No use of modulo primes for simplicity, we don't expect
//   QEMU/QAPI to degenerate here.
// - Dumb container only: doesn't own and free keys and values.
// - No optimization for sets (i.e. when key == value for each entry).
// - No iterators.
//
typedef struct {
  gpointer key;
  gpointer value;
  guint    hash;
} GHashEntry;

#define HASH_UNUSED    0   // Must be 0, see _remove_all() below.
#define HASH_TOMBSTONE 1
#define HASH_IS_REAL(h)  ((h) >= 2)

#define HASH_MIN_SHIFT  3
#define HASH_MIN_CAPACITY  (1 << HASH_MIN_SHIFT)

struct _GHashTable {
  int ref_count;
  int num_items;
  int num_used;  // count of items + tombstones
  int shift;
  int capacity;
  GHashEntry* entries;
  GHashFunc hash_func;
  GEqualFunc key_equal_func;
};

// Compute the hash value of a given key.
static inline size_t
_g_hash_table_hash(GHashTable* table, gconstpointer key) {
  size_t hash = table->hash_func(key);
  return HASH_IS_REAL(hash) ? hash : 2;
}


GHashTable* g_hash_table_new(GHashFunc hash_func,
                             GEqualFunc key_equal_func) {
  GHashTable* hash_table = g_new0(GHashTable, 1);

  hash_table->ref_count = 1;
  hash_table->num_items = 0;
  hash_table->capacity = HASH_MIN_CAPACITY;
  hash_table->entries = g_new0(GHashEntry, hash_table->capacity);
  hash_table->hash_func = hash_func;
  hash_table->key_equal_func = key_equal_func;

  return hash_table;
}


static void _g_hash_table_remove_all(GHashTable* hash_table) {
  // NOTE: This uses the fact that HASH_UNUSED is 0!
  hash_table->num_items = 0;
  memset(hash_table->entries,
         0,
         sizeof(hash_table->entries[0]) * hash_table->capacity);
}


GHashTable* g_hash_table_ref(GHashTable* hash_table) {
  if (!hash_table)
    return NULL;

  g_atomic_int_inc(&hash_table->ref_count);
  return hash_table;
}


void g_hash_table_unref(GHashTable* hash_table) {
  if (!hash_table)
    return;

  if (!g_atomic_int_dec_and_test(&hash_table->ref_count))
    return;

  _g_hash_table_remove_all(hash_table);

  g_free(hash_table->entries);
  hash_table->capacity = 0;
  hash_table->entries = NULL;

  g_free(hash_table);
}


void g_hash_table_destroy(GHashTable* hash_table) {
  if (!hash_table)
    return;

  _g_hash_table_remove_all(hash_table);
  g_hash_table_unref(hash_table);
}


// Probe the hash table for |key|. If it is in the table, return the index
// to the corresponding entry. Otherwise, return the index of an unused
// or tombstone entry. Also sets |*key_hash| to the key hash value on
// return.
static guint _g_hash_table_lookup_index(GHashTable* hash_table,
                                        gconstpointer key,
                                        guint* key_hash) {
  guint hash = _g_hash_table_hash(hash_table, key);
  *key_hash = hash;

  guint probe_mask = (hash_table->capacity - 1);
  gint tombstone = -1;
  guint probe_index = hash & probe_mask;
  guint step = 0;

  GHashEntry* probe = &hash_table->entries[probe_index];
  while (probe->hash != HASH_UNUSED) {
    if (probe->hash == hash) {
      if (hash_table->key_equal_func) {
        if (hash_table->key_equal_func(probe->key, key))
          return probe_index;
      } else if (probe->key == key) {
        return probe_index;
      }
    } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) {
      tombstone = (int)probe_index;
    }

    step++;
    probe_index = (probe_index + step) & probe_mask;
    probe = &hash_table->entries[probe_index];
  }

  if (tombstone >= 0)
    return (guint)tombstone;

  return probe_index;
}


void* g_hash_table_lookup(GHashTable* hash_table,
                          const void* key) {
  guint key_hash = HASH_UNUSED;
  guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash);
  GHashEntry* entry = &hash_table->entries[probe_index];

  return HASH_IS_REAL(entry->hash) ? entry->value : NULL;
}


// Remove key/value pair at index position |i|.
static void _g_hash_table_remove_index(GHashTable* hash_table,
                                       int i) {
  GHashEntry* entry = &hash_table->entries[i];
  entry->hash = HASH_TOMBSTONE;
  entry->key = NULL;
  entry->value = NULL;
}


gboolean g_hash_table_remove(GHashTable* hash_table,
                             const void* key) {
  guint key_hash = HASH_UNUSED;
  guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash);
  GHashEntry* entry = &hash_table->entries[probe_index];
  if (!HASH_IS_REAL(entry->hash))
    return 0;

  _g_hash_table_remove_index(hash_table, probe_index);
  hash_table->num_items--;
  return 1;
}

// Resize the hash table, this also gets rid of all tombstones.
static void _g_hash_table_resize(GHashTable* hash_table) {
  guint old_capacity = hash_table->capacity;

  // Compute new shift from new size
  guint new_size = hash_table->num_items * 2;
  guint new_capacity = HASH_MIN_CAPACITY;
  while (new_capacity < new_size)
    new_capacity <<= 1;

  GHashEntry* new_entries = g_new0(GHashEntry, new_capacity);
  guint n;
  for (n = 0; n < old_capacity; ++n) {
    GHashEntry* old_entry = &hash_table->entries[n];
    guint old_hash = old_entry->hash;

    if (!HASH_IS_REAL(old_hash))
      continue;

    guint probe_mask = (new_capacity - 1);
    guint probe_n = old_hash & probe_mask;
    GHashEntry* probe = &new_entries[probe_n];
    guint step = 0;
    while (probe->hash != HASH_UNUSED) {
      step++;
      probe_n = (probe_n + step) & probe_mask;
      probe = &new_entries[probe_n];
    }
    probe[0] = old_entry[0];
  }

  g_free(hash_table->entries);
  hash_table->entries = new_entries;
  hash_table->capacity = new_capacity;
  hash_table->num_used = hash_table->num_items;
}

// Resize the hash table if needed.
static void _g_hash_table_maybe_resize(GHashTable* hash_table) {
  guint used = hash_table->num_used;
  guint count = hash_table->num_items;
  guint capacity = hash_table->capacity;
  if ((capacity > count * 4 && capacity > HASH_MIN_CAPACITY) ||
      capacity < used + (used / 16)) {
    _g_hash_table_resize(hash_table);
  }
}

static void _g_hash_table_insert_index(GHashTable* hash_table,
                                       guint key_index,
                                       guint new_key_hash,
                                       gpointer new_key,
                                       gpointer new_value) {
  GHashEntry* entry = &hash_table->entries[key_index];
  guint old_hash = entry->hash;

  entry->key = new_key;
  entry->value = new_value;
  entry->hash = new_key_hash;

  if (HASH_IS_REAL(old_hash)) {
    // Simple replacement, exit immediately.
    return;
  }

  hash_table->num_items++;
  if (old_hash == HASH_TOMBSTONE) {
    // No need to resize when replacing a tombstone.
    return;
  }

  hash_table->num_used++;
  _g_hash_table_maybe_resize(hash_table);
}

void g_hash_table_insert(GHashTable* hash_table,
                         void* key,
                         void* value) {
  guint key_hash;
  guint key_index =
      _g_hash_table_lookup_index(hash_table, key, &key_hash);

  _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value);
}


void g_hash_table_foreach(GHashTable* hash_table,
                          GHFunc func,
                          gpointer user_data) {
  guint n;
  for (n = 0; n < hash_table->capacity; ++n) {
    GHashEntry* entry = &hash_table->entries[n];
    if (HASH_IS_REAL(entry->hash))
      (*func)(entry->key, entry->value, user_data);
  }
}


gpointer g_hash_table_find(GHashTable* hash_table,
                           GHRFunc predicate,
                           gpointer user_data) {
  guint n;
  for (n = 0; n < hash_table->capacity; ++n) {
    GHashEntry* entry = &hash_table->entries[n];
    if (HASH_IS_REAL(entry->hash) &&
        (*predicate)(entry->key, entry->value, user_data)) {
      return entry->value;
    }
  }
  return NULL;
}


guint g_hash_table_size(GHashTable* hash_table) {
  return hash_table->num_items;
}