2 * Copyright © 2010 Codethink Limited
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 of the licence, or (at your option) any later version.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
19 * Author: Ryan Lortie <desrt@desrt.ca>
22 #include "gvdb-builder.h"
23 #include "gvdb-format.h"
35 guint32_le assigned_index
;
54 gvdb_item_free (gpointer data
)
56 GvdbItem
*item
= data
;
61 g_variant_unref (item
->value
);
64 g_variant_unref (item
->options
);
67 g_hash_table_unref (item
->table
);
69 g_slice_free (GvdbItem
, item
);
73 gvdb_hash_table_new (GHashTable
*parent
,
74 const gchar
*name_in_parent
)
78 table
= g_hash_table_new_full (g_str_hash
, g_str_equal
,
79 g_free
, gvdb_item_free
);
85 item
= gvdb_hash_table_insert (parent
, name_in_parent
);
86 gvdb_item_set_hash_table (item
, table
);
93 djb_hash (const gchar
*key
)
95 guint32 hash_value
= 5381;
98 hash_value
= hash_value
* 33 + *key
++;
104 gvdb_hash_table_insert (GHashTable
*table
,
109 item
= g_slice_new0 (GvdbItem
);
110 item
->key
= g_strdup (key
);
111 item
->hash_value
= djb_hash (key
);
113 g_hash_table_insert (table
, g_strdup (key
), item
);
119 gvdb_hash_table_insert_string (GHashTable
*table
,
125 item
= gvdb_hash_table_insert (table
, key
);
126 gvdb_item_set_value (item
, g_variant_new_string (value
));
130 gvdb_item_set_value (GvdbItem
*item
,
133 g_return_if_fail (!item
->value
&& !item
->table
&& !item
->child
);
135 item
->value
= g_variant_ref_sink (value
);
139 gvdb_item_set_options (GvdbItem
*item
,
142 g_return_if_fail (!item
->options
);
144 item
->options
= g_variant_ref_sink (options
);
148 gvdb_item_set_hash_table (GvdbItem
*item
,
151 g_return_if_fail (!item
->value
&& !item
->table
&& !item
->child
);
153 item
->table
= g_hash_table_ref (table
);
157 gvdb_item_set_parent (GvdbItem
*item
,
162 g_return_if_fail (g_str_has_prefix (item
->key
, parent
->key
));
163 g_return_if_fail (!parent
->value
&& !parent
->table
);
164 g_return_if_fail (!item
->parent
&& !item
->sibling
);
166 for (node
= &parent
->child
; *node
; node
= &(*node
)->sibling
)
167 if (strcmp ((*node
)->key
, item
->key
) > 0)
170 item
->parent
= parent
;
171 item
->sibling
= *node
;
182 hash_table_new (gint n_buckets
)
186 table
= g_slice_new (HashTable
);
187 table
->buckets
= g_new0 (GvdbItem
*, n_buckets
);
188 table
->n_buckets
= n_buckets
;
194 hash_table_insert (gpointer key
,
198 guint32 hash_value
, bucket
;
199 HashTable
*table
= data
;
200 GvdbItem
*item
= value
;
202 hash_value
= djb_hash (key
);
203 bucket
= hash_value
% table
->n_buckets
;
204 item
->next
= table
->buckets
[bucket
];
205 table
->buckets
[bucket
] = item
;
209 item_to_index (GvdbItem
*item
)
212 return item
->assigned_index
;
214 return guint32_to_le (-1u);
232 file_builder_allocate (FileBuilder
*fb
,
235 struct gvdb_pointer
*pointer
)
239 fb
->offset
+= (-fb
->offset
) & (alignment
- 1);
240 chunk
= g_slice_new (FileChunk
);
241 chunk
->offset
= fb
->offset
;
243 chunk
->data
= g_malloc (size
);
245 pointer
->start
= guint32_to_le (fb
->offset
);
247 pointer
->end
= guint32_to_le (fb
->offset
);
249 g_queue_push_tail (fb
->chunks
, chunk
);
255 file_builder_add_value (FileBuilder
*fb
,
257 struct gvdb_pointer
*pointer
)
259 GVariant
*variant
, *normal
;
265 value
= g_variant_byteswap (value
);
266 variant
= g_variant_new_variant (value
);
267 g_variant_unref (value
);
270 variant
= g_variant_new_variant (value
);
272 normal
= g_variant_get_normal_form (variant
);
273 g_variant_unref (variant
);
275 size
= g_variant_get_size (normal
);
276 data
= file_builder_allocate (fb
, 8, size
, pointer
);
277 g_variant_store (normal
, data
);
278 g_variant_unref (normal
);
282 file_builder_add_options (FileBuilder
*fb
,
284 struct gvdb_pointer
*pointer
)
294 options
= g_variant_byteswap (options
);
295 normal
= g_variant_get_normal_form (options
);
296 g_variant_unref (options
);
299 normal
= g_variant_get_normal_form (options
);
301 size
= g_variant_get_size (normal
);
302 data
= file_builder_allocate (fb
, 8, size
, pointer
);
303 g_variant_store (normal
, data
);
304 g_variant_unref (normal
);
309 file_builder_add_string (FileBuilder
*fb
,
317 length
= strlen (string
);
319 chunk
= g_slice_new (FileChunk
);
320 chunk
->offset
= fb
->offset
;
321 chunk
->size
= length
;
322 chunk
->data
= g_malloc (length
);
323 memcpy (chunk
->data
, string
, length
);
325 *start
= guint32_to_le (fb
->offset
);
326 *size
= guint16_to_le (length
);
327 fb
->offset
+= length
;
329 g_queue_push_tail (fb
->chunks
, chunk
);
333 file_builder_allocate_for_hash (FileBuilder
*fb
,
338 guint32_le
**bloom_filter
,
339 guint32_le
**hash_buckets
,
340 struct gvdb_hash_item
**hash_items
,
341 struct gvdb_pointer
*pointer
)
343 guint32_le bloom_hdr
, table_hdr
;
347 g_assert (n_bloom_words
< (1u << 27));
349 bloom_hdr
= guint32_to_le (bloom_shift
<< 27 | n_bloom_words
);
350 table_hdr
= guint32_to_le (n_buckets
);
352 size
= sizeof bloom_hdr
+ sizeof table_hdr
+
353 n_bloom_words
* sizeof (guint32_le
) +
354 n_buckets
* sizeof (guint32_le
) +
355 n_items
* sizeof (struct gvdb_hash_item
);
357 data
= file_builder_allocate (fb
, 4, size
, pointer
);
359 #define chunk(s) (size -= (s), data += (s), data - (s))
360 memcpy (chunk (sizeof bloom_hdr
), &bloom_hdr
, sizeof bloom_hdr
);
361 memcpy (chunk (sizeof table_hdr
), &table_hdr
, sizeof table_hdr
);
362 *bloom_filter
= (guint32_le
*) chunk (n_bloom_words
* sizeof (guint32_le
));
363 *hash_buckets
= (guint32_le
*) chunk (n_buckets
* sizeof (guint32_le
));
364 *hash_items
= (struct gvdb_hash_item
*) chunk (n_items
*
365 sizeof (struct gvdb_hash_item
));
366 g_assert (size
== 0);
369 memset (*bloom_filter
, 0, n_bloom_words
* sizeof (guint32_le
));
373 file_builder_add_hash (FileBuilder
*fb
,
375 struct gvdb_pointer
*pointer
)
377 guint32_le
*buckets
, *bloom_filter
;
378 struct gvdb_hash_item
*items
;
384 mytable
= hash_table_new (g_hash_table_size (table
));
385 g_hash_table_foreach (table
, hash_table_insert
, mytable
);
388 for (bucket
= 0; bucket
< mytable
->n_buckets
; bucket
++)
389 for (item
= mytable
->buckets
[bucket
]; item
; item
= item
->next
)
390 item
->assigned_index
= guint32_to_le (index
++);
392 file_builder_allocate_for_hash (fb
, mytable
->n_buckets
, index
, 5, 0,
393 &bloom_filter
, &buckets
, &items
, pointer
);
396 for (bucket
= 0; bucket
< mytable
->n_buckets
; bucket
++)
398 buckets
[bucket
] = guint32_to_le (index
);
400 for (item
= mytable
->buckets
[bucket
]; item
; item
= item
->next
)
402 struct gvdb_hash_item
*entry
= items
++;
403 const gchar
*basename
;
405 g_assert (index
== guint32_from_le (item
->assigned_index
));
406 entry
->hash_value
= guint32_to_le (item
->hash_value
);
407 entry
->parent
= item_to_index (item
->parent
);
410 if (item
->parent
!= NULL
)
411 basename
= item
->key
+ strlen (item
->parent
->key
);
413 basename
= item
->key
;
415 file_builder_add_string (fb
, basename
,
419 if (item
->value
!= NULL
)
421 g_assert (item
->child
== NULL
&& item
->table
== NULL
);
423 file_builder_add_value (fb
, item
->value
, &entry
->value
.pointer
);
424 file_builder_add_options (fb
, item
->options
, &entry
->options
);
428 if (item
->child
!= NULL
)
430 guint32 children
= 0;
434 g_assert (item
->table
== NULL
);
436 for (child
= item
->child
; child
; child
= child
->sibling
)
439 offsets
= file_builder_allocate (fb
, 4, 4 * children
,
440 &entry
->value
.pointer
);
443 for (child
= item
->child
; child
; child
= child
->sibling
)
444 offsets
[--children
] = child
->assigned_index
;
446 g_assert (children
== 0);
449 if (item
->table
!= NULL
)
452 file_builder_add_hash (fb
, item
->table
, &entry
->value
.pointer
);
461 file_builder_new (gboolean byteswap
)
463 FileBuilder
*builder
;
465 builder
= g_slice_new (FileBuilder
);
466 builder
->chunks
= g_queue_new ();
467 builder
->offset
= sizeof (struct gvdb_header
);
468 builder
->byteswap
= byteswap
;
474 file_builder_serialise (FileBuilder
*fb
,
475 struct gvdb_pointer root
)
477 struct gvdb_header header
;
482 header
.signature
[0] = GVDB_SWAPPED_SIGNATURE0
;
483 header
.signature
[1] = GVDB_SWAPPED_SIGNATURE1
;
487 header
.signature
[0] = GVDB_SIGNATURE0
;
488 header
.signature
[1] = GVDB_SIGNATURE1
;
491 result
= g_string_new (NULL
);
494 g_string_append_len (result
, (gpointer
) &header
, sizeof header
);
496 while (!g_queue_is_empty (fb
->chunks
))
498 FileChunk
*chunk
= g_queue_pop_head (fb
->chunks
);
500 if (result
->len
!= chunk
->offset
)
502 gchar zero
[8] = { 0, };
504 g_assert (chunk
->offset
> result
->len
);
505 g_assert (chunk
->offset
- result
->len
< 8);
507 g_string_append_len (result
, zero
, chunk
->offset
- result
->len
);
508 g_assert (result
->len
== chunk
->offset
);
511 g_string_append_len (result
, chunk
->data
, chunk
->size
);
512 g_free (chunk
->data
);
515 g_queue_free (fb
->chunks
);
516 g_slice_free (FileBuilder
, fb
);
522 gvdb_table_write_contents (GHashTable
*table
,
523 const gchar
*filename
,
527 struct gvdb_pointer root
;
532 fb
= file_builder_new (byteswap
);
533 file_builder_add_hash (fb
, table
, &root
);
534 str
= file_builder_serialise (fb
, root
);
536 status
= g_file_set_contents (filename
, str
->str
, str
->len
, error
);
537 g_string_free (str
, TRUE
);