C Container Collection (CCC)
Loading...
Searching...
No Matches
handle_ordered_map.h
Go to the documentation of this file.
1
47#ifndef CCC_HANDLE_ORDERED_MAP_H
48#define CCC_HANDLE_ORDERED_MAP_H
49
51#include <stddef.h>
54#include "impl/impl_handle_ordered_map.h"
55#include "types.h"
56
67typedef struct ccc_homap ccc_handle_ordered_map;
68
76typedef struct ccc_homap_elem ccc_homap_elem;
77
82typedef union ccc_homap_handle ccc_homap_handle;
83
100#define ccc_hom_init(mem_ptr, om_elem_field, key_elem_field, key_cmp, \
101 alloc_fn, aux, capacity) \
102 ccc_impl_hom_init(mem_ptr, om_elem_field, key_elem_field, key_cmp, \
103 alloc_fn, aux, capacity)
104
187ccc_result ccc_hom_copy(ccc_handle_ordered_map *dst,
188 ccc_handle_ordered_map const *src,
189 ccc_any_alloc_fn *fn);
190
208ccc_result ccc_hom_reserve(ccc_handle_ordered_map *hom, size_t to_add,
209 ccc_any_alloc_fn *fn);
210
228[[nodiscard]] void *ccc_hom_at(ccc_handle_ordered_map const *h, ccc_handle_i i);
229
236#define ccc_hom_as(handle_ordered_map_ptr, type_name, handle_i...) \
237 ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle_i)
238
244[[nodiscard]] ccc_tribool ccc_hom_contains(ccc_handle_ordered_map *hom,
245 void const *key);
246
251[[nodiscard]] ccc_handle_i ccc_hom_get_key_val(ccc_handle_ordered_map *hom,
252 void const *key);
253
271[[nodiscard]] ccc_handle ccc_hom_swap_handle(ccc_handle_ordered_map *hom,
272 ccc_homap_elem *out_handle);
273
285#define ccc_hom_swap_handle_r(handle_ordered_map_ptr, out_handle_ptr) \
286 &(ccc_handle) \
287 { \
288 ccc_hom_swap_handle((handle_ordered_map_ptr), (out_handle_ptr)).impl \
289 }
290
298[[nodiscard]] ccc_handle ccc_hom_try_insert(ccc_handle_ordered_map *hom,
299 ccc_homap_elem *key_val_handle);
300
308#define ccc_hom_try_insert_r(handle_ordered_map_ptr, key_val_handle_ptr) \
309 &(ccc_handle) \
310 { \
311 ccc_hom_try_insert((handle_ordered_map_ptr), (key_val_handle_ptr)) \
312 .impl \
313 }
314
327#define ccc_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value...) \
328 &(ccc_handle) \
329 { \
330 ccc_impl_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value) \
331 }
332
341[[nodiscard]] ccc_handle
342ccc_hom_insert_or_assign(ccc_handle_ordered_map *hom,
343 ccc_homap_elem *key_val_handle);
344
357#define ccc_hom_insert_or_assign_w(handle_ordered_map_ptr, key, lazy_value...) \
358 &(ccc_handle) \
359 { \
360 ccc_impl_hom_insert_or_assign_w(handle_ordered_map_ptr, key, \
361 lazy_value) \
362 }
363
374[[nodiscard]] ccc_handle ccc_hom_remove(ccc_handle_ordered_map *hom,
375 ccc_homap_elem *out_handle);
376
387#define ccc_hom_remove_r(handle_ordered_map_ptr, out_handle_ptr) \
388 &(ccc_handle) \
389 { \
390 ccc_hom_remove((handle_ordered_map_ptr), (out_handle_ptr)).impl \
391 }
392
408[[nodiscard]] ccc_homap_handle ccc_hom_handle(ccc_handle_ordered_map *hom,
409 void const *key);
410
426#define ccc_hom_handle_r(handle_ordered_map_ptr, key_ptr) \
427 &(ccc_homap_handle) \
428 { \
429 ccc_hom_handle((handle_ordered_map_ptr), (key_ptr)).impl \
430 }
431
441[[nodiscard]] ccc_homap_handle *ccc_hom_and_modify(ccc_homap_handle *h,
442 ccc_any_type_update_fn *fn);
443
452[[nodiscard]] ccc_homap_handle *
453ccc_hom_and_modify_aux(ccc_homap_handle *h, ccc_any_type_update_fn *fn,
454 void *aux);
455
482#define ccc_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, \
483 closure_over_T...) \
484 &(ccc_homap_handle) \
485 { \
486 ccc_impl_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, \
487 closure_over_T) \
488 }
489
501[[nodiscard]] ccc_handle_i ccc_hom_or_insert(ccc_homap_handle const *h,
502 ccc_homap_elem *elem);
503
515#define ccc_hom_or_insert_w(handle_ordered_map_handle_ptr, lazy_key_value...) \
516 ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, lazy_key_value)
517
525[[nodiscard]] ccc_handle_i ccc_hom_insert_handle(ccc_homap_handle const *h,
526 ccc_homap_elem *elem);
527
533#define ccc_hom_insert_handle_w(handle_ordered_map_handle_ptr, \
534 lazy_key_value...) \
535 ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, lazy_key_value)
536
542[[nodiscard]] ccc_handle ccc_hom_remove_handle(ccc_homap_handle *h);
543
549#define ccc_hom_remove_handle_r(handle_ordered_map_handle_ptr) \
550 &(ccc_handle) \
551 { \
552 ccc_hom_remove_handle((handle_ordered_map_handle_ptr)).impl \
553 }
554
558[[nodiscard]] ccc_handle_i ccc_hom_unwrap(ccc_homap_handle const *h);
559
563[[nodiscard]] ccc_tribool ccc_hom_occupied(ccc_homap_handle const *h);
564
570[[nodiscard]] ccc_tribool ccc_hom_insert_error(ccc_homap_handle const *h);
571
581[[nodiscard]] ccc_handle_status
582ccc_hom_handle_status(ccc_homap_handle const *h);
583
610[[nodiscard]] ccc_range ccc_hom_equal_range(ccc_handle_ordered_map *hom,
611 void const *begin_key,
612 void const *end_key);
613
620#define ccc_hom_equal_range_r(handle_ordered_map_ptr, \
621 begin_and_end_key_ptrs...) \
622 &(ccc_range) \
623 { \
624 ccc_hom_equal_range(handle_ordered_map_ptr, begin_and_end_key_ptrs) \
625 .impl \
626 }
627
648[[nodiscard]] ccc_rrange ccc_hom_equal_rrange(ccc_handle_ordered_map *hom,
649 void const *rbegin_key,
650 void const *rend_key);
651
659#define ccc_hom_equal_rrange_r(handle_ordered_map_ptr, \
660 rbegin_and_rend_key_ptrs...) \
661 &(ccc_rrange) \
662 { \
663 ccc_hom_equal_rrange(handle_ordered_map_ptr, rbegin_and_rend_key_ptrs) \
664 .impl \
665 }
666
671[[nodiscard]] void *ccc_hom_begin(ccc_handle_ordered_map const *hom);
672
677[[nodiscard]] void *ccc_hom_rbegin(ccc_handle_ordered_map const *hom);
678
684[[nodiscard]] void *ccc_hom_next(ccc_handle_ordered_map const *hom,
685 ccc_homap_elem const *iter_handle);
686
693[[nodiscard]] void *ccc_hom_rnext(ccc_handle_ordered_map const *hom,
694 ccc_homap_elem const *iter_handle);
695
699[[nodiscard]] void *ccc_hom_end(ccc_handle_ordered_map const *hom);
700
704[[nodiscard]] void *ccc_hom_rend(ccc_handle_ordered_map const *hom);
705
719ccc_result ccc_hom_clear(ccc_handle_ordered_map *hom,
720 ccc_any_type_destructor_fn *fn);
721
732ccc_result ccc_hom_clear_and_free(ccc_handle_ordered_map *hom,
733 ccc_any_type_destructor_fn *fn);
734
761ccc_result
762ccc_hom_clear_and_free_reserve(ccc_handle_ordered_map *hom,
763 ccc_any_type_destructor_fn *destructor,
764 ccc_any_alloc_fn *alloc);
765
775[[nodiscard]] ccc_ucount ccc_hom_size(ccc_handle_ordered_map const *hom);
776
780[[nodiscard]] ccc_ucount ccc_hom_capacity(ccc_handle_ordered_map const *hom);
781
791[[nodiscard]] void *ccc_hom_data(ccc_handle_ordered_map const *hom);
792
796[[nodiscard]] ccc_tribool ccc_hom_is_empty(ccc_handle_ordered_map const *hom);
797
802[[nodiscard]] ccc_tribool ccc_hom_validate(ccc_handle_ordered_map const *hom);
803
808#ifdef HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC
809typedef ccc_handle_ordered_map handle_ordered_map;
810typedef ccc_homap_elem homap_elem;
811typedef ccc_homap_handle homap_handle;
812# define hom_at(args...) ccc_hom_at(args)
813# define hom_as(args...) ccc_hom_as(args)
814# define hom_and_modify_w(args...) ccc_hom_and_modify_w(args)
815# define hom_or_insert_w(args...) ccc_hom_or_insert_w(args)
816# define hom_insert_handle_w(args...) ccc_hom_insert_handle_w(args)
817# define hom_try_insert_w(args...) ccc_hom_try_insert_w(args)
818# define hom_insert_or_assign_w(args...) ccc_hom_insert_or_assign_w(args)
819# define hom_init(args...) ccc_hom_init(args)
820# define hom_copy(args...) ccc_hom_copy(args)
821# define hom_reserve(args...) ccc_hom_reserve(args)
822# define hom_contains(args...) ccc_hom_contains(args)
823# define hom_get_key_val(args...) ccc_hom_get_key_val(args)
824# define hom_swap_handle_r(args...) ccc_hom_swap_handle_r(args)
825# define hom_try_insert_r(args...) ccc_hom_try_insert_r(args)
826# define hom_remove_r(args...) ccc_hom_remove_r(args)
827# define hom_remove_handle_r(args...) ccc_hom_remove_handle_r(args)
828# define hom_swap_handle(args...) ccc_hom_swap_handle(args)
829# define hom_try_insert(args...) ccc_hom_try_insert(args)
830# define hom_insert_or_assign(args...) ccc_hom_insert_or_assign(args)
831# define hom_remove(args...) ccc_hom_remove(args)
832# define hom_remove_handle(args...) ccc_hom_remove_handle(args)
833# define hom_handle_r(args...) ccc_hom_handle_r(args)
834# define hom_handle(args...) ccc_hom_handle(args)
835# define hom_and_modify(args...) ccc_hom_and_modify(args)
836# define hom_and_modify_aux(args...) ccc_hom_and_modify_aux(args)
837# define hom_or_insert(args...) ccc_hom_or_insert(args)
838# define hom_insert_handle(args...) ccc_hom_insert_handle(args)
839# define hom_unwrap(args...) ccc_hom_unwrap(args)
840# define hom_insert_error(args...) ccc_hom_insert_error(args)
841# define hom_occupied(args...) ccc_hom_occupied(args)
842# define hom_clear(args...) ccc_hom_clear(args)
843# define hom_clear_and_free(args...) ccc_hom_clear_and_free(args)
844# define hom_clear_and_free_reserve(args...) \
845 ccc_hom_clear_and_free_reserve(args)
846# define hom_begin(args...) ccc_hom_begin(args)
847# define hom_rbegin(args...) ccc_hom_rbegin(args)
848# define hom_end(args...) ccc_hom_end(args)
849# define hom_rend(args...) ccc_hom_rend(args)
850# define hom_next(args...) ccc_hom_next(args)
851# define hom_rnext(args...) ccc_hom_rnext(args)
852# define hom_data(args...) ccc_hom_data(args)
853# define hom_size(args...) ccc_hom_size(args)
854# define hom_is_empty(args...) ccc_hom_is_empty(args)
855# define hom_validate(args...) ccc_hom_validate(args)
856#endif /* HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC */
857
858#endif /* CCC_HANDLE_ORDERED_MAP_H */
ccc_hom_data
void * ccc_hom_data(ccc_handle_ordered_map const *hom)
Return a reference to the base of backing array. O(1).
ccc_hom_is_empty
ccc_tribool ccc_hom_is_empty(ccc_handle_ordered_map const *hom)
Returns the size status of the map.
ccc_hom_equal_rrange
ccc_rrange ccc_hom_equal_rrange(ccc_handle_ordered_map *hom, void const *rbegin_key, void const *rend_key)
Return an iterable rrange of values from [rbegin_key, end_key). Amortized O(lg N).
ccc_hom_rbegin
void * ccc_hom_rbegin(ccc_handle_ordered_map const *hom)
Return the start of a reverse inorder traversal of the map. Amortized O(lg N).
ccc_homap_handle
union ccc_homap_handle ccc_homap_handle
A container specific handle used to implement the Handle Interface.
Definition: handle_ordered_map.h:82
ccc_hom_and_modify
ccc_homap_handle * ccc_hom_and_modify(ccc_homap_handle *h, ccc_any_type_update_fn *fn)
Modifies the provided handle if it is Occupied.
ccc_hom_insert_handle
ccc_handle_i ccc_hom_insert_handle(ccc_homap_handle const *h, ccc_homap_elem *elem)
Inserts the provided handle invariantly.
ccc_hom_get_key_val
ccc_handle_i ccc_hom_get_key_val(ccc_handle_ordered_map *hom, void const *key)
Returns a reference into the map at handle key.
ccc_hom_copy
ccc_result ccc_hom_copy(ccc_handle_ordered_map *dst, ccc_handle_ordered_map const *src, ccc_any_alloc_fn *fn)
Copy the map at source to destination.
ccc_homap_elem
struct ccc_homap_elem ccc_homap_elem
The intrusive element for the user defined type being stored in the map.
Definition: handle_ordered_map.h:76
ccc_hom_clear_and_free_reserve
ccc_result ccc_hom_clear_and_free_reserve(ccc_handle_ordered_map *hom, ccc_any_type_destructor_fn *destructor, ccc_any_alloc_fn *alloc)
Frees all slots in the hom and frees the underlying buffer that was previously dynamically reserved w...
ccc_hom_capacity
ccc_ucount ccc_hom_capacity(ccc_handle_ordered_map const *hom)
Returns the capacity of the map representing total possible slots.
ccc_hom_handle_status
ccc_handle_status ccc_hom_handle_status(ccc_homap_handle const *h)
Obtain the handle status from a container handle.
ccc_hom_begin
void * ccc_hom_begin(ccc_handle_ordered_map const *hom)
Return the start of an inorder traversal of the map. Amortized O(lg N).
ccc_hom_unwrap
ccc_handle_i ccc_hom_unwrap(ccc_homap_handle const *h)
Unwraps the provided handle to obtain a view into the map element.
ccc_handle_ordered_map
struct ccc_homap ccc_handle_ordered_map
A self-optimizing data structure offering amortized O(lg N) search, insert, and erase.
Definition: handle_ordered_map.h:67
ccc_hom_rend
void * ccc_hom_rend(ccc_handle_ordered_map const *hom)
Return the rend of a reverse inorder traversal of the map. O(1).
ccc_hom_or_insert
ccc_handle_i ccc_hom_or_insert(ccc_homap_handle const *h, ccc_homap_elem *elem)
Inserts the struct with handle elem if the handle is Vacant.
ccc_hom_validate
ccc_tribool ccc_hom_validate(ccc_handle_ordered_map const *hom)
Validation of invariants for the map.
ccc_hom_at
void * ccc_hom_at(ccc_handle_ordered_map const *h, ccc_handle_i i)
Returns a reference to the user data at the provided handle.
ccc_hom_and_modify_aux
ccc_homap_handle * ccc_hom_and_modify_aux(ccc_homap_handle *h, ccc_any_type_update_fn *fn, void *aux)
Modifies the provided handle if it is Occupied.
ccc_hom_swap_handle
ccc_handle ccc_hom_swap_handle(ccc_handle_ordered_map *hom, ccc_homap_elem *out_handle)
Invariantly inserts the key value wrapping key_val_handle.
ccc_hom_handle
ccc_homap_handle ccc_hom_handle(ccc_handle_ordered_map *hom, void const *key)
Obtains a handle for the provided key in the map for future use.
ccc_hom_end
void * ccc_hom_end(ccc_handle_ordered_map const *hom)
Return the end of an inorder traversal of the map. O(1).
ccc_hom_next
void * ccc_hom_next(ccc_handle_ordered_map const *hom, ccc_homap_elem const *iter_handle)
Return the next element in an inorder traversal of the map. O(1).
ccc_hom_remove
ccc_handle ccc_hom_remove(ccc_handle_ordered_map *hom, ccc_homap_elem *out_handle)
Removes the key value in the map storing the old value, if present, in the struct containing out_hand...
ccc_hom_remove_handle
ccc_handle ccc_hom_remove_handle(ccc_homap_handle *h)
Remove the handle from the map if Occupied.
ccc_hom_try_insert
ccc_handle ccc_hom_try_insert(ccc_handle_ordered_map *hom, ccc_homap_elem *key_val_handle)
Attempts to insert the key value wrapping key_val_handle.
ccc_hom_insert_error
ccc_tribool ccc_hom_insert_error(ccc_homap_handle const *h)
Provides the status of the handle should an insertion follow.
ccc_hom_clear
ccc_result ccc_hom_clear(ccc_handle_ordered_map *hom, ccc_any_type_destructor_fn *fn)
Frees all slots in the map for use without affecting capacity.
ccc_hom_clear_and_free
ccc_result ccc_hom_clear_and_free(ccc_handle_ordered_map *hom, ccc_any_type_destructor_fn *fn)
Frees all slots in the map and frees the underlying buffer.
ccc_hom_equal_range
ccc_range ccc_hom_equal_range(ccc_handle_ordered_map *hom, void const *begin_key, void const *end_key)
Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).
ccc_hom_insert_or_assign
ccc_handle ccc_hom_insert_or_assign(ccc_handle_ordered_map *hom, ccc_homap_elem *key_val_handle)
Invariantly inserts or overwrites a user struct into the map.
ccc_hom_reserve
ccc_result ccc_hom_reserve(ccc_handle_ordered_map *hom, size_t to_add, ccc_any_alloc_fn *fn)
Reserves space for at least to_add more elements.
ccc_hom_size
ccc_ucount ccc_hom_size(ccc_handle_ordered_map const *hom)
Returns the size of the map representing active slots.
ccc_hom_occupied
ccc_tribool ccc_hom_occupied(ccc_homap_handle const *h)
Returns the Vacant or Occupied status of the handle.
ccc_hom_contains
ccc_tribool ccc_hom_contains(ccc_handle_ordered_map *hom, void const *key)
Searches the map for the presence of key.
ccc_hom_rnext
void * ccc_hom_rnext(ccc_handle_ordered_map const *hom, ccc_homap_elem const *iter_handle)
Return the rnext element in a reverse inorder traversal of the map. O(1).
ccc_ucount
A type for returning an unsigned integer from a container for counting. Intended to count sizes,...
Definition: types.h:187
ccc_handle
#define ccc_handle(container_ptr, key_ptr...)
Obtain a container specific handle for the handle Interface.
Definition: traits.h:150
types.h
The C Container Collection Fundamental Types.
ccc_handle_i
size_t ccc_handle_i
A stable index to user data in a container that uses a flat array as the underlying storage method.
Definition: types.h:93
ccc_any_alloc_fn
void * ccc_any_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:312
ccc_handle_status
enum ccc_entry_status ccc_handle_status
The status monitoring and handle state once it is obtained.
Definition: types.h:103
ccc_result
ccc_result
A result of actions on containers.
Definition: types.h:132
ccc_range
union ccc_range ccc_range
The result of a range query on iterable containers.
Definition: types.h:44
ccc_rrange
union ccc_rrange ccc_rrange
The result of a rrange query on iterable containers.
Definition: types.h:52
ccc_tribool
ccc_tribool
A three state boolean to allow for an error state. Error is -1, False is 0, and True is 1.
Definition: types.h:117
ccc_any_type_destructor_fn
void ccc_any_type_destructor_fn(ccc_any_type)
A callback function for destroying an element in the container.
Definition: types.h:347
ccc_any_type_update_fn
void ccc_any_type_update_fn(ccc_any_type)
A callback function for modifying an element in the container.
Definition: types.h:329