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
);
297 memcpy (chunk
->data
, string
, length
);
299 *start
= guint32_to_le (fb
->offset
);
300 *size
= guint16_to_le (length
);
301 fb
->offset
+= length
;
303 g_queue_push_tail (fb
->chunks
, chunk
);
307 file_builder_allocate_for_hash (FileBuilder
*fb
,
312 guint32_le
**bloom_filter
,
313 guint32_le
**hash_buckets
,
314 struct gvdb_hash_item
**hash_items
,
315 struct gvdb_pointer
*pointer
)
317 guint32_le bloom_hdr
, table_hdr
;
321 g_assert (n_bloom_words
< (1u << 27));
323 bloom_hdr
= guint32_to_le (bloom_shift
<< 27 | n_bloom_words
);
324 table_hdr
= guint32_to_le (n_buckets
);
326 size
= sizeof bloom_hdr
+ sizeof table_hdr
+
327 n_bloom_words
* sizeof (guint32_le
) +
328 n_buckets
* sizeof (guint32_le
) +
329 n_items
* sizeof (struct gvdb_hash_item
);
331 data
= file_builder_allocate (fb
, 4, size
, pointer
);
333 #define chunk(s) (size -= (s), data += (s), data - (s))
334 memcpy (chunk (sizeof bloom_hdr
), &bloom_hdr
, sizeof bloom_hdr
);
335 memcpy (chunk (sizeof table_hdr
), &table_hdr
, sizeof table_hdr
);
336 *bloom_filter
= (guint32_le
*) chunk (n_bloom_words
* sizeof (guint32_le
));
337 *hash_buckets
= (guint32_le
*) chunk (n_buckets
* sizeof (guint32_le
));
338 *hash_items
= (struct gvdb_hash_item
*) chunk (n_items
*
339 sizeof (struct gvdb_hash_item
));
340 g_assert (size
== 0);
343 memset (*bloom_filter
, 0, n_bloom_words
* sizeof (guint32_le
));
345 /* NOTE - the code to actually fill in the bloom filter here is missing.
348 * http://en.wikipedia.org/wiki/Bloom_filter
349 * http://0pointer.de/blog/projects/bloom.html
354 file_builder_add_hash (FileBuilder
*fb
,
356 struct gvdb_pointer
*pointer
)
358 guint32_le
*buckets
, *bloom_filter
;
359 struct gvdb_hash_item
*items
;
365 mytable
= hash_table_new (g_hash_table_size (table
));
366 g_hash_table_foreach (table
, hash_table_insert
, mytable
);
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
++);
373 file_builder_allocate_for_hash (fb
, mytable
->n_buckets
, index
, 5, 0,
374 &bloom_filter
, &buckets
, &items
, pointer
);
377 for (bucket
= 0; bucket
< mytable
->n_buckets
; bucket
++)
379 buckets
[bucket
] = guint32_to_le (index
);
381 for (item
= mytable
->buckets
[bucket
]; item
; item
= item
->next
)
383 struct gvdb_hash_item
*entry
= items
++;
384 const gchar
*basename
;
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
);
391 if (item
->parent
!= NULL
)
392 basename
= item
->key
+ strlen (item
->parent
->key
);
394 basename
= item
->key
;
396 file_builder_add_string (fb
, basename
,
400 if (item
->value
!= NULL
)
402 g_assert (item
->child
== NULL
&& item
->table
== NULL
);
404 file_builder_add_value (fb
, item
->value
, &entry
->value
.pointer
);
408 if (item
->child
!= NULL
)
410 guint32 children
= 0, i
= 0;
414 g_assert (item
->table
== NULL
);
416 for (child
= item
->child
; child
; child
= child
->sibling
)
419 offsets
= file_builder_allocate (fb
, 4, 4 * children
,
420 &entry
->value
.pointer
);
423 for (child
= item
->child
; child
; child
= child
->sibling
)
424 offsets
[i
++] = child
->assigned_index
;
426 g_assert (children
== i
);
429 if (item
->table
!= NULL
)
432 file_builder_add_hash (fb
, item
->table
, &entry
->value
.pointer
);
439 hash_table_free (mytable
);
443 file_builder_new (gboolean byteswap
)
445 FileBuilder
*builder
;
447 builder
= g_slice_new (FileBuilder
);
448 builder
->chunks
= g_queue_new ();
449 builder
->offset
= sizeof (struct gvdb_header
);
450 builder
->byteswap
= byteswap
;
456 file_builder_serialise (FileBuilder
*fb
,
457 struct gvdb_pointer root
)
459 struct gvdb_header header
= { { 0, }, };
464 header
.signature
[0] = GVDB_SWAPPED_SIGNATURE0
;
465 header
.signature
[1] = GVDB_SWAPPED_SIGNATURE1
;
469 header
.signature
[0] = GVDB_SIGNATURE0
;
470 header
.signature
[1] = GVDB_SIGNATURE1
;
473 result
= g_string_new (NULL
);
476 g_string_append_len (result
, (gpointer
) &header
, sizeof header
);
478 while (!g_queue_is_empty (fb
->chunks
))
480 FileChunk
*chunk
= g_queue_pop_head (fb
->chunks
);
482 if (result
->len
!= chunk
->offset
)
484 gchar zero
[8] = { 0, };
486 g_assert (chunk
->offset
> result
->len
);
487 g_assert (chunk
->offset
- result
->len
< 8);
489 g_string_append_len (result
, zero
, chunk
->offset
- result
->len
);
490 g_assert (result
->len
== chunk
->offset
);
493 g_string_append_len (result
, chunk
->data
, chunk
->size
);
494 g_free (chunk
->data
);
496 g_slice_free (FileChunk
, chunk
);
499 g_queue_free (fb
->chunks
);
500 g_slice_free (FileBuilder
, fb
);
506 gvdb_table_write_contents (GHashTable
*table
,
507 const gchar
*filename
,
511 struct gvdb_pointer root
;
516 fb
= file_builder_new (byteswap
);
517 file_builder_add_hash (fb
, table
, &root
);
518 str
= file_builder_serialise (fb
, root
);
520 status
= g_file_set_contents (filename
, str
->str
, str
->len
, error
);
521 g_string_free (str
, TRUE
);