C Container Collection (CCC)
Loading...
Searching...
No Matches
flat_realtime_ordered_map.h
Go to the documentation of this file.
1
25#ifndef CCC_FLAT_REALTIME_ORDERED_MAP_H
26#define CCC_FLAT_REALTIME_ORDERED_MAP_H
27
29#include <stdbool.h>
30#include <stddef.h>
33#include "impl/impl_flat_realtime_ordered_map.h"
34#include "types.h"
35
46typedef struct ccc_fromap_ ccc_flat_realtime_ordered_map;
47
52typedef struct ccc_fromap_elem_ ccc_fromap_elem;
53
59typedef union ccc_fromap_entry_ ccc_fromap_entry;
60
78#define ccc_frm_init(memory_ptr, capacity, frm_elem_field, key_elem_field, \
79 alloc_fn, key_cmp_fn, aux_data) \
80 ccc_impl_frm_init(memory_ptr, capacity, frm_elem_field, key_elem_field, \
81 alloc_fn, key_cmp_fn, aux_data)
82
165ccc_result ccc_frm_copy(ccc_flat_realtime_ordered_map *dst,
166 ccc_flat_realtime_ordered_map const *src,
167 ccc_alloc_fn *fn);
168
179[[nodiscard]] bool ccc_frm_contains(ccc_flat_realtime_ordered_map const *frm,
180 void const *key);
181
186[[nodiscard]] void *
187ccc_frm_get_key_val(ccc_flat_realtime_ordered_map const *frm, void const *key);
188
206[[nodiscard]] ccc_entry ccc_frm_insert(ccc_flat_realtime_ordered_map *frm,
207 ccc_fromap_elem *out_handle);
208
220#define ccc_frm_insert_r(flat_realtime_ordered_map_ptr, out_handle_ptr) \
221 &(ccc_entry) \
222 { \
223 ccc_frm_insert((flat_realtime_ordered_map_ptr), (out_handle_ptr)) \
224 .impl_ \
225 }
226
234[[nodiscard]] ccc_entry ccc_frm_try_insert(ccc_flat_realtime_ordered_map *frm,
235 ccc_fromap_elem *key_val_handle);
236
244#define ccc_frm_try_insert_r(flat_realtime_ordered_map_ptr, \
245 key_val_handle_ptr) \
246 &(ccc_entry) \
247 { \
248 ccc_frm_try_insert((flat_realtime_ordered_map_ptr), \
249 (key_val_handle_ptr)) \
250 .impl_ \
251 }
252
265#define ccc_frm_try_insert_w(flat_realtime_ordered_map_ptr, key, \
266 lazy_value...) \
267 &(ccc_entry) \
268 { \
269 ccc_impl_frm_try_insert_w(flat_realtime_ordered_map_ptr, key, \
270 lazy_value) \
271 }
272
281[[nodiscard]] ccc_entry
282ccc_frm_insert_or_assign(ccc_flat_realtime_ordered_map *frm,
283 ccc_fromap_elem *key_val_handle);
284
297#define ccc_frm_insert_or_assign_w(flat_realtime_ordered_map_ptr, key, \
298 lazy_value...) \
299 &(ccc_entry) \
300 { \
301 ccc_impl_frm_insert_or_assign_w(flat_realtime_ordered_map_ptr, key, \
302 lazy_value) \
303 }
304
315[[nodiscard]] ccc_entry ccc_frm_remove(ccc_flat_realtime_ordered_map *frm,
316 ccc_fromap_elem *out_handle);
317
328#define ccc_frm_remove_r(flat_realtime_ordered_map_ptr, out_handle_ptr) \
329 &(ccc_entry) \
330 { \
331 ccc_frm_remove((flat_realtime_ordered_map_ptr), (out_handle_ptr)) \
332 .impl_ \
333 }
334
349[[nodiscard]] ccc_fromap_entry
350ccc_frm_entry(ccc_flat_realtime_ordered_map const *frm, void const *key);
351
367#define ccc_frm_entry_r(flat_realtime_ordered_map_ptr, key_ptr) \
368 &(ccc_fromap_entry) \
369 { \
370 ccc_frm_entry((flat_realtime_ordered_map_ptr), (key_ptr)).impl_ \
371 }
372
381[[nodiscard]] ccc_fromap_entry *ccc_frm_and_modify(ccc_fromap_entry *e,
382 ccc_update_fn *fn);
383
392[[nodiscard]] ccc_fromap_entry *
393ccc_frm_and_modify_aux(ccc_fromap_entry *e, ccc_update_fn *fn, void *aux);
394
421#define ccc_frm_and_modify_w(flat_realtime_ordered_map_entry_ptr, type_name, \
422 closure_over_T...) \
423 &(ccc_fromap_entry) \
424 { \
425 ccc_impl_frm_and_modify_w(flat_realtime_ordered_map_entry_ptr, \
426 type_name, closure_over_T) \
427 }
428
440[[nodiscard]] void *ccc_frm_or_insert(ccc_fromap_entry const *e,
441 ccc_fromap_elem *elem);
442
454#define ccc_frm_or_insert_w(flat_realtime_ordered_map_entry_ptr, \
455 lazy_key_value...) \
456 ccc_impl_frm_or_insert_w(flat_realtime_ordered_map_entry_ptr, \
457 lazy_key_value)
458
466[[nodiscard]] void *ccc_frm_insert_entry(ccc_fromap_entry const *e,
467 ccc_fromap_elem *elem);
468
474#define ccc_frm_insert_entry_w(flat_realtime_ordered_map_entry_ptr, \
475 lazy_key_value...) \
476 ccc_impl_frm_insert_entry_w(flat_realtime_ordered_map_entry_ptr, \
477 lazy_key_value)
478
486ccc_entry ccc_frm_remove_entry(ccc_fromap_entry const *e);
487
496#define ccc_frm_remove_entry_r(flat_realtime_ordered_map_entry_ptr) \
497 &(ccc_entry) \
498 { \
499 ccc_frm_remove_entry((flat_realtime_ordered_map_entry_ptr)).impl_ \
500 }
501
505[[nodiscard]] void *ccc_frm_unwrap(ccc_fromap_entry const *e);
506
510[[nodiscard]] bool ccc_frm_occupied(ccc_fromap_entry const *e);
511
516[[nodiscard]] bool ccc_frm_insert_error(ccc_fromap_entry const *e);
517
527[[nodiscard]] ccc_entry_status ccc_frm_entry_status(ccc_fromap_entry const *e);
528
542ccc_result ccc_frm_clear(ccc_flat_realtime_ordered_map *frm,
543 ccc_destructor_fn *fn);
544
555ccc_result ccc_frm_clear_and_free(ccc_flat_realtime_ordered_map *frm,
556 ccc_destructor_fn *fn);
557
582[[nodiscard]] ccc_range
583ccc_frm_equal_range(ccc_flat_realtime_ordered_map const *frm,
584 void const *begin_key, void const *end_key);
585
592#define ccc_frm_equal_range_r(flat_realtime_ordered_map_ptr, \
593 begin_and_end_key_ptrs...) \
594 &(ccc_range) \
595 { \
596 ccc_frm_equal_range((flat_realtime_ordered_map_ptr), \
597 (begin_and_end_key_ptrs)) \
598 .impl_ \
599 }
600
619[[nodiscard]] ccc_rrange
620ccc_frm_equal_rrange(ccc_flat_realtime_ordered_map const *frm,
621 void const *rbegin_key, void const *rend_key);
622
630#define ccc_frm_equal_rrange_r(flat_realtime_ordered_map_ptr, \
631 rbegin_and_rend_key_ptrs...) \
632 &(ccc_rrange) \
633 { \
634 ccc_frm_equal_rrange((flat_realtime_ordered_map_ptr), \
635 (rbegin_and_rend_key_ptrs)) \
636 .impl_ \
637 }
638
642[[nodiscard]] void *ccc_frm_begin(ccc_flat_realtime_ordered_map const *frm);
643
647[[nodiscard]] void *ccc_frm_rbegin(ccc_flat_realtime_ordered_map const *frm);
648
654[[nodiscard]] void *ccc_frm_next(ccc_flat_realtime_ordered_map const *frm,
655 ccc_fromap_elem const *iter_handle);
656
663[[nodiscard]] void *ccc_frm_rnext(ccc_flat_realtime_ordered_map const *frm,
664 ccc_fromap_elem const *iter_handle);
665
669[[nodiscard]] void *ccc_frm_end(ccc_flat_realtime_ordered_map const *frm);
670
674[[nodiscard]] void *ccc_frm_rend(ccc_flat_realtime_ordered_map const *frm);
675
685[[nodiscard]] bool ccc_frm_is_empty(ccc_flat_realtime_ordered_map const *frm);
686
690[[nodiscard]] size_t ccc_frm_size(ccc_flat_realtime_ordered_map const *frm);
691
695[[nodiscard]] size_t ccc_frm_capacity(ccc_flat_realtime_ordered_map const *frm);
696
706[[nodiscard]] void *ccc_frm_data(ccc_flat_realtime_ordered_map const *frm);
707
711[[nodiscard]] bool ccc_frm_validate(ccc_flat_realtime_ordered_map const *frm);
712
717#ifdef FLAT_REALTIME_ORDERED_MAP_USING_NAMESPACE_CCC
718typedef ccc_fromap_elem fromap_elem;
719typedef ccc_flat_realtime_ordered_map flat_realtime_ordered_map;
720typedef ccc_fromap_entry fromap_entry;
721# define frm_and_modify_w(args...) ccc_frm_and_modify_w(args)
722# define frm_or_insert_w(args...) ccc_frm_or_insert_w(args)
723# define frm_insert_entry_w(args...) ccc_frm_insert_entry_w(args)
724# define frm_try_insert_w(args...) ccc_frm_try_insert_w(args)
725# define frm_insert_or_assign_w(args...) ccc_frm_insert_or_assign_w(args)
726# define frm_init(args...) ccc_frm_init(args)
727# define frm_copy(args...) ccc_frm_copy(args)
728# define frm_contains(args...) ccc_frm_contains(args)
729# define frm_get_key_val(args...) ccc_frm_get_key_val(args)
730# define frm_insert(args...) ccc_frm_insert(args)
731# define frm_begin(args...) ccc_frm_begin(args)
732# define frm_rbegin(args...) ccc_frm_rbegin(args)
733# define frm_next(args...) ccc_frm_next(args)
734# define frm_rnext(args...) ccc_frm_rnext(args)
735# define frm_end(args...) ccc_frm_end(args)
736# define frm_rend(args...) ccc_frm_rend(args)
737# define frm_data(args...) ccc_frm_data(args)
738# define frm_is_empty(args...) ccc_frm_is_empty(args)
739# define frm_size(args...) ccc_frm_size(args)
740# define frm_clear(args...) ccc_frm_clear(args)
741# define frm_clear_and_free(args...) ccc_frm_clear_and_free(args)
742# define frm_validate(args...) ccc_frm_validate(args)
743#endif /* FLAT_REALTIME_ORDERED_MAP_USING_NAMESPACE_CCC */
744
745#endif /* CCC_FLAT_REALTIME_ORDERED_MAP_H */
ccc_frm_end
void * ccc_frm_end(ccc_flat_realtime_ordered_map const *frm)
Return the end of an inorder traversal of the map. O(1).
ccc_frm_capacity
size_t ccc_frm_capacity(ccc_flat_realtime_ordered_map const *frm)
Returns the capacity of the map.
ccc_frm_data
void * ccc_frm_data(ccc_flat_realtime_ordered_map const *frm)
Return a reference to the base of backing array. O(1).
ccc_frm_contains
bool ccc_frm_contains(ccc_flat_realtime_ordered_map const *frm, void const *key)
Searches the map for the presence of key.
ccc_frm_remove_entry
ccc_entry ccc_frm_remove_entry(ccc_fromap_entry const *e)
Remove the entry from the map if Occupied.
ccc_frm_occupied
bool ccc_frm_occupied(ccc_fromap_entry const *e)
Returns the Vacant or Occupied status of the entry.
ccc_frm_is_empty
bool ccc_frm_is_empty(ccc_flat_realtime_ordered_map const *frm)
Returns the size status of the map.
ccc_fromap_entry
union ccc_fromap_entry_ ccc_fromap_entry
A container specific entry used to implement the Entry Interface.
Definition: flat_realtime_ordered_map.h:59
ccc_frm_rend
void * ccc_frm_rend(ccc_flat_realtime_ordered_map const *frm)
Return the rend of a reverse inorder traversal of the map. O(1).
ccc_fromap_elem
struct ccc_fromap_elem_ ccc_fromap_elem
The intrusive element for the user defined struct being stored in the map.
Definition: flat_realtime_ordered_map.h:52
ccc_frm_get_key_val
void * ccc_frm_get_key_val(ccc_flat_realtime_ordered_map const *frm, void const *key)
Returns a reference into the map at entry key.
ccc_flat_realtime_ordered_map
struct ccc_fromap_ ccc_flat_realtime_ordered_map
A flat realtime ordered map offers O(lg N) search and erase, and amortized O(lg N) insert.
Definition: flat_realtime_ordered_map.h:46
ccc_frm_insert
ccc_entry ccc_frm_insert(ccc_flat_realtime_ordered_map *frm, ccc_fromap_elem *out_handle)
Invariantly inserts the key value wrapping key_val_handle.
ccc_frm_clear
ccc_result ccc_frm_clear(ccc_flat_realtime_ordered_map *frm, ccc_destructor_fn *fn)
Frees all slots in the map for use without affecting capacity.
ccc_frm_try_insert
ccc_entry ccc_frm_try_insert(ccc_flat_realtime_ordered_map *frm, ccc_fromap_elem *key_val_handle)
Attempts to insert the key value wrapping key_val_handle.
ccc_frm_begin
void * ccc_frm_begin(ccc_flat_realtime_ordered_map const *frm)
Return the start of an inorder traversal of the map. O(lg N).
ccc_frm_next
void * ccc_frm_next(ccc_flat_realtime_ordered_map const *frm, ccc_fromap_elem const *iter_handle)
Return the next element in an inorder traversal of the map. O(1).
ccc_frm_equal_rrange
ccc_rrange ccc_frm_equal_rrange(ccc_flat_realtime_ordered_map const *frm, void const *rbegin_key, void const *rend_key)
Return an iterable rrange of values from [begin_key, end_key). O(lg N).
ccc_frm_clear_and_free
ccc_result ccc_frm_clear_and_free(ccc_flat_realtime_ordered_map *frm, ccc_destructor_fn *fn)
Frees all slots in the map and frees the underlying buffer.
ccc_frm_rnext
void * ccc_frm_rnext(ccc_flat_realtime_ordered_map const *frm, ccc_fromap_elem const *iter_handle)
Return the rnext element in a reverse inorder traversal of the map. O(1).
ccc_frm_entry
ccc_fromap_entry ccc_frm_entry(ccc_flat_realtime_ordered_map const *frm, void const *key)
Obtains an entry for the provided key in the map for future use.
ccc_frm_insert_entry
void * ccc_frm_insert_entry(ccc_fromap_entry const *e, ccc_fromap_elem *elem)
Inserts the provided entry invariantly.
ccc_frm_remove
ccc_entry ccc_frm_remove(ccc_flat_realtime_ordered_map *frm, ccc_fromap_elem *out_handle)
Removes the key value in the map storing the old value, if present, in the struct containing out_hand...
ccc_frm_size
size_t ccc_frm_size(ccc_flat_realtime_ordered_map const *frm)
Returns the size of the map.
ccc_frm_and_modify
ccc_fromap_entry * ccc_frm_and_modify(ccc_fromap_entry *e, ccc_update_fn *fn)
Modifies the provided entry if it is Occupied.
ccc_frm_copy
ccc_result ccc_frm_copy(ccc_flat_realtime_ordered_map *dst, ccc_flat_realtime_ordered_map const *src, ccc_alloc_fn *fn)
Copy the map at source to destination.
ccc_frm_entry_status
ccc_entry_status ccc_frm_entry_status(ccc_fromap_entry const *e)
Obtain the entry status from a container entry.
ccc_frm_insert_error
bool ccc_frm_insert_error(ccc_fromap_entry const *e)
Provides the status of the entry should an insertion follow.
ccc_frm_rbegin
void * ccc_frm_rbegin(ccc_flat_realtime_ordered_map const *frm)
Return the start of a reverse inorder traversal of the map. O(lg N).
ccc_frm_or_insert
void * ccc_frm_or_insert(ccc_fromap_entry const *e, ccc_fromap_elem *elem)
Inserts the struct with handle elem if the entry is Vacant.
ccc_frm_and_modify_aux
ccc_fromap_entry * ccc_frm_and_modify_aux(ccc_fromap_entry *e, ccc_update_fn *fn, void *aux)
Modifies the provided entry if it is Occupied.
ccc_frm_unwrap
void * ccc_frm_unwrap(ccc_fromap_entry const *e)
Unwraps the provided entry to obtain a view into the map element.
ccc_frm_validate
bool ccc_frm_validate(ccc_flat_realtime_ordered_map const *frm)
Validation of invariants for the map.
ccc_frm_equal_range
ccc_range ccc_frm_equal_range(ccc_flat_realtime_ordered_map const *frm, void const *begin_key, void const *end_key)
Return an iterable range of values from [begin_key, end_key). O(lg N).
ccc_frm_insert_or_assign
ccc_entry ccc_frm_insert_or_assign(ccc_flat_realtime_ordered_map *frm, ccc_fromap_elem *key_val_handle)
Invariantly inserts or overwrites a user struct into the map.
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_alloc_fn
void * ccc_alloc_fn(void *ptr, size_t size, void *aux)
An allocation function at the core of all containers.
Definition: types.h:199
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