1/*
2 * Copyright © 2010 Codethink Limited
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 *
17 * Author: Ryan Lortie <desrt@desrt.ca>
18 */
19
20#include "gvdb-builder.h"
21#include "gvdb-format.h"
22
23#include <glib.h>
24#include <fcntl.h>
25#if !defined(G_OS_WIN32) || !defined(_MSC_VER)
26#include <unistd.h>
27#endif
28#include <string.h>
29
30
31struct _GvdbItem
32{
33 gchar *key;
34 guint32 hash_value;
35 guint32_le assigned_index;
36 GvdbItem *parent;
37 GvdbItem *sibling;
38 GvdbItem *next;
39
40 /* one of:
41 * this:
42 */
43 GVariant *value;
44
45 /* this: */
46 GHashTable *table;
47
48 /* or this: */
49 GvdbItem *child;
50};
51
52static void
53gvdb_item_free (gpointer data)
54{
55 GvdbItem *item = data;
56
57 g_free (mem: item->key);
58
59 if (item->value)
60 g_variant_unref (value: item->value);
61
62 if (item->table)
63 g_hash_table_unref (hash_table: item->table);
64
65 g_slice_free (GvdbItem, item);
66}
67
68GHashTable *
69gvdb_hash_table_new (GHashTable *parent,
70 const gchar *name_in_parent)
71{
72 GHashTable *table;
73
74 table = g_hash_table_new_full (hash_func: g_str_hash, key_equal_func: g_str_equal,
75 key_destroy_func: g_free, value_destroy_func: gvdb_item_free);
76
77 if (parent)
78 {
79 GvdbItem *item;
80
81 item = gvdb_hash_table_insert (table: parent, key: name_in_parent);
82 gvdb_item_set_hash_table (item, table);
83 }
84
85 return table;
86}
87
88static guint32
89djb_hash (const gchar *key)
90{
91 guint32 hash_value = 5381;
92
93 while (*key)
94 hash_value = hash_value * 33 + *(signed char *)key++;
95
96 return hash_value;
97}
98
99GvdbItem *
100gvdb_hash_table_insert (GHashTable *table,
101 const gchar *key)
102{
103 GvdbItem *item;
104
105 item = g_slice_new0 (GvdbItem);
106 item->key = g_strdup (str: key);
107 item->hash_value = djb_hash (key);
108
109 g_hash_table_insert (hash_table: table, key: g_strdup (str: key), value: item);
110
111 return item;
112}
113
114void
115gvdb_hash_table_insert_string (GHashTable *table,
116 const gchar *key,
117 const gchar *value)
118{
119 GvdbItem *item;
120
121 item = gvdb_hash_table_insert (table, key);
122 gvdb_item_set_value (item, value: g_variant_new_string (string: value));
123}
124
125void
126gvdb_item_set_value (GvdbItem *item,
127 GVariant *value)
128{
129 g_return_if_fail (!item->value && !item->table && !item->child);
130
131 item->value = g_variant_ref_sink (value);
132}
133
134void
135gvdb_item_set_hash_table (GvdbItem *item,
136 GHashTable *table)
137{
138 g_return_if_fail (!item->value && !item->table && !item->child);
139
140 item->table = g_hash_table_ref (hash_table: table);
141}
142
143void
144gvdb_item_set_parent (GvdbItem *item,
145 GvdbItem *parent)
146{
147 GvdbItem **node;
148
149 g_return_if_fail (g_str_has_prefix (item->key, parent->key));
150 g_return_if_fail (!parent->value && !parent->table);
151 g_return_if_fail (!item->parent && !item->sibling);
152
153 for (node = &parent->child; *node; node = &(*node)->sibling)
154 if (strcmp (s1: (*node)->key, s2: item->key) > 0)
155 break;
156
157 item->parent = parent;
158 item->sibling = *node;
159 *node = item;
160}
161
162typedef struct
163{
164 GvdbItem **buckets;
165 gint n_buckets;
166} HashTable;
167
168static HashTable *
169hash_table_new (gint n_buckets)
170{
171 HashTable *table;
172
173 table = g_slice_new (HashTable);
174 table->buckets = g_new0 (GvdbItem *, n_buckets);
175 table->n_buckets = n_buckets;
176
177 return table;
178}
179
180static void
181hash_table_free (HashTable *table)
182{
183 g_free (mem: table->buckets);
184
185 g_slice_free (HashTable, table);
186}
187
188static void
189hash_table_insert (gpointer key,
190 gpointer value,
191 gpointer data)
192{
193 guint32 hash_value, bucket;
194 HashTable *table = data;
195 GvdbItem *item = value;
196
197 hash_value = djb_hash (key);
198 bucket = hash_value % table->n_buckets;
199 item->next = table->buckets[bucket];
200 table->buckets[bucket] = item;
201}
202
203static guint32_le
204item_to_index (GvdbItem *item)
205{
206 if (item != NULL)
207 return item->assigned_index;
208
209 return guint32_to_le (value: (guint32) -1);
210}
211
212typedef struct
213{
214 GQueue *chunks;
215 guint64 offset;
216 gboolean byteswap;
217} FileBuilder;
218
219typedef struct
220{
221 gsize offset;
222 gsize size;
223 gpointer data;
224} FileChunk;
225
226static gpointer
227file_builder_allocate (FileBuilder *fb,
228 guint alignment,
229 gsize size,
230 struct gvdb_pointer *pointer)
231{
232 FileChunk *chunk;
233
234 if (size == 0)
235 return NULL;
236
237 fb->offset += (guint64) (-fb->offset) & (alignment - 1);
238 chunk = g_slice_new (FileChunk);
239 chunk->offset = fb->offset;
240 chunk->size = size;
241 chunk->data = g_malloc (n_bytes: size);
242
243 pointer->start = guint32_to_le (value: fb->offset);
244 fb->offset += size;
245 pointer->end = guint32_to_le (value: fb->offset);
246
247 g_queue_push_tail (queue: fb->chunks, data: chunk);
248
249 return chunk->data;
250}
251
252static void
253file_builder_add_value (FileBuilder *fb,
254 GVariant *value,
255 struct gvdb_pointer *pointer)
256{
257 GVariant *variant, *normal;
258 gpointer data;
259 gsize size;
260
261 if (fb->byteswap)
262 {
263 value = g_variant_byteswap (value);
264 variant = g_variant_new_variant (value);
265 g_variant_unref (value);
266 }
267 else
268 variant = g_variant_new_variant (value);
269
270 normal = g_variant_get_normal_form (value: variant);
271 g_variant_unref (value: variant);
272
273 size = g_variant_get_size (value: normal);
274 data = file_builder_allocate (fb, alignment: 8, size, pointer);
275 g_variant_store (value: normal, data);
276 g_variant_unref (value: normal);
277}
278
279static void
280file_builder_add_string (FileBuilder *fb,
281 const gchar *string,
282 guint32_le *start,
283 guint16_le *size)
284{
285 FileChunk *chunk;
286 gsize length;
287
288 length = strlen (s: string);
289
290 chunk = g_slice_new (FileChunk);
291 chunk->offset = fb->offset;
292 chunk->size = length;
293 chunk->data = g_malloc (n_bytes: length);
294 if (length != 0)
295 memcpy (dest: chunk->data, src: string, n: length);
296
297 *start = guint32_to_le (value: fb->offset);
298 *size = guint16_to_le (value: length);
299 fb->offset += length;
300
301 g_queue_push_tail (queue: fb->chunks, data: chunk);
302}
303
304static void
305file_builder_allocate_for_hash (FileBuilder *fb,
306 gsize n_buckets,
307 gsize n_items,
308 guint bloom_shift,
309 gsize n_bloom_words,
310 guint32_le **bloom_filter,
311 guint32_le **hash_buckets,
312 struct gvdb_hash_item **hash_items,
313 struct gvdb_pointer *pointer)
314{
315 guint32_le bloom_hdr, table_hdr;
316 guchar *data;
317 gsize size;
318
319 g_assert (n_bloom_words < (1u << 27));
320
321 bloom_hdr = guint32_to_le (value: bloom_shift << 27 | n_bloom_words);
322 table_hdr = guint32_to_le (value: n_buckets);
323
324 size = sizeof bloom_hdr + sizeof table_hdr +
325 n_bloom_words * sizeof (guint32_le) +
326 n_buckets * sizeof (guint32_le) +
327 n_items * sizeof (struct gvdb_hash_item);
328
329 data = file_builder_allocate (fb, alignment: 4, size, pointer);
330
331#define chunk(s) (size -= (s), data += (s), data - (s))
332 memcpy (chunk (sizeof bloom_hdr), src: &bloom_hdr, n: sizeof bloom_hdr);
333 memcpy (chunk (sizeof table_hdr), src: &table_hdr, n: sizeof table_hdr);
334 *bloom_filter = (guint32_le *) chunk (n_bloom_words * sizeof (guint32_le));
335 *hash_buckets = (guint32_le *) chunk (n_buckets * sizeof (guint32_le));
336 *hash_items = (struct gvdb_hash_item *) chunk (n_items *
337 sizeof (struct gvdb_hash_item));
338 g_assert (size == 0);
339#undef chunk
340
341 memset (s: *bloom_filter, c: 0, n: n_bloom_words * sizeof (guint32_le));
342 memset (s: *hash_buckets, c: 0, n: n_buckets * sizeof (guint32_le));
343 memset (s: *hash_items, c: 0, n: n_items * sizeof (struct gvdb_hash_item));
344
345 /* NOTE - the code to actually fill in the bloom filter here is missing.
346 * Patches welcome!
347 *
348 * http://en.wikipedia.org/wiki/Bloom_filter
349 * http://0pointer.de/blog/projects/bloom.html
350 */
351}
352
353static void
354file_builder_add_hash (FileBuilder *fb,
355 GHashTable *table,
356 struct gvdb_pointer *pointer)
357{
358 guint32_le *buckets, *bloom_filter;
359 struct gvdb_hash_item *items;
360 HashTable *mytable;
361 GvdbItem *item;
362 guint32 index;
363 gint bucket;
364
365 mytable = hash_table_new (n_buckets: g_hash_table_size (hash_table: table));
366 g_hash_table_foreach (hash_table: table, func: hash_table_insert, user_data: mytable);
367 index = 0;
368
369 for (bucket = 0; bucket < mytable->n_buckets; bucket++)
370 for (item = mytable->buckets[bucket]; item; item = item->next)
371 item->assigned_index = guint32_to_le (value: index++);
372
373 file_builder_allocate_for_hash (fb, n_buckets: mytable->n_buckets, n_items: index, bloom_shift: 5, n_bloom_words: 0,
374 bloom_filter: &bloom_filter, hash_buckets: &buckets, hash_items: &items, pointer);
375
376 index = 0;
377 for (bucket = 0; bucket < mytable->n_buckets; bucket++)
378 {
379 buckets[bucket] = guint32_to_le (value: index);
380
381 for (item = mytable->buckets[bucket]; item; item = item->next)
382 {
383 struct gvdb_hash_item *entry = items++;
384 const gchar *basename;
385
386 g_assert (index == guint32_from_le (item->assigned_index));
387 entry->hash_value = guint32_to_le (value: item->hash_value);
388 entry->parent = item_to_index (item: item->parent);
389 entry->unused = 0;
390
391 if (item->parent != NULL)
392 basename = item->key + strlen (s: item->parent->key);
393 else
394 basename = item->key;
395
396 file_builder_add_string (fb, string: basename,
397 start: &entry->key_start,
398 size: &entry->key_size);
399
400 if (item->value != NULL)
401 {
402 g_assert (item->child == NULL && item->table == NULL);
403
404 file_builder_add_value (fb, value: item->value, pointer: &entry->value.pointer);
405 entry->type = 'v';
406 }
407
408 if (item->child != NULL)
409 {
410 guint32 children = 0, i = 0;
411 guint32_le *offsets;
412 GvdbItem *child;
413
414 g_assert (item->table == NULL);
415
416 for (child = item->child; child; child = child->sibling)
417 children++;
418
419 offsets = file_builder_allocate (fb, alignment: 4, size: 4 * children,
420 pointer: &entry->value.pointer);
421 entry->type = 'L';
422
423 for (child = item->child; child; child = child->sibling)
424 offsets[i++] = child->assigned_index;
425
426 g_assert (children == i);
427 }
428
429 if (item->table != NULL)
430 {
431 entry->type = 'H';
432 file_builder_add_hash (fb, table: item->table, pointer: &entry->value.pointer);
433 }
434
435 index++;
436 }
437 }
438
439 hash_table_free (table: mytable);
440}
441
442static FileBuilder *
443file_builder_new (gboolean byteswap)
444{
445 FileBuilder *builder;
446
447 builder = g_slice_new (FileBuilder);
448 builder->chunks = g_queue_new ();
449 builder->offset = sizeof (struct gvdb_header);
450 builder->byteswap = byteswap;
451
452 return builder;
453}
454
455static void
456file_builder_free (FileBuilder *fb)
457{
458 g_queue_free (queue: fb->chunks);
459 g_slice_free (FileBuilder, fb);
460}
461
462static GString *
463file_builder_serialise (FileBuilder *fb,
464 struct gvdb_pointer root)
465{
466 struct gvdb_header header = { { 0, 0 }, { 0 }, { 0 }, { { 0 }, { 0 } } };
467 GString *result;
468
469 memset (s: &header, c: 0, n: sizeof (header));
470
471 if (fb->byteswap)
472 {
473 header.signature[0] = GVDB_SWAPPED_SIGNATURE0;
474 header.signature[1] = GVDB_SWAPPED_SIGNATURE1;
475 }
476 else
477 {
478 header.signature[0] = GVDB_SIGNATURE0;
479 header.signature[1] = GVDB_SIGNATURE1;
480 }
481
482 result = g_string_new (NULL);
483
484 header.root = root;
485 g_string_append_len (string: result, val: (gpointer) &header, len: sizeof header);
486
487 while (!g_queue_is_empty (queue: fb->chunks))
488 {
489 FileChunk *chunk = g_queue_pop_head (queue: fb->chunks);
490
491 if (result->len != chunk->offset)
492 {
493 gchar zero[8] = { 0, };
494
495 g_assert (chunk->offset > result->len);
496 g_assert (chunk->offset - result->len < 8);
497
498 g_string_append_len (string: result, val: zero, len: chunk->offset - result->len);
499 g_assert (result->len == chunk->offset);
500 }
501
502 g_string_append_len (string: result, val: chunk->data, len: chunk->size);
503 g_free (mem: chunk->data);
504
505 g_slice_free (FileChunk, chunk);
506 }
507
508 return result;
509}
510
511gboolean
512gvdb_table_write_contents (GHashTable *table,
513 const gchar *filename,
514 gboolean byteswap,
515 GError **error)
516{
517 struct gvdb_pointer root;
518 gboolean status;
519 FileBuilder *fb;
520 GString *str;
521
522 g_return_val_if_fail (table != NULL, FALSE);
523 g_return_val_if_fail (filename != NULL, FALSE);
524 g_return_val_if_fail (error == NULL || *error == NULL, FALSE);
525
526 fb = file_builder_new (byteswap);
527 file_builder_add_hash (fb, table, pointer: &root);
528 str = file_builder_serialise (fb, root);
529 file_builder_free (fb);
530
531 status = g_file_set_contents (filename, contents: str->str, length: str->len, error);
532 g_string_free (string: str, TRUE);
533
534 return status;
535}
536
537typedef struct {
538 GBytes *contents; /* (owned) */
539 GFile *file; /* (owned) */
540} WriteContentsData;
541
542static WriteContentsData *
543write_contents_data_new (GBytes *contents,
544 GFile *file)
545{
546 WriteContentsData *data;
547
548 data = g_slice_new (WriteContentsData);
549 data->contents = g_bytes_ref (bytes: contents);
550 data->file = g_object_ref (file);
551
552 return data;
553}
554
555static void
556write_contents_data_free (WriteContentsData *data)
557{
558 g_bytes_unref (bytes: data->contents);
559 g_object_unref (object: data->file);
560 g_slice_free (WriteContentsData, data);
561}
562
563static void
564replace_contents_cb (GObject *source_object,
565 GAsyncResult *result,
566 gpointer user_data)
567{
568 GTask *task = user_data;
569 WriteContentsData *data = g_task_get_task_data (task);
570 GError *error = NULL;
571
572 g_return_if_fail (g_task_get_source_tag (task) == gvdb_table_write_contents_async);
573
574 if (!g_file_replace_contents_finish (file: data->file, res: result, NULL, error: &error))
575 g_task_return_error (task, g_steal_pointer (&error));
576 else
577 g_task_return_boolean (task, TRUE);
578
579 g_object_unref (object: task);
580}
581
582void
583gvdb_table_write_contents_async (GHashTable *table,
584 const gchar *filename,
585 gboolean byteswap,
586 GCancellable *cancellable,
587 GAsyncReadyCallback callback,
588 gpointer user_data)
589{
590 struct gvdb_pointer root;
591 FileBuilder *fb;
592 WriteContentsData *data;
593 GString *str;
594 GBytes *bytes;
595 GFile *file;
596 GTask *task;
597
598 g_return_if_fail (table != NULL);
599 g_return_if_fail (filename != NULL);
600 g_return_if_fail (cancellable == NULL || G_IS_CANCELLABLE (cancellable));
601
602 fb = file_builder_new (byteswap);
603 file_builder_add_hash (fb, table, pointer: &root);
604 str = file_builder_serialise (fb, root);
605 bytes = g_string_free_to_bytes (string: str);
606 file_builder_free (fb);
607
608 file = g_file_new_for_path (path: filename);
609 data = write_contents_data_new (contents: bytes, file);
610
611 task = g_task_new (NULL, cancellable, callback, callback_data: user_data);
612 g_task_set_task_data (task, task_data: data, task_data_destroy: (GDestroyNotify)write_contents_data_free);
613 g_task_set_source_tag (task, gvdb_table_write_contents_async);
614
615 g_file_replace_contents_async (file,
616 contents: g_bytes_get_data (bytes, NULL),
617 length: g_bytes_get_size (bytes),
618 NULL, FALSE,
619 flags: G_FILE_CREATE_PRIVATE,
620 cancellable, callback: replace_contents_cb, g_steal_pointer (&task));
621
622 g_bytes_unref (bytes);
623 g_object_unref (object: file);
624}
625
626gboolean
627gvdb_table_write_contents_finish (GHashTable *table,
628 GAsyncResult *result,
629 GError **error)
630{
631 g_return_val_if_fail (table != NULL, FALSE);
632 g_return_val_if_fail (g_task_is_valid (result, NULL), FALSE);
633 g_return_val_if_fail (error == NULL || *error == NULL, FALSE);
634
635 return g_task_propagate_boolean (G_TASK (result), error);
636}
637

source code of gtk/subprojects/glib/gio/gvdb/gvdb-builder.c