C Container Collection (CCC)
Loading...
Searching...
No Matches
tree_map.h
Go to the documentation of this file.
1
32#ifndef CCC_TREE_MAP_H
33#define CCC_TREE_MAP_H
34
36#include <stddef.h>
39#include "private/private_tree_map.h"
40#include "types.h"
41
52typedef struct CCC_Tree_map CCC_Tree_map;
53
63typedef struct CCC_Tree_map_node CCC_Tree_map_node;
64
69typedef struct CCC_Tree_map_entry CCC_Tree_map_entry;
70
83#define CCC_tree_map_default( \
84 type_name, type_intruder_field_name, type_key_field_name, comparator... \
85) \
86 CCC_private_tree_map_default( \
87 type_name, type_intruder_field_name, type_key_field_name, comparator \
88 )
89
97#define CCC_tree_map_for( \
98 type_name, type_intruder_field_name, type_key_field_name, comparator... \
99) \
100 CCC_private_tree_map_for( \
101 type_name, type_intruder_field_name, type_key_field_name, comparator \
102 )
103
120#define CCC_tree_map_from( \
121 type_intruder_field_name, \
122 type_key_field_name, \
123 comparator, \
124 allocator, \
125 destructor, \
126 compound_literal_array... \
127) \
128 CCC_private_tree_map_from( \
129 type_intruder_field_name, \
130 type_key_field_name, \
131 comparator, \
132 allocator, \
133 destructor, \
134 compound_literal_array \
135 )
136
148[[nodiscard]] CCC_Tribool
149CCC_tree_map_contains(CCC_Tree_map const *map, void const *key);
150
155[[nodiscard]] void *
156CCC_tree_map_get_key_value(CCC_Tree_map const *map, void const *key);
157
178[[nodiscard]] CCC_Entry CCC_tree_map_swap_entry(
179 CCC_Tree_map *map,
180 CCC_Tree_map_node *type_intruder,
181 CCC_Tree_map_node *temp_intruder,
182 CCC_Allocator const *allocator
183);
184
201#define CCC_tree_map_swap_entry_wrap( \
202 map_pointer, \
203 type_intruder_pointer, \
204 temp_intruder_pointer, \
205 allocator_pointer... \
206) \
207 &(struct { CCC_Entry private; }){CCC_tree_map_swap_entry( \
208 (map_pointer), \
209 (type_intruder_pointer), \
210 (temp_intruder_pointer), \
211 allocator_pointer \
212 )} \
213 .private
214
223[[nodiscard]] CCC_Entry CCC_tree_map_try_insert(
224 CCC_Tree_map *map,
225 CCC_Tree_map_node *type_intruder,
226 CCC_Allocator const *allocator
227);
228
239#define CCC_tree_map_try_insert_wrap( \
240 map_pointer, type_intruder_pointer, allocator_pointer... \
241) \
242 &(struct { CCC_Entry private; }){ \
243 CCC_tree_map_try_insert( \
244 (map_pointer), (type_intruder_pointer), allocator_pointer \
245 )} \
246 .private
247
262#define CCC_tree_map_try_insert_with( \
263 map_pointer, key, allocator_pointer, type_compound_literal... \
264) \
265 &(struct { CCC_Entry private; }){ \
266 CCC_private_tree_map_try_insert_with( \
267 map_pointer, key, allocator_pointer, type_compound_literal \
268 )} \
269 .private
270
280[[nodiscard]] CCC_Entry CCC_tree_map_insert_or_assign(
281 CCC_Tree_map *map,
282 CCC_Tree_map_node *type_intruder,
283 CCC_Allocator const *allocator
284);
285
299#define CCC_tree_map_insert_or_assign_wrap( \
300 map_pointer, type_intruder_pointer, allocator_pointer... \
301) \
302 &(struct { CCC_Entry private; }){ \
303 CCC_tree_map_insert_or_assign( \
304 (map_pointer), (type_intruder_pointer), allocator_pointer \
305 )} \
306 .private
307
322#define CCC_tree_map_insert_or_assign_with( \
323 map_pointer, key, allocator_pointer, type_compound_literal... \
324) \
325 &(struct { CCC_Entry private; }){ \
326 CCC_private_tree_map_insert_or_assign_with( \
327 map_pointer, key, allocator_pointer, type_compound_literal \
328 )} \
329 .private
330
347[[nodiscard]] CCC_Entry CCC_tree_map_remove_key_value(
348 CCC_Tree_map *map,
349 CCC_Tree_map_node *output_intruder,
350 CCC_Allocator const *allocator
351);
352
370#define CCC_tree_map_remove_key_value_wrap( \
371 map_pointer, output_intruder_pointer, allocator_pointer... \
372) \
373 &(struct { CCC_Entry private; }){ \
374 CCC_tree_map_remove_key_value( \
375 (map_pointer), (output_intruder_pointer), allocator_pointer \
376 )} \
377 .private
378
393[[nodiscard]] CCC_Tree_map_entry
394CCC_tree_map_entry(CCC_Tree_map const *map, void const *key);
395
412#define CCC_tree_map_entry_wrap(map_pointer, key_pointer...) \
413 &(struct { CCC_Tree_map_entry private; }){ \
414 CCC_tree_map_entry((map_pointer), key_pointer)} \
415 .private
416
421[[nodiscard]] CCC_Tree_map_entry *CCC_tree_map_and_modify(
422 CCC_Tree_map_entry *entry, CCC_Modifier const *modifier
423);
424
460#define CCC_tree_map_and_modify_with( \
461 map_pointer, closure_parameter, closure_over_closure_parameter... \
462) \
463 &(struct { CCC_Tree_map_entry private; }){ \
464 CCC_private_tree_map_and_modify_with( \
465 map_pointer, closure_parameter, closure_over_closure_parameter \
466 )} \
467 .private
468
482[[nodiscard]] void *CCC_tree_map_or_insert(
483 CCC_Tree_map_entry const *entry,
484 CCC_Tree_map_node *type_intruder,
485 CCC_Allocator const *allocator
486);
487
500#define CCC_tree_map_or_insert_with( \
501 map_pointer, allocator_pointer, type_compound_literal... \
502) \
503 CCC_private_tree_map_or_insert_with( \
504 map_pointer, allocator_pointer, type_compound_literal \
505 )
506
515[[nodiscard]] void *CCC_tree_map_insert_entry(
516 CCC_Tree_map_entry const *entry,
517 CCC_Tree_map_node *type_intruder,
518 CCC_Allocator const *allocator
519);
520
528#define CCC_tree_map_insert_entry_with( \
529 map_pointer, allocator_pointer, type_compound_literal... \
530) \
531 CCC_private_tree_map_insert_entry_with( \
532 map_pointer, allocator_pointer, type_compound_literal \
533 )
534
546[[nodiscard]] CCC_Entry CCC_tree_map_remove_entry(
547 CCC_Tree_map_entry const *entry, CCC_Allocator const *allocator
548);
549
561#define CCC_tree_map_remove_entry_wrap(map_pointer, allocator_pointer...) \
562 &(struct { CCC_Entry private; }){ \
563 CCC_tree_map_remove_entry((map_pointer), allocator_pointer)} \
564 .private
565
569[[nodiscard]] void *CCC_tree_map_unwrap(CCC_Tree_map_entry const *entry);
570
574[[nodiscard]] CCC_Tribool
575CCC_tree_map_insert_error(CCC_Tree_map_entry const *entry);
576
582[[nodiscard]] CCC_Tribool
583CCC_tree_map_occupied(CCC_Tree_map_entry const *entry);
584
594[[nodiscard]] CCC_Entry_status
595CCC_tree_map_entry_status(CCC_Tree_map_entry const *entry);
596
614CCC_Result CCC_tree_map_clear(
615 CCC_Tree_map *map,
616 CCC_Destructor const *destructor,
617 CCC_Allocator const *allocator
618);
619
644[[nodiscard]] CCC_Range CCC_tree_map_equal_range(
645 CCC_Tree_map const *map, void const *begin_key, void const *end_key
646);
647
655#define CCC_tree_map_equal_range_wrap( \
656 map_pointer, begin_and_end_key_pointers... \
657) \
658 &(struct { CCC_Range private; }){ \
659 CCC_tree_map_equal_range((map_pointer), begin_and_end_key_pointers)} \
660 .private
661
683[[nodiscard]] CCC_Range_reverse CCC_tree_map_equal_range_reverse(
684 CCC_Tree_map const *map,
685 void const *reverse_begin_key,
686 void const *reverse_end_key
687);
688
696#define CCC_tree_map_equal_range_reverse_wrap( \
697 map_pointer, reverse_begin_and_reverse_end_key_pointers... \
698) \
699 &(struct { CCC_Range_reverse private; }){ \
700 CCC_tree_map_equal_range_reverse( \
701 (map_pointer), reverse_begin_and_reverse_end_key_pointers \
702 )} \
703 .private
704
709[[nodiscard]] void *CCC_tree_map_begin(CCC_Tree_map const *map);
710
715[[nodiscard]] void *CCC_tree_map_reverse_begin(CCC_Tree_map const *map);
716
722[[nodiscard]] void *CCC_tree_map_next(
723 CCC_Tree_map const *map, CCC_Tree_map_node const *iterator_intruder
724);
725
733[[nodiscard]] void *CCC_tree_map_reverse_next(
734 CCC_Tree_map const *map, CCC_Tree_map_node const *iterator_intruder
735);
736
740[[nodiscard]] void *CCC_tree_map_end(CCC_Tree_map const *map);
741
746[[nodiscard]] void *CCC_tree_map_reverse_end(CCC_Tree_map const *map);
747
757[[nodiscard]] CCC_Count CCC_tree_map_count(CCC_Tree_map const *map);
758
762[[nodiscard]] CCC_Tribool CCC_tree_map_is_empty(CCC_Tree_map const *map);
763
768[[nodiscard]] CCC_Tribool CCC_tree_map_validate(CCC_Tree_map const *map);
769
774#ifdef TREE_MAP_USING_NAMESPACE_CCC
775/* NOLINTBEGIN(readability-identifier-naming) */
776typedef CCC_Tree_map_node Tree_map_node;
777typedef CCC_Tree_map Tree_map;
778typedef CCC_Tree_map_entry Tree_map_entry;
779# define tree_map_default(arguments...) CCC_tree_map_default(arguments)
780# define tree_map_for(arguments...) CCC_tree_map_for(arguments)
781# define tree_map_from(arguments...) CCC_tree_map_from(arguments)
782# define tree_map_and_modify(arguments...) CCC_tree_map_and_modify(arguments)
783# define tree_map_and_modify_with(arguments...) \
784 CCC_tree_map_and_modify_with(arguments)
785# define tree_map_and_modify_wrap(arguments...) \
786 CCC_tree_map_and_modify_wrap(arguments)
787# define tree_map_or_insert_with(arguments...) \
788 CCC_tree_map_or_insert_with(arguments)
789# define tree_map_insert_entry_with(arguments...) \
790 CCC_tree_map_insert_entry_with(arguments)
791# define tree_map_try_insert(arguments...) CCC_tree_map_try_insert(arguments)
792# define tree_map_try_insert_wrap(arguments...) \
793 CCC_tree_map_try_insert_wrap(arguments)
794# define tree_map_try_insert_with(arguments...) \
795 CCC_tree_map_try_insert_with(arguments)
796# define tree_map_insert_or_assign(arguments...) \
797 CCC_tree_map_insert_or_assign(arguments)
798# define tree_map_insert_or_assign_wrap(arguments...) \
799 CCC_tree_map_insert_or_assign_wrap(arguments)
800# define tree_map_insert_or_assign_with(arguments...) \
801 CCC_tree_map_insert_or_assign_with(arguments)
802# define tree_map_swap_entry_wrap(arguments...) \
803 CCC_tree_map_swap_entry_wrap(arguments)
804# define tree_map_remove_key_value_wrap(arguments...) \
805 CCC_tree_map_remove_key_value_wrap(arguments)
806# define tree_map_remove_entry_wrap(arguments...) \
807 CCC_tree_map_remove_entry_wrap(arguments)
808# define tree_map_entry_wrap(arguments...) CCC_tree_map_entry_wrap(arguments)
809# define tree_map_contains(arguments...) CCC_tree_map_contains(arguments)
810# define tree_map_get_key_value(arguments...) \
811 CCC_tree_map_get_key_value(arguments)
812# define tree_map_get_mut(arguments...) CCC_tree_map_get_mut(arguments)
813# define tree_map_swap_entry(arguments...) CCC_tree_map_swap_entry(arguments)
814# define tree_map_remove_key_value(arguments...) \
815 CCC_tree_map_remove_key_value(arguments)
816# define tree_map_entry(arguments...) CCC_tree_map_entry(arguments)
817# define tree_map_remove_entry(arguments...) \
818 CCC_tree_map_remove_entry(arguments)
819# define tree_map_or_insert(arguments...) CCC_tree_map_or_insert(arguments)
820# define tree_map_insert_entry(arguments...) \
821 CCC_tree_map_insert_entry(arguments)
822# define tree_map_unwrap(arguments...) CCC_tree_map_unwrap(arguments)
823# define tree_map_unwrap_mut(arguments...) CCC_tree_map_unwrap_mut(arguments)
824# define tree_map_begin(arguments...) CCC_tree_map_begin(arguments)
825# define tree_map_next(arguments...) CCC_tree_map_next(arguments)
826# define tree_map_reverse_begin(arguments...) \
827 CCC_tree_map_reverse_begin(arguments)
828# define tree_map_reverse_next(arguments...) \
829 CCC_tree_map_reverse_next(arguments)
830# define tree_map_end(arguments...) CCC_tree_map_end(arguments)
831# define tree_map_reverse_end(arguments...) \
832 CCC_tree_map_reverse_end(arguments)
833# define tree_map_equal_range(arguments...) \
834 CCC_tree_map_equal_range(arguments)
835# define tree_map_equal_range_wrap(arguments...) \
836 CCC_tree_map_equal_range_wrap(arguments)
837# define tree_map_equal_range_reverse(arguments...) \
838 CCC_tree_map_equal_range_reverse(arguments)
839# define tree_map_equal_range_reverse_wrap(arguments...) \
840 CCC_tree_map_equal_range_reverse_wrap(arguments)
841# define tree_map_count(arguments...) CCC_tree_map_count(arguments)
842# define tree_map_is_empty(arguments...) CCC_tree_map_is_empty(arguments)
843# define tree_map_clear(arguments...) CCC_tree_map_clear(arguments)
844# define tree_map_validate(arguments...) CCC_tree_map_validate(arguments)
845# define tree_map_entry_status(arguments...) \
846 CCC_tree_map_entry_status(arguments)
847/* NOLINTEND(readability-identifier-naming) */
848#endif
849
850#endif /* CCC_TREE_MAP_H */
CCC_Allocator
The type passed by reference to any container function that may need to allocate memory....
Definition: types.h:376
CCC_Count
A type for returning an unsigned integer from a container for counting. Intended to count sizes,...
Definition: types.h:244
CCC_Destructor
The type passed by reference to any container function that may need to destroy elements....
Definition: types.h:464
CCC_Entry
An Occupied or Vacant position in a searchable container.
Definition: types.h:135
CCC_Modifier
The type passed by reference to any container function that may need to modify elements....
Definition: types.h:436
CCC_Range_reverse
The result of a range_reverse query on iterable containers.
Definition: types.h:55
CCC_Range
The result of a range query on iterable containers.
Definition: types.h:42
CCC_Tree_map_entry
Definition: private_tree_map.h:70
CCC_Tree_map_entry::entry
CCC_Entry entry
Definition: private_tree_map.h:78
CCC_Tree_map_entry::map
struct CCC_Tree_map * map
Definition: private_tree_map.h:72
CCC_Tree_map_node
Definition: private_tree_map.h:30
CCC_Tree_map
Definition: private_tree_map.h:51
CCC_tree_map_is_empty
CCC_Tribool CCC_tree_map_is_empty(CCC_Tree_map const *map)
Returns the size status of the map.
CCC_tree_map_validate
CCC_Tribool CCC_tree_map_validate(CCC_Tree_map const *map)
Validation of invariants for the map.
CCC_tree_map_reverse_begin
void * CCC_tree_map_reverse_begin(CCC_Tree_map const *map)
Return the start of a reverse inorder traversal of the map. Amortized O(lg N).
CCC_tree_map_equal_range
CCC_Range CCC_tree_map_equal_range(CCC_Tree_map const *map, void const *begin_key, void const *end_key)
Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).
CCC_tree_map_remove_key_value
CCC_Entry CCC_tree_map_remove_key_value(CCC_Tree_map *map, CCC_Tree_map_node *output_intruder, CCC_Allocator const *allocator)
Removes the key value in the map storing the old value, if present, in the struct containing output_i...
CCC_tree_map_entry_status
CCC_Entry_status CCC_tree_map_entry_status(CCC_Tree_map_entry const *entry)
Obtain the entry status from a container entry.
CCC_tree_map_try_insert
CCC_Entry CCC_tree_map_try_insert(CCC_Tree_map *map, CCC_Tree_map_node *type_intruder, CCC_Allocator const *allocator)
Attempts to insert the key value wrapping type_intruder.
CCC_tree_map_equal_range_reverse
CCC_Range_reverse CCC_tree_map_equal_range_reverse(CCC_Tree_map const *map, void const *reverse_begin_key, void const *reverse_end_key)
Return an iterable range_reverse of values from [begin_key, end_key). Amortized O(lg N).
CCC_tree_map_insert_error
CCC_Tribool CCC_tree_map_insert_error(CCC_Tree_map_entry const *entry)
Returns the Vacant or Occupied status of the entry.
CCC_tree_map_insert_or_assign
CCC_Entry CCC_tree_map_insert_or_assign(CCC_Tree_map *map, CCC_Tree_map_node *type_intruder, CCC_Allocator const *allocator)
Invariantly inserts or overwrites a user struct into the map.
CCC_tree_map_entry
CCC_Tree_map_entry CCC_tree_map_entry(CCC_Tree_map const *map, void const *key)
Obtains an entry for the provided key in the map for future use.
CCC_tree_map_contains
CCC_Tribool CCC_tree_map_contains(CCC_Tree_map const *map, void const *key)
Searches the map for the presence of key.
CCC_tree_map_clear
CCC_Result CCC_tree_map_clear(CCC_Tree_map *map, CCC_Destructor const *destructor, CCC_Allocator const *allocator)
Pops every element from the map calling destructor if destructor is non-NULL. O(N).
CCC_tree_map_or_insert
void * CCC_tree_map_or_insert(CCC_Tree_map_entry const *entry, CCC_Tree_map_node *type_intruder, CCC_Allocator const *allocator)
Inserts the struct with handle type_intruder if the entry is Vacant.
CCC_tree_map_next
void * CCC_tree_map_next(CCC_Tree_map const *map, CCC_Tree_map_node const *iterator_intruder)
Return the next element in an inorder traversal of the map. O(1).
CCC_tree_map_end
void * CCC_tree_map_end(CCC_Tree_map const *map)
Return the end of an inorder traversal of the map. O(1).
CCC_tree_map_insert_entry
void * CCC_tree_map_insert_entry(CCC_Tree_map_entry const *entry, CCC_Tree_map_node *type_intruder, CCC_Allocator const *allocator)
Inserts the provided entry invariantly.
CCC_tree_map_and_modify
CCC_Tree_map_entry * CCC_tree_map_and_modify(CCC_Tree_map_entry *entry, CCC_Modifier const *modifier)
Modifies the provided entry if it is Occupied.
CCC_tree_map_count
CCC_Count CCC_tree_map_count(CCC_Tree_map const *map)
Returns the count of map occupied nodes.
CCC_tree_map_swap_entry
CCC_Entry CCC_tree_map_swap_entry(CCC_Tree_map *map, CCC_Tree_map_node *type_intruder, CCC_Tree_map_node *temp_intruder, CCC_Allocator const *allocator)
Invariantly inserts the key value wrapping type_intruder.
CCC_tree_map_remove_entry
CCC_Entry CCC_tree_map_remove_entry(CCC_Tree_map_entry const *entry, CCC_Allocator const *allocator)
Remove the entry from the map if Occupied.
CCC_tree_map_reverse_next
void * CCC_tree_map_reverse_next(CCC_Tree_map const *map, CCC_Tree_map_node const *iterator_intruder)
Return the reverse_next element in a reverse inorder traversal of the map. O(1).
CCC_tree_map_reverse_end
void * CCC_tree_map_reverse_end(CCC_Tree_map const *map)
Return the reverse_end of a reverse inorder traversal of the map. O(1).
CCC_tree_map_occupied
CCC_Tribool CCC_tree_map_occupied(CCC_Tree_map_entry const *entry)
Provides the status of the entry should an insertion follow.
CCC_tree_map_unwrap
void * CCC_tree_map_unwrap(CCC_Tree_map_entry const *entry)
Unwraps the provided entry to obtain a view into the map element.
CCC_tree_map_begin
void * CCC_tree_map_begin(CCC_Tree_map const *map)
Return the start of an inorder traversal of the map. Amortized O(lg N).
CCC_tree_map_get_key_value
void * CCC_tree_map_get_key_value(CCC_Tree_map const *map, void const *key)
Returns a reference into the map at entry key.
types.h
The C Container Collection Fundamental Types.
CCC_Entry_status
CCC_Entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:112
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:178
CCC_Result
CCC_Result
A result of actions on containers.
Definition: types.h:192