# 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);