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"
27 #if !defined(G_OS_WIN32) || !defined(_MSC_VER)
37 guint32_le assigned_index
;
55 gvdb_item_free (gpointer data
)
57 GvdbItem
*item
= data
;
62 g_variant_unref (item
->value
);
65 g_hash_table_unref (item
->table
);
67 g_slice_free (GvdbItem
, item
);
71 gvdb_hash_table_new (GHashTable
*parent
,
72 const gchar
*name_in_parent
)
76 table
= g_hash_table_new_full (g_str_hash
, g_str_equal
,
77 g_free
, gvdb_item_free
);
83 item
= gvdb_hash_table_insert (parent
, name_in_parent
);
84 gvdb_item_set_hash_table (item
, table
);
91 djb_hash (const gchar
*key
)
93 guint32 hash_value
= 5381;
96 hash_value
= hash_value
* 33 + *(signed char *)key
++;
102 gvdb_hash_table_insert (GHashTable
*table
,
107 item
= g_slice_new0 (GvdbItem
);
108 item
->key
= g_strdup (key
);
109 item
->hash_value
= djb_hash (key
);
111 g_hash_table_insert (table
, g_strdup (key
), item
);
117 gvdb_hash_table_insert_string (GHashTable
*table
,
123 item
= gvdb_hash_table_insert (table
, key
);
124 gvdb_item_set_value (item
, g_variant_new_string (value
));
128 gvdb_item_set_value (GvdbItem
*item
,
131 g_return_if_fail (!item
->value
&& !item
->table
&& !item
->child
);
133 item
->value
= g_variant_ref_sink (value
);
137 gvdb_item_set_hash_table (GvdbItem
*item
,
140 g_return_if_fail (!item
->value
&& !item
->table
&& !item
->child
);
142 item
->table
= g_hash_table_ref (table
);
146 gvdb_item_set_parent (GvdbItem
*item
,
151 g_return_if_fail (g_str_has_prefix (item
->key
, parent
->key
));
152 g_return_if_fail (!parent
->value
&& !parent
->table
);
153 g_return_if_fail (!item
->parent
&& !item
->sibling
);
155 for (node
= &parent
->child
; *node
; node
= &(*node
)->sibling
)
156 if (strcmp ((*node
)->key
, item
->key
) > 0)
159 item
->parent
= parent
;
160 item
->sibling
= *node
;
171 hash_table_new (gint n_buckets
)
175 table
= g_slice_new (HashTable
);
176 table
->buckets
= g_new0 (GvdbItem
*, n_buckets
);
177 table
->n_buckets
= n_buckets
;
183 hash_table_free (HashTable
*table
)
185 g_free (table
->buckets
);
187 g_slice_free (HashTable
, table
);
191 hash_table_insert (gpointer key
,
195 guint32 hash_value
, bucket
;
196 HashTable
*table
= data
;
197 GvdbItem
*item
= value
;
199 hash_value
= djb_hash (key
);
200 bucket
= hash_value
% table
->n_buckets
;
201 item
->next
= table
->buckets
[bucket
];
202 table
->buckets
[bucket
] = item
;
206 item_to_index (GvdbItem
*item
)
209 return item
->assigned_index
;
211 return guint32_to_le (-1u);
229 file_builder_allocate (FileBuilder
*fb
,
232 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_string (FileBuilder
*fb
,
290 length
= strlen (string
);
292 chunk
= g_slice_new (FileChunk
);
293 chunk
->offset
= fb
->offset
;
294 chunk
->size
= length
;
295 chunk
->data
= g_malloc (length
);
296 memcpy (chunk
->data
, string
, length
);
298 *start
= guint32_to_le (fb
->offset
);
299 *size
= guint16_to_le (length
);
300 fb
->offset
+= length
;
302 g_queue_push_tail (fb
->chunks
, chunk
);
306 file_builder_allocate_for_hash (FileBuilder
*fb
,
311 guint32_le
**bloom_filter
,
312 guint32_le
**hash_buckets
,
313 struct gvdb_hash_item
**hash_items
,
314 struct gvdb_pointer
*pointer
)
316 guint32_le bloom_hdr
, table_hdr
;
320 g_assert (n_bloom_words
< (1u << 27));
322 bloom_hdr
= guint32_to_le (bloom_shift
<< 27 | n_bloom_words
);
323 table_hdr
= guint32_to_le (n_buckets
);
325 size
= sizeof bloom_hdr
+ sizeof table_hdr
+
326 n_bloom_words
* sizeof (guint32_le
) +
327 n_buckets
* sizeof (guint32_le
) +
328 n_items
* sizeof (struct gvdb_hash_item
);
330 data
= file_builder_allocate (fb
, 4, size
, pointer
);
332 #define chunk(s) (size -= (s), data += (s), data - (s))
333 memcpy (chunk (sizeof bloom_hdr
), &bloom_hdr
, sizeof bloom_hdr
);
334 memcpy (chunk (sizeof table_hdr
), &table_hdr
, sizeof table_hdr
);
335 *bloom_filter
= (guint32_le
*) chunk (n_bloom_words
* sizeof (guint32_le
));
336 *hash_buckets
= (guint32_le
*) chunk (n_buckets
* sizeof (guint32_le
));
337 *hash_items
= (struct gvdb_hash_item
*) chunk (n_items
*
338 sizeof (struct gvdb_hash_item
));
339 g_assert (size
== 0);
342 memset (*bloom_filter
, 0, n_bloom_words
* sizeof (guint32_le
));
344 /* NOTE - the code to actually fill in the bloom filter here is missing.
347 * http://en.wikipedia.org/wiki/Bloom_filter
348 * http://0pointer.de/blog/projects/bloom.html
353 file_builder_add_hash (FileBuilder
*fb
,
355 struct gvdb_pointer
*pointer
)
357 guint32_le
*buckets
, *bloom_filter
;
358 struct gvdb_hash_item
*items
;
364 mytable
= hash_table_new (g_hash_table_size (table
));
365 g_hash_table_foreach (table
, hash_table_insert
, mytable
);
368 for (bucket
= 0; bucket
< mytable
->n_buckets
; bucket
++)
369 for (item
= mytable
->buckets
[bucket
]; item
; item
= item
->next
)
370 item
->assigned_index
= guint32_to_le (index
++);
372 file_builder_allocate_for_hash (fb
, mytable
->n_buckets
, index
, 5, 0,
373 &bloom_filter
, &buckets
, &items
, pointer
);
376 for (bucket
= 0; bucket
< mytable
->n_buckets
; bucket
++)
378 buckets
[bucket
] = guint32_to_le (index
);
380 for (item
= mytable
->buckets
[bucket
]; item
; item
= item
->next
)
382 struct gvdb_hash_item
*entry
= items
++;
383 const gchar
*basename
;
385 g_assert (index
== guint32_from_le (item
->assigned_index
));
386 entry
->hash_value
= guint32_to_le (item
->hash_value
);
387 entry
->parent
= item_to_index (item
->parent
);
390 if (item
->parent
!= NULL
)
391 basename
= item
->key
+ strlen (item
->parent
->key
);
393 basename
= item
->key
;
395 file_builder_add_string (fb
, basename
,
399 if (item
->value
!= NULL
)
401 g_assert (item
->child
== NULL
&& item
->table
== NULL
);
403 file_builder_add_value (fb
, item
->value
, &entry
->value
.pointer
);
407 if (item
->child
!= NULL
)
409 guint32 children
= 0, i
= 0;
413 g_assert (item
->table
== NULL
);
415 for (child
= item
->child
; child
; child
= child
->sibling
)
418 offsets
= file_builder_allocate (fb
, 4, 4 * children
,
419 &entry
->value
.pointer
);
422 for (child
= item
->child
; child
; child
= child
->sibling
)
423 offsets
[i
++] = child
->assigned_index
;
425 g_assert (children
== i
);
428 if (item
->table
!= NULL
)
431 file_builder_add_hash (fb
, item
->table
, &entry
->value
.pointer
);
438 hash_table_free (mytable
);
442 file_builder_new (gboolean byteswap
)
444 FileBuilder
*builder
;
446 builder
= g_slice_new (FileBuilder
);
447 builder
->chunks
= g_queue_new ();
448 builder
->offset
= sizeof (struct gvdb_header
);
449 builder
->byteswap
= byteswap
;
455 file_builder_serialise (FileBuilder
*fb
,
456 struct gvdb_pointer root
)
458 struct gvdb_header header
= { { 0, }, };
463 header
.signature
[0] = GVDB_SWAPPED_SIGNATURE0
;
464 header
.signature
[1] = GVDB_SWAPPED_SIGNATURE1
;
468 header
.signature
[0] = GVDB_SIGNATURE0
;
469 header
.signature
[1] = GVDB_SIGNATURE1
;
472 result
= g_string_new (NULL
);
475 g_string_append_len (result
, (gpointer
) &header
, sizeof header
);
477 while (!g_queue_is_empty (fb
->chunks
))
479 FileChunk
*chunk
= g_queue_pop_head (fb
->chunks
);
481 if (result
->len
!= chunk
->offset
)
483 gchar zero
[8] = { 0, };
485 g_assert (chunk
->offset
> result
->len
);
486 g_assert (chunk
->offset
- result
->len
< 8);
488 g_string_append_len (result
, zero
, chunk
->offset
- result
->len
);
489 g_assert (result
->len
== chunk
->offset
);
492 g_string_append_len (result
, chunk
->data
, chunk
->size
);
493 g_free (chunk
->data
);
495 g_slice_free (FileChunk
, chunk
);
498 g_queue_free (fb
->chunks
);
499 g_slice_free (FileBuilder
, fb
);
505 gvdb_table_write_contents (GHashTable
*table
,
506 const gchar
*filename
,
510 struct gvdb_pointer root
;
515 fb
= file_builder_new (byteswap
);
516 file_builder_add_hash (fb
, table
, &root
);
517 str
= file_builder_serialise (fb
, root
);
519 status
= g_file_set_contents (filename
, str
->str
, str
->len
, error
);
520 g_string_free (str
, TRUE
);