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-reader.h"
23 #include "gvdb-format.h"
36 const guint32_le
*bloom_words
;
37 guint32 n_bloom_words
;
40 const guint32_le
*hash_buckets
;
43 struct gvdb_hash_item
*hash_items
;
48 gvdb_table_item_get_key (GvdbTable
*file
,
49 const struct gvdb_hash_item
*item
,
54 start
= guint32_from_le (item
->key_start
);
55 *size
= guint16_from_le (item
->key_size
);
58 if G_UNLIKELY (start
> end
|| end
> file
->size
)
61 return file
->data
+ start
;
65 gvdb_table_dereference (GvdbTable
*file
,
66 const struct gvdb_pointer
*pointer
,
72 start
= guint32_from_le (pointer
->start
);
73 end
= guint32_from_le (pointer
->end
);
75 if G_UNLIKELY (start
> end
|| end
> file
->size
|| start
& (alignment
- 1))
80 return file
->data
+ start
;
84 gvdb_table_setup_root (GvdbTable
*file
,
85 const struct gvdb_pointer
*pointer
)
87 const struct gvdb_hash_header
*header
;
88 guint32 n_bloom_words
;
92 header
= gvdb_table_dereference (file
, pointer
, 4, &size
);
94 if G_UNLIKELY (header
== NULL
|| size
< sizeof *header
)
97 size
-= sizeof *header
;
99 n_bloom_words
= guint32_from_le (header
->n_bloom_words
);
100 n_buckets
= guint32_from_le (header
->n_buckets
);
101 n_bloom_words
&= (1u << 27) - 1;
103 if G_UNLIKELY (n_bloom_words
* sizeof (guint32_le
) > size
)
106 file
->bloom_words
= (gpointer
) (header
+ 1);
107 size
-= n_bloom_words
* sizeof (guint32_le
);
108 file
->n_bloom_words
= n_bloom_words
;
110 if G_UNLIKELY (n_buckets
> G_MAXUINT
/ sizeof (guint32_le
) ||
111 n_buckets
* sizeof (guint32_le
) > size
)
114 file
->hash_buckets
= file
->bloom_words
+ file
->n_bloom_words
;
115 size
-= n_buckets
* sizeof (guint32_le
);
116 file
->n_buckets
= n_buckets
;
118 if G_UNLIKELY (size
% sizeof (struct gvdb_hash_item
))
121 file
->hash_items
= (gpointer
) (file
->hash_buckets
+ n_buckets
);
122 file
->n_hash_items
= size
/ sizeof (struct gvdb_hash_item
);
126 * gvdb_table_new_from_bytes:
127 * @bytes: the #GBytes with the data
128 * @trusted: if the contents of @bytes are trusted
129 * @error: %NULL, or a pointer to a %NULL #GError
130 * @returns: a new #GvdbTable
132 * Creates a new #GvdbTable from the contents of @bytes.
134 * This call can fail if the header contained in @bytes is invalid.
136 * You should call gvdb_table_free() on the return result when you no
140 gvdb_table_new_from_bytes (GBytes
*bytes
,
144 const struct gvdb_header
*header
;
147 file
= g_slice_new0 (GvdbTable
);
148 file
->bytes
= g_bytes_ref (bytes
);
149 file
->data
= g_bytes_get_data (bytes
, &file
->size
);
150 file
->trusted
= trusted
;
152 if (file
->size
< sizeof (struct gvdb_header
))
155 header
= (gpointer
) file
->data
;
157 if (header
->signature
[0] == GVDB_SIGNATURE0
&&
158 header
->signature
[1] == GVDB_SIGNATURE1
&&
159 guint32_from_le (header
->version
) == 0)
160 file
->byteswapped
= FALSE
;
162 else if (header
->signature
[0] == GVDB_SWAPPED_SIGNATURE0
&&
163 header
->signature
[1] == GVDB_SWAPPED_SIGNATURE1
&&
164 guint32_from_le (header
->version
) == 0)
165 file
->byteswapped
= TRUE
;
170 gvdb_table_setup_root (file
, &header
->root
);
175 g_set_error_literal (error
, G_FILE_ERROR
, G_FILE_ERROR_INVAL
, "invalid gvdb header");
177 g_bytes_unref (file
->bytes
);
179 g_slice_free (GvdbTable
, file
);
186 * @filename: a filename
187 * @trusted: if the contents of @bytes are trusted
188 * @error: %NULL, or a pointer to a %NULL #GError
189 * @returns: a new #GvdbTable
191 * Creates a new #GvdbTable using the #GMappedFile for @filename as the
195 gvdb_table_new (const gchar
*filename
,
203 mapped
= g_mapped_file_new (filename
, FALSE
, error
);
207 bytes
= g_mapped_file_get_bytes (mapped
);
208 table
= gvdb_table_new_from_bytes (bytes
, trusted
, error
);
209 g_mapped_file_unref (mapped
);
210 g_bytes_unref (bytes
);
212 g_prefix_error (error
, "%s: ", filename
);
218 gvdb_table_bloom_filter (GvdbTable
*file
,
223 if (file
->n_bloom_words
== 0)
226 word
= (hash_value
/ 32) % file
->n_bloom_words
;
227 mask
= 1 << (hash_value
& 31);
228 mask
|= 1 << ((hash_value
>> file
->bloom_shift
) & 31);
230 return (guint32_from_le (file
->bloom_words
[word
]) & mask
) == mask
;
234 gvdb_table_check_name (GvdbTable
*file
,
235 struct gvdb_hash_item
*item
,
239 const gchar
*this_key
;
243 this_key
= gvdb_table_item_get_key (file
, item
, &this_size
);
245 if G_UNLIKELY (this_key
== NULL
|| this_size
> key_length
)
248 key_length
-= this_size
;
250 if G_UNLIKELY (memcmp (this_key
, key
+ key_length
, this_size
) != 0)
253 parent
= guint32_from_le (item
->parent
);
254 if (key_length
== 0 && parent
== 0xffffffffu
)
257 if G_LIKELY (parent
< file
->n_hash_items
&& this_size
> 0)
258 return gvdb_table_check_name (file
,
259 &file
->hash_items
[parent
],
265 static const struct gvdb_hash_item
*
266 gvdb_table_lookup (GvdbTable
*file
,
270 guint32 hash_value
= 5381;
276 if G_UNLIKELY (file
->n_buckets
== 0 || file
->n_hash_items
== 0)
279 for (key_length
= 0; key
[key_length
]; key_length
++)
280 hash_value
= (hash_value
* 33) + ((signed char *) key
)[key_length
];
282 if (!gvdb_table_bloom_filter (file
, hash_value
))
285 bucket
= hash_value
% file
->n_buckets
;
286 itemno
= guint32_from_le (file
->hash_buckets
[bucket
]);
288 if (bucket
== file
->n_buckets
- 1 ||
289 (lastno
= guint32_from_le(file
->hash_buckets
[bucket
+ 1])) > file
->n_hash_items
)
290 lastno
= file
->n_hash_items
;
292 while G_LIKELY (itemno
< lastno
)
294 struct gvdb_hash_item
*item
= &file
->hash_items
[itemno
];
296 if (hash_value
== guint32_from_le (item
->hash_value
))
297 if G_LIKELY (gvdb_table_check_name (file
, item
, key
, key_length
))
298 if G_LIKELY (item
->type
== type
)
308 gvdb_table_list_from_item (GvdbTable
*table
,
309 const struct gvdb_hash_item
*item
,
310 const guint32_le
**list
,
315 *list
= gvdb_table_dereference (table
, &item
->value
.pointer
, 4, &size
);
317 if G_LIKELY (*list
== NULL
|| size
% 4)
326 * gvdb_table_get_names:
327 * @table: a #GvdbTable
328 * @length: the number of items returned, or %NULL
330 * Gets a list of all names contained in @table.
332 * No call to gvdb_table_get_table(), gvdb_table_list() or
333 * gvdb_table_get_value() will succeed unless it is for one of the
334 * names returned by this function.
336 * Note that some names that are returned may still fail for all of the
337 * above calls in the case of the corrupted file. Note also that the
338 * returned strings may not be utf8.
340 * Returns: a %NULL-terminated list of strings, of length @length
343 gvdb_table_get_names (GvdbTable
*table
,
352 /* We generally proceed by iterating over the list of items in the
353 * hash table (in order of appearance) recording them into an array.
355 * Each item has a parent item (except root items). The parent item
356 * forms part of the name of the item. We could go fetching the
357 * parent item chain at the point that we encounter each item but then
358 * we would need to implement some sort of recursion along with checks
359 * for self-referential items.
361 * Instead, we do a number of passes. Each pass will build up one
362 * level of names (starting from the root). We continue to do passes
363 * until no more items are left. The first pass will only add root
364 * items and each further pass will only add items whose direct parent
365 * is an item added in the immediately previous pass. It's also
366 * possible that items get filled if they follow their parent within a
369 * At most we will have a number of passes equal to the depth of the
370 * tree. Self-referential items will never be filled in (since their
371 * parent will have never been filled in). We continue until we have
372 * a pass that fills in no additional items.
374 * This takes an O(n) algorithm and turns it into O(n*m) where m is
375 * the depth of the tree, but in all sane cases the tree won't be very
376 * deep and the constant factor of this algorithm is lower (and the
377 * complexity of coding it, as well).
380 n_names
= table
->n_hash_items
;
381 names
= g_new0 (gchar
*, n_names
+ 1);
383 /* 'names' starts out all-NULL. On each pass we record the number
384 * of items changed from NULL to non-NULL in 'filled' so we know if we
385 * should repeat the loop. 'total' counts the total number of items
386 * filled. If 'total' ends up equal to 'n_names' then we know that
387 * 'names' has been completely filled.
393 /* Loop until we have filled no more entries */
396 for (i
= 0; i
< n_names
; i
++)
398 const struct gvdb_hash_item
*item
= &table
->hash_items
[i
];
403 /* already got it on a previous pass */
404 if (names
[i
] != NULL
)
407 parent
= guint32_from_le (item
->parent
);
409 if (parent
== 0xffffffffu
)
411 /* it's a root item */
412 name
= gvdb_table_item_get_key (table
, item
, &name_length
);
416 names
[i
] = g_strndup (name
, name_length
);
421 else if (parent
< n_names
&& names
[parent
] != NULL
)
423 /* It's a non-root item whose parent was filled in already.
425 * Calculate the name of this item by combining it with
428 name
= gvdb_table_item_get_key (table
, item
, &name_length
);
432 const gchar
*parent_name
= names
[parent
];
436 parent_length
= strlen (parent_name
);
437 fullname
= g_malloc (parent_length
+ name_length
+ 1);
438 memcpy (fullname
, parent_name
, parent_length
);
439 memcpy (fullname
+ parent_length
, name
, name_length
);
440 fullname
[parent_length
+ name_length
] = '\0';
449 while (filled
&& total
< n_names
);
451 /* If the table was corrupted then 'names' may have holes in it.
454 if G_UNLIKELY (total
!= n_names
)
456 GPtrArray
*fixed_names
;
458 fixed_names
= g_ptr_array_new ();
459 for (i
= 0; i
< n_names
; i
++)
460 if (names
[i
] != NULL
)
461 g_ptr_array_add (fixed_names
, names
[i
]);
464 n_names
= fixed_names
->len
;
465 g_ptr_array_add (fixed_names
, NULL
);
466 names
= (gchar
**) g_ptr_array_free (fixed_names
, FALSE
);
477 * @file: a #GvdbTable
479 * @returns: a %NULL-terminated string array
481 * List all of the keys that appear below @key. The nesting of keys
482 * within the hash file is defined by the program that created the hash
483 * file. One thing is constant: each item in the returned array can be
484 * concatenated to @key to obtain the full name of that key.
486 * It is not possible to tell from this function if a given key is
487 * itself a path, a value, or another hash table; you are expected to
488 * know this for yourself.
490 * You should call g_strfreev() on the return result when you no longer
494 gvdb_table_list (GvdbTable
*file
,
497 const struct gvdb_hash_item
*item
;
498 const guint32_le
*list
;
503 if ((item
= gvdb_table_lookup (file
, key
, 'L')) == NULL
)
506 if (!gvdb_table_list_from_item (file
, item
, &list
, &length
))
509 strv
= g_new (gchar
*, length
+ 1);
510 for (i
= 0; i
< length
; i
++)
512 guint32 itemno
= guint32_from_le (list
[i
]);
514 if (itemno
< file
->n_hash_items
)
516 const struct gvdb_hash_item
*item
;
520 item
= file
->hash_items
+ itemno
;
522 string
= gvdb_table_item_get_key (file
, item
, &strsize
);
525 strv
[i
] = g_strndup (string
, strsize
);
527 strv
[i
] = g_malloc0 (1);
530 strv
[i
] = g_malloc0 (1);
539 * gvdb_table_has_value:
540 * @file: a #GvdbTable
542 * @returns: %TRUE if @key is in the table
544 * Checks for a value named @key in @file.
546 * Note: this function does not consider non-value nodes (other hash
547 * tables, for example).
550 gvdb_table_has_value (GvdbTable
*file
,
553 static const struct gvdb_hash_item
*item
;
556 item
= gvdb_table_lookup (file
, key
, 'v');
561 return gvdb_table_dereference (file
, &item
->value
.pointer
, 8, &size
) != NULL
;
565 gvdb_table_value_from_item (GvdbTable
*table
,
566 const struct gvdb_hash_item
*item
)
568 GVariant
*variant
, *value
;
573 data
= gvdb_table_dereference (table
, &item
->value
.pointer
, 8, &size
);
575 if G_UNLIKELY (data
== NULL
)
578 bytes
= g_bytes_new_from_bytes (table
->bytes
, ((gchar
*) data
) - table
->data
, size
);
579 variant
= g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT
, bytes
, table
->trusted
);
580 value
= g_variant_get_variant (variant
);
581 g_variant_unref (variant
);
582 g_bytes_unref (bytes
);
588 * gvdb_table_get_value:
589 * @file: a #GvdbTable
591 * @returns: a #GVariant, or %NULL
593 * Looks up a value named @key in @file.
595 * If the value is not found then %NULL is returned. Otherwise, a new
596 * #GVariant instance is returned. The #GVariant does not depend on the
597 * continued existence of @file.
599 * You should call g_variant_unref() on the return result when you no
603 gvdb_table_get_value (GvdbTable
*file
,
606 const struct gvdb_hash_item
*item
;
609 if ((item
= gvdb_table_lookup (file
, key
, 'v')) == NULL
)
612 value
= gvdb_table_value_from_item (file
, item
);
614 if (value
&& file
->byteswapped
)
618 tmp
= g_variant_byteswap (value
);
619 g_variant_unref (value
);
627 * gvdb_table_get_raw_value:
628 * @table: a #GvdbTable
630 * @returns: a #GVariant, or %NULL
632 * Looks up a value named @key in @file.
634 * This call is equivalent to gvdb_table_get_value() except that it
635 * never byteswaps the value.
638 gvdb_table_get_raw_value (GvdbTable
*table
,
641 const struct gvdb_hash_item
*item
;
643 if ((item
= gvdb_table_lookup (table
, key
, 'v')) == NULL
)
646 return gvdb_table_value_from_item (table
, item
);
650 * gvdb_table_get_table:
651 * @file: a #GvdbTable
653 * @returns: a new #GvdbTable, or %NULL
655 * Looks up the hash table named @key in @file.
657 * The toplevel hash table in a #GvdbTable can contain reference to
658 * child hash tables (and those can contain further references...).
660 * If @key is not found in @file then %NULL is returned. Otherwise, a
661 * new #GvdbTable is returned, referring to the child hashtable as
662 * contained in the file. This newly-created #GvdbTable does not depend
663 * on the continued existence of @file.
665 * You should call gvdb_table_free() on the return result when you no
669 gvdb_table_get_table (GvdbTable
*file
,
672 const struct gvdb_hash_item
*item
;
675 item
= gvdb_table_lookup (file
, key
, 'H');
680 new = g_slice_new0 (GvdbTable
);
681 new->bytes
= g_bytes_ref (file
->bytes
);
682 new->byteswapped
= file
->byteswapped
;
683 new->trusted
= file
->trusted
;
684 new->data
= file
->data
;
685 new->size
= file
->size
;
687 gvdb_table_setup_root (new, &item
->value
.pointer
);
694 * @file: a #GvdbTable
699 gvdb_table_free (GvdbTable
*file
)
701 g_bytes_unref (file
->bytes
);
702 g_slice_free (GvdbTable
, file
);
706 * gvdb_table_is_valid:
707 * @table: a #GvdbTable
708 * @returns: %TRUE if @table is still valid
710 * Checks if the table is still valid.
712 * An on-disk GVDB can be marked as invalid. This happens when the file
713 * has been replaced. The appropriate action is typically to reopen the
717 gvdb_table_is_valid (GvdbTable
*table
)
719 return !!*table
->data
;