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
31 struct _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
52 static void
gvdb_item_free(gpointer data)53 gvdb_item_free (gpointer data)
54 {
55 GvdbItem *item = data;
56
57 g_free (item->key);
58
59 if (item->value)
60 g_variant_unref (item->value);
61
62 if (item->table)
63 g_hash_table_unref (item->table);
64
65 g_slice_free (GvdbItem, item);
66 }
67
68 GHashTable *
gvdb_hash_table_new(GHashTable * parent,const gchar * name_in_parent)69 gvdb_hash_table_new (GHashTable *parent,
70 const gchar *name_in_parent)
71 {
72 GHashTable *table;
73
74 table = g_hash_table_new_full (g_str_hash, g_str_equal,
75 g_free, gvdb_item_free);
76
77 if (parent)
78 {
79 GvdbItem *item;
80
81 item = gvdb_hash_table_insert (parent, name_in_parent);
82 gvdb_item_set_hash_table (item, table);
83 }
84
85 return table;
86 }
87
88 static guint32
djb_hash(const gchar * key)89 djb_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
99 GvdbItem *
gvdb_hash_table_insert(GHashTable * table,const gchar * key)100 gvdb_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 (key);
107 item->hash_value = djb_hash (key);
108
109 g_hash_table_insert (table, g_strdup (key), item);
110
111 return item;
112 }
113
114 void
gvdb_hash_table_insert_string(GHashTable * table,const gchar * key,const gchar * value)115 gvdb_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, g_variant_new_string (value));
123 }
124
125 void
gvdb_item_set_value(GvdbItem * item,GVariant * value)126 gvdb_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
134 void
gvdb_item_set_hash_table(GvdbItem * item,GHashTable * table)135 gvdb_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 (table);
141 }
142
143 void
gvdb_item_set_parent(GvdbItem * item,GvdbItem * parent)144 gvdb_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 ((*node)->key, item->key) > 0)
155 break;
156
157 item->parent = parent;
158 item->sibling = *node;
159 *node = item;
160 }
161
162 typedef struct
163 {
164 GvdbItem **buckets;
165 gint n_buckets;
166 } HashTable;
167
168 static HashTable *
hash_table_new(gint n_buckets)169 hash_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
180 static void
hash_table_free(HashTable * table)181 hash_table_free (HashTable *table)
182 {
183 g_free (table->buckets);
184
185 g_slice_free (HashTable, table);
186 }
187
188 static void
hash_table_insert(gpointer key,gpointer value,gpointer data)189 hash_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
203 static guint32_le
item_to_index(GvdbItem * item)204 item_to_index (GvdbItem *item)
205 {
206 if (item != NULL)
207 return item->assigned_index;
208
209 return guint32_to_le ((guint32) -1);
210 }
211
212 typedef struct
213 {
214 GQueue *chunks;
215 guint64 offset;
216 gboolean byteswap;
217 } FileBuilder;
218
219 typedef struct
220 {
221 gsize offset;
222 gsize size;
223 gpointer data;
224 } FileChunk;
225
226 static gpointer
file_builder_allocate(FileBuilder * fb,guint alignment,gsize size,struct gvdb_pointer * pointer)227 file_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 (size);
242
243 pointer->start = guint32_to_le (fb->offset);
244 fb->offset += size;
245 pointer->end = guint32_to_le (fb->offset);
246
247 g_queue_push_tail (fb->chunks, chunk);
248
249 return chunk->data;
250 }
251
252 static void
file_builder_add_value(FileBuilder * fb,GVariant * value,struct gvdb_pointer * pointer)253 file_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 (variant);
271 g_variant_unref (variant);
272
273 size = g_variant_get_size (normal);
274 data = file_builder_allocate (fb, 8, size, pointer);
275 g_variant_store (normal, data);
276 g_variant_unref (normal);
277 }
278
279 static void
file_builder_add_string(FileBuilder * fb,const gchar * string,guint32_le * start,guint16_le * size)280 file_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 (string);
289
290 chunk = g_slice_new (FileChunk);
291 chunk->offset = fb->offset;
292 chunk->size = length;
293 chunk->data = g_malloc (length);
294 if (length != 0)
295 memcpy (chunk->data, string, length);
296
297 *start = guint32_to_le (fb->offset);
298 *size = guint16_to_le (length);
299 fb->offset += length;
300
301 g_queue_push_tail (fb->chunks, chunk);
302 }
303
304 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)305 file_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 (bloom_shift << 27 | n_bloom_words);
322 table_hdr = guint32_to_le (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, 4, size, pointer);
330
331 #define chunk(s) (size -= (s), data += (s), data - (s))
332 memcpy (chunk (sizeof bloom_hdr), &bloom_hdr, sizeof bloom_hdr);
333 memcpy (chunk (sizeof table_hdr), &table_hdr, 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 (*bloom_filter, 0, n_bloom_words * sizeof (guint32_le));
342 memset (*hash_buckets, 0, n_buckets * sizeof (guint32_le));
343 memset (*hash_items, 0, 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
353 static void
file_builder_add_hash(FileBuilder * fb,GHashTable * table,struct gvdb_pointer * pointer)354 file_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 (g_hash_table_size (table));
366 g_hash_table_foreach (table, hash_table_insert, 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 (index++);
372
373 file_builder_allocate_for_hash (fb, mytable->n_buckets, index, 5, 0,
374 &bloom_filter, &buckets, &items, pointer);
375
376 index = 0;
377 for (bucket = 0; bucket < mytable->n_buckets; bucket++)
378 {
379 buckets[bucket] = guint32_to_le (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 (item->hash_value);
388 entry->parent = item_to_index (item->parent);
389 entry->unused = 0;
390
391 if (item->parent != NULL)
392 basename = item->key + strlen (item->parent->key);
393 else
394 basename = item->key;
395
396 file_builder_add_string (fb, basename,
397 &entry->key_start,
398 &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, item->value, &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, 4, 4 * children,
420 &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, item->table, &entry->value.pointer);
433 }
434
435 index++;
436 }
437 }
438
439 hash_table_free (mytable);
440 }
441
442 static FileBuilder *
file_builder_new(gboolean byteswap)443 file_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
455 static void
file_builder_free(FileBuilder * fb)456 file_builder_free (FileBuilder *fb)
457 {
458 g_queue_free (fb->chunks);
459 g_slice_free (FileBuilder, fb);
460 }
461
462 static GString *
file_builder_serialise(FileBuilder * fb,struct gvdb_pointer root)463 file_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 (&header, 0, 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 (result, (gpointer) &header, sizeof header);
486
487 while (!g_queue_is_empty (fb->chunks))
488 {
489 FileChunk *chunk = g_queue_pop_head (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 (result, zero, chunk->offset - result->len);
499 g_assert (result->len == chunk->offset);
500 }
501
502 g_string_append_len (result, chunk->data, chunk->size);
503 g_free (chunk->data);
504
505 g_slice_free (FileChunk, chunk);
506 }
507
508 return result;
509 }
510
511 gboolean
gvdb_table_write_contents(GHashTable * table,const gchar * filename,gboolean byteswap,GError ** error)512 gvdb_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, &root);
528 str = file_builder_serialise (fb, root);
529 file_builder_free (fb);
530
531 status = g_file_set_contents (filename, str->str, str->len, error);
532 g_string_free (str, TRUE);
533
534 return status;
535 }
536
537 typedef struct {
538 GBytes *contents; /* (owned) */
539 GFile *file; /* (owned) */
540 } WriteContentsData;
541
542 static WriteContentsData *
write_contents_data_new(GBytes * contents,GFile * file)543 write_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 (contents);
550 data->file = g_object_ref (file);
551
552 return data;
553 }
554
555 static void
write_contents_data_free(WriteContentsData * data)556 write_contents_data_free (WriteContentsData *data)
557 {
558 g_bytes_unref (data->contents);
559 g_object_unref (data->file);
560 g_slice_free (WriteContentsData, data);
561 }
562
563 static void
replace_contents_cb(GObject * source_object,GAsyncResult * result,gpointer user_data)564 replace_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 (data->file, result, NULL, &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 (task);
580 }
581
582 void
gvdb_table_write_contents_async(GHashTable * table,const gchar * filename,gboolean byteswap,GCancellable * cancellable,GAsyncReadyCallback callback,gpointer user_data)583 gvdb_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, &root);
604 str = file_builder_serialise (fb, root);
605 bytes = g_string_free_to_bytes (str);
606 file_builder_free (fb);
607
608 file = g_file_new_for_path (filename);
609 data = write_contents_data_new (bytes, file);
610
611 task = g_task_new (NULL, cancellable, callback, user_data);
612 g_task_set_task_data (task, data, (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 g_bytes_get_data (bytes, NULL),
617 g_bytes_get_size (bytes),
618 NULL, FALSE,
619 G_FILE_CREATE_PRIVATE,
620 cancellable, replace_contents_cb, g_steal_pointer (&task));
621
622 g_bytes_unref (bytes);
623 g_object_unref (file);
624 }
625
626 gboolean
gvdb_table_write_contents_finish(GHashTable * table,GAsyncResult * result,GError ** error)627 gvdb_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