1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
# Data Structures
MuPDF has implementations of many generally useful data structures and algorithms
such as hash tables and binary trees.
## Hash Table
We have a generic hash table structure with fixed length keys.
The keys and values are not reference counted by the hash table. Callers are responsible for manually taking care of reference counting when inserting and removing values from the table, should that be desired.
`fz_hash_table *fz_new_hash_table(fz_context *ctx, int initial_size, int key_length, int lock, void (*drop_value)(fz_context *ctx, void *value));`
: The lock parameter should be zero, any other value will result in
unpredictable behavior. The `drop_value` callback function to the
constructor is only used to release values when the hash table is
destroyed.
`void fz_drop_hash_table(fz_context *ctx, fz_hash_table *table);`
: Free the hash table and call the `drop_value` function on all the
values in the table.
`void *fz_hash_find(fz_context *ctx, fz_hash_table *table, const void *key);`
: Find the value associated with the key. Returns `NULL` if not found.
`void *fz_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *value);`
: Insert the value into the hash table. Inserting a duplicate entry will
**not** overwrite the old value, it will return the old value instead.
Return `NULL` if the value was inserted for the first time. Does not
reference count the value!
`void fz_hash_remove(fz_context *ctx, fz_hash_table *table, const void *key);`
: Remove the associated value from the hash table. This will not
reference count the value!
`void fz_hash_for_each(fz_context *ctx, fz_hash_table *table, void *state, void (*callback)(fz_context *ctx, void *state, void *key, int key_length, void *value);`
: Iterate and call a function for each key-value pair in the table.
## Binary Tree
The `fz_tree` structure is a self-balancing binary tree that maps text strings to values.
`void *fz_tree_lookup(fz_context *ctx, fz_tree *node, const char *key);`
: Look up an entry in the tree. Returns `NULL` if not found.
`fz_tree *fz_tree_insert(fz_context *ctx, fz_tree *root, const char *key, void *value);`
: Insert a new entry into the tree. Do not insert duplicate entries.
Returns the new root object.
`void fz_drop_tree(fz_context *ctx, fz_tree *node, void (*dropfunc)(fz_context *ctx, void *value));`
: Free the tree and all the values in it.
There is no constructor for this structure, since there is no containing root
structure. Instead, the insert function returns the new root node. Use `NULL`
for the initial empty tree.
fz_tree *tree = NULL;
tree = fz_tree_insert(ctx, tree, "A", my_a_obj);
tree = fz_tree_insert(ctx, tree, "B", my_b_obj);
tree = fz_tree_insert(ctx, tree, "C", my_c_obj);
assert(fz_tree_lookup(ctx, tree, "B") == my_b_obj);
|
