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 alloc_fn, key_cmp_fn, aux_data) \
75 ccc_impl_rom_init(rom_name, struct_name, rom_elem_field, key_elem_field, \
76 alloc_fn, key_cmp_fn, aux_data)
77
88[[nodiscard]] bool ccc_rom_contains(ccc_realtime_ordered_map const *rom,
89 void const *key);
90
95[[nodiscard]] void *ccc_rom_get_key_val(ccc_realtime_ordered_map const *rom,
96 void const *key);
97
117[[nodiscard]] ccc_entry ccc_rom_insert(ccc_realtime_ordered_map *rom,
118 ccc_romap_elem *key_val_handle,
119 ccc_romap_elem *tmp);
120
134#define ccc_rom_insert_r(realtime_ordered_map_ptr, key_val_handle_ptr, \
135 tmp_ptr) \
136 &(ccc_entry) \
137 { \
138 ccc_rom_insert((realtime_ordered_map_ptr), (key_val_handle_ptr), \
139 (tmp_ptr)) \
140 .impl_ \
141 }
142
150[[nodiscard]] ccc_entry ccc_rom_try_insert(ccc_realtime_ordered_map *rom,
151 ccc_romap_elem *key_val_handle);
152
161#define ccc_rom_try_insert_r(realtime_ordered_map_ptr, key_val_handle_ptr) \
162 &(ccc_entry) \
163 { \
164 ccc_rom_try_insert((realtime_ordered_map_ptr), (key_val_handle_ptr)) \
165 .impl_ \
166 }
167
180#define ccc_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value...) \
181 &(ccc_entry) \
182 { \
183 ccc_impl_rom_try_insert_w(realtime_ordered_map_ptr, key, lazy_value) \
184 }
185
194[[nodiscard]] ccc_entry
195ccc_rom_insert_or_assign(ccc_realtime_ordered_map *rom,
196 ccc_romap_elem *key_val_handle);
197
210#define ccc_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
211 lazy_value...) \
212 &(ccc_entry) \
213 { \
214 ccc_impl_rom_insert_or_assign_w(realtime_ordered_map_ptr, key, \
215 lazy_value) \
216 }
217
233[[nodiscard]] ccc_entry ccc_rom_remove(ccc_realtime_ordered_map *rom,
234 ccc_romap_elem *out_handle);
235
251#define ccc_rom_remove_r(realtime_ordered_map_ptr, out_handle_ptr) \
252 &(ccc_entry) \
253 { \
254 ccc_rom_remove((realtime_ordered_map_ptr), (out_handle_ptr)).impl_ \
255 }
256
271[[nodiscard]] ccc_romap_entry ccc_rom_entry(ccc_realtime_ordered_map const *rom,
272 void const *key);
273
289#define ccc_rom_entry_r(realtime_ordered_map_ptr, key_ptr) \
290 &(ccc_romap_entry) \
291 { \
292 ccc_rom_entry((realtime_ordered_map_ptr), (key_ptr)).impl_ \
293 }
294
303[[nodiscard]] ccc_romap_entry *ccc_rom_and_modify(ccc_romap_entry *e,
304 ccc_update_fn *fn);
305
314[[nodiscard]] ccc_romap_entry *
315ccc_rom_and_modify_aux(ccc_romap_entry *e, ccc_update_fn *fn, void *aux);
316
343#define ccc_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
344 closure_over_T...) \
345 &(ccc_romap_entry) \
346 { \
347 ccc_impl_rom_and_modify_w(realtime_ordered_map_entry_ptr, type_name, \
348 closure_over_T) \
349 }
350
362[[nodiscard]] void *ccc_rom_or_insert(ccc_romap_entry const *e,
363 ccc_romap_elem *elem);
364
376#define ccc_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value...) \
377 ccc_impl_rom_or_insert_w(realtime_ordered_map_entry_ptr, lazy_key_value)
378
386[[nodiscard]] void *ccc_rom_insert_entry(ccc_romap_entry const *e,
387 ccc_romap_elem *elem);
388
394#define ccc_rom_insert_entry_w(realtime_ordered_map_entry_ptr, \
395 lazy_key_value...) \
396 ccc_impl_rom_insert_entry_w(realtime_ordered_map_entry_ptr, lazy_key_value)
397
408[[nodiscard]] ccc_entry ccc_rom_remove_entry(ccc_romap_entry const *e);
409
420#define ccc_rom_remove_entry_r(realtime_ordered_map_entry_ptr) \
421 &(ccc_entry) \
422 { \
423 ccc_rom_remove_entry((realtime_ordered_map_entry_ptr)).impl_ \
424 }
425
429[[nodiscard]] void *ccc_rom_unwrap(ccc_romap_entry const *e);
430
434[[nodiscard]] bool ccc_rom_insert_error(ccc_romap_entry const *e);
435
440[[nodiscard]] bool ccc_rom_occupied(ccc_romap_entry const *e);
441
451[[nodiscard]] ccc_entry_status ccc_rom_entry_status(ccc_romap_entry const *e);
452
473ccc_result ccc_rom_clear(ccc_realtime_ordered_map *rom,
474 ccc_destructor_fn *destructor);
475
500[[nodiscard]] ccc_range ccc_rom_equal_range(ccc_realtime_ordered_map const *rom,
501 void const *begin_key,
502 void const *end_key);
503
511#define ccc_rom_equal_range_r(realtime_ordered_map_ptr, \
512 begin_and_end_key_ptrs...) \
513 &(ccc_range) \
514 { \
515 ccc_rom_equal_range((realtime_ordered_map_ptr), \
516 (begin_and_end_key_ptrs)) \
517 .impl_ \
518 }
519
538[[nodiscard]] ccc_rrange
539ccc_rom_equal_rrange(ccc_realtime_ordered_map const *rom,
540 void const *rbegin_key, void const *rend_key);
541
549#define ccc_rom_equal_rrange_r(realtime_ordered_map_ptr, \
550 rbegin_and_rend_key_ptrs...) \
551 &(ccc_rrange) \
552 { \
553 ccc_rom_equal_rrange((realtime_ordered_map_ptr), \
554 (rbegin_and_rend_key_ptrs)) \
555 .impl_ \
556 }
557
562[[nodiscard]] void *ccc_rom_begin(ccc_realtime_ordered_map const *rom);
563
568[[nodiscard]] void *ccc_rom_rbegin(ccc_realtime_ordered_map const *rom);
569
575[[nodiscard]] void *ccc_rom_next(ccc_realtime_ordered_map const *rom,
576 ccc_romap_elem const *iter_handle);
577
584[[nodiscard]] void *ccc_rom_rnext(ccc_realtime_ordered_map const *rom,
585 ccc_romap_elem const *iter_handle);
586
590[[nodiscard]] void *ccc_rom_end(ccc_realtime_ordered_map const *rom);
591
595[[nodiscard]] void *ccc_rom_rend(ccc_realtime_ordered_map const *rom);
596
606[[nodiscard]] size_t ccc_rom_size(ccc_realtime_ordered_map const *rom);
607
611[[nodiscard]] bool ccc_rom_is_empty(ccc_realtime_ordered_map const *rom);
612
616[[nodiscard]] bool ccc_rom_validate(ccc_realtime_ordered_map const *rom);
617
622#ifdef REALTIME_ORDERED_MAP_USING_NAMESPACE_CCC
623typedef ccc_romap_elem romap_elem;
624typedef ccc_realtime_ordered_map realtime_ordered_map;
625typedef ccc_romap_entry romap_entry;
626# define rom_init(args...) ccc_rom_init(args)
627# define rom_and_modify_w(args...) ccc_rom_and_modify_w(args)
628# define rom_or_insert_w(args...) ccc_rom_or_insert_w(args)
629# define rom_insert_entry_w(args...) ccc_rom_insert_entry_w(args)
630# define rom_try_insert_w(args...) ccc_rom_try_insert_w(args)
631# define rom_insert_or_assign_w(args...) ccc_rom_insert_or_assign_w(args)
632# define rom_insert_r(args...) ccc_rom_insert_r(args)
633# define rom_remove_r(args...) ccc_rom_remove_r(args)
634# define rom_remove_entry_r(args...) ccc_rom_remove_entry_r(args)
635# define rom_entry_r(args...) ccc_rom_entry_r(args)
636# define rom_and_modify_r(args...) ccc_rom_and_modify_r(args)
637# define rom_and_modify_aux_r(args...) ccc_rom_and_modify_aux_r(args)
638# define rom_contains(args...) ccc_rom_contains(args)
639# define rom_get_key_val(args...) ccc_rom_get_key_val(args)
640# define rom_get_mut(args...) ccc_rom_get_mut(args)
641# define rom_insert(args...) ccc_rom_insert(args)
642# define rom_remove(args...) ccc_rom_remove(args)
643# define rom_entry(args...) ccc_rom_entry(args)
644# define rom_remove_entry(args...) ccc_rom_remove_entry(args)
645# define rom_or_insert(args...) ccc_rom_or_insert(args)
646# define rom_insert_entry(args...) ccc_rom_insert_entry(args)
647# define rom_unwrap(args...) ccc_rom_unwrap(args)
648# define rom_unwrap_mut(args...) ccc_rom_unwrap_mut(args)
649# define rom_begin(args...) ccc_rom_begin(args)
650# define rom_next(args...) ccc_rom_next(args)
651# define rom_rbegin(args...) ccc_rom_rbegin(args)
652# define rom_rnext(args...) ccc_rom_rnext(args)
653# define rom_end(args...) ccc_rom_end(args)
654# define rom_rend(args...) ccc_rom_rend(args)
655# define rom_size(args...) ccc_rom_size(args)
656# define rom_is_empty(args...) ccc_rom_is_empty(args)
657# define rom_clear(args...) ccc_rom_clear(args)
658# define rom_validate(args...) ccc_rom_validate(args)
659#endif
660
661#endif /* CCC_REALTIME_ORDERED_MAP_H */
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_insert_error
bool ccc_rom_insert_error(ccc_romap_entry const *e)
Returns the Vacant or Occupied status of the entry.
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_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_is_empty
bool ccc_rom_is_empty(ccc_realtime_ordered_map const *rom)
Returns the size status of the map.
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_unwrap
void * ccc_rom_unwrap(ccc_romap_entry const *e)
Unwraps the provided entry to obtain a view into the map element.
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_occupied
bool ccc_rom_occupied(ccc_romap_entry const *e)
Provides the status of the entry should an insertion follow.
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_size
size_t ccc_rom_size(ccc_realtime_ordered_map const *rom)
Returns the size of the map.
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_entry_status
ccc_entry_status ccc_rom_entry_status(ccc_romap_entry const *e)
Obtain the entry status from a container entry.
ccc_rom_insert
ccc_entry ccc_rom_insert(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_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_contains
bool ccc_rom_contains(ccc_realtime_ordered_map const *rom, void const *key)
Searches the map for the presence of key.
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_rom_validate
bool ccc_rom_validate(ccc_realtime_ordered_map const *rom)
Validation of invariants for 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:37
types.h
The C Container Collection Fundamental Types.
ccc_result
ccc_result
A result of actions on containers.
Definition: types.h:65
ccc_update_fn
void ccc_update_fn(ccc_user_type)
A callback function for modifying an element in the container.
Definition: types.h:216
ccc_range
union ccc_range_ ccc_range
The result of a range query on iterable containers.
Definition: types.h:30
ccc_entry
union ccc_entry_ ccc_entry
An Occupied or Vacant position in a searchable container.
Definition: types.h:47
ccc_entry_status
enum ccc_entry_status_ ccc_entry_status
The status monitoring and entry state once it is obtained.
Definition: types.h:57
ccc_destructor_fn
void ccc_destructor_fn(ccc_user_type)
A callback function for destroying an element in the container.
Definition: types.h:234
ccc_rrange
union ccc_rrange_ ccc_rrange
The result of a rrange query on iterable containers.
Definition: types.h:38