Go to the source code of this file.
Classes | |
| struct | mkavl_avl_ctx_st_ |
| struct | mkavl_avl_tree_st_ |
| struct | mkavl_allocator_wrapper_st_ |
| struct | mkavl_tree_st_ |
| struct | mkavl_iterator_st_ |
Defines | |
| #define | CT_ASSERT(e) extern char (*CT_ASSERT(void)) [sizeof(char[1 - 2*!(e)])] |
| #define | NELEMS(x) (sizeof(x) / sizeof(x[0])) |
| #define | MKAVL_RUNAWAY_SANITY 100000 |
| #define | MKAVL_CTX_MAGIC 0xCAFEBABE |
| #define | MKAVL_CTX_STALE 0xDEADBEEF |
Typedefs | |
| typedef struct mkavl_avl_ctx_st_ | mkavl_avl_ctx_st |
| typedef struct mkavl_avl_tree_st_ | mkavl_avl_tree_st |
| typedef struct mkavl_allocator_wrapper_st_ | mkavl_allocator_wrapper_st |
| typedef struct mkavl_tree_st_ | mkavl_tree_st |
| typedef struct mkavl_iterator_st_ | mkavl_iterator_st |
Functions | |
| static void | mkavl_assert_abort (bool condition) |
| bool | mkavl_rc_e_is_notok (mkavl_rc_e rc) |
| bool | mkavl_rc_e_is_ok (mkavl_rc_e rc) |
| bool | mkavl_rc_e_is_valid (mkavl_rc_e rc) |
| const char * | mkavl_rc_e_get_string (mkavl_rc_e rc) |
| bool | mkavl_find_type_e_is_valid (mkavl_find_type_e type) |
| const char * | mkavl_find_type_e_get_string (mkavl_find_type_e type) |
| static bool | mkavl_avl_ctx_is_valid (mkavl_avl_ctx_st *avl_ctx) |
| static bool | mkavl_allocator_wrapper_is_valid (mkavl_allocator_wrapper_st *allocator) |
| static void * | mkavl_malloc_wrapper (struct libavl_allocator *allocator, size_t size) |
| static void | mkavl_free_wrapper (struct libavl_allocator *allocator, void *libavl_block) |
| static void * | mkavl_default_malloc_fn (size_t size, void *context) |
| static void | mkavl_default_free_fn (void *ptr, void *context) |
| static int | mkavl_compare_wrapper (const void *avl_a, const void *avl_b, void *avl_param) |
| static void * | mkavl_copy_wrapper (void *avl_item, void *avl_param) |
| static mkavl_rc_e | mkavl_delete_tree (mkavl_tree_handle *tree_h) |
| static bool | mkavl_tree_is_valid (mkavl_tree_handle tree_h) |
| static bool | mkavl_iterator_is_valid (mkavl_iterator_handle iterator_h) |
| mkavl_rc_e | mkavl_new (mkavl_tree_handle *tree_h, mkavl_compare_fn *compare_fn_array, size_t compare_fn_array_count, void *context, mkavl_allocator_st *allocator) |
| void * | mkavl_get_tree_context (mkavl_tree_handle tree_h) |
| mkavl_rc_e | mkavl_delete (mkavl_tree_handle *tree_h, mkavl_item_fn item_fn, mkavl_delete_context_fn delete_context_fn) |
| mkavl_rc_e | mkavl_copy (mkavl_tree_handle source_tree_h, mkavl_tree_handle *new_tree_h, mkavl_copy_fn copy_fn, mkavl_item_fn item_fn, bool use_source_context, void *new_context, mkavl_delete_context_fn delete_context_fn, mkavl_allocator_st *allocator) |
| mkavl_rc_e | mkavl_add (mkavl_tree_handle tree_h, void *item_to_add, void **existing_item) |
| static mkavl_rc_e | mkavl_avl_end_item (const struct avl_node *node, void **found_item, uint8_t side) |
| static mkavl_rc_e | mkavl_avl_first (const struct avl_node *node, void **found_item) |
| static mkavl_rc_e | mkavl_avl_last (const struct avl_node *node, void **found_item) |
| static mkavl_rc_e | mkavl_find_avl_lt (const struct avl_table *avl_tree, const struct avl_node *node, bool find_equal_to, const void *lookup_item, void **found_item) |
| static mkavl_rc_e | mkavl_find_avl_gt (const struct avl_table *avl_tree, const struct avl_node *node, bool find_equal_to, const void *lookup_item, void **found_item) |
| mkavl_rc_e | mkavl_find (mkavl_tree_handle tree_h, mkavl_find_type_e type, size_t key_idx, const void *lookup_item, void **found_item) |
| mkavl_rc_e | mkavl_remove (mkavl_tree_handle tree_h, const void *item_to_remove, void **found_item) |
| mkavl_rc_e | mkavl_add_key_idx (mkavl_tree_handle tree_h, size_t key_idx, void *item_to_add, void **existing_item) |
| mkavl_rc_e | mkavl_remove_key_idx (mkavl_tree_handle tree_h, size_t key_idx, const void *item_to_remove, void **found_item) |
| uint32_t | mkavl_count (mkavl_tree_handle tree_h) |
| mkavl_rc_e | mkavl_walk (mkavl_tree_handle tree_h, mkavl_walk_cb_fn cb_fn, void *walk_context) |
| mkavl_rc_e | mkavl_iter_new (mkavl_iterator_handle *iterator_h, mkavl_tree_handle tree_h, size_t key_idx) |
| mkavl_rc_e | mkavl_iter_delete (mkavl_iterator_handle *iterator_h) |
| mkavl_rc_e | mkavl_iter_first (mkavl_iterator_handle iterator_h, void **item) |
| mkavl_rc_e | mkavl_iter_last (mkavl_iterator_handle iterator_h, void **item) |
| mkavl_rc_e | mkavl_iter_find (mkavl_iterator_handle iterator_h, void *lookup_item, void **found_item) |
| mkavl_rc_e | mkavl_iter_next (mkavl_iterator_handle iterator_h, void **item) |
| mkavl_rc_e | mkavl_iter_prev (mkavl_iterator_handle iterator_h, void **item) |
| mkavl_rc_e | mkavl_iter_cur (mkavl_iterator_handle iterator_h, void **item) |
Variables | |
| static const char *const | mkavl_rc_e_string [] |
| static const char *const | mkavl_find_type_e_string [] |
| static mkavl_allocator_st | mkavl_allocator_default |
| static struct libavl_allocator | mkavl_allocator_wrapper |
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.
This is the implementation for the multi-key AVL interface.
Definition in file mkavl.c.
| #define CT_ASSERT | ( | e | ) | extern char (*CT_ASSERT(void)) [sizeof(char[1 - 2*!(e)])] |
Compile time assert macro from: http://www.pixelbeat.org/programming/gcc/static_assert.html
| #define MKAVL_CTX_MAGIC 0xCAFEBABE |
| #define MKAVL_CTX_STALE 0xDEADBEEF |
| #define MKAVL_RUNAWAY_SANITY 100000 |
| #define NELEMS | ( | x | ) | (sizeof(x) / sizeof(x[0])) |
| typedef struct mkavl_allocator_wrapper_st_ mkavl_allocator_wrapper_st |
A wrapper structure to map the mkavl_allocator to the avl_allocator.
| typedef struct mkavl_avl_ctx_st_ mkavl_avl_ctx_st |
The internal context data for AVL callbacks.
| typedef struct mkavl_avl_tree_st_ mkavl_avl_tree_st |
Maintains info on the AVL data associated with an AVL tree in the mkavl tree.
| typedef struct mkavl_iterator_st_ mkavl_iterator_st |
The internal representation of the mkavl iterator.
| typedef struct mkavl_tree_st_ mkavl_tree_st |
The internal representation of the mkavl tree object.
| mkavl_rc_e mkavl_add | ( | mkavl_tree_handle | tree_h, |
| void * | item_to_add, | ||
| void ** | existing_item | ||
| ) |
| mkavl_rc_e mkavl_add_key_idx | ( | mkavl_tree_handle | tree_h, |
| size_t | key_idx, | ||
| void * | item_to_add, | ||
| void ** | existing_item | ||
| ) |
Add an item only to a specific AVL tree within the mkavl tree. Note that this must be used very carefully in conjunction with mkavl_remove_key_idx to make sure the mkavl does not become out of sync. In steady state, the mkavl should always have an equal number of data items in each AVL tree. However, if a field changes in an item that affects some keys but not other, these APIs may be used to remove the item with the old values from the affected AVLs, update the values, and then re-add to each AVL tree from which the old item was removed.
| tree_h | The mkavl tree. |
| key_idx | The index of the AVL tree to which the item is added. |
| item_to_add | The item being added. |
| existing_item | If an existing item is found, it is returned. |
| static bool mkavl_allocator_wrapper_is_valid | ( | mkavl_allocator_wrapper_st * | allocator | ) | [static] |
| static void mkavl_assert_abort | ( | bool | condition | ) | [inline, static] |
Assert utility to crash (via abort()) if the condition is not met regardless of whether NDEBUG is defined. E.g., if we hit an error condition where the data structures are irreversibly out of sync.
| condition | The condition for which a crash will happen if false. |
| static bool mkavl_avl_ctx_is_valid | ( | mkavl_avl_ctx_st * | avl_ctx | ) | [static] |
| static mkavl_rc_e mkavl_avl_end_item | ( | const struct avl_node * | node, |
| void ** | found_item, | ||
| uint8_t | side | ||
| ) | [inline, static] |
Get the item at the end of the AVL tree. That is, either the first or last item in the tree rooted at the node depending on the side input.
| node | The root of the subtree to search. |
| found_item | The item found. |
| side | 0 to find the first (smallest) item or 1 to find the last (largest) item |
| static mkavl_rc_e mkavl_avl_first | ( | const struct avl_node * | node, |
| void ** | found_item | ||
| ) | [static] |
| static mkavl_rc_e mkavl_avl_last | ( | const struct avl_node * | node, |
| void ** | found_item | ||
| ) | [static] |
| static int mkavl_compare_wrapper | ( | const void * | avl_a, |
| const void * | avl_b, | ||
| void * | avl_param | ||
| ) | [static] |
A wrapper to map the AVL callback to the client callback for the mkavl tree.
| avl_a | The first item in the comparison |
| avl_b | The second item in the comparison |
| avl_param | The context associated with the callback |
| mkavl_rc_e mkavl_copy | ( | mkavl_tree_handle | source_tree_h, |
| mkavl_tree_handle * | new_tree_h, | ||
| mkavl_copy_fn | copy_fn, | ||
| mkavl_item_fn | item_fn, | ||
| bool | use_source_context, | ||
| void * | new_context, | ||
| mkavl_delete_context_fn | delete_context_fn, | ||
| mkavl_allocator_st * | allocator | ||
| ) |
Deep copy a mkavl tree into a new tree.
| source_tree_h | The tree from which to copy. |
| new_tree_h | A pointer to the new tree to which the copy will be done. |
| copy_fn | A function that is applied to each item in the source tree before it is copied to the new tree. This is applied once per item regardless of how many AVL trees there are. E.g., this may allocate a deep copy of the data. If NULL, then a shallow copy of the data is copied to the new tree. Note that this function is called with the source tree's context value. |
| item_fn | If there is an error copying the new tree, this function is applied to all items in the new tree as it is destroyed. E.g., this may be a function to free the data. |
| use_source_context | If true, the client context from source_tree_h is used for the new tree. If false, new_context is used for the new tree. |
| new_context | The opaque client context to use for the new tree if user_source_context if false. |
| delete_context_fn | Upon an error, this function will be applied to the new_context if use_source_context is false. If use_source_context is true, this is a no-op in the case of an error (will not call on the source tree's context). If NULL, no function is applied. If given, the function will be called even if the client context is NULL. |
| allocator | The memory allocation functions to use for the new tree. |
| static void* mkavl_copy_wrapper | ( | void * | avl_item, |
| void * | avl_param | ||
| ) | [static] |
| uint32_t mkavl_count | ( | mkavl_tree_handle | tree_h | ) |
Get a count of the total number of items within the tree. Note that this is the steady state account, i.e., broadly, the number of calls to mkavl_add that succeeded minus the number of calls to mkavl_remove that succeeded. If this is called in between calls to mkavl_add_key_idx and mkavl_remove_key_idx, then it is possible for individual AVL trees to have a different count.
| static void mkavl_default_free_fn | ( | void * | ptr, |
| void * | context | ||
| ) | [static] |
| static void* mkavl_default_malloc_fn | ( | size_t | size, |
| void * | context | ||
| ) | [static] |
| mkavl_rc_e mkavl_delete | ( | mkavl_tree_handle * | tree_h, |
| mkavl_item_fn | item_fn, | ||
| mkavl_delete_context_fn | delete_context_fn | ||
| ) |
The destroys the tree that was allocated by mkavl_new. Note that this doesn't actually free the data of the items as that is left to the client. The item_fn parameter can be used for this purpose. Upon return, the tree_h memory is set to NULL. This is O(N lg N) for N items.
| tree_h | A pointer the the tree to free. |
| item_fn | This function is applied to each item after it has been removed from all the AVL trees. This is only called once per item regardless of how many AVL trees there are. E.g., this could be the function to free the memory for the data. If NULL, no function is applied. |
| delete_context_fn | This function is applied to the tree's opaque client context that was given via mkavl_new(). E.g., this could free the client context if it was a heap memory pointer. If NULL, no function is applied. If given, the function will be called even if the client context is NULL. This function is called after all the items have been deleted and item functions called. |
| static mkavl_rc_e mkavl_delete_tree | ( | mkavl_tree_handle * | tree_h | ) | [static] |
| mkavl_rc_e mkavl_find | ( | mkavl_tree_handle | tree_h, |
| mkavl_find_type_e | type, | ||
| size_t | key_idx, | ||
| const void * | lookup_item, | ||
| void ** | found_item | ||
| ) |
| static mkavl_rc_e mkavl_find_avl_gt | ( | const struct avl_table * | avl_tree, |
| const struct avl_node * | node, | ||
| bool | find_equal_to, | ||
| const void * | lookup_item, | ||
| void ** | found_item | ||
| ) | [static] |
Find the item greater than (or equal to) the given lookup_item. Note that the lookup_item does not necessarily have to exist in the tree for an item to be found. This is a recursive funciton.
| avl_tree | The AVL tree to search. |
| node | The current node to compare. |
| find_equal_to | Indicates whether to return an equal item if found or only strictly greater than. |
| lookup_item | The item to use as the lookup target. |
| found_item | The item found. |
| static mkavl_rc_e mkavl_find_avl_lt | ( | const struct avl_table * | avl_tree, |
| const struct avl_node * | node, | ||
| bool | find_equal_to, | ||
| const void * | lookup_item, | ||
| void ** | found_item | ||
| ) | [static] |
Find the item less than (or equal to) the given lookup_item. Note that the lookup_item does not necessarily have to exist in the tree for an item to be found. This is a recursive funciton.
| avl_tree | The AVL tree to search. |
| node | The current node to compare. |
| find_equal_to | Indicates whether to return an equal item if found or only strictly less than. |
| lookup_item | The item to use as the lookup target. |
| found_item | The item found. |
| const char* mkavl_find_type_e_get_string | ( | mkavl_find_type_e | type | ) |
| bool mkavl_find_type_e_is_valid | ( | mkavl_find_type_e | type | ) |
| static void mkavl_free_wrapper | ( | struct libavl_allocator * | allocator, |
| void * | libavl_block | ||
| ) | [static] |
| void* mkavl_get_tree_context | ( | mkavl_tree_handle | tree_h | ) |
Get the context pointer for the tree.
| tree_h | The tree whose context to get. This must be a valid, non-NULL tree pointer or else a crash will occur. |
| mkavl_rc_e mkavl_iter_cur | ( | mkavl_iterator_handle | iterator_h, |
| void ** | item | ||
| ) |
Get the current item in the iteration.
| iterator_h | The iterator to use. |
| item | The item found. |
| mkavl_rc_e mkavl_iter_delete | ( | mkavl_iterator_handle * | iterator_h | ) |
Destroy the iterator.
| iterator_h | The iterator to free. Upon return, this will be set to NULL. |
| mkavl_rc_e mkavl_iter_find | ( | mkavl_iterator_handle | iterator_h, |
| void * | lookup_item, | ||
| void ** | found_item | ||
| ) |
Find an item and update the iterator to that node.
| iterator_h | The iterator to use. |
| lookup_item | The item to find. |
| found_item | The item found. |
| mkavl_rc_e mkavl_iter_first | ( | mkavl_iterator_handle | iterator_h, |
| void ** | item | ||
| ) |
Get the first item in the iteration.
| iterator_h | The iterator to use. |
| item | The item found. |
| mkavl_rc_e mkavl_iter_last | ( | mkavl_iterator_handle | iterator_h, |
| void ** | item | ||
| ) |
Get the last item in the iteration.
| iterator_h | The iterator to use. |
| item | The item found. |
| mkavl_rc_e mkavl_iter_new | ( | mkavl_iterator_handle * | iterator_h, |
| mkavl_tree_handle | tree_h, | ||
| size_t | key_idx | ||
| ) |
Create a new iterator to use.
| iterator_h | The pointer to fill in with the new iterator. |
| tree_h | The tree on which to iterate. |
| key_idx | The index of the AVL tree on which to iterate. |
| mkavl_rc_e mkavl_iter_next | ( | mkavl_iterator_handle | iterator_h, |
| void ** | item | ||
| ) |
Get the next item in the iteration and update the iterator to that node.
| iterator_h | The iterator to use. |
| item | The item found. |
| mkavl_rc_e mkavl_iter_prev | ( | mkavl_iterator_handle | iterator_h, |
| void ** | item | ||
| ) |
Get the previous item in the iteration and update the iterator to that node.
| iterator_h | The iterator to use. |
| item | The item found. |
| static bool mkavl_iterator_is_valid | ( | mkavl_iterator_handle | iterator_h | ) | [static] |
| static void* mkavl_malloc_wrapper | ( | struct libavl_allocator * | allocator, |
| size_t | size | ||
| ) | [static] |
| mkavl_rc_e mkavl_new | ( | mkavl_tree_handle * | tree_h, |
| mkavl_compare_fn * | compare_fn_array, | ||
| size_t | compare_fn_array_count, | ||
| void * | context, | ||
| mkavl_allocator_st * | allocator | ||
| ) |
Create a new mkavl tree composed of AVL trees using the given array of comparison functions.
| tree_h | A pointer to the memory location for the new tree. |
| compare_fn_array | An array of size compare_fn_array_count of the comparison functions for the mkavl. This allows the same set of data items to be stored in different orders by mulitple keys. A deep copy of the functions is made for the tree_h. There must be at least one function passed in. |
| compare_fn_array_count | The size of the compare_fn_array. |
| context | An opaque context passed back to the client in callbacks. |
| allocator | The memory allocation functions to use for the tree, or NULL if the default functions are to be used. |
| const char* mkavl_rc_e_get_string | ( | mkavl_rc_e | rc | ) |
| bool mkavl_rc_e_is_notok | ( | mkavl_rc_e | rc | ) |
| bool mkavl_rc_e_is_ok | ( | mkavl_rc_e | rc | ) |
| bool mkavl_rc_e_is_valid | ( | mkavl_rc_e | rc | ) |
| mkavl_rc_e mkavl_remove | ( | mkavl_tree_handle | tree_h, |
| const void * | item_to_remove, | ||
| void ** | found_item | ||
| ) |
| mkavl_rc_e mkavl_remove_key_idx | ( | mkavl_tree_handle | tree_h, |
| size_t | key_idx, | ||
| const void * | item_to_remove, | ||
| void ** | found_item | ||
| ) |
Remove an item only from a specific AVL tree within the mkavl tree. Note that this must be used very carefully in conjunction with mkavl_add_key_idx to make sure the mkavl does not become out of sync. In steady state, the mkavl should always have an equal number of data items in each AVL tree. However, if a field changes in an item that affects some keys but not other, these APIs may be used to remove the item with the old values from the affected AVLs, update the values, and then re-add to each AVL tree from which the old item was removed.
| tree_h | The mkavl tree. |
| key_idx | The index of the AVL tree to which the item is added. |
| item_to_remove | The item being removed. |
| found_item | If the item existed, the item that was found and removed. |
| static bool mkavl_tree_is_valid | ( | mkavl_tree_handle | tree_h | ) | [static] |
| mkavl_rc_e mkavl_walk | ( | mkavl_tree_handle | tree_h, |
| mkavl_walk_cb_fn | cb_fn, | ||
| void * | walk_context | ||
| ) |
Walk every node in the tree, calling the given function for each item. There is no guarantee on the order of the walk.
| tree_h | The tree to walk. |
| cb_fn | The callback function to apply to each item. |
| walk_context | The opaque walk context passed to the callback. |
By default, we'll just use malloc and free if the client passes nothing in.
struct libavl_allocator mkavl_allocator_wrapper [static] |
Wrapper to convert AVL callback to client callback passed to mkavl.
const char* const mkavl_find_type_e_string[] [static] |
{
"Invalid",
"Equal",
"Greater than",
"Less than",
"Greater than or equal",
"Less than or equal",
"Max type"
}
String representations of the return codes.
const char* const mkavl_rc_e_string[] [static] |
{
"Invalid RC",
"Success",
"Invalid input",
"No memory",
"Out of sync",
"Max RC"
}
String representations of the return codes.
1.7.4