C Container Collection (CCC)
Loading...
Searching...
No Matches
realtime_ordered_map.h
Go to the documentation of this file.
1
17#ifndef CCC_REALTIME_ORDERED_MAP_H
18#define CCC_REALTIME_ORDERED_MAP_H
19
21#include <stddef.h>
24#include "impl/impl_realtime_ordered_map.h"
25#include "types.h"
26
37typedef struct ccc_romap_ ccc_realtime_ordered_map;
38
48typedef struct ccc_romap_elem_ ccc_romap_elem;
49
54typedef union ccc_romap_entry_ ccc_romap_entry;
55
73#define ccc_rom_init(rom_name, struct_name, rom_elem_field, key_elem_field, \
74 key_cmp_fn, alloc_fn, aux_data) \
75 ccc_impl_rom_init(rom_name, struct_name, rom_elem_field, key_elem_field, \
76 key_cmp_fn, alloc_fn, aux_data)
77
89[[nodiscard]] ccc_tribool ccc_rom_contains(ccc_realtime_ordered_map const *rom,
90 void const *key);
91
96[[nodiscard]] void *ccc_rom_get_key_val(ccc_realtime_ordered_map const *rom,
97 void const *key);
98
118[[nodiscard]] ccc_entry ccc_rom_swap_entry(ccc_realtime_ordered_map *rom,
119 ccc_romap_elem *key_val_handle,
120 ccc_romap_elem *tmp);
121
135#define ccc_rom_swap_entry_r(realtime_ordered_map_ptr, key_val_handle_ptr, \
136 tmp_ptr) \
137 &(ccc_entry) \
138 { \
139 ccc_rom_swap_entry((realtime_ordered_map_ptr), (key_val_handle_ptr), \
140 (tmp_ptr)) \
141 .impl_ \
142 }
143
151[[nodiscard]] ccc_entry ccc_rom_try_insert(ccc_realtime_ordered_map *rom,
152 ccc_romap_elem *key_val_handle);
153
162#define ccc_rom_try_insert_r(realtime_ordered_map_ptr, key_val_handle_ptr) \
163 &(ccc_entry) \
164 { \
165 ccc_rom_try_insert((realtime_ordered_map_ptr), (key_val_handle_ptr)) \
166 .impl_ \
167 }
168
181#define ccc_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value...) \
182 &(ccc_entry) \
183 { \
184 ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value) \
185 }
186
195[[nodiscard]] ccc_entry
196ccc_rom_insert_or_assign(ccc_realtime_ordered_map *rom,
197 ccc_romap_elem *key_val_handle);
198
211#define ccc_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
212 lazy_value...) \
213 &(ccc_entry) \
214 { \
215 ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
216 lazy_value) \
217 }
218
234[[nodiscard]] ccc_entry ccc_rom_remove(ccc_realtime_ordered_map *rom,
235 ccc_romap_elem *out_handle);
236
252#define ccc_rom_remove_r(realtime_ordered_map_ptr, out_handle_ptr) \
253 &(ccc_entry) \
254 { \
255 ccc_rom_remove((realtime_ordered_map_ptr), (out_handle_ptr)).impl_ \
256 }
257
272[[nodiscard]] ccc_romap_entry ccc_rom_entry(ccc_realtime_ordered_map const *rom,
273 void const *key);
274
290#define ccc_rom_entry_r(realtime_ordered_map_ptr, key_ptr) \
291 &(ccc_romap_entry) \
292 { \
293 ccc_rom_entry((realtime_ordered_map_ptr), (key_ptr)).impl_ \
294 }
295
304[[nodiscard]] ccc_romap_entry *ccc_rom_and_modify(ccc_romap_entry *e,
305 ccc_update_fn *fn);
306
315[[nodiscard]] ccc_romap_entry *
316ccc_rom_and_modify_aux(ccc_romap_entry *e, ccc_update_fn *fn, void *aux);
317
344#define ccc_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
345 closure_over_T...) \
346 &(ccc_romap_entry) \
347 { \
348 ccc_impl_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
349 closure_over_T) \
350 }
351
363[[nodiscard]] void *ccc_rom_or_insert(ccc_romap_entry const *e,
364 ccc_romap_elem *elem);
365
377#define ccc_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value...) \
378 ccc_impl_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value)
379
387[[nodiscard]] void *ccc_rom_insert_entry(ccc_romap_entry const *e,
388 ccc_romap_elem *elem);
389
395#define ccc_rom_insert_entry_w(realtime_ordered_map_entry_ptr, \
396 lazy_key_value...) \
397 ccc_impl_rom_insert_entry_w(realtime_ordered_map_entry_ptr, lazy_key_value)
398
409[[nodiscard]] ccc_entry ccc_rom_remove_entry(ccc_romap_entry const *e);
410
421#define ccc_rom_remove_entry_r(realtime_ordered_map_entry_ptr) \
422 &(ccc_entry) \
423 { \
424 ccc_rom_remove_entry((realtime_ordered_map_entry_ptr)).impl_ \
425 }
426
430[[nodiscard]] void *ccc_rom_unwrap(ccc_romap_entry const *e);
431
435[[nodiscard]] ccc_tribool ccc_rom_insert_error(ccc_romap_entry const *e);
436
442[[nodiscard]] ccc_tribool ccc_rom_occupied(ccc_romap_entry const *e);
443
453[[nodiscard]] ccc_entry_status ccc_rom_entry_status(ccc_romap_entry const *e);
454
475ccc_result ccc_rom_clear(ccc_realtime_ordered_map *rom,
476 ccc_destructor_fn *destructor);
477
502[[nodiscard]] ccc_range ccc_rom_equal_range(ccc_realtime_ordered_map const *rom,
503 void const *begin_key,
504 void const *end_key);
505
513#define ccc_rom_equal_range_r(realtime_ordered_map_ptr, \
514 begin_and_end_key_ptrs...) \
515 &(ccc_range) \
516 { \
517 ccc_rom_equal_range((realtime_ordered_map_ptr), \
518 (begin_and_end_key_ptrs)) \
519 .impl_ \
520 }
521
540[[nodiscard]] ccc_rrange
541ccc_rom_equal_rrange(ccc_realtime_ordered_map const *rom,
542 void const *rbegin_key, void const *rend_key);
543
551#define ccc_rom_equal_rrange_r(realtime_ordered_map_ptr, \
552 rbegin_and_rend_key_ptrs...) \
553 &(ccc_rrange) \
554 { \
555 ccc_rom_equal_rrange((realtime_ordered_map_ptr), \
556 (rbegin_and_rend_key_ptrs)) \
557 .impl_ \
558 }
559
564[[nodiscard]] void *ccc_rom_begin(ccc_realtime_ordered_map const *rom);
565
570[[nodiscard]] void *ccc_rom_rbegin(ccc_realtime_ordered_map const *rom);
571
577[[nodiscard]] void *ccc_rom_next(ccc_realtime_ordered_map const *rom,
578 ccc_romap_elem const *iter_handle);
579
586[[nodiscard]] void *ccc_rom_rnext(ccc_realtime_ordered_map const *rom,
587 ccc_romap_elem const *iter_handle);
588
592[[nodiscard]] void *ccc_rom_end(ccc_realtime_ordered_map const *rom);
593
597[[nodiscard]] void *ccc_rom_rend(ccc_realtime_ordered_map const *rom);
598
608[[nodiscard]] ccc_ucount ccc_rom_size(ccc_realtime_ordered_map const *rom);
609
613[[nodiscard]] ccc_tribool ccc_rom_is_empty(ccc_realtime_ordered_map const *rom);
614
619[[nodiscard]] ccc_tribool ccc_rom_validate(ccc_realtime_ordered_map const *rom);
620
625#ifdef REALTIME_ORDERED_MAP_USING_NAMESPACE_CCC
626typedef ccc_romap_elem romap_elem;
627typedef ccc_realtime_ordered_map realtime_ordered_map;
628typedef ccc_romap_entry romap_entry;
629# define rom_init(args...) ccc_rom_init(args)
630# define rom_and_modify_w(args...) ccc_rom_and_modify_w(args)
631# define rom_or_insert_w(args...) ccc_rom_or_insert_w(args)
632# define rom_insert_entry_w(args...) ccc_rom_insert_entry_w(args)
633# define rom_try_insert_w(args...) ccc_rom_try_insert_w(args)
634# define rom_insert_or_assign_w(args...) ccc_rom_insert_or_assign_w(args)
635# define rom_swap_entry_r(args...) ccc_rom_swap_entry_r(args)
636# define rom_remove_r(args...) ccc_rom_remove_r(args)
637# define rom_remove_entry_r(args...) ccc_rom_remove_entry_r(args)
638# define rom_entry_r(args...) ccc_rom_entry_r(args)
639# define rom_and_modify_r(args...) ccc_rom_and_modify_r(args)
640# define rom_and_modify_aux_r(args...) ccc_rom_and_modify_aux_r(args)
641# define rom_contains(args...) ccc_rom_contains(args)
642# define rom_get_key_val(args...) ccc_rom_get_key_val(args)
643# define rom_get_mut(args...) ccc_rom_get_mut(args)
644# define rom_swap_entry(args...) ccc_rom_swap_entry(args)
645# define rom_remove(args...) ccc_rom_remove(args)
646# define rom_entry(args...) ccc_rom_entry(args)
647# define rom_remove_entry(args...) ccc_rom_remove_entry(args)
648# define rom_or_insert(args...) ccc_rom_or_insert(args)
649# define rom_insert_entry(args...) ccc_rom_insert_entry(args)
650# define rom_unwrap(args...) ccc_rom_unwrap(args)
651# define rom_unwrap_mut(args...) ccc_rom_unwrap_mut(args)
652# define rom_begin(args...) ccc_rom_begin(args)
653# define rom_next(args...) ccc_rom_next(args)
654# define rom_rbegin(args...) ccc_rom_rbegin(args)
655# define rom_rnext(args...) ccc_rom_rnext(args)
656# define rom_end(args...) ccc_rom_end(args)
657# define rom_rend(args...) ccc_rom_rend(args)
658# define rom_size(args...) ccc_rom_size(args)
659# define rom_is_empty(args...) ccc_rom_is_empty(args)
660# define rom_clear(args...) ccc_rom_clear(args)
661# define rom_validate(args...) ccc_rom_validate(args)
662#endif
663
664#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_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_clear
ccc_result ccc_rom_clear(ccc_realtime_ordered_map *rom, ccc_destructor_fn *destructor)
Pops every element from the map calling destructor if destructor is non-NULL. O(N).
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_and_modify
ccc_romap_entry * ccc_rom_and_modify(ccc_romap_entry *e, ccc_update_fn *fn)
Modifies the provided entry if it is Occupied.
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_aux
ccc_romap_entry * ccc_rom_and_modify_aux(ccc_romap_entry *e, ccc_update_fn *fn, void *aux)
Modifies the provided entry if it is Occupied.
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_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:48
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_romap_entry
union ccc_romap_entry_ ccc_romap_entry
A container specific entry used to implement the Entry Interface.
Definition: realtime_ordered_map.h:54
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_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_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_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_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:37
ccc_ucount
A type for returning an unsigned integer from a container for counting. Intended to count sizes,...
Definition: types.h:172
types.h
The C Container Collection Fundamental Types.
ccc_update_fn
void ccc_update_fn(ccc_user_type)
A callback function for modifying an element in the container.
Definition: types.h:300
ccc_range
union ccc_range_ ccc_range
The result of a range query on iterable containers.
Definition: types.h:29
ccc_result
ccc_result
A result of actions on containers.
Definition: types.h:117
ccc_entry
union ccc_entry_ ccc_entry
An Occupied or Vacant position in a searchable container.
Definition: types.h:46
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:102
ccc_entry_status
enum ccc_entry_status_ ccc_entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:56
ccc_destructor_fn
void ccc_destructor_fn(ccc_user_type)
A callback function for destroying an element in the container.
Definition: types.h:318
ccc_rrange
union ccc_rrange_ ccc_rrange
The result of a rrange query on iterable containers.
Definition: types.h:37