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 |
53 | gvdb_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 | |
68 | GHashTable * |
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 (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 | |
88 | static guint32 |
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 * |
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 (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 | |
114 | void |
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, value: g_variant_new_string (string: value)); |
123 | } |
124 | |
125 | void |
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 |
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 (hash_table: table); |
141 | } |
142 | |
143 | void |
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 (s1: (*node)->key, s2: 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 * |
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 |
181 | hash_table_free (HashTable *table) |
182 | { |
183 | g_free (mem: table->buckets); |
184 | |
185 | g_slice_free (HashTable, table); |
186 | } |
187 | |
188 | static void |
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 |
204 | item_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 | |
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 |
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 (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 | |
252 | static void |
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 (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 | |
279 | static void |
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 (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 | |
304 | static void |
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 (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 | |
353 | static void |
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 (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 | |
442 | static FileBuilder * |
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 |
456 | file_builder_free (FileBuilder *fb) |
457 | { |
458 | g_queue_free (queue: fb->chunks); |
459 | g_slice_free (FileBuilder, fb); |
460 | } |
461 | |
462 | static GString * |
463 | file_builder_serialise (FileBuilder *fb, |
464 | struct gvdb_pointer root) |
465 | { |
466 | struct gvdb_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 | |
511 | gboolean |
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, 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 | |
537 | typedef struct { |
538 | GBytes *contents; /* (owned) */ |
539 | GFile *file; /* (owned) */ |
540 | } WriteContentsData; |
541 | |
542 | static WriteContentsData * |
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 (bytes: contents); |
550 | data->file = g_object_ref (file); |
551 | |
552 | return data; |
553 | } |
554 | |
555 | static void |
556 | write_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 | |
563 | static void |
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 (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 | |
582 | void |
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, 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 | |
626 | gboolean |
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 | |