From 061e9b92539cfb5c5c57cca04aa41a9cbf7434ba Mon Sep 17 00:00:00 2001 From: Philip Withnall Date: Tue, 7 Jun 2022 18:00:41 +0100 Subject: build: Add very basic meson build system MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This doesn’t build any files, but does expose the list of sources as a Meson variable so it can be used as a subproject from other projects. I thought about building a static library for gvdb, but this would cause problems for libgio (and gvdb’s use inside libgio is the motivation for making it subproject-able). gvdb depends on libgio types, such as `GCancellable`, but also is a dependency of parts of libgio, such as `GResource`. That circular dependency means that building a static library is non-trivial. There is an approach for achieving this, detailed by Eli Schwartz at https://gitlab.gnome.org/GNOME/gvdb/-/merge_requests/18#note_1474750, but that’s too much work for what I would like to achieve here. It can always be implemented in future, particularly if we add unit tests to gvdb (in this git repository) or if another project starts linking gvdb in using Meson subprojects rather than copy/paste. The files have to be moved to a `gvdb/` subdirectory to keep the include paths working correctly — code in GLib which uses gvdb uses `#include `. Signed-off-by: Philip Withnall --- gvdb-builder.c | 637 --------------------------------------------- gvdb-builder.h | 66 ----- gvdb-format.h | 85 ------ gvdb-reader.c | 736 ---------------------------------------------------- gvdb-reader.h | 78 ------ gvdb/gvdb-builder.c | 637 +++++++++++++++++++++++++++++++++++++++++++++ gvdb/gvdb-builder.h | 66 +++++ gvdb/gvdb-format.h | 85 ++++++ gvdb/gvdb-reader.c | 736 ++++++++++++++++++++++++++++++++++++++++++++++++++++ gvdb/gvdb-reader.h | 78 ++++++ meson.build | 15 ++ 11 files changed, 1617 insertions(+), 1602 deletions(-) delete mode 100644 gvdb-builder.c delete mode 100644 gvdb-builder.h delete mode 100644 gvdb-format.h delete mode 100644 gvdb-reader.c delete mode 100644 gvdb-reader.h create mode 100644 gvdb/gvdb-builder.c create mode 100644 gvdb/gvdb-builder.h create mode 100644 gvdb/gvdb-format.h create mode 100644 gvdb/gvdb-reader.c create mode 100644 gvdb/gvdb-reader.h create mode 100644 meson.build diff --git a/gvdb-builder.c b/gvdb-builder.c deleted file mode 100644 index 5dae03e..0000000 --- a/gvdb-builder.c +++ /dev/null @@ -1,637 +0,0 @@ -/* - * Copyright © 2010 Codethink Limited - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see . - * - * Author: Ryan Lortie - */ - -#include "gvdb-builder.h" -#include "gvdb-format.h" - -#include -#include -#if !defined(G_OS_WIN32) || !defined(_MSC_VER) -#include -#endif -#include - - -struct _GvdbItem -{ - gchar *key; - guint32 hash_value; - guint32_le assigned_index; - GvdbItem *parent; - GvdbItem *sibling; - GvdbItem *next; - - /* one of: - * this: - */ - GVariant *value; - - /* this: */ - GHashTable *table; - - /* or this: */ - GvdbItem *child; -}; - -static void -gvdb_item_free (gpointer data) -{ - GvdbItem *item = data; - - g_free (item->key); - - if (item->value) - g_variant_unref (item->value); - - if (item->table) - g_hash_table_unref (item->table); - - g_slice_free (GvdbItem, item); -} - -GHashTable * -gvdb_hash_table_new (GHashTable *parent, - const gchar *name_in_parent) -{ - GHashTable *table; - - table = g_hash_table_new_full (g_str_hash, g_str_equal, - g_free, gvdb_item_free); - - if (parent) - { - GvdbItem *item; - - item = gvdb_hash_table_insert (parent, name_in_parent); - gvdb_item_set_hash_table (item, table); - } - - return table; -} - -static guint32 -djb_hash (const gchar *key) -{ - guint32 hash_value = 5381; - - while (*key) - hash_value = hash_value * 33 + *(signed char *)key++; - - return hash_value; -} - -GvdbItem * -gvdb_hash_table_insert (GHashTable *table, - const gchar *key) -{ - GvdbItem *item; - - item = g_slice_new0 (GvdbItem); - item->key = g_strdup (key); - item->hash_value = djb_hash (key); - - g_hash_table_insert (table, g_strdup (key), item); - - return item; -} - -void -gvdb_hash_table_insert_string (GHashTable *table, - const gchar *key, - const gchar *value) -{ - GvdbItem *item; - - item = gvdb_hash_table_insert (table, key); - gvdb_item_set_value (item, g_variant_new_string (value)); -} - -void -gvdb_item_set_value (GvdbItem *item, - GVariant *value) -{ - g_return_if_fail (!item->value && !item->table && !item->child); - - item->value = g_variant_ref_sink (value); -} - -void -gvdb_item_set_hash_table (GvdbItem *item, - GHashTable *table) -{ - g_return_if_fail (!item->value && !item->table && !item->child); - - item->table = g_hash_table_ref (table); -} - -void -gvdb_item_set_parent (GvdbItem *item, - GvdbItem *parent) -{ - GvdbItem **node; - - g_return_if_fail (g_str_has_prefix (item->key, parent->key)); - g_return_if_fail (!parent->value && !parent->table); - g_return_if_fail (!item->parent && !item->sibling); - - for (node = &parent->child; *node; node = &(*node)->sibling) - if (strcmp ((*node)->key, item->key) > 0) - break; - - item->parent = parent; - item->sibling = *node; - *node = item; -} - -typedef struct -{ - GvdbItem **buckets; - gsize n_buckets; -} HashTable; - -static HashTable * -hash_table_new (gsize n_buckets) -{ - HashTable *table; - - table = g_slice_new (HashTable); - table->buckets = g_new0 (GvdbItem *, n_buckets); - table->n_buckets = n_buckets; - - return table; -} - -static void -hash_table_free (HashTable *table) -{ - g_free (table->buckets); - - g_slice_free (HashTable, table); -} - -static void -hash_table_insert (gpointer key, - gpointer value, - gpointer data) -{ - guint32 hash_value, bucket; - HashTable *table = data; - GvdbItem *item = value; - - hash_value = djb_hash (key); - bucket = hash_value % table->n_buckets; - item->next = table->buckets[bucket]; - table->buckets[bucket] = item; -} - -static guint32_le -item_to_index (GvdbItem *item) -{ - if (item != NULL) - return item->assigned_index; - - return guint32_to_le ((guint32) -1); -} - -typedef struct -{ - GQueue *chunks; - guint64 offset; - gboolean byteswap; -} FileBuilder; - -typedef struct -{ - gsize offset; - gsize size; - gpointer data; -} FileChunk; - -static gpointer -file_builder_allocate (FileBuilder *fb, - guint alignment, - gsize size, - struct gvdb_pointer *pointer) -{ - FileChunk *chunk; - - if (size == 0) - return NULL; - - fb->offset += (guint64) (-fb->offset) & (alignment - 1); - chunk = g_slice_new (FileChunk); - chunk->offset = fb->offset; - chunk->size = size; - chunk->data = g_malloc (size); - - pointer->start = guint32_to_le (fb->offset); - fb->offset += size; - pointer->end = guint32_to_le (fb->offset); - - g_queue_push_tail (fb->chunks, chunk); - - return chunk->data; -} - -static void -file_builder_add_value (FileBuilder *fb, - GVariant *value, - struct gvdb_pointer *pointer) -{ - GVariant *variant, *normal; - gpointer data; - gsize size; - - if (fb->byteswap) - { - value = g_variant_byteswap (value); - variant = g_variant_new_variant (value); - g_variant_unref (value); - } - else - variant = g_variant_new_variant (value); - - normal = g_variant_get_normal_form (variant); - g_variant_unref (variant); - - size = g_variant_get_size (normal); - data = file_builder_allocate (fb, 8, size, pointer); - g_variant_store (normal, data); - g_variant_unref (normal); -} - -static void -file_builder_add_string (FileBuilder *fb, - const gchar *string, - guint32_le *start, - guint16_le *size) -{ - FileChunk *chunk; - gsize length; - - length = strlen (string); - - chunk = g_slice_new (FileChunk); - chunk->offset = fb->offset; - chunk->size = length; - chunk->data = g_malloc (length); - if (length != 0) - memcpy (chunk->data, string, length); - - *start = guint32_to_le (fb->offset); - *size = guint16_to_le (length); - fb->offset += length; - - g_queue_push_tail (fb->chunks, chunk); -} - -static void -file_builder_allocate_for_hash (FileBuilder *fb, - gsize n_buckets, - gsize n_items, - guint bloom_shift, - gsize n_bloom_words, - guint32_le **bloom_filter, - guint32_le **hash_buckets, - struct gvdb_hash_item **hash_items, - struct gvdb_pointer *pointer) -{ - guint32_le bloom_hdr, table_hdr; - guchar *data; - gsize size; - - g_assert (n_bloom_words < (1u << 27)); - - bloom_hdr = guint32_to_le (bloom_shift << 27 | n_bloom_words); - table_hdr = guint32_to_le (n_buckets); - - size = sizeof bloom_hdr + sizeof table_hdr + - n_bloom_words * sizeof (guint32_le) + - n_buckets * sizeof (guint32_le) + - n_items * sizeof (struct gvdb_hash_item); - - data = file_builder_allocate (fb, 4, size, pointer); - g_assert (data); - -#define chunk(s) (size -= (s), data += (s), data - (s)) - memcpy (chunk (sizeof bloom_hdr), &bloom_hdr, sizeof bloom_hdr); - memcpy (chunk (sizeof table_hdr), &table_hdr, sizeof table_hdr); - *bloom_filter = (guint32_le *) chunk (n_bloom_words * sizeof (guint32_le)); - *hash_buckets = (guint32_le *) chunk (n_buckets * sizeof (guint32_le)); - *hash_items = (struct gvdb_hash_item *) chunk (n_items * - sizeof (struct gvdb_hash_item)); - g_assert (size == 0); -#undef chunk - - memset (*bloom_filter, 0, n_bloom_words * sizeof (guint32_le)); - memset (*hash_buckets, 0, n_buckets * sizeof (guint32_le)); - memset (*hash_items, 0, n_items * sizeof (struct gvdb_hash_item)); - - /* NOTE - the code to actually fill in the bloom filter here is missing. - * Patches welcome! - * - * http://en.wikipedia.org/wiki/Bloom_filter - * http://0pointer.de/blog/projects/bloom.html - */ -} - -static void -file_builder_add_hash (FileBuilder *fb, - GHashTable *table, - struct gvdb_pointer *pointer) -{ - guint32_le *buckets, *bloom_filter; - struct gvdb_hash_item *items; - HashTable *mytable; - GvdbItem *item; - guint32 index; - gsize bucket; - - mytable = hash_table_new (g_hash_table_size (table)); - g_hash_table_foreach (table, hash_table_insert, mytable); - index = 0; - - for (bucket = 0; bucket < mytable->n_buckets; bucket++) - for (item = mytable->buckets[bucket]; item; item = item->next) - item->assigned_index = guint32_to_le (index++); - - file_builder_allocate_for_hash (fb, mytable->n_buckets, index, 5, 0, - &bloom_filter, &buckets, &items, pointer); - - index = 0; - for (bucket = 0; bucket < mytable->n_buckets; bucket++) - { - buckets[bucket] = guint32_to_le (index); - - for (item = mytable->buckets[bucket]; item; item = item->next) - { - struct gvdb_hash_item *entry = items++; - const gchar *basename; - - g_assert (index == guint32_from_le (item->assigned_index)); - entry->hash_value = guint32_to_le (item->hash_value); - entry->parent = item_to_index (item->parent); - entry->unused = 0; - - if (item->parent != NULL) - basename = item->key + strlen (item->parent->key); - else - basename = item->key; - - file_builder_add_string (fb, basename, - &entry->key_start, - &entry->key_size); - - if (item->value != NULL) - { - g_assert (item->child == NULL && item->table == NULL); - - file_builder_add_value (fb, item->value, &entry->value.pointer); - entry->type = 'v'; - } - - if (item->child != NULL) - { - guint32 children = 0, i = 0; - guint32_le *offsets; - GvdbItem *child; - - g_assert (item->table == NULL); - - for (child = item->child; child; child = child->sibling) - children++; - - offsets = file_builder_allocate (fb, 4, 4 * children, - &entry->value.pointer); - entry->type = 'L'; - - for (child = item->child; child; child = child->sibling) - offsets[i++] = child->assigned_index; - - g_assert (children == i); - } - - if (item->table != NULL) - { - entry->type = 'H'; - file_builder_add_hash (fb, item->table, &entry->value.pointer); - } - - index++; - } - } - - hash_table_free (mytable); -} - -static FileBuilder * -file_builder_new (gboolean byteswap) -{ - FileBuilder *builder; - - builder = g_slice_new (FileBuilder); - builder->chunks = g_queue_new (); - builder->offset = sizeof (struct gvdb_header); - builder->byteswap = byteswap; - - return builder; -} - -static void -file_builder_free (FileBuilder *fb) -{ - g_queue_free (fb->chunks); - g_slice_free (FileBuilder, fb); -} - -static GString * -file_builder_serialise (FileBuilder *fb, - struct gvdb_pointer root) -{ - struct gvdb_header header; - GString *result; - - memset (&header, 0, sizeof (header)); - - if (fb->byteswap) - { - header.signature[0] = GVDB_SWAPPED_SIGNATURE0; - header.signature[1] = GVDB_SWAPPED_SIGNATURE1; - } - else - { - header.signature[0] = GVDB_SIGNATURE0; - header.signature[1] = GVDB_SIGNATURE1; - } - - result = g_string_new (NULL); - - header.root = root; - g_string_append_len (result, (gpointer) &header, sizeof header); - - while (!g_queue_is_empty (fb->chunks)) - { - FileChunk *chunk = g_queue_pop_head (fb->chunks); - - if (result->len != chunk->offset) - { - gchar zero[8] = { 0, }; - - g_assert (chunk->offset > result->len); - g_assert (chunk->offset - result->len < 8); - - g_string_append_len (result, zero, chunk->offset - result->len); - g_assert (result->len == chunk->offset); - } - - g_string_append_len (result, chunk->data, chunk->size); - g_free (chunk->data); - - g_slice_free (FileChunk, chunk); - } - - return result; -} - -gboolean -gvdb_table_write_contents (GHashTable *table, - const gchar *filename, - gboolean byteswap, - GError **error) -{ - struct gvdb_pointer root; - gboolean status; - FileBuilder *fb; - GString *str; - - g_return_val_if_fail (table != NULL, FALSE); - g_return_val_if_fail (filename != NULL, FALSE); - g_return_val_if_fail (error == NULL || *error == NULL, FALSE); - - fb = file_builder_new (byteswap); - file_builder_add_hash (fb, table, &root); - str = file_builder_serialise (fb, root); - file_builder_free (fb); - - status = g_file_set_contents (filename, str->str, str->len, error); - g_string_free (str, TRUE); - - return status; -} - -typedef struct { - GBytes *contents; /* (owned) */ - GFile *file; /* (owned) */ -} WriteContentsData; - -static WriteContentsData * -write_contents_data_new (GBytes *contents, - GFile *file) -{ - WriteContentsData *data; - - data = g_slice_new (WriteContentsData); - data->contents = g_bytes_ref (contents); - data->file = g_object_ref (file); - - return data; -} - -static void -write_contents_data_free (WriteContentsData *data) -{ - g_bytes_unref (data->contents); - g_object_unref (data->file); - g_slice_free (WriteContentsData, data); -} - -static void -replace_contents_cb (GObject *source_object, - GAsyncResult *result, - gpointer user_data) -{ - GTask *task = user_data; - WriteContentsData *data = g_task_get_task_data (task); - GError *error = NULL; - - g_return_if_fail (g_task_get_source_tag (task) == gvdb_table_write_contents_async); - - if (!g_file_replace_contents_finish (data->file, result, NULL, &error)) - g_task_return_error (task, g_steal_pointer (&error)); - else - g_task_return_boolean (task, TRUE); - - g_object_unref (task); -} - -void -gvdb_table_write_contents_async (GHashTable *table, - const gchar *filename, - gboolean byteswap, - GCancellable *cancellable, - GAsyncReadyCallback callback, - gpointer user_data) -{ - struct gvdb_pointer root; - FileBuilder *fb; - WriteContentsData *data; - GString *str; - GBytes *bytes; - GFile *file; - GTask *task; - - g_return_if_fail (table != NULL); - g_return_if_fail (filename != NULL); - g_return_if_fail (cancellable == NULL || G_IS_CANCELLABLE (cancellable)); - - fb = file_builder_new (byteswap); - file_builder_add_hash (fb, table, &root); - str = file_builder_serialise (fb, root); - bytes = g_string_free_to_bytes (str); - file_builder_free (fb); - - file = g_file_new_for_path (filename); - data = write_contents_data_new (bytes, file); - - task = g_task_new (NULL, cancellable, callback, user_data); - g_task_set_task_data (task, data, (GDestroyNotify)write_contents_data_free); - g_task_set_source_tag (task, gvdb_table_write_contents_async); - - g_file_replace_contents_async (file, - g_bytes_get_data (bytes, NULL), - g_bytes_get_size (bytes), - NULL, FALSE, - G_FILE_CREATE_PRIVATE, - cancellable, replace_contents_cb, g_steal_pointer (&task)); - - g_bytes_unref (bytes); - g_object_unref (file); -} - -gboolean -gvdb_table_write_contents_finish (GHashTable *table, - GAsyncResult *result, - GError **error) -{ - g_return_val_if_fail (table != NULL, FALSE); - g_return_val_if_fail (g_task_is_valid (result, NULL), FALSE); - g_return_val_if_fail (error == NULL || *error == NULL, FALSE); - - return g_task_propagate_boolean (G_TASK (result), error); -} diff --git a/gvdb-builder.h b/gvdb-builder.h deleted file mode 100644 index 30757d0..0000000 --- a/gvdb-builder.h +++ /dev/null @@ -1,66 +0,0 @@ -/* - * Copyright © 2010 Codethink Limited - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see . - * - * Author: Ryan Lortie - */ - -#ifndef __gvdb_builder_h__ -#define __gvdb_builder_h__ - -#include - -typedef struct _GvdbItem GvdbItem; - -G_GNUC_INTERNAL -GHashTable * gvdb_hash_table_new (GHashTable *parent, - const gchar *key); - -G_GNUC_INTERNAL -GvdbItem * gvdb_hash_table_insert (GHashTable *table, - const gchar *key); -G_GNUC_INTERNAL -void gvdb_hash_table_insert_string (GHashTable *table, - const gchar *key, - const gchar *value); - -G_GNUC_INTERNAL -void gvdb_item_set_value (GvdbItem *item, - GVariant *value); -G_GNUC_INTERNAL -void gvdb_item_set_hash_table (GvdbItem *item, - GHashTable *table); -G_GNUC_INTERNAL -void gvdb_item_set_parent (GvdbItem *item, - GvdbItem *parent); - -G_GNUC_INTERNAL -gboolean gvdb_table_write_contents (GHashTable *table, - const gchar *filename, - gboolean byteswap, - GError **error); -G_GNUC_INTERNAL -void gvdb_table_write_contents_async (GHashTable *table, - const gchar *filename, - gboolean byteswap, - GCancellable *cancellable, - GAsyncReadyCallback callback, - gpointer user_data); -G_GNUC_INTERNAL -gboolean gvdb_table_write_contents_finish (GHashTable *table, - GAsyncResult *result, - GError **error); - -#endif /* __gvdb_builder_h__ */ diff --git a/gvdb-format.h b/gvdb-format.h deleted file mode 100644 index ed6adab..0000000 --- a/gvdb-format.h +++ /dev/null @@ -1,85 +0,0 @@ -/* - * Copyright © 2010 Codethink Limited - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see . - * - * Author: Ryan Lortie - */ - -#ifndef __gvdb_format_h__ -#define __gvdb_format_h__ - -#include - -typedef struct { guint16 value; } guint16_le; -typedef struct { guint32 value; } guint32_le; - -struct gvdb_pointer { - guint32_le start; - guint32_le end; -}; - -struct gvdb_hash_header { - guint32_le n_bloom_words; - guint32_le n_buckets; -}; - -struct gvdb_hash_item { - guint32_le hash_value; - guint32_le parent; - - guint32_le key_start; - guint16_le key_size; - gchar type; - gchar unused; - - union - { - struct gvdb_pointer pointer; - gchar direct[8]; - } value; -}; - -struct gvdb_header { - guint32 signature[2]; - guint32_le version; - guint32_le options; - - struct gvdb_pointer root; -}; - -static inline guint32_le guint32_to_le (guint32 value) { - guint32_le result = { GUINT32_TO_LE (value) }; - return result; -} - -static inline guint32 guint32_from_le (guint32_le value) { - return GUINT32_FROM_LE (value.value); -} - -static inline guint16_le guint16_to_le (guint16 value) { - guint16_le result = { GUINT16_TO_LE (value) }; - return result; -} - -static inline guint16 guint16_from_le (guint16_le value) { - return GUINT16_FROM_LE (value.value); -} - -#define GVDB_SIGNATURE0 1918981703 -#define GVDB_SIGNATURE1 1953390953 -#define GVDB_SWAPPED_SIGNATURE0 GUINT32_SWAP_LE_BE (GVDB_SIGNATURE0) -#define GVDB_SWAPPED_SIGNATURE1 GUINT32_SWAP_LE_BE (GVDB_SIGNATURE1) - -#endif /* __gvdb_format_h__ */ diff --git a/gvdb-reader.c b/gvdb-reader.c deleted file mode 100644 index 820ce4c..0000000 --- a/gvdb-reader.c +++ /dev/null @@ -1,736 +0,0 @@ -/* - * Copyright © 2010 Codethink Limited - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see . - * - * Author: Ryan Lortie - */ - -#include "gvdb-reader.h" -#include "gvdb-format.h" - -#include - -struct _GvdbTable { - GBytes *bytes; - - const gchar *data; - gsize size; - - gboolean byteswapped; - gboolean trusted; - - const guint32_le *bloom_words; - guint32 n_bloom_words; - guint bloom_shift; - - const guint32_le *hash_buckets; - guint32 n_buckets; - - struct gvdb_hash_item *hash_items; - guint32 n_hash_items; -}; - -static const gchar * -gvdb_table_item_get_key (GvdbTable *file, - const struct gvdb_hash_item *item, - gsize *size) -{ - guint32 start, end; - - start = guint32_from_le (item->key_start); - *size = guint16_from_le (item->key_size); - end = start + *size; - - if G_UNLIKELY (start > end || end > file->size) - return NULL; - - return file->data + start; -} - -static gconstpointer -gvdb_table_dereference (GvdbTable *file, - const struct gvdb_pointer *pointer, - gint alignment, - gsize *size) -{ - guint32 start, end; - - start = guint32_from_le (pointer->start); - end = guint32_from_le (pointer->end); - - if G_UNLIKELY (start > end || end > file->size || start & (alignment - 1)) - return NULL; - - *size = end - start; - - return file->data + start; -} - -static void -gvdb_table_setup_root (GvdbTable *file, - const struct gvdb_pointer *pointer) -{ - const struct gvdb_hash_header *header; - guint32 n_bloom_words; - guint32 n_buckets; - gsize size; - - header = gvdb_table_dereference (file, pointer, 4, &size); - - if G_UNLIKELY (header == NULL || size < sizeof *header) - return; - - size -= sizeof *header; - - n_bloom_words = guint32_from_le (header->n_bloom_words); - n_buckets = guint32_from_le (header->n_buckets); - n_bloom_words &= (1u << 27) - 1; - - if G_UNLIKELY (n_bloom_words * sizeof (guint32_le) > size) - return; - - file->bloom_words = (gpointer) (header + 1); - size -= n_bloom_words * sizeof (guint32_le); - file->n_bloom_words = n_bloom_words; - - if G_UNLIKELY (n_buckets > G_MAXUINT / sizeof (guint32_le) || - n_buckets * sizeof (guint32_le) > size) - return; - - file->hash_buckets = file->bloom_words + file->n_bloom_words; - size -= n_buckets * sizeof (guint32_le); - file->n_buckets = n_buckets; - - if G_UNLIKELY (size % sizeof (struct gvdb_hash_item)) - return; - - file->hash_items = (gpointer) (file->hash_buckets + n_buckets); - file->n_hash_items = size / sizeof (struct gvdb_hash_item); -} - -/** - * gvdb_table_new_from_bytes: - * @bytes: the #GBytes with the data - * @trusted: if the contents of @bytes are trusted - * @error: %NULL, or a pointer to a %NULL #GError - * - * Creates a new #GvdbTable from the contents of @bytes. - * - * This call can fail if the header contained in @bytes is invalid or if @bytes - * is empty; if so, %G_FILE_ERROR_INVAL will be returned. - * - * You should call gvdb_table_free() on the return result when you no - * longer require it. - * - * Returns: a new #GvdbTable - **/ -GvdbTable * -gvdb_table_new_from_bytes (GBytes *bytes, - gboolean trusted, - GError **error) -{ - const struct gvdb_header *header; - GvdbTable *file; - - file = g_slice_new0 (GvdbTable); - file->bytes = g_bytes_ref (bytes); - file->data = g_bytes_get_data (bytes, &file->size); - file->trusted = trusted; - - if (file->size < sizeof (struct gvdb_header)) - goto invalid; - - header = (gpointer) file->data; - - if (header->signature[0] == GVDB_SIGNATURE0 && - header->signature[1] == GVDB_SIGNATURE1 && - guint32_from_le (header->version) == 0) - file->byteswapped = FALSE; - - else if (header->signature[0] == GVDB_SWAPPED_SIGNATURE0 && - header->signature[1] == GVDB_SWAPPED_SIGNATURE1 && - guint32_from_le (header->version) == 0) - file->byteswapped = TRUE; - - else - goto invalid; - - gvdb_table_setup_root (file, &header->root); - - return file; - -invalid: - g_set_error_literal (error, G_FILE_ERROR, G_FILE_ERROR_INVAL, "invalid gvdb header"); - - g_bytes_unref (file->bytes); - - g_slice_free (GvdbTable, file); - - return NULL; -} - -/** - * gvdb_table_new: - * @filename: a filename - * @trusted: if the contents of @bytes are trusted - * @error: %NULL, or a pointer to a %NULL #GError - * - * Creates a new #GvdbTable using the #GMappedFile for @filename as the - * #GBytes. - * - * This function will fail if the file cannot be opened. - * In that case, the #GError that is returned will be an error from - * g_mapped_file_new(). - * - * An empty or corrupt file will result in %G_FILE_ERROR_INVAL. - * - * Returns: a new #GvdbTable - **/ -GvdbTable * -gvdb_table_new (const gchar *filename, - gboolean trusted, - GError **error) -{ - GMappedFile *mapped; - GvdbTable *table; - GBytes *bytes; - - mapped = g_mapped_file_new (filename, FALSE, error); - if (!mapped) - return NULL; - - bytes = g_mapped_file_get_bytes (mapped); - table = gvdb_table_new_from_bytes (bytes, trusted, error); - g_mapped_file_unref (mapped); - g_bytes_unref (bytes); - - g_prefix_error (error, "%s: ", filename); - - return table; -} - -static gboolean -gvdb_table_bloom_filter (GvdbTable *file, - guint32 hash_value) -{ - guint32 word, mask; - - if (file->n_bloom_words == 0) - return TRUE; - - word = (hash_value / 32) % file->n_bloom_words; - mask = 1 << (hash_value & 31); - mask |= 1 << ((hash_value >> file->bloom_shift) & 31); - - return (guint32_from_le (file->bloom_words[word]) & mask) == mask; -} - -static gboolean -gvdb_table_check_name (GvdbTable *file, - struct gvdb_hash_item *item, - const gchar *key, - guint key_length) -{ - const gchar *this_key; - gsize this_size; - guint32 parent; - - this_key = gvdb_table_item_get_key (file, item, &this_size); - - if G_UNLIKELY (this_key == NULL || this_size > key_length) - return FALSE; - - key_length -= this_size; - - if G_UNLIKELY (memcmp (this_key, key + key_length, this_size) != 0) - return FALSE; - - parent = guint32_from_le (item->parent); - if (key_length == 0 && parent == 0xffffffffu) - return TRUE; - - if G_LIKELY (parent < file->n_hash_items && this_size > 0) - return gvdb_table_check_name (file, - &file->hash_items[parent], - key, key_length); - - return FALSE; -} - -static const struct gvdb_hash_item * -gvdb_table_lookup (GvdbTable *file, - const gchar *key, - gchar type) -{ - guint32 hash_value = 5381; - guint key_length; - guint32 bucket; - guint32 lastno; - guint32 itemno; - - if G_UNLIKELY (file->n_buckets == 0 || file->n_hash_items == 0) - return NULL; - - for (key_length = 0; key[key_length]; key_length++) - hash_value = (hash_value * 33) + ((signed char *) key)[key_length]; - - if (!gvdb_table_bloom_filter (file, hash_value)) - return NULL; - - bucket = hash_value % file->n_buckets; - itemno = guint32_from_le (file->hash_buckets[bucket]); - - if (bucket == file->n_buckets - 1 || - (lastno = guint32_from_le(file->hash_buckets[bucket + 1])) > file->n_hash_items) - lastno = file->n_hash_items; - - while G_LIKELY (itemno < lastno) - { - struct gvdb_hash_item *item = &file->hash_items[itemno]; - - if (hash_value == guint32_from_le (item->hash_value)) - if G_LIKELY (gvdb_table_check_name (file, item, key, key_length)) - if G_LIKELY (item->type == type) - return item; - - itemno++; - } - - return NULL; -} - -static gboolean -gvdb_table_list_from_item (GvdbTable *table, - const struct gvdb_hash_item *item, - const guint32_le **list, - guint *length) -{ - gsize size; - - *list = gvdb_table_dereference (table, &item->value.pointer, 4, &size); - - if G_LIKELY (*list == NULL || size % 4) - return FALSE; - - *length = size / 4; - - return TRUE; -} - -/** - * gvdb_table_get_names: - * @table: a #GvdbTable - * @length: (out) (optional): the number of items returned, or %NULL - * - * Gets a list of all names contained in @table. - * - * No call to gvdb_table_get_table(), gvdb_table_list() or - * gvdb_table_get_value() will succeed unless it is for one of the - * names returned by this function. - * - * Note that some names that are returned may still fail for all of the - * above calls in the case of the corrupted file. Note also that the - * returned strings may not be utf8. - * - * Returns: (array length=length): a %NULL-terminated list of strings, of length @length - **/ -gchar ** -gvdb_table_get_names (GvdbTable *table, - gsize *length) -{ - gchar **names; - guint n_names; - guint filled; - guint total; - guint i; - - /* We generally proceed by iterating over the list of items in the - * hash table (in order of appearance) recording them into an array. - * - * Each item has a parent item (except root items). The parent item - * forms part of the name of the item. We could go fetching the - * parent item chain at the point that we encounter each item but then - * we would need to implement some sort of recursion along with checks - * for self-referential items. - * - * Instead, we do a number of passes. Each pass will build up one - * level of names (starting from the root). We continue to do passes - * until no more items are left. The first pass will only add root - * items and each further pass will only add items whose direct parent - * is an item added in the immediately previous pass. It's also - * possible that items get filled if they follow their parent within a - * particular pass. - * - * At most we will have a number of passes equal to the depth of the - * tree. Self-referential items will never be filled in (since their - * parent will have never been filled in). We continue until we have - * a pass that fills in no additional items. - * - * This takes an O(n) algorithm and turns it into O(n*m) where m is - * the depth of the tree, but typically the tree won't be very - * deep and the constant factor of this algorithm is lower (and the - * complexity of coding it, as well). - */ - - n_names = table->n_hash_items; - names = g_new0 (gchar *, n_names + 1); - - /* 'names' starts out all-NULL. On each pass we record the number - * of items changed from NULL to non-NULL in 'filled' so we know if we - * should repeat the loop. 'total' counts the total number of items - * filled. If 'total' ends up equal to 'n_names' then we know that - * 'names' has been completely filled. - */ - - total = 0; - do - { - /* Loop until we have filled no more entries */ - filled = 0; - - for (i = 0; i < n_names; i++) - { - const struct gvdb_hash_item *item = &table->hash_items[i]; - const gchar *name; - gsize name_length; - guint32 parent; - - /* already got it on a previous pass */ - if (names[i] != NULL) - continue; - - parent = guint32_from_le (item->parent); - - if (parent == 0xffffffffu) - { - /* it's a root item */ - name = gvdb_table_item_get_key (table, item, &name_length); - - if (name != NULL) - { - names[i] = g_strndup (name, name_length); - filled++; - } - } - - else if (parent < n_names && names[parent] != NULL) - { - /* It's a non-root item whose parent was filled in already. - * - * Calculate the name of this item by combining it with - * its parent name. - */ - name = gvdb_table_item_get_key (table, item, &name_length); - - if (name != NULL) - { - const gchar *parent_name = names[parent]; - gsize parent_length; - gchar *fullname; - - parent_length = strlen (parent_name); - fullname = g_malloc (parent_length + name_length + 1); - memcpy (fullname, parent_name, parent_length); - memcpy (fullname + parent_length, name, name_length); - fullname[parent_length + name_length] = '\0'; - names[i] = fullname; - filled++; - } - } - } - - total += filled; - } - while (filled && total < n_names); - - /* If the table was corrupted then 'names' may have holes in it. - * Collapse those. - */ - if G_UNLIKELY (total != n_names) - { - GPtrArray *fixed_names; - - fixed_names = g_ptr_array_sized_new (n_names + 1 /* NULL terminator */); - for (i = 0; i < n_names; i++) - if (names[i] != NULL) - g_ptr_array_add (fixed_names, names[i]); - - g_free (names); - n_names = fixed_names->len; - g_ptr_array_add (fixed_names, NULL); - names = (gchar **) g_ptr_array_free (fixed_names, FALSE); - } - - if (length) - { - G_STATIC_ASSERT (sizeof (*length) >= sizeof (n_names)); - *length = n_names; - } - - return names; -} - -/** - * gvdb_table_list: - * @file: a #GvdbTable - * @key: a string - * - * List all of the keys that appear below @key. The nesting of keys - * within the hash file is defined by the program that created the hash - * file. One thing is constant: each item in the returned array can be - * concatenated to @key to obtain the full name of that key. - * - * It is not possible to tell from this function if a given key is - * itself a path, a value, or another hash table; you are expected to - * know this for yourself. - * - * You should call g_strfreev() on the return result when you no longer - * require it. - * - * Returns: a %NULL-terminated string array - **/ -gchar ** -gvdb_table_list (GvdbTable *file, - const gchar *key) -{ - const struct gvdb_hash_item *item; - const guint32_le *list; - gchar **strv; - guint length; - guint i; - - if ((item = gvdb_table_lookup (file, key, 'L')) == NULL) - return NULL; - - if (!gvdb_table_list_from_item (file, item, &list, &length)) - return NULL; - - strv = g_new (gchar *, length + 1); - for (i = 0; i < length; i++) - { - guint32 itemno = guint32_from_le (list[i]); - - if (itemno < file->n_hash_items) - { - const struct gvdb_hash_item *item; - const gchar *string; - gsize strsize; - - item = file->hash_items + itemno; - - string = gvdb_table_item_get_key (file, item, &strsize); - - if (string != NULL) - strv[i] = g_strndup (string, strsize); - else - strv[i] = g_malloc0 (1); - } - else - strv[i] = g_malloc0 (1); - } - - strv[i] = NULL; - - return strv; -} - -/** - * gvdb_table_has_value: - * @file: a #GvdbTable - * @key: a string - * - * Checks for a value named @key in @file. - * - * Note: this function does not consider non-value nodes (other hash - * tables, for example). - * - * Returns: %TRUE if @key is in the table - **/ -gboolean -gvdb_table_has_value (GvdbTable *file, - const gchar *key) -{ - static const struct gvdb_hash_item *item; - gsize size; - - item = gvdb_table_lookup (file, key, 'v'); - - if (item == NULL) - return FALSE; - - return gvdb_table_dereference (file, &item->value.pointer, 8, &size) != NULL; -} - -static GVariant * -gvdb_table_value_from_item (GvdbTable *table, - const struct gvdb_hash_item *item) -{ - GVariant *variant, *value; - gconstpointer data; - GBytes *bytes; - gsize size; - - data = gvdb_table_dereference (table, &item->value.pointer, 8, &size); - - if G_UNLIKELY (data == NULL) - return NULL; - - bytes = g_bytes_new_from_bytes (table->bytes, ((gchar *) data) - table->data, size); - variant = g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT, bytes, table->trusted); - value = g_variant_get_variant (variant); - g_variant_unref (variant); - g_bytes_unref (bytes); - - return value; -} - -/** - * gvdb_table_get_value: - * @file: a #GvdbTable - * @key: a string - * - * Looks up a value named @key in @file. - * - * If the value is not found then %NULL is returned. Otherwise, a new - * #GVariant instance is returned. The #GVariant does not depend on the - * continued existence of @file. - * - * You should call g_variant_unref() on the return result when you no - * longer require it. - * - * Returns: a #GVariant, or %NULL - **/ -GVariant * -gvdb_table_get_value (GvdbTable *file, - const gchar *key) -{ - const struct gvdb_hash_item *item; - GVariant *value; - - if ((item = gvdb_table_lookup (file, key, 'v')) == NULL) - return NULL; - - value = gvdb_table_value_from_item (file, item); - - if (value && file->byteswapped) - { - GVariant *tmp; - - tmp = g_variant_byteswap (value); - g_variant_unref (value); - value = tmp; - } - - return value; -} - -/** - * gvdb_table_get_raw_value: - * @table: a #GvdbTable - * @key: a string - * - * Looks up a value named @key in @file. - * - * This call is equivalent to gvdb_table_get_value() except that it - * never byteswaps the value. - * - * Returns: a #GVariant, or %NULL - **/ -GVariant * -gvdb_table_get_raw_value (GvdbTable *table, - const gchar *key) -{ - const struct gvdb_hash_item *item; - - if ((item = gvdb_table_lookup (table, key, 'v')) == NULL) - return NULL; - - return gvdb_table_value_from_item (table, item); -} - -/** - * gvdb_table_get_table: - * @file: a #GvdbTable - * @key: a string - * - * Looks up the hash table named @key in @file. - * - * The toplevel hash table in a #GvdbTable can contain reference to - * child hash tables (and those can contain further references...). - * - * If @key is not found in @file then %NULL is returned. Otherwise, a - * new #GvdbTable is returned, referring to the child hashtable as - * contained in the file. This newly-created #GvdbTable does not depend - * on the continued existence of @file. - * - * You should call gvdb_table_free() on the return result when you no - * longer require it. - * - * Returns: a new #GvdbTable, or %NULL - **/ -GvdbTable * -gvdb_table_get_table (GvdbTable *file, - const gchar *key) -{ - const struct gvdb_hash_item *item; - GvdbTable *new; - - item = gvdb_table_lookup (file, key, 'H'); - - if (item == NULL) - return NULL; - - new = g_slice_new0 (GvdbTable); - new->bytes = g_bytes_ref (file->bytes); - new->byteswapped = file->byteswapped; - new->trusted = file->trusted; - new->data = file->data; - new->size = file->size; - - gvdb_table_setup_root (new, &item->value.pointer); - - return new; -} - -/** - * gvdb_table_free: - * @file: a #GvdbTable - * - * Frees @file. - **/ -void -gvdb_table_free (GvdbTable *file) -{ - g_bytes_unref (file->bytes); - g_slice_free (GvdbTable, file); -} - -/** - * gvdb_table_is_valid: - * @table: a #GvdbTable - * - * Checks if the table is still valid. - * - * An on-disk GVDB can be marked as invalid. This happens when the file - * has been replaced. The appropriate action is typically to reopen the - * file. - * - * Returns: %TRUE if @table is still valid - **/ -gboolean -gvdb_table_is_valid (GvdbTable *table) -{ - return !!*table->data; -} diff --git a/gvdb-reader.h b/gvdb-reader.h deleted file mode 100644 index 79a97d3..0000000 --- a/gvdb-reader.h +++ /dev/null @@ -1,78 +0,0 @@ -/* - * Copyright © 2010 Codethink Limited - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library 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 - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see . - * - * Author: Ryan Lortie - */ - -#ifndef __gvdb_reader_h__ -#define __gvdb_reader_h__ - -#include - -/* We cannot enable the weak attribute unconditionally here because both - * gvdb/gvdb-reader.c and tests/dconf-mock-gvdb.c include this file. The - * intention of using weak symbols here is to allow the latter to override - * functions defined in the former, so functions in tests/dconf-mock-gvdb.c - * must have strong bindings. */ -#ifdef GVDB_USE_WEAK_SYMBOLS -# ifdef __GNUC__ -# define GVDB_GNUC_WEAK __attribute__((weak)) -# else -# define GVDB_GNUC_WEAK -# endif -#else -# define GVDB_GNUC_WEAK -#endif - -typedef struct _GvdbTable GvdbTable; - -G_BEGIN_DECLS - -G_GNUC_INTERNAL GVDB_GNUC_WEAK -GvdbTable * gvdb_table_new_from_bytes (GBytes *bytes, - gboolean trusted, - GError **error); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -GvdbTable * gvdb_table_new (const gchar *filename, - gboolean trusted, - GError **error); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -void gvdb_table_free (GvdbTable *table); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -gchar ** gvdb_table_get_names (GvdbTable *table, - gsize *length); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -gchar ** gvdb_table_list (GvdbTable *table, - const gchar *key); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -GvdbTable * gvdb_table_get_table (GvdbTable *table, - const gchar *key); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -GVariant * gvdb_table_get_raw_value (GvdbTable *table, - const gchar *key); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -GVariant * gvdb_table_get_value (GvdbTable *table, - const gchar *key); - -G_GNUC_INTERNAL GVDB_GNUC_WEAK -gboolean gvdb_table_has_value (GvdbTable *table, - const gchar *key); -G_GNUC_INTERNAL GVDB_GNUC_WEAK -gboolean gvdb_table_is_valid (GvdbTable *table); - -G_END_DECLS - -#endif /* __gvdb_reader_h__ */ diff --git a/gvdb/gvdb-builder.c b/gvdb/gvdb-builder.c new file mode 100644 index 0000000..5dae03e --- /dev/null +++ b/gvdb/gvdb-builder.c @@ -0,0 +1,637 @@ +/* + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + * + * Author: Ryan Lortie + */ + +#include "gvdb-builder.h" +#include "gvdb-format.h" + +#include +#include +#if !defined(G_OS_WIN32) || !defined(_MSC_VER) +#include +#endif +#include + + +struct _GvdbItem +{ + gchar *key; + guint32 hash_value; + guint32_le assigned_index; + GvdbItem *parent; + GvdbItem *sibling; + GvdbItem *next; + + /* one of: + * this: + */ + GVariant *value; + + /* this: */ + GHashTable *table; + + /* or this: */ + GvdbItem *child; +}; + +static void +gvdb_item_free (gpointer data) +{ + GvdbItem *item = data; + + g_free (item->key); + + if (item->value) + g_variant_unref (item->value); + + if (item->table) + g_hash_table_unref (item->table); + + g_slice_free (GvdbItem, item); +} + +GHashTable * +gvdb_hash_table_new (GHashTable *parent, + const gchar *name_in_parent) +{ + GHashTable *table; + + table = g_hash_table_new_full (g_str_hash, g_str_equal, + g_free, gvdb_item_free); + + if (parent) + { + GvdbItem *item; + + item = gvdb_hash_table_insert (parent, name_in_parent); + gvdb_item_set_hash_table (item, table); + } + + return table; +} + +static guint32 +djb_hash (const gchar *key) +{ + guint32 hash_value = 5381; + + while (*key) + hash_value = hash_value * 33 + *(signed char *)key++; + + return hash_value; +} + +GvdbItem * +gvdb_hash_table_insert (GHashTable *table, + const gchar *key) +{ + GvdbItem *item; + + item = g_slice_new0 (GvdbItem); + item->key = g_strdup (key); + item->hash_value = djb_hash (key); + + g_hash_table_insert (table, g_strdup (key), item); + + return item; +} + +void +gvdb_hash_table_insert_string (GHashTable *table, + const gchar *key, + const gchar *value) +{ + GvdbItem *item; + + item = gvdb_hash_table_insert (table, key); + gvdb_item_set_value (item, g_variant_new_string (value)); +} + +void +gvdb_item_set_value (GvdbItem *item, + GVariant *value) +{ + g_return_if_fail (!item->value && !item->table && !item->child); + + item->value = g_variant_ref_sink (value); +} + +void +gvdb_item_set_hash_table (GvdbItem *item, + GHashTable *table) +{ + g_return_if_fail (!item->value && !item->table && !item->child); + + item->table = g_hash_table_ref (table); +} + +void +gvdb_item_set_parent (GvdbItem *item, + GvdbItem *parent) +{ + GvdbItem **node; + + g_return_if_fail (g_str_has_prefix (item->key, parent->key)); + g_return_if_fail (!parent->value && !parent->table); + g_return_if_fail (!item->parent && !item->sibling); + + for (node = &parent->child; *node; node = &(*node)->sibling) + if (strcmp ((*node)->key, item->key) > 0) + break; + + item->parent = parent; + item->sibling = *node; + *node = item; +} + +typedef struct +{ + GvdbItem **buckets; + gsize n_buckets; +} HashTable; + +static HashTable * +hash_table_new (gsize n_buckets) +{ + HashTable *table; + + table = g_slice_new (HashTable); + table->buckets = g_new0 (GvdbItem *, n_buckets); + table->n_buckets = n_buckets; + + return table; +} + +static void +hash_table_free (HashTable *table) +{ + g_free (table->buckets); + + g_slice_free (HashTable, table); +} + +static void +hash_table_insert (gpointer key, + gpointer value, + gpointer data) +{ + guint32 hash_value, bucket; + HashTable *table = data; + GvdbItem *item = value; + + hash_value = djb_hash (key); + bucket = hash_value % table->n_buckets; + item->next = table->buckets[bucket]; + table->buckets[bucket] = item; +} + +static guint32_le +item_to_index (GvdbItem *item) +{ + if (item != NULL) + return item->assigned_index; + + return guint32_to_le ((guint32) -1); +} + +typedef struct +{ + GQueue *chunks; + guint64 offset; + gboolean byteswap; +} FileBuilder; + +typedef struct +{ + gsize offset; + gsize size; + gpointer data; +} FileChunk; + +static gpointer +file_builder_allocate (FileBuilder *fb, + guint alignment, + gsize size, + struct gvdb_pointer *pointer) +{ + FileChunk *chunk; + + if (size == 0) + return NULL; + + fb->offset += (guint64) (-fb->offset) & (alignment - 1); + chunk = g_slice_new (FileChunk); + chunk->offset = fb->offset; + chunk->size = size; + chunk->data = g_malloc (size); + + pointer->start = guint32_to_le (fb->offset); + fb->offset += size; + pointer->end = guint32_to_le (fb->offset); + + g_queue_push_tail (fb->chunks, chunk); + + return chunk->data; +} + +static void +file_builder_add_value (FileBuilder *fb, + GVariant *value, + struct gvdb_pointer *pointer) +{ + GVariant *variant, *normal; + gpointer data; + gsize size; + + if (fb->byteswap) + { + value = g_variant_byteswap (value); + variant = g_variant_new_variant (value); + g_variant_unref (value); + } + else + variant = g_variant_new_variant (value); + + normal = g_variant_get_normal_form (variant); + g_variant_unref (variant); + + size = g_variant_get_size (normal); + data = file_builder_allocate (fb, 8, size, pointer); + g_variant_store (normal, data); + g_variant_unref (normal); +} + +static void +file_builder_add_string (FileBuilder *fb, + const gchar *string, + guint32_le *start, + guint16_le *size) +{ + FileChunk *chunk; + gsize length; + + length = strlen (string); + + chunk = g_slice_new (FileChunk); + chunk->offset = fb->offset; + chunk->size = length; + chunk->data = g_malloc (length); + if (length != 0) + memcpy (chunk->data, string, length); + + *start = guint32_to_le (fb->offset); + *size = guint16_to_le (length); + fb->offset += length; + + g_queue_push_tail (fb->chunks, chunk); +} + +static void +file_builder_allocate_for_hash (FileBuilder *fb, + gsize n_buckets, + gsize n_items, + guint bloom_shift, + gsize n_bloom_words, + guint32_le **bloom_filter, + guint32_le **hash_buckets, + struct gvdb_hash_item **hash_items, + struct gvdb_pointer *pointer) +{ + guint32_le bloom_hdr, table_hdr; + guchar *data; + gsize size; + + g_assert (n_bloom_words < (1u << 27)); + + bloom_hdr = guint32_to_le (bloom_shift << 27 | n_bloom_words); + table_hdr = guint32_to_le (n_buckets); + + size = sizeof bloom_hdr + sizeof table_hdr + + n_bloom_words * sizeof (guint32_le) + + n_buckets * sizeof (guint32_le) + + n_items * sizeof (struct gvdb_hash_item); + + data = file_builder_allocate (fb, 4, size, pointer); + g_assert (data); + +#define chunk(s) (size -= (s), data += (s), data - (s)) + memcpy (chunk (sizeof bloom_hdr), &bloom_hdr, sizeof bloom_hdr); + memcpy (chunk (sizeof table_hdr), &table_hdr, sizeof table_hdr); + *bloom_filter = (guint32_le *) chunk (n_bloom_words * sizeof (guint32_le)); + *hash_buckets = (guint32_le *) chunk (n_buckets * sizeof (guint32_le)); + *hash_items = (struct gvdb_hash_item *) chunk (n_items * + sizeof (struct gvdb_hash_item)); + g_assert (size == 0); +#undef chunk + + memset (*bloom_filter, 0, n_bloom_words * sizeof (guint32_le)); + memset (*hash_buckets, 0, n_buckets * sizeof (guint32_le)); + memset (*hash_items, 0, n_items * sizeof (struct gvdb_hash_item)); + + /* NOTE - the code to actually fill in the bloom filter here is missing. + * Patches welcome! + * + * http://en.wikipedia.org/wiki/Bloom_filter + * http://0pointer.de/blog/projects/bloom.html + */ +} + +static void +file_builder_add_hash (FileBuilder *fb, + GHashTable *table, + struct gvdb_pointer *pointer) +{ + guint32_le *buckets, *bloom_filter; + struct gvdb_hash_item *items; + HashTable *mytable; + GvdbItem *item; + guint32 index; + gsize bucket; + + mytable = hash_table_new (g_hash_table_size (table)); + g_hash_table_foreach (table, hash_table_insert, mytable); + index = 0; + + for (bucket = 0; bucket < mytable->n_buckets; bucket++) + for (item = mytable->buckets[bucket]; item; item = item->next) + item->assigned_index = guint32_to_le (index++); + + file_builder_allocate_for_hash (fb, mytable->n_buckets, index, 5, 0, + &bloom_filter, &buckets, &items, pointer); + + index = 0; + for (bucket = 0; bucket < mytable->n_buckets; bucket++) + { + buckets[bucket] = guint32_to_le (index); + + for (item = mytable->buckets[bucket]; item; item = item->next) + { + struct gvdb_hash_item *entry = items++; + const gchar *basename; + + g_assert (index == guint32_from_le (item->assigned_index)); + entry->hash_value = guint32_to_le (item->hash_value); + entry->parent = item_to_index (item->parent); + entry->unused = 0; + + if (item->parent != NULL) + basename = item->key + strlen (item->parent->key); + else + basename = item->key; + + file_builder_add_string (fb, basename, + &entry->key_start, + &entry->key_size); + + if (item->value != NULL) + { + g_assert (item->child == NULL && item->table == NULL); + + file_builder_add_value (fb, item->value, &entry->value.pointer); + entry->type = 'v'; + } + + if (item->child != NULL) + { + guint32 children = 0, i = 0; + guint32_le *offsets; + GvdbItem *child; + + g_assert (item->table == NULL); + + for (child = item->child; child; child = child->sibling) + children++; + + offsets = file_builder_allocate (fb, 4, 4 * children, + &entry->value.pointer); + entry->type = 'L'; + + for (child = item->child; child; child = child->sibling) + offsets[i++] = child->assigned_index; + + g_assert (children == i); + } + + if (item->table != NULL) + { + entry->type = 'H'; + file_builder_add_hash (fb, item->table, &entry->value.pointer); + } + + index++; + } + } + + hash_table_free (mytable); +} + +static FileBuilder * +file_builder_new (gboolean byteswap) +{ + FileBuilder *builder; + + builder = g_slice_new (FileBuilder); + builder->chunks = g_queue_new (); + builder->offset = sizeof (struct gvdb_header); + builder->byteswap = byteswap; + + return builder; +} + +static void +file_builder_free (FileBuilder *fb) +{ + g_queue_free (fb->chunks); + g_slice_free (FileBuilder, fb); +} + +static GString * +file_builder_serialise (FileBuilder *fb, + struct gvdb_pointer root) +{ + struct gvdb_header header; + GString *result; + + memset (&header, 0, sizeof (header)); + + if (fb->byteswap) + { + header.signature[0] = GVDB_SWAPPED_SIGNATURE0; + header.signature[1] = GVDB_SWAPPED_SIGNATURE1; + } + else + { + header.signature[0] = GVDB_SIGNATURE0; + header.signature[1] = GVDB_SIGNATURE1; + } + + result = g_string_new (NULL); + + header.root = root; + g_string_append_len (result, (gpointer) &header, sizeof header); + + while (!g_queue_is_empty (fb->chunks)) + { + FileChunk *chunk = g_queue_pop_head (fb->chunks); + + if (result->len != chunk->offset) + { + gchar zero[8] = { 0, }; + + g_assert (chunk->offset > result->len); + g_assert (chunk->offset - result->len < 8); + + g_string_append_len (result, zero, chunk->offset - result->len); + g_assert (result->len == chunk->offset); + } + + g_string_append_len (result, chunk->data, chunk->size); + g_free (chunk->data); + + g_slice_free (FileChunk, chunk); + } + + return result; +} + +gboolean +gvdb_table_write_contents (GHashTable *table, + const gchar *filename, + gboolean byteswap, + GError **error) +{ + struct gvdb_pointer root; + gboolean status; + FileBuilder *fb; + GString *str; + + g_return_val_if_fail (table != NULL, FALSE); + g_return_val_if_fail (filename != NULL, FALSE); + g_return_val_if_fail (error == NULL || *error == NULL, FALSE); + + fb = file_builder_new (byteswap); + file_builder_add_hash (fb, table, &root); + str = file_builder_serialise (fb, root); + file_builder_free (fb); + + status = g_file_set_contents (filename, str->str, str->len, error); + g_string_free (str, TRUE); + + return status; +} + +typedef struct { + GBytes *contents; /* (owned) */ + GFile *file; /* (owned) */ +} WriteContentsData; + +static WriteContentsData * +write_contents_data_new (GBytes *contents, + GFile *file) +{ + WriteContentsData *data; + + data = g_slice_new (WriteContentsData); + data->contents = g_bytes_ref (contents); + data->file = g_object_ref (file); + + return data; +} + +static void +write_contents_data_free (WriteContentsData *data) +{ + g_bytes_unref (data->contents); + g_object_unref (data->file); + g_slice_free (WriteContentsData, data); +} + +static void +replace_contents_cb (GObject *source_object, + GAsyncResult *result, + gpointer user_data) +{ + GTask *task = user_data; + WriteContentsData *data = g_task_get_task_data (task); + GError *error = NULL; + + g_return_if_fail (g_task_get_source_tag (task) == gvdb_table_write_contents_async); + + if (!g_file_replace_contents_finish (data->file, result, NULL, &error)) + g_task_return_error (task, g_steal_pointer (&error)); + else + g_task_return_boolean (task, TRUE); + + g_object_unref (task); +} + +void +gvdb_table_write_contents_async (GHashTable *table, + const gchar *filename, + gboolean byteswap, + GCancellable *cancellable, + GAsyncReadyCallback callback, + gpointer user_data) +{ + struct gvdb_pointer root; + FileBuilder *fb; + WriteContentsData *data; + GString *str; + GBytes *bytes; + GFile *file; + GTask *task; + + g_return_if_fail (table != NULL); + g_return_if_fail (filename != NULL); + g_return_if_fail (cancellable == NULL || G_IS_CANCELLABLE (cancellable)); + + fb = file_builder_new (byteswap); + file_builder_add_hash (fb, table, &root); + str = file_builder_serialise (fb, root); + bytes = g_string_free_to_bytes (str); + file_builder_free (fb); + + file = g_file_new_for_path (filename); + data = write_contents_data_new (bytes, file); + + task = g_task_new (NULL, cancellable, callback, user_data); + g_task_set_task_data (task, data, (GDestroyNotify)write_contents_data_free); + g_task_set_source_tag (task, gvdb_table_write_contents_async); + + g_file_replace_contents_async (file, + g_bytes_get_data (bytes, NULL), + g_bytes_get_size (bytes), + NULL, FALSE, + G_FILE_CREATE_PRIVATE, + cancellable, replace_contents_cb, g_steal_pointer (&task)); + + g_bytes_unref (bytes); + g_object_unref (file); +} + +gboolean +gvdb_table_write_contents_finish (GHashTable *table, + GAsyncResult *result, + GError **error) +{ + g_return_val_if_fail (table != NULL, FALSE); + g_return_val_if_fail (g_task_is_valid (result, NULL), FALSE); + g_return_val_if_fail (error == NULL || *error == NULL, FALSE); + + return g_task_propagate_boolean (G_TASK (result), error); +} diff --git a/gvdb/gvdb-builder.h b/gvdb/gvdb-builder.h new file mode 100644 index 0000000..30757d0 --- /dev/null +++ b/gvdb/gvdb-builder.h @@ -0,0 +1,66 @@ +/* + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + * + * Author: Ryan Lortie + */ + +#ifndef __gvdb_builder_h__ +#define __gvdb_builder_h__ + +#include + +typedef struct _GvdbItem GvdbItem; + +G_GNUC_INTERNAL +GHashTable * gvdb_hash_table_new (GHashTable *parent, + const gchar *key); + +G_GNUC_INTERNAL +GvdbItem * gvdb_hash_table_insert (GHashTable *table, + const gchar *key); +G_GNUC_INTERNAL +void gvdb_hash_table_insert_string (GHashTable *table, + const gchar *key, + const gchar *value); + +G_GNUC_INTERNAL +void gvdb_item_set_value (GvdbItem *item, + GVariant *value); +G_GNUC_INTERNAL +void gvdb_item_set_hash_table (GvdbItem *item, + GHashTable *table); +G_GNUC_INTERNAL +void gvdb_item_set_parent (GvdbItem *item, + GvdbItem *parent); + +G_GNUC_INTERNAL +gboolean gvdb_table_write_contents (GHashTable *table, + const gchar *filename, + gboolean byteswap, + GError **error); +G_GNUC_INTERNAL +void gvdb_table_write_contents_async (GHashTable *table, + const gchar *filename, + gboolean byteswap, + GCancellable *cancellable, + GAsyncReadyCallback callback, + gpointer user_data); +G_GNUC_INTERNAL +gboolean gvdb_table_write_contents_finish (GHashTable *table, + GAsyncResult *result, + GError **error); + +#endif /* __gvdb_builder_h__ */ diff --git a/gvdb/gvdb-format.h b/gvdb/gvdb-format.h new file mode 100644 index 0000000..ed6adab --- /dev/null +++ b/gvdb/gvdb-format.h @@ -0,0 +1,85 @@ +/* + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + * + * Author: Ryan Lortie + */ + +#ifndef __gvdb_format_h__ +#define __gvdb_format_h__ + +#include + +typedef struct { guint16 value; } guint16_le; +typedef struct { guint32 value; } guint32_le; + +struct gvdb_pointer { + guint32_le start; + guint32_le end; +}; + +struct gvdb_hash_header { + guint32_le n_bloom_words; + guint32_le n_buckets; +}; + +struct gvdb_hash_item { + guint32_le hash_value; + guint32_le parent; + + guint32_le key_start; + guint16_le key_size; + gchar type; + gchar unused; + + union + { + struct gvdb_pointer pointer; + gchar direct[8]; + } value; +}; + +struct gvdb_header { + guint32 signature[2]; + guint32_le version; + guint32_le options; + + struct gvdb_pointer root; +}; + +static inline guint32_le guint32_to_le (guint32 value) { + guint32_le result = { GUINT32_TO_LE (value) }; + return result; +} + +static inline guint32 guint32_from_le (guint32_le value) { + return GUINT32_FROM_LE (value.value); +} + +static inline guint16_le guint16_to_le (guint16 value) { + guint16_le result = { GUINT16_TO_LE (value) }; + return result; +} + +static inline guint16 guint16_from_le (guint16_le value) { + return GUINT16_FROM_LE (value.value); +} + +#define GVDB_SIGNATURE0 1918981703 +#define GVDB_SIGNATURE1 1953390953 +#define GVDB_SWAPPED_SIGNATURE0 GUINT32_SWAP_LE_BE (GVDB_SIGNATURE0) +#define GVDB_SWAPPED_SIGNATURE1 GUINT32_SWAP_LE_BE (GVDB_SIGNATURE1) + +#endif /* __gvdb_format_h__ */ diff --git a/gvdb/gvdb-reader.c b/gvdb/gvdb-reader.c new file mode 100644 index 0000000..820ce4c --- /dev/null +++ b/gvdb/gvdb-reader.c @@ -0,0 +1,736 @@ +/* + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + * + * Author: Ryan Lortie + */ + +#include "gvdb-reader.h" +#include "gvdb-format.h" + +#include + +struct _GvdbTable { + GBytes *bytes; + + const gchar *data; + gsize size; + + gboolean byteswapped; + gboolean trusted; + + const guint32_le *bloom_words; + guint32 n_bloom_words; + guint bloom_shift; + + const guint32_le *hash_buckets; + guint32 n_buckets; + + struct gvdb_hash_item *hash_items; + guint32 n_hash_items; +}; + +static const gchar * +gvdb_table_item_get_key (GvdbTable *file, + const struct gvdb_hash_item *item, + gsize *size) +{ + guint32 start, end; + + start = guint32_from_le (item->key_start); + *size = guint16_from_le (item->key_size); + end = start + *size; + + if G_UNLIKELY (start > end || end > file->size) + return NULL; + + return file->data + start; +} + +static gconstpointer +gvdb_table_dereference (GvdbTable *file, + const struct gvdb_pointer *pointer, + gint alignment, + gsize *size) +{ + guint32 start, end; + + start = guint32_from_le (pointer->start); + end = guint32_from_le (pointer->end); + + if G_UNLIKELY (start > end || end > file->size || start & (alignment - 1)) + return NULL; + + *size = end - start; + + return file->data + start; +} + +static void +gvdb_table_setup_root (GvdbTable *file, + const struct gvdb_pointer *pointer) +{ + const struct gvdb_hash_header *header; + guint32 n_bloom_words; + guint32 n_buckets; + gsize size; + + header = gvdb_table_dereference (file, pointer, 4, &size); + + if G_UNLIKELY (header == NULL || size < sizeof *header) + return; + + size -= sizeof *header; + + n_bloom_words = guint32_from_le (header->n_bloom_words); + n_buckets = guint32_from_le (header->n_buckets); + n_bloom_words &= (1u << 27) - 1; + + if G_UNLIKELY (n_bloom_words * sizeof (guint32_le) > size) + return; + + file->bloom_words = (gpointer) (header + 1); + size -= n_bloom_words * sizeof (guint32_le); + file->n_bloom_words = n_bloom_words; + + if G_UNLIKELY (n_buckets > G_MAXUINT / sizeof (guint32_le) || + n_buckets * sizeof (guint32_le) > size) + return; + + file->hash_buckets = file->bloom_words + file->n_bloom_words; + size -= n_buckets * sizeof (guint32_le); + file->n_buckets = n_buckets; + + if G_UNLIKELY (size % sizeof (struct gvdb_hash_item)) + return; + + file->hash_items = (gpointer) (file->hash_buckets + n_buckets); + file->n_hash_items = size / sizeof (struct gvdb_hash_item); +} + +/** + * gvdb_table_new_from_bytes: + * @bytes: the #GBytes with the data + * @trusted: if the contents of @bytes are trusted + * @error: %NULL, or a pointer to a %NULL #GError + * + * Creates a new #GvdbTable from the contents of @bytes. + * + * This call can fail if the header contained in @bytes is invalid or if @bytes + * is empty; if so, %G_FILE_ERROR_INVAL will be returned. + * + * You should call gvdb_table_free() on the return result when you no + * longer require it. + * + * Returns: a new #GvdbTable + **/ +GvdbTable * +gvdb_table_new_from_bytes (GBytes *bytes, + gboolean trusted, + GError **error) +{ + const struct gvdb_header *header; + GvdbTable *file; + + file = g_slice_new0 (GvdbTable); + file->bytes = g_bytes_ref (bytes); + file->data = g_bytes_get_data (bytes, &file->size); + file->trusted = trusted; + + if (file->size < sizeof (struct gvdb_header)) + goto invalid; + + header = (gpointer) file->data; + + if (header->signature[0] == GVDB_SIGNATURE0 && + header->signature[1] == GVDB_SIGNATURE1 && + guint32_from_le (header->version) == 0) + file->byteswapped = FALSE; + + else if (header->signature[0] == GVDB_SWAPPED_SIGNATURE0 && + header->signature[1] == GVDB_SWAPPED_SIGNATURE1 && + guint32_from_le (header->version) == 0) + file->byteswapped = TRUE; + + else + goto invalid; + + gvdb_table_setup_root (file, &header->root); + + return file; + +invalid: + g_set_error_literal (error, G_FILE_ERROR, G_FILE_ERROR_INVAL, "invalid gvdb header"); + + g_bytes_unref (file->bytes); + + g_slice_free (GvdbTable, file); + + return NULL; +} + +/** + * gvdb_table_new: + * @filename: a filename + * @trusted: if the contents of @bytes are trusted + * @error: %NULL, or a pointer to a %NULL #GError + * + * Creates a new #GvdbTable using the #GMappedFile for @filename as the + * #GBytes. + * + * This function will fail if the file cannot be opened. + * In that case, the #GError that is returned will be an error from + * g_mapped_file_new(). + * + * An empty or corrupt file will result in %G_FILE_ERROR_INVAL. + * + * Returns: a new #GvdbTable + **/ +GvdbTable * +gvdb_table_new (const gchar *filename, + gboolean trusted, + GError **error) +{ + GMappedFile *mapped; + GvdbTable *table; + GBytes *bytes; + + mapped = g_mapped_file_new (filename, FALSE, error); + if (!mapped) + return NULL; + + bytes = g_mapped_file_get_bytes (mapped); + table = gvdb_table_new_from_bytes (bytes, trusted, error); + g_mapped_file_unref (mapped); + g_bytes_unref (bytes); + + g_prefix_error (error, "%s: ", filename); + + return table; +} + +static gboolean +gvdb_table_bloom_filter (GvdbTable *file, + guint32 hash_value) +{ + guint32 word, mask; + + if (file->n_bloom_words == 0) + return TRUE; + + word = (hash_value / 32) % file->n_bloom_words; + mask = 1 << (hash_value & 31); + mask |= 1 << ((hash_value >> file->bloom_shift) & 31); + + return (guint32_from_le (file->bloom_words[word]) & mask) == mask; +} + +static gboolean +gvdb_table_check_name (GvdbTable *file, + struct gvdb_hash_item *item, + const gchar *key, + guint key_length) +{ + const gchar *this_key; + gsize this_size; + guint32 parent; + + this_key = gvdb_table_item_get_key (file, item, &this_size); + + if G_UNLIKELY (this_key == NULL || this_size > key_length) + return FALSE; + + key_length -= this_size; + + if G_UNLIKELY (memcmp (this_key, key + key_length, this_size) != 0) + return FALSE; + + parent = guint32_from_le (item->parent); + if (key_length == 0 && parent == 0xffffffffu) + return TRUE; + + if G_LIKELY (parent < file->n_hash_items && this_size > 0) + return gvdb_table_check_name (file, + &file->hash_items[parent], + key, key_length); + + return FALSE; +} + +static const struct gvdb_hash_item * +gvdb_table_lookup (GvdbTable *file, + const gchar *key, + gchar type) +{ + guint32 hash_value = 5381; + guint key_length; + guint32 bucket; + guint32 lastno; + guint32 itemno; + + if G_UNLIKELY (file->n_buckets == 0 || file->n_hash_items == 0) + return NULL; + + for (key_length = 0; key[key_length]; key_length++) + hash_value = (hash_value * 33) + ((signed char *) key)[key_length]; + + if (!gvdb_table_bloom_filter (file, hash_value)) + return NULL; + + bucket = hash_value % file->n_buckets; + itemno = guint32_from_le (file->hash_buckets[bucket]); + + if (bucket == file->n_buckets - 1 || + (lastno = guint32_from_le(file->hash_buckets[bucket + 1])) > file->n_hash_items) + lastno = file->n_hash_items; + + while G_LIKELY (itemno < lastno) + { + struct gvdb_hash_item *item = &file->hash_items[itemno]; + + if (hash_value == guint32_from_le (item->hash_value)) + if G_LIKELY (gvdb_table_check_name (file, item, key, key_length)) + if G_LIKELY (item->type == type) + return item; + + itemno++; + } + + return NULL; +} + +static gboolean +gvdb_table_list_from_item (GvdbTable *table, + const struct gvdb_hash_item *item, + const guint32_le **list, + guint *length) +{ + gsize size; + + *list = gvdb_table_dereference (table, &item->value.pointer, 4, &size); + + if G_LIKELY (*list == NULL || size % 4) + return FALSE; + + *length = size / 4; + + return TRUE; +} + +/** + * gvdb_table_get_names: + * @table: a #GvdbTable + * @length: (out) (optional): the number of items returned, or %NULL + * + * Gets a list of all names contained in @table. + * + * No call to gvdb_table_get_table(), gvdb_table_list() or + * gvdb_table_get_value() will succeed unless it is for one of the + * names returned by this function. + * + * Note that some names that are returned may still fail for all of the + * above calls in the case of the corrupted file. Note also that the + * returned strings may not be utf8. + * + * Returns: (array length=length): a %NULL-terminated list of strings, of length @length + **/ +gchar ** +gvdb_table_get_names (GvdbTable *table, + gsize *length) +{ + gchar **names; + guint n_names; + guint filled; + guint total; + guint i; + + /* We generally proceed by iterating over the list of items in the + * hash table (in order of appearance) recording them into an array. + * + * Each item has a parent item (except root items). The parent item + * forms part of the name of the item. We could go fetching the + * parent item chain at the point that we encounter each item but then + * we would need to implement some sort of recursion along with checks + * for self-referential items. + * + * Instead, we do a number of passes. Each pass will build up one + * level of names (starting from the root). We continue to do passes + * until no more items are left. The first pass will only add root + * items and each further pass will only add items whose direct parent + * is an item added in the immediately previous pass. It's also + * possible that items get filled if they follow their parent within a + * particular pass. + * + * At most we will have a number of passes equal to the depth of the + * tree. Self-referential items will never be filled in (since their + * parent will have never been filled in). We continue until we have + * a pass that fills in no additional items. + * + * This takes an O(n) algorithm and turns it into O(n*m) where m is + * the depth of the tree, but typically the tree won't be very + * deep and the constant factor of this algorithm is lower (and the + * complexity of coding it, as well). + */ + + n_names = table->n_hash_items; + names = g_new0 (gchar *, n_names + 1); + + /* 'names' starts out all-NULL. On each pass we record the number + * of items changed from NULL to non-NULL in 'filled' so we know if we + * should repeat the loop. 'total' counts the total number of items + * filled. If 'total' ends up equal to 'n_names' then we know that + * 'names' has been completely filled. + */ + + total = 0; + do + { + /* Loop until we have filled no more entries */ + filled = 0; + + for (i = 0; i < n_names; i++) + { + const struct gvdb_hash_item *item = &table->hash_items[i]; + const gchar *name; + gsize name_length; + guint32 parent; + + /* already got it on a previous pass */ + if (names[i] != NULL) + continue; + + parent = guint32_from_le (item->parent); + + if (parent == 0xffffffffu) + { + /* it's a root item */ + name = gvdb_table_item_get_key (table, item, &name_length); + + if (name != NULL) + { + names[i] = g_strndup (name, name_length); + filled++; + } + } + + else if (parent < n_names && names[parent] != NULL) + { + /* It's a non-root item whose parent was filled in already. + * + * Calculate the name of this item by combining it with + * its parent name. + */ + name = gvdb_table_item_get_key (table, item, &name_length); + + if (name != NULL) + { + const gchar *parent_name = names[parent]; + gsize parent_length; + gchar *fullname; + + parent_length = strlen (parent_name); + fullname = g_malloc (parent_length + name_length + 1); + memcpy (fullname, parent_name, parent_length); + memcpy (fullname + parent_length, name, name_length); + fullname[parent_length + name_length] = '\0'; + names[i] = fullname; + filled++; + } + } + } + + total += filled; + } + while (filled && total < n_names); + + /* If the table was corrupted then 'names' may have holes in it. + * Collapse those. + */ + if G_UNLIKELY (total != n_names) + { + GPtrArray *fixed_names; + + fixed_names = g_ptr_array_sized_new (n_names + 1 /* NULL terminator */); + for (i = 0; i < n_names; i++) + if (names[i] != NULL) + g_ptr_array_add (fixed_names, names[i]); + + g_free (names); + n_names = fixed_names->len; + g_ptr_array_add (fixed_names, NULL); + names = (gchar **) g_ptr_array_free (fixed_names, FALSE); + } + + if (length) + { + G_STATIC_ASSERT (sizeof (*length) >= sizeof (n_names)); + *length = n_names; + } + + return names; +} + +/** + * gvdb_table_list: + * @file: a #GvdbTable + * @key: a string + * + * List all of the keys that appear below @key. The nesting of keys + * within the hash file is defined by the program that created the hash + * file. One thing is constant: each item in the returned array can be + * concatenated to @key to obtain the full name of that key. + * + * It is not possible to tell from this function if a given key is + * itself a path, a value, or another hash table; you are expected to + * know this for yourself. + * + * You should call g_strfreev() on the return result when you no longer + * require it. + * + * Returns: a %NULL-terminated string array + **/ +gchar ** +gvdb_table_list (GvdbTable *file, + const gchar *key) +{ + const struct gvdb_hash_item *item; + const guint32_le *list; + gchar **strv; + guint length; + guint i; + + if ((item = gvdb_table_lookup (file, key, 'L')) == NULL) + return NULL; + + if (!gvdb_table_list_from_item (file, item, &list, &length)) + return NULL; + + strv = g_new (gchar *, length + 1); + for (i = 0; i < length; i++) + { + guint32 itemno = guint32_from_le (list[i]); + + if (itemno < file->n_hash_items) + { + const struct gvdb_hash_item *item; + const gchar *string; + gsize strsize; + + item = file->hash_items + itemno; + + string = gvdb_table_item_get_key (file, item, &strsize); + + if (string != NULL) + strv[i] = g_strndup (string, strsize); + else + strv[i] = g_malloc0 (1); + } + else + strv[i] = g_malloc0 (1); + } + + strv[i] = NULL; + + return strv; +} + +/** + * gvdb_table_has_value: + * @file: a #GvdbTable + * @key: a string + * + * Checks for a value named @key in @file. + * + * Note: this function does not consider non-value nodes (other hash + * tables, for example). + * + * Returns: %TRUE if @key is in the table + **/ +gboolean +gvdb_table_has_value (GvdbTable *file, + const gchar *key) +{ + static const struct gvdb_hash_item *item; + gsize size; + + item = gvdb_table_lookup (file, key, 'v'); + + if (item == NULL) + return FALSE; + + return gvdb_table_dereference (file, &item->value.pointer, 8, &size) != NULL; +} + +static GVariant * +gvdb_table_value_from_item (GvdbTable *table, + const struct gvdb_hash_item *item) +{ + GVariant *variant, *value; + gconstpointer data; + GBytes *bytes; + gsize size; + + data = gvdb_table_dereference (table, &item->value.pointer, 8, &size); + + if G_UNLIKELY (data == NULL) + return NULL; + + bytes = g_bytes_new_from_bytes (table->bytes, ((gchar *) data) - table->data, size); + variant = g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT, bytes, table->trusted); + value = g_variant_get_variant (variant); + g_variant_unref (variant); + g_bytes_unref (bytes); + + return value; +} + +/** + * gvdb_table_get_value: + * @file: a #GvdbTable + * @key: a string + * + * Looks up a value named @key in @file. + * + * If the value is not found then %NULL is returned. Otherwise, a new + * #GVariant instance is returned. The #GVariant does not depend on the + * continued existence of @file. + * + * You should call g_variant_unref() on the return result when you no + * longer require it. + * + * Returns: a #GVariant, or %NULL + **/ +GVariant * +gvdb_table_get_value (GvdbTable *file, + const gchar *key) +{ + const struct gvdb_hash_item *item; + GVariant *value; + + if ((item = gvdb_table_lookup (file, key, 'v')) == NULL) + return NULL; + + value = gvdb_table_value_from_item (file, item); + + if (value && file->byteswapped) + { + GVariant *tmp; + + tmp = g_variant_byteswap (value); + g_variant_unref (value); + value = tmp; + } + + return value; +} + +/** + * gvdb_table_get_raw_value: + * @table: a #GvdbTable + * @key: a string + * + * Looks up a value named @key in @file. + * + * This call is equivalent to gvdb_table_get_value() except that it + * never byteswaps the value. + * + * Returns: a #GVariant, or %NULL + **/ +GVariant * +gvdb_table_get_raw_value (GvdbTable *table, + const gchar *key) +{ + const struct gvdb_hash_item *item; + + if ((item = gvdb_table_lookup (table, key, 'v')) == NULL) + return NULL; + + return gvdb_table_value_from_item (table, item); +} + +/** + * gvdb_table_get_table: + * @file: a #GvdbTable + * @key: a string + * + * Looks up the hash table named @key in @file. + * + * The toplevel hash table in a #GvdbTable can contain reference to + * child hash tables (and those can contain further references...). + * + * If @key is not found in @file then %NULL is returned. Otherwise, a + * new #GvdbTable is returned, referring to the child hashtable as + * contained in the file. This newly-created #GvdbTable does not depend + * on the continued existence of @file. + * + * You should call gvdb_table_free() on the return result when you no + * longer require it. + * + * Returns: a new #GvdbTable, or %NULL + **/ +GvdbTable * +gvdb_table_get_table (GvdbTable *file, + const gchar *key) +{ + const struct gvdb_hash_item *item; + GvdbTable *new; + + item = gvdb_table_lookup (file, key, 'H'); + + if (item == NULL) + return NULL; + + new = g_slice_new0 (GvdbTable); + new->bytes = g_bytes_ref (file->bytes); + new->byteswapped = file->byteswapped; + new->trusted = file->trusted; + new->data = file->data; + new->size = file->size; + + gvdb_table_setup_root (new, &item->value.pointer); + + return new; +} + +/** + * gvdb_table_free: + * @file: a #GvdbTable + * + * Frees @file. + **/ +void +gvdb_table_free (GvdbTable *file) +{ + g_bytes_unref (file->bytes); + g_slice_free (GvdbTable, file); +} + +/** + * gvdb_table_is_valid: + * @table: a #GvdbTable + * + * Checks if the table is still valid. + * + * An on-disk GVDB can be marked as invalid. This happens when the file + * has been replaced. The appropriate action is typically to reopen the + * file. + * + * Returns: %TRUE if @table is still valid + **/ +gboolean +gvdb_table_is_valid (GvdbTable *table) +{ + return !!*table->data; +} diff --git a/gvdb/gvdb-reader.h b/gvdb/gvdb-reader.h new file mode 100644 index 0000000..79a97d3 --- /dev/null +++ b/gvdb/gvdb-reader.h @@ -0,0 +1,78 @@ +/* + * Copyright © 2010 Codethink Limited + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see . + * + * Author: Ryan Lortie + */ + +#ifndef __gvdb_reader_h__ +#define __gvdb_reader_h__ + +#include + +/* We cannot enable the weak attribute unconditionally here because both + * gvdb/gvdb-reader.c and tests/dconf-mock-gvdb.c include this file. The + * intention of using weak symbols here is to allow the latter to override + * functions defined in the former, so functions in tests/dconf-mock-gvdb.c + * must have strong bindings. */ +#ifdef GVDB_USE_WEAK_SYMBOLS +# ifdef __GNUC__ +# define GVDB_GNUC_WEAK __attribute__((weak)) +# else +# define GVDB_GNUC_WEAK +# endif +#else +# define GVDB_GNUC_WEAK +#endif + +typedef struct _GvdbTable GvdbTable; + +G_BEGIN_DECLS + +G_GNUC_INTERNAL GVDB_GNUC_WEAK +GvdbTable * gvdb_table_new_from_bytes (GBytes *bytes, + gboolean trusted, + GError **error); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +GvdbTable * gvdb_table_new (const gchar *filename, + gboolean trusted, + GError **error); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +void gvdb_table_free (GvdbTable *table); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +gchar ** gvdb_table_get_names (GvdbTable *table, + gsize *length); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +gchar ** gvdb_table_list (GvdbTable *table, + const gchar *key); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +GvdbTable * gvdb_table_get_table (GvdbTable *table, + const gchar *key); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +GVariant * gvdb_table_get_raw_value (GvdbTable *table, + const gchar *key); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +GVariant * gvdb_table_get_value (GvdbTable *table, + const gchar *key); + +G_GNUC_INTERNAL GVDB_GNUC_WEAK +gboolean gvdb_table_has_value (GvdbTable *table, + const gchar *key); +G_GNUC_INTERNAL GVDB_GNUC_WEAK +gboolean gvdb_table_is_valid (GvdbTable *table); + +G_END_DECLS + +#endif /* __gvdb_reader_h__ */ diff --git a/meson.build b/meson.build new file mode 100644 index 0000000..01c86b4 --- /dev/null +++ b/meson.build @@ -0,0 +1,15 @@ +project('gvdb', 'c', + version: '0.0', + meson_version: '>=0.54.0', +) + +libgvdb_sources = files( + 'gvdb/gvdb-builder.c', + 'gvdb/gvdb-reader.c', +) + +gvdb_dep = declare_dependency( + sources: libgvdb_sources, + include_directories: include_directories('.'), +) +meson.override_dependency('gvdb', gvdb_dep) -- cgit v1.2.1