treap.h File Reference

The cdc_treap is a struct and functions that provide a cartesion tree. More...

#include <cdcontainers/common.h>
#include <cdcontainers/status.h>
#include <assert.h>
#include <stdarg.h>
#include <stdbool.h>

Go to the source code of this file.

Data Structures
struct	cdc_treap_node
	The cdc_treap_node is service struct. More...
struct	cdc_treap
	The cdc_treap is service struct. More...
struct	cdc_treap_iter
	The cdc_treap_iter is service struct. More...
struct	cdc_pair_treap_iter_bool

Typedefs
typedef int(*	cdc_priority_fn_t) (void *)

Functions
enum cdc_stat	cdc_treap_ctor (struct cdc_treap **t, struct cdc_data_info *info)
	Constructs an empty treap. More...
enum cdc_stat	cdc_treap_ctorl (struct cdc_treap **t, struct cdc_data_info *info,...)
	Constructs a treap, initialized by an variable number of pointers on cdc_pair's(first - key, and the second - value). The last item must be CDC_END. More...
enum cdc_stat	cdc_treap_ctorv (struct cdc_treap **t, struct cdc_data_info *info, va_list args)
	Constructs a treap, initialized by args. The last item must be CDC_END. More...
enum cdc_stat	cdc_treap_ctor1 (struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior)
	Constructs an empty treap. More...
enum cdc_stat	cdc_treap_ctorl1 (struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior,...)
	Constructs a treap, initialized by an variable number of pointers on cdc_pair's(first - key, and the second - value). The last item must be CDC_END. More...
enum cdc_stat	cdc_treap_ctorv1 (struct cdc_treap **t, struct cdc_data_info *info, cdc_priority_fn_t prior, va_list args)
	Constructs a treap, initialized by args. The last item must be CDC_END. More...
void	cdc_treap_dtor (struct cdc_treap *t)
	Destroys the treap. More...
enum cdc_stat	cdc_treap_get (struct cdc_treap *t, void *key, void **value)
	Returns a value that is mapped to a key. If the key does not exist, then NULL will return. More...
size_t	cdc_treap_count (struct cdc_treap *t, void *key)
	Returns the number of elements with key that compares equal to the specified argument key, which is either 1 or 0 since this container does not allow duplicates. More...
void	cdc_treap_find (struct cdc_treap *t, void *key, struct cdc_treap_iter *it)
	Finds an element with key equivalent to key. More...
static size_t	cdc_treap_size (struct cdc_treap *t)
	Returns the number of items in the treap. More...
static bool	cdc_treap_empty (struct cdc_treap *t)
	Checks if the treap has no elements. More...
void	cdc_treap_clear (struct cdc_treap *t)
	Removes all the elements from the treap. More...
enum cdc_stat	cdc_treap_insert (struct cdc_treap *t, void *key, void *value, struct cdc_pair_treap_iter_bool *ret)
	Inserts an element into the container, if the container doesn't already contain an element with an equivalent key. More...
enum cdc_stat	cdc_treap_insert1 (struct cdc_treap *t, void *key, void *value, struct cdc_treap_iter *it, bool *inserted)
	Inserts an element into the container, if the container doesn't already contain an element with an equivalent key. More...
enum cdc_stat	cdc_treap_insert_or_assign (struct cdc_treap *t, void *key, void *value, struct cdc_pair_treap_iter_bool *ret)
	Inserts an element or assigns to the current element if the key already exists. More...
enum cdc_stat	cdc_treap_insert_or_assign1 (struct cdc_treap *t, void *key, void *value, struct cdc_treap_iter *it, bool *inserted)
	Inserts an element or assigns to the current element if the key already exists. More...
size_t	cdc_treap_erase (struct cdc_treap *t, void *key)
	Removes the element (if one exists) with the key equivalent to key. More...
void	cdc_treap_swap (struct cdc_treap *a, struct cdc_treap *b)
	Swaps treaps a and b. This operation is very fast and never fails. More...
void	cdc_treap_begin (struct cdc_treap *t, struct cdc_treap_iter *it)
	Initializes the iterator to the beginning. More...
void	cdc_treap_end (struct cdc_treap *t, struct cdc_treap_iter *it)
	Initializes the iterator to the end. More...
void	cdc_treap_iter_next (struct cdc_treap_iter *it)
	Advances the iterator to the next element in the treap. More...
void	cdc_treap_iter_prev (struct cdc_treap_iter *it)
	Advances the iterator to the previous element in the treap. More...
static bool	cdc_treap_iter_has_next (struct cdc_treap_iter *it)
	Returns true if there is at least one element ahead of the iterator, i.e. the iterator is not at the back of the container; otherwise returns false. More...
static bool	cdc_treap_iter_has_prev (struct cdc_treap_iter *it)
	Returns true if there is at least one element behind the iterator, i.e. the iterator is not at the front of the container; otherwise returns false. More...
static void *	cdc_treap_iter_key (struct cdc_treap_iter *it)
	Returns an item's key. More...
static void *	cdc_treap_iter_value (struct cdc_treap_iter *it)
	Returns an item's value. More...
static struct cdc_pair	cdc_treap_iter_key_value (struct cdc_treap_iter *it)
	Returns a pair, where first - key, second - value. More...
static bool	cdc_treap_iter_is_eq (struct cdc_treap_iter *it1, struct cdc_treap_iter *it2)
	Returns false if the iterator |it1| equal to the iterator |it2|, otherwise returns false. More...

Detailed Description

The cdc_treap is a struct and functions that provide a cartesion tree.

Author

Maksim Andrianov maksi.nosp@m.mand.nosp@m.riano.nosp@m.v1@y.nosp@m.andex.nosp@m..ru