cannam@226: /*
cannam@226:   Copyright 2011-2016 David Robillard <http://drobilla.net>
cannam@226: 
cannam@226:   Permission to use, copy, modify, and/or distribute this software for any
cannam@226:   purpose with or without fee is hereby granted, provided that the above
cannam@226:   copyright notice and this permission notice appear in all copies.
cannam@226: 
cannam@226:   THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
cannam@226:   WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
cannam@226:   MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
cannam@226:   ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
cannam@226:   WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
cannam@226:   ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
cannam@226:   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
cannam@226: */
cannam@226: 
cannam@226: #ifndef ZIX_BTREE_H
cannam@226: #define ZIX_BTREE_H
cannam@226: 
cannam@226: #include <stddef.h>
cannam@226: 
cannam@245: #include "common.h"
cannam@226: 
cannam@226: #ifdef __cplusplus
cannam@226: extern "C" {
cannam@226: #else
cannam@226: #    include <stdbool.h>
cannam@226: #endif
cannam@226: 
cannam@226: /**
cannam@226:    @addtogroup zix
cannam@226:    @{
cannam@226:    @name BTree
cannam@226:    @{
cannam@226: */
cannam@226: 
cannam@226: /**
cannam@226:    A B-Tree.
cannam@226: */
cannam@226: typedef struct ZixBTreeImpl ZixBTree;
cannam@226: 
cannam@226: /**
cannam@226:    A B-Tree node (opaque).
cannam@226: */
cannam@226: typedef struct ZixBTreeNodeImpl ZixBTreeNode;
cannam@226: 
cannam@226: /**
cannam@226:    An iterator over a B-Tree.
cannam@226: 
cannam@226:    Note that modifying the trees invalidates all iterators, so all iterators
cannam@226:    are const iterators.
cannam@226: */
cannam@226: typedef struct ZixBTreeIterImpl ZixBTreeIter;
cannam@226: 
cannam@226: /**
cannam@226:    Create a new (empty) B-Tree.
cannam@226: */
cannam@226: ZIX_API ZixBTree*
cannam@226: zix_btree_new(ZixComparator  cmp,
cannam@226:               void*          cmp_data,
cannam@226:               ZixDestroyFunc destroy);
cannam@226: 
cannam@226: /**
cannam@226:    Free `t`.
cannam@226: */
cannam@226: ZIX_API void
cannam@226: zix_btree_free(ZixBTree* t);
cannam@226: 
cannam@226: /**
cannam@226:    Return the number of elements in `t`.
cannam@226: */
cannam@226: ZIX_API size_t
cannam@226: zix_btree_size(const ZixBTree* t);
cannam@226: 
cannam@226: /**
cannam@226:    Insert the element `e` into `t`.
cannam@226: */
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_insert(ZixBTree* t, void* e);
cannam@226: 
cannam@226: /**
cannam@226:    Remove the value `e` from `t`.
cannam@226: 
cannam@226:    @param t Tree to remove from.
cannam@226: 
cannam@226:    @param e Value to remove.
cannam@226: 
cannam@226:    @param out Set to point to the removed pointer (which may not equal `e`).
cannam@226: 
cannam@226:    @param next If non-NULL, pointed to the value following `e`.  If *next is
cannam@226:    also non-NULL, the iterator is reused, otherwise a new one is allocated.  To
cannam@226:    reuse an iterator, no items may have been added since its creation.
cannam@226: */
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next);
cannam@226: 
cannam@226: /**
cannam@226:    Set `ti` to an element equal to `e` in `t`.
cannam@226:    If no such item exists, `ti` is set to NULL.
cannam@226: */
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
cannam@226: 
cannam@226: /**
cannam@226:    Set `ti` to the smallest element in `t` that is not less than `e`.
cannam@226: 
cannam@226:    Wildcards are supported, so if the search key `e` compares equal to many
cannam@226:    values in the tree, `ti` will be set to the least such element.  The search
cannam@226:    key `e` is always passed as the second argument to the comparator.
cannam@226: */
cannam@226: ZIX_API ZixStatus
cannam@226: zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
cannam@226: 
cannam@226: /**
cannam@226:    Return the data associated with the given tree item.
cannam@226: */
cannam@226: ZIX_API void*
cannam@226: zix_btree_get(const ZixBTreeIter* ti);
cannam@226: 
cannam@226: /**
cannam@226:    Return an iterator to the first (smallest) element in `t`.
cannam@226: 
cannam@226:    The returned iterator must be freed with zix_btree_iter_free().
cannam@226: */
cannam@226: ZIX_API ZixBTreeIter*
cannam@226: zix_btree_begin(const ZixBTree* t);
cannam@226: 
cannam@226: /**
cannam@226:    Return true iff `i` is an iterator to the end of its tree.
cannam@226: */
cannam@226: ZIX_API bool
cannam@226: zix_btree_iter_is_end(const ZixBTreeIter* i);
cannam@226: 
cannam@226: /**
cannam@226:    Increment `i` to point to the next element in the tree.
cannam@226: */
cannam@226: ZIX_API void
cannam@226: zix_btree_iter_increment(ZixBTreeIter* i);
cannam@226: 
cannam@226: /**
cannam@226:    Free `i`.
cannam@226: */
cannam@226: ZIX_API void
cannam@226: zix_btree_iter_free(ZixBTreeIter* i);
cannam@226: 
cannam@226: /**
cannam@226:    @}
cannam@226:    @}
cannam@226: */
cannam@226: 
cannam@226: #ifdef __cplusplus
cannam@226: }  /* extern "C" */
cannam@226: #endif
cannam@226: 
cannam@226: #endif  /* ZIX_BTREE_H */