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.1 of the License, 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, see <http://www.gnu.org/licenses/>.
17 * Author: Ryan Lortie <desrt@desrt.ca>
20 #include "gvdb-reader.h"
21 #include "gvdb-format.h"
34 const guint32_le
*bloom_words
;
35 guint32 n_bloom_words
;
38 const guint32_le
*hash_buckets
;
41 struct gvdb_hash_item
*hash_items
;
46 gvdb_table_item_get_key (GvdbTable
*file
,
47 const struct gvdb_hash_item
*item
,
52 start
= guint32_from_le (item
->key_start
);
53 *size
= guint16_from_le (item
->key_size
);
56 if G_UNLIKELY (start
> end
|| end
> file
->size
)
59 return file
->data
+ start
;
63 gvdb_table_dereference (GvdbTable
*file
,
64 const struct gvdb_pointer
*pointer
,
70 start
= guint32_from_le (pointer
->start
);
71 end
= guint32_from_le (pointer
->end
);
73 if G_UNLIKELY (start
> end
|| end
> file
->size
|| start
& (alignment
- 1))
78 return file
->data
+ start
;
82 gvdb_table_setup_root (GvdbTable
*file
,
83 const struct gvdb_pointer
*pointer
)
85 const struct gvdb_hash_header
*header
;
86 guint32 n_bloom_words
;
90 header
= gvdb_table_dereference (file
, pointer
, 4, &size
);
92 if G_UNLIKELY (header
== NULL
|| size
< sizeof *header
)
95 size
-= sizeof *header
;
97 n_bloom_words
= guint32_from_le (header
->n_bloom_words
);
98 n_buckets
= guint32_from_le (header
->n_buckets
);
99 n_bloom_words
&= (1u << 27) - 1;
101 if G_UNLIKELY (n_bloom_words
* sizeof (guint32_le
) > size
)
104 file
->bloom_words
= (gpointer
) (header
+ 1);
105 size
-= n_bloom_words
* sizeof (guint32_le
);
106 file
->n_bloom_words
= n_bloom_words
;
108 if G_UNLIKELY (n_buckets
> G_MAXUINT
/ sizeof (guint32_le
) ||
109 n_buckets
* sizeof (guint32_le
) > size
)
112 file
->hash_buckets
= file
->bloom_words
+ file
->n_bloom_words
;
113 size
-= n_buckets
* sizeof (guint32_le
);
114 file
->n_buckets
= n_buckets
;
116 if G_UNLIKELY (size
% sizeof (struct gvdb_hash_item
))
119 file
->hash_items
= (gpointer
) (file
->hash_buckets
+ n_buckets
);
120 file
->n_hash_items
= size
/ sizeof (struct gvdb_hash_item
);
124 * gvdb_table_new_from_bytes:
125 * @bytes: the #GBytes with the data
126 * @trusted: if the contents of @bytes are trusted
127 * @error: %NULL, or a pointer to a %NULL #GError
128 * @returns: a new #GvdbTable
130 * Creates a new #GvdbTable from the contents of @bytes.
132 * This call can fail if the header contained in @bytes is invalid.
134 * You should call gvdb_table_free() on the return result when you no
138 gvdb_table_new_from_bytes (GBytes
*bytes
,
142 const struct gvdb_header
*header
;
145 file
= g_slice_new0 (GvdbTable
);
146 file
->bytes
= g_bytes_ref (bytes
);
147 file
->data
= g_bytes_get_data (bytes
, &file
->size
);
148 file
->trusted
= trusted
;
150 if (file
->size
< sizeof (struct gvdb_header
))
153 header
= (gpointer
) file
->data
;
155 if (header
->signature
[0] == GVDB_SIGNATURE0
&&
156 header
->signature
[1] == GVDB_SIGNATURE1
&&
157 guint32_from_le (header
->version
) == 0)
158 file
->byteswapped
= FALSE
;
160 else if (header
->signature
[0] == GVDB_SWAPPED_SIGNATURE0
&&
161 header
->signature
[1] == GVDB_SWAPPED_SIGNATURE1
&&
162 guint32_from_le (header
->version
) == 0)
163 file
->byteswapped
= TRUE
;
168 gvdb_table_setup_root (file
, &header
->root
);
173 g_set_error_literal (error
, G_FILE_ERROR
, G_FILE_ERROR_INVAL
, "invalid gvdb header");
175 g_bytes_unref (file
->bytes
);
177 g_slice_free (GvdbTable
, file
);
184 * @filename: a filename
185 * @trusted: if the contents of @bytes are trusted
186 * @error: %NULL, or a pointer to a %NULL #GError
187 * @returns: a new #GvdbTable
189 * Creates a new #GvdbTable using the #GMappedFile for @filename as the
193 gvdb_table_new (const gchar
*filename
,
201 mapped
= g_mapped_file_new (filename
, FALSE
, error
);
205 bytes
= g_mapped_file_get_bytes (mapped
);
206 table
= gvdb_table_new_from_bytes (bytes
, trusted
, error
);
207 g_mapped_file_unref (mapped
);
208 g_bytes_unref (bytes
);
210 g_prefix_error (error
, "%s: ", filename
);
216 gvdb_table_bloom_filter (GvdbTable
*file
,
221 if (file
->n_bloom_words
== 0)
224 word
= (hash_value
/ 32) % file
->n_bloom_words
;
225 mask
= 1 << (hash_value
& 31);
226 mask
|= 1 << ((hash_value
>> file
->bloom_shift
) & 31);
228 return (guint32_from_le (file
->bloom_words
[word
]) & mask
) == mask
;
232 gvdb_table_check_name (GvdbTable
*file
,
233 struct gvdb_hash_item
*item
,
237 const gchar
*this_key
;
241 this_key
= gvdb_table_item_get_key (file
, item
, &this_size
);
243 if G_UNLIKELY (this_key
== NULL
|| this_size
> key_length
)
246 key_length
-= this_size
;
248 if G_UNLIKELY (memcmp (this_key
, key
+ key_length
, this_size
) != 0)
251 parent
= guint32_from_le (item
->parent
);
252 if (key_length
== 0 && parent
== 0xffffffffu
)
255 if G_LIKELY (parent
< file
->n_hash_items
&& this_size
> 0)
256 return gvdb_table_check_name (file
,
257 &file
->hash_items
[parent
],
263 static const struct gvdb_hash_item
*
264 gvdb_table_lookup (GvdbTable
*file
,
268 guint32 hash_value
= 5381;
274 if G_UNLIKELY (file
->n_buckets
== 0 || file
->n_hash_items
== 0)
277 for (key_length
= 0; key
[key_length
]; key_length
++)
278 hash_value
= (hash_value
* 33) + ((signed char *) key
)[key_length
];
280 if (!gvdb_table_bloom_filter (file
, hash_value
))
283 bucket
= hash_value
% file
->n_buckets
;
284 itemno
= guint32_from_le (file
->hash_buckets
[bucket
]);
286 if (bucket
== file
->n_buckets
- 1 ||
287 (lastno
= guint32_from_le(file
->hash_buckets
[bucket
+ 1])) > file
->n_hash_items
)
288 lastno
= file
->n_hash_items
;
290 while G_LIKELY (itemno
< lastno
)
292 struct gvdb_hash_item
*item
= &file
->hash_items
[itemno
];
294 if (hash_value
== guint32_from_le (item
->hash_value
))
295 if G_LIKELY (gvdb_table_check_name (file
, item
, key
, key_length
))
296 if G_LIKELY (item
->type
== type
)
306 gvdb_table_list_from_item (GvdbTable
*table
,
307 const struct gvdb_hash_item
*item
,
308 const guint32_le
**list
,
313 *list
= gvdb_table_dereference (table
, &item
->value
.pointer
, 4, &size
);
315 if G_LIKELY (*list
== NULL
|| size
% 4)
324 * gvdb_table_get_names:
325 * @table: a #GvdbTable
326 * @length: the number of items returned, or %NULL
328 * Gets a list of all names contained in @table.
330 * No call to gvdb_table_get_table(), gvdb_table_list() or
331 * gvdb_table_get_value() will succeed unless it is for one of the
332 * names returned by this function.
334 * Note that some names that are returned may still fail for all of the
335 * above calls in the case of the corrupted file. Note also that the
336 * returned strings may not be utf8.
338 * Returns: a %NULL-terminated list of strings, of length @length
341 gvdb_table_get_names (GvdbTable
*table
,
350 /* We generally proceed by iterating over the list of items in the
351 * hash table (in order of appearance) recording them into an array.
353 * Each item has a parent item (except root items). The parent item
354 * forms part of the name of the item. We could go fetching the
355 * parent item chain at the point that we encounter each item but then
356 * we would need to implement some sort of recursion along with checks
357 * for self-referential items.
359 * Instead, we do a number of passes. Each pass will build up one
360 * level of names (starting from the root). We continue to do passes
361 * until no more items are left. The first pass will only add root
362 * items and each further pass will only add items whose direct parent
363 * is an item added in the immediately previous pass. It's also
364 * possible that items get filled if they follow their parent within a
367 * At most we will have a number of passes equal to the depth of the
368 * tree. Self-referential items will never be filled in (since their
369 * parent will have never been filled in). We continue until we have
370 * a pass that fills in no additional items.
372 * This takes an O(n) algorithm and turns it into O(n*m) where m is
373 * the depth of the tree, but in all sane cases the tree won't be very
374 * deep and the constant factor of this algorithm is lower (and the
375 * complexity of coding it, as well).
378 n_names
= table
->n_hash_items
;
379 names
= g_new0 (gchar
*, n_names
+ 1);
381 /* 'names' starts out all-NULL. On each pass we record the number
382 * of items changed from NULL to non-NULL in 'filled' so we know if we
383 * should repeat the loop. 'total' counts the total number of items
384 * filled. If 'total' ends up equal to 'n_names' then we know that
385 * 'names' has been completely filled.
391 /* Loop until we have filled no more entries */
394 for (i
= 0; i
< n_names
; i
++)
396 const struct gvdb_hash_item
*item
= &table
->hash_items
[i
];
401 /* already got it on a previous pass */
402 if (names
[i
] != NULL
)
405 parent
= guint32_from_le (item
->parent
);
407 if (parent
== 0xffffffffu
)
409 /* it's a root item */
410 name
= gvdb_table_item_get_key (table
, item
, &name_length
);
414 names
[i
] = g_strndup (name
, name_length
);
419 else if (parent
< n_names
&& names
[parent
] != NULL
)
421 /* It's a non-root item whose parent was filled in already.
423 * Calculate the name of this item by combining it with
426 name
= gvdb_table_item_get_key (table
, item
, &name_length
);
430 const gchar
*parent_name
= names
[parent
];
434 parent_length
= strlen (parent_name
);
435 fullname
= g_malloc (parent_length
+ name_length
+ 1);
436 memcpy (fullname
, parent_name
, parent_length
);
437 memcpy (fullname
+ parent_length
, name
, name_length
);
438 fullname
[parent_length
+ name_length
] = '\0';
447 while (filled
&& total
< n_names
);
449 /* If the table was corrupted then 'names' may have holes in it.
452 if G_UNLIKELY (total
!= n_names
)
454 GPtrArray
*fixed_names
;
456 fixed_names
= g_ptr_array_new ();
457 for (i
= 0; i
< n_names
; i
++)
458 if (names
[i
] != NULL
)
459 g_ptr_array_add (fixed_names
, names
[i
]);
462 n_names
= fixed_names
->len
;
463 g_ptr_array_add (fixed_names
, NULL
);
464 names
= (gchar
**) g_ptr_array_free (fixed_names
, FALSE
);
475 * @file: a #GvdbTable
477 * @returns: a %NULL-terminated string array
479 * List all of the keys that appear below @key. The nesting of keys
480 * within the hash file is defined by the program that created the hash
481 * file. One thing is constant: each item in the returned array can be
482 * concatenated to @key to obtain the full name of that key.
484 * It is not possible to tell from this function if a given key is
485 * itself a path, a value, or another hash table; you are expected to
486 * know this for yourself.
488 * You should call g_strfreev() on the return result when you no longer
492 gvdb_table_list (GvdbTable
*file
,
495 const struct gvdb_hash_item
*item
;
496 const guint32_le
*list
;
501 if ((item
= gvdb_table_lookup (file
, key
, 'L')) == NULL
)
504 if (!gvdb_table_list_from_item (file
, item
, &list
, &length
))
507 strv
= g_new (gchar
*, length
+ 1);
508 for (i
= 0; i
< length
; i
++)
510 guint32 itemno
= guint32_from_le (list
[i
]);
512 if (itemno
< file
->n_hash_items
)
514 const struct gvdb_hash_item
*item
;
518 item
= file
->hash_items
+ itemno
;
520 string
= gvdb_table_item_get_key (file
, item
, &strsize
);
523 strv
[i
] = g_strndup (string
, strsize
);
525 strv
[i
] = g_malloc0 (1);
528 strv
[i
] = g_malloc0 (1);
537 * gvdb_table_has_value:
538 * @file: a #GvdbTable
540 * @returns: %TRUE if @key is in the table
542 * Checks for a value named @key in @file.
544 * Note: this function does not consider non-value nodes (other hash
545 * tables, for example).
548 gvdb_table_has_value (GvdbTable
*file
,
551 static const struct gvdb_hash_item
*item
;
554 item
= gvdb_table_lookup (file
, key
, 'v');
559 return gvdb_table_dereference (file
, &item
->value
.pointer
, 8, &size
) != NULL
;
563 gvdb_table_value_from_item (GvdbTable
*table
,
564 const struct gvdb_hash_item
*item
)
566 GVariant
*variant
, *value
;
571 data
= gvdb_table_dereference (table
, &item
->value
.pointer
, 8, &size
);
573 if G_UNLIKELY (data
== NULL
)
576 bytes
= g_bytes_new_from_bytes (table
->bytes
, ((gchar
*) data
) - table
->data
, size
);
577 variant
= g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT
, bytes
, table
->trusted
);
578 value
= g_variant_get_variant (variant
);
579 g_variant_unref (variant
);
580 g_bytes_unref (bytes
);
586 * gvdb_table_get_value:
587 * @file: a #GvdbTable
589 * @returns: a #GVariant, or %NULL
591 * Looks up a value named @key in @file.
593 * If the value is not found then %NULL is returned. Otherwise, a new
594 * #GVariant instance is returned. The #GVariant does not depend on the
595 * continued existence of @file.
597 * You should call g_variant_unref() on the return result when you no
601 gvdb_table_get_value (GvdbTable
*file
,
604 const struct gvdb_hash_item
*item
;
607 if ((item
= gvdb_table_lookup (file
, key
, 'v')) == NULL
)
610 value
= gvdb_table_value_from_item (file
, item
);
612 if (value
&& file
->byteswapped
)
616 tmp
= g_variant_byteswap (value
);
617 g_variant_unref (value
);
625 * gvdb_table_get_raw_value:
626 * @table: a #GvdbTable
628 * @returns: a #GVariant, or %NULL
630 * Looks up a value named @key in @file.
632 * This call is equivalent to gvdb_table_get_value() except that it
633 * never byteswaps the value.
636 gvdb_table_get_raw_value (GvdbTable
*table
,
639 const struct gvdb_hash_item
*item
;
641 if ((item
= gvdb_table_lookup (table
, key
, 'v')) == NULL
)
644 return gvdb_table_value_from_item (table
, item
);
648 * gvdb_table_get_table:
649 * @file: a #GvdbTable
651 * @returns: a new #GvdbTable, or %NULL
653 * Looks up the hash table named @key in @file.
655 * The toplevel hash table in a #GvdbTable can contain reference to
656 * child hash tables (and those can contain further references...).
658 * If @key is not found in @file then %NULL is returned. Otherwise, a
659 * new #GvdbTable is returned, referring to the child hashtable as
660 * contained in the file. This newly-created #GvdbTable does not depend
661 * on the continued existence of @file.
663 * You should call gvdb_table_free() on the return result when you no
667 gvdb_table_get_table (GvdbTable
*file
,
670 const struct gvdb_hash_item
*item
;
673 item
= gvdb_table_lookup (file
, key
, 'H');
678 new = g_slice_new0 (GvdbTable
);
679 new->bytes
= g_bytes_ref (file
->bytes
);
680 new->byteswapped
= file
->byteswapped
;
681 new->trusted
= file
->trusted
;
682 new->data
= file
->data
;
683 new->size
= file
->size
;
685 gvdb_table_setup_root (new, &item
->value
.pointer
);
692 * @file: a #GvdbTable
697 gvdb_table_free (GvdbTable
*file
)
699 g_bytes_unref (file
->bytes
);
700 g_slice_free (GvdbTable
, file
);
704 * gvdb_table_is_valid:
705 * @table: a #GvdbTable
706 * @returns: %TRUE if @table is still valid
708 * Checks if the table is still valid.
710 * An on-disk GVDB can be marked as invalid. This happens when the file
711 * has been replaced. The appropriate action is typically to reopen the
715 gvdb_table_is_valid (GvdbTable
*table
)
717 return !!*table
->data
;