C Container Collection (CCC)
Loading...
Searching...
No Matches
realtime_ordered_map.h
Go to the documentation of this file.
1
32#ifndef CCC_REALTIME_ORDERED_MAP_H
33#define CCC_REALTIME_ORDERED_MAP_H
34
36#include <stddef.h>
39#include "impl/impl_realtime_ordered_map.h"
40#include "types.h"
41
52typedef struct ccc_romap ccc_realtime_ordered_map;
53
63typedef struct ccc_romap_elem ccc_romap_elem;
64
69typedef union ccc_romap_entry ccc_romap_entry;
70
88#define ccc_rom_init(rom_name, struct_name, rom_elem_field, key_elem_field, \
89 key_cmp_fn, alloc_fn, aux_data) \
90 ccc_impl_rom_init(rom_name, struct_name, rom_elem_field, key_elem_field, \
91 key_cmp_fn, alloc_fn, aux_data)
92
104[[nodiscard]] ccc_tribool ccc_rom_contains(ccc_realtime_ordered_map const *rom,
105 void const *key);
106
111[[nodiscard]] void *ccc_rom_get_key_val(ccc_realtime_ordered_map const *rom,
112 void const *key);
113
133[[nodiscard]] ccc_entry ccc_rom_swap_entry(ccc_realtime_ordered_map *rom,
134 ccc_romap_elem *key_val_handle,
135 ccc_romap_elem *tmp);
136
150#define ccc_rom_swap_entry_r(realtime_ordered_map_ptr, key_val_handle_ptr, \
151 tmp_ptr) \
152 &(ccc_entry) \
153 { \
154 ccc_rom_swap_entry((realtime_ordered_map_ptr), (key_val_handle_ptr), \
155 (tmp_ptr)) \
156 .impl \
157 }
158
166[[nodiscard]] ccc_entry ccc_rom_try_insert(ccc_realtime_ordered_map *rom,
167 ccc_romap_elem *key_val_handle);
168
177#define ccc_rom_try_insert_r(realtime_ordered_map_ptr, key_val_handle_ptr) \
178 &(ccc_entry) \
179 { \
180 ccc_rom_try_insert((realtime_ordered_map_ptr), (key_val_handle_ptr)) \
181 .impl \
182 }
183
196#define ccc_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value...) \
197 &(ccc_entry) \
198 { \
199 ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value) \
200 }
201
210[[nodiscard]] ccc_entry
211ccc_rom_insert_or_assign(ccc_realtime_ordered_map *rom,
212 ccc_romap_elem *key_val_handle);
213
226#define ccc_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
227 lazy_value...) \
228 &(ccc_entry) \
229 { \
230 ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
231 lazy_value) \
232 }
233
249[[nodiscard]] ccc_entry ccc_rom_remove(ccc_realtime_ordered_map *rom,
250 ccc_romap_elem *out_handle);
251
267#define ccc_rom_remove_r(realtime_ordered_map_ptr, out_handle_ptr) \
268 &(ccc_entry) \
269 { \
270 ccc_rom_remove((realtime_ordered_map_ptr), (out_handle_ptr)).impl \
271 }
272
287[[nodiscard]] ccc_romap_entry ccc_rom_entry(ccc_realtime_ordered_map const *rom,
288 void const *key);
289
305#define ccc_rom_entry_r(realtime_ordered_map_ptr, key_ptr) \
306 &(ccc_romap_entry) \
307 { \
308 ccc_rom_entry((realtime_ordered_map_ptr), (key_ptr)).impl \
309 }
310
320[[nodiscard]] ccc_romap_entry *ccc_rom_and_modify(ccc_romap_entry *e,
321 ccc_any_type_update_fn *fn);
322
331[[nodiscard]] ccc_romap_entry *
332ccc_rom_and_modify_aux(ccc_romap_entry *e, ccc_any_type_update_fn *fn,
333 void *aux);
334
361#define ccc_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
362 closure_over_T...) \
363 &(ccc_romap_entry) \
364 { \
365 ccc_impl_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
366 closure_over_T) \
367 }
368
380[[nodiscard]] void *ccc_rom_or_insert(ccc_romap_entry const *e,
381 ccc_romap_elem *elem);
382
394#define ccc_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value...) \
395 ccc_impl_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value)
396
404[[nodiscard]] void *ccc_rom_insert_entry(ccc_romap_entry const *e,
405 ccc_romap_elem *elem);
406
412#define ccc_rom_insert_entry_w(realtime_ordered_map_entry_ptr, \
413 lazy_key_value...) \
414 ccc_impl_rom_insert_entry_w(realtime_ordered_map_entry_ptr, lazy_key_value)
415
426[[nodiscard]] ccc_entry ccc_rom_remove_entry(ccc_romap_entry const *e);
427
438#define ccc_rom_remove_entry_r(realtime_ordered_map_entry_ptr) \
439 &(ccc_entry) \
440 { \
441 ccc_rom_remove_entry((realtime_ordered_map_entry_ptr)).impl \
442 }
443
447[[nodiscard]] void *ccc_rom_unwrap(ccc_romap_entry const *e);
448
452[[nodiscard]] ccc_tribool ccc_rom_insert_error(ccc_romap_entry const *e);
453
459[[nodiscard]] ccc_tribool ccc_rom_occupied(ccc_romap_entry const *e);
460
470[[nodiscard]] ccc_entry_status ccc_rom_entry_status(ccc_romap_entry const *e);
471
492ccc_result ccc_rom_clear(ccc_realtime_ordered_map *rom,
493 ccc_any_type_destructor_fn *destructor);
494
519[[nodiscard]] ccc_range ccc_rom_equal_range(ccc_realtime_ordered_map const *rom,
520 void const *begin_key,
521 void const *end_key);
522
530#define ccc_rom_equal_range_r(realtime_ordered_map_ptr, \
531 begin_and_end_key_ptrs...) \
532 &(ccc_range) \
533 { \
534 ccc_rom_equal_range((realtime_ordered_map_ptr), \
535 (begin_and_end_key_ptrs)) \
536 .impl \
537 }
538
557[[nodiscard]] ccc_rrange
558ccc_rom_equal_rrange(ccc_realtime_ordered_map const *rom,
559 void const *rbegin_key, void const *rend_key);
560
568#define ccc_rom_equal_rrange_r(realtime_ordered_map_ptr, \
569 rbegin_and_rend_key_ptrs...) \
570 &(ccc_rrange) \
571 { \
572 ccc_rom_equal_rrange((realtime_ordered_map_ptr), \
573 (rbegin_and_rend_key_ptrs)) \
574 .impl \
575 }
576
581[[nodiscard]] void *ccc_rom_begin(ccc_realtime_ordered_map const *rom);
582
587[[nodiscard]] void *ccc_rom_rbegin(ccc_realtime_ordered_map const *rom);
588
594[[nodiscard]] void *ccc_rom_next(ccc_realtime_ordered_map const *rom,
595 ccc_romap_elem const *iter_handle);
596
603[[nodiscard]] void *ccc_rom_rnext(ccc_realtime_ordered_map const *rom,
604 ccc_romap_elem const *iter_handle);
605
609[[nodiscard]] void *ccc_rom_end(ccc_realtime_ordered_map const *rom);
610
614[[nodiscard]] void *ccc_rom_rend(ccc_realtime_ordered_map const *rom);
615
625[[nodiscard]] ccc_ucount ccc_rom_size(ccc_realtime_ordered_map const *rom);
626
630[[nodiscard]] ccc_tribool ccc_rom_is_empty(ccc_realtime_ordered_map const *rom);
631
636[[nodiscard]] ccc_tribool ccc_rom_validate(ccc_realtime_ordered_map const *rom);
637
642#ifdef REALTIME_ORDERED_MAP_USING_NAMESPACE_CCC
643typedef ccc_romap_elem romap_elem;
644typedef ccc_realtime_ordered_map realtime_ordered_map;
645typedef ccc_romap_entry romap_entry;
646# define rom_init(args...) ccc_rom_init(args)
647# define rom_and_modify_w(args...) ccc_rom_and_modify_w(args)
648# define rom_or_insert_w(args...) ccc_rom_or_insert_w(args)
649# define rom_insert_entry_w(args...) ccc_rom_insert_entry_w(args)
650# define rom_try_insert_w(args...) ccc_rom_try_insert_w(args)
651# define rom_insert_or_assign_w(args...) ccc_rom_insert_or_assign_w(args)
652# define rom_swap_entry_r(args...) ccc_rom_swap_entry_r(args)
653# define rom_remove_r(args...) ccc_rom_remove_r(args)
654# define rom_remove_entry_r(args...) ccc_rom_remove_entry_r(args)
655# define rom_entry_r(args...) ccc_rom_entry_r(args)
656# define rom_and_modify_r(args...) ccc_rom_and_modify_r(args)
657# define rom_and_modify_aux_r(args...) ccc_rom_and_modify_aux_r(args)
658# define rom_contains(args...) ccc_rom_contains(args)
659# define rom_get_key_val(args...) ccc_rom_get_key_val(args)
660# define rom_get_mut(args...) ccc_rom_get_mut(args)
661# define rom_swap_entry(args...) ccc_rom_swap_entry(args)
662# define rom_remove(args...) ccc_rom_remove(args)
663# define rom_entry(args...) ccc_rom_entry(args)
664# define rom_remove_entry(args...) ccc_rom_remove_entry(args)
665# define rom_or_insert(args...) ccc_rom_or_insert(args)
666# define rom_insert_entry(args...) ccc_rom_insert_entry(args)
667# define rom_unwrap(args...) ccc_rom_unwrap(args)
668# define rom_unwrap_mut(args...) ccc_rom_unwrap_mut(args)
669# define rom_begin(args...) ccc_rom_begin(args)
670# define rom_next(args...) ccc_rom_next(args)
671# define rom_rbegin(args...) ccc_rom_rbegin(args)
672# define rom_rnext(args...) ccc_rom_rnext(args)
673# define rom_end(args...) ccc_rom_end(args)
674# define rom_rend(args...) ccc_rom_rend(args)
675# define rom_size(args...) ccc_rom_size(args)
676# define rom_is_empty(args...) ccc_rom_is_empty(args)
677# define rom_clear(args...) ccc_rom_clear(args)
678# define rom_validate(args...) ccc_rom_validate(args)
679#endif
680
681#endif /* CCC_REALTIME_ORDERED_MAP_H */
ccc_rom_size
ccc_ucount ccc_rom_size(ccc_realtime_ordered_map const *rom)
Returns the size of the map.
ccc_realtime_ordered_map
struct ccc_romap ccc_realtime_ordered_map
A container for amortized O(lg N) search, insert, erase, ranges, and pointer stability.
Definition: realtime_ordered_map.h:52
ccc_rom_entry
ccc_romap_entry ccc_rom_entry(ccc_realtime_ordered_map const *rom, void const *key)
Obtains an entry for the provided key in the map for future use.
ccc_rom_remove_entry
ccc_entry ccc_rom_remove_entry(ccc_romap_entry const *e)
Remove the entry from the map if Occupied.
ccc_rom_swap_entry
ccc_entry ccc_rom_swap_entry(ccc_realtime_ordered_map *rom, ccc_romap_elem *key_val_handle, ccc_romap_elem *tmp)
Invariantly inserts the key value wrapping key_val_handle.
ccc_rom_rbegin
void * ccc_rom_rbegin(ccc_realtime_ordered_map const *rom)
Return the start of a reverse inorder traversal of the map. Amortized O(lg N).
ccc_rom_equal_range
ccc_range ccc_rom_equal_range(ccc_realtime_ordered_map const *rom, void const *begin_key, void const *end_key)
Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).
ccc_rom_and_modify
ccc_romap_entry * ccc_rom_and_modify(ccc_romap_entry *e, ccc_any_type_update_fn *fn)
Modifies the provided entry if it is Occupied.
ccc_romap_entry
union ccc_romap_entry ccc_romap_entry
A container specific entry used to implement the Entry Interface.
Definition: realtime_ordered_map.h:69
ccc_rom_validate
ccc_tribool ccc_rom_validate(ccc_realtime_ordered_map const *rom)
Validation of invariants for the map.
ccc_rom_contains
ccc_tribool ccc_rom_contains(ccc_realtime_ordered_map const *rom, void const *key)
Searches the map for the presence of key.
ccc_rom_unwrap
void * ccc_rom_unwrap(ccc_romap_entry const *e)
Unwraps the provided entry to obtain a view into the map element.
ccc_rom_is_empty
ccc_tribool ccc_rom_is_empty(ccc_realtime_ordered_map const *rom)
Returns the size status of the map.
ccc_rom_rend
void * ccc_rom_rend(ccc_realtime_ordered_map const *rom)
Return the rend of a reverse inorder traversal of the map. O(1).
ccc_rom_end
void * ccc_rom_end(ccc_realtime_ordered_map const *rom)
Return the end of an inorder traversal of the map. O(1).
ccc_rom_try_insert
ccc_entry ccc_rom_try_insert(ccc_realtime_ordered_map *rom, ccc_romap_elem *key_val_handle)
Attempts to insert the key value wrapping key_val_handle.
ccc_rom_get_key_val
void * ccc_rom_get_key_val(ccc_realtime_ordered_map const *rom, void const *key)
Returns a reference into the map at entry key.
ccc_rom_insert_entry
void * ccc_rom_insert_entry(ccc_romap_entry const *e, ccc_romap_elem *elem)
Inserts the provided entry invariantly.
ccc_rom_begin
void * ccc_rom_begin(ccc_realtime_ordered_map const *rom)
Return the start of an inorder traversal of the map. Amortized O(lg N).
ccc_rom_clear
ccc_result ccc_rom_clear(ccc_realtime_ordered_map *rom, ccc_any_type_destructor_fn *destructor)
Pops every element from the map calling destructor if destructor is non-NULL. O(N).
ccc_rom_equal_rrange
ccc_rrange ccc_rom_equal_rrange(ccc_realtime_ordered_map const *rom, void const *rbegin_key, void const *rend_key)
Return an iterable rrange of values from [begin_key, end_key). Amortized O(lg N).
ccc_romap_elem
struct ccc_romap_elem ccc_romap_elem
The intrusive element of the user defined struct being stored in the map.
Definition: realtime_ordered_map.h:63
ccc_rom_insert_or_assign
ccc_entry ccc_rom_insert_or_assign(ccc_realtime_ordered_map *rom, ccc_romap_elem *key_val_handle)
Invariantly inserts or overwrites a user struct into the map.
ccc_rom_insert_error
ccc_tribool ccc_rom_insert_error(ccc_romap_entry const *e)
Returns the Vacant or Occupied status of the entry.
ccc_rom_and_modify_aux
ccc_romap_entry * ccc_rom_and_modify_aux(ccc_romap_entry *e, ccc_any_type_update_fn *fn, void *aux)
Modifies the provided entry if it is Occupied.
ccc_rom_entry_status
ccc_entry_status ccc_rom_entry_status(ccc_romap_entry const *e)
Obtain the entry status from a container entry.
ccc_rom_or_insert
void * ccc_rom_or_insert(ccc_romap_entry const *e, ccc_romap_elem *elem)
Inserts the struct with handle elem if the entry is Vacant.
ccc_rom_rnext
void * ccc_rom_rnext(ccc_realtime_ordered_map const *rom, ccc_romap_elem const *iter_handle)
Return the rnext element in a reverse inorder traversal of the map. O(1).
ccc_rom_occupied
ccc_tribool ccc_rom_occupied(ccc_romap_entry const *e)
Provides the status of the entry should an insertion follow.
ccc_rom_remove
ccc_entry ccc_rom_remove(ccc_realtime_ordered_map *rom, ccc_romap_elem *out_handle)
Removes the key value in the map storing the old value, if present, in the struct containing out_hand...
ccc_rom_next
void * ccc_rom_next(ccc_realtime_ordered_map const *rom, ccc_romap_elem const *iter_handle)
Return the next element in an 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_entry
#define ccc_entry(container_ptr, key_ptr...)
Obtain a container specific entry for the Entry Interface.
Definition: traits.h:141
types.h
The C Container Collection Fundamental Types.
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