C Container Collection (CCC)
Loading...
Searching...
No Matches
Data Structures | Macros | Functions
private_adaptive_map.h File Reference

The Adaptive Map Private Interface. More...

#include "../types.h"
Include dependency graph for private_adaptive_map.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Detailed Description

The Adaptive Map Private Interface.

The adaptive map is currently implemented as a Splay Tree. A Splay Tree is a self-optimizing data structure that "adapts" the usage pattern of the user by moving frequently accessed elements to the root. In the process, the trees height is also reduced through rotations.

Adaptive, is the word used for this container because there are many self-optimizing data structures that could take over this implementation. It is best not to tie the naming to any one type of tree or data structure.

Data Structures

struct  CCC_Adaptive_map_node
 
struct  CCC_Adaptive_map
 
struct  CCC_Adaptive_map_entry
 

Macros

#define CCC_private_adaptive_map_default( private_struct_name, private_node_node_field, private_key_node_field, private_comparator...)
 
#define CCC_private_adaptive_map_for( private_struct_name, private_node_node_field, private_key_node_field, private_comparator...)
 
#define CCC_private_adaptive_map_from( private_type_intruder_field_name, private_key_field_name, private_comparator, private_allocator, private_destructor, private_compound_literal_array...)
 
#define CCC_private_adaptive_map_new(adaptive_map_entry, private_allocator)
 
#define CCC_private_adaptive_map_insert_key_val( adaptive_map_entry, new_data, type_compound_literal...)
 
#define CCC_private_adaptive_map_insert_and_copy_key( om_insert_entry, om_insert_entry_ret, key, private_allocator, type_compound_literal...)
 
#define CCC_private_adaptive_map_and_modify_with( adaptive_map_entry_pointer, closure_parameter, closure_over_closure_parameter...)
 
#define CCC_private_adaptive_map_or_insert_with( adaptive_map_entry_pointer, private_allocator_pointer, type_compound_literal...)
 
#define CCC_private_adaptive_map_insert_entry_with( adaptive_map_entry_pointer, private_allocator_pointer, type_compound_literal...)
 
#define CCC_private_adaptive_map_try_insert_with( adaptive_map_pointer, key, private_allocator_pointer, type_compound_literal...)
 
#define CCC_private_adaptive_map_insert_or_assign_with( adaptive_map_pointer, key, private_allocator_pointer, type_compound_literal...)
 

Functions

void * CCC_private_adaptive_map_key_in_slot (struct CCC_Adaptive_map const *, void const *)
 
struct CCC_Adaptive_map_node * CCC_private_adaptive_map_node_in_slot (struct CCC_Adaptive_map const *, void const *)
 
struct CCC_Adaptive_map_entry CCC_private_adaptive_map_entry (struct CCC_Adaptive_map *, void const *)
 
void * CCC_private_adaptive_map_insert (struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *)
 

Macro Definition Documentation

◆ CCC_private_adaptive_map_and_modify_with

#define CCC_private_adaptive_map_and_modify_with (   adaptive_map_entry_pointer,
  closure_parameter,
  closure_over_closure_parameter... 
)
Value:
(__extension__({ \
__auto_type private_adaptive_map_ent_pointer \
= (adaptive_map_entry_pointer); \
struct CCC_Adaptive_map_entry private_adaptive_map_mod_ent \
= {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}}; \
if (private_adaptive_map_ent_pointer) { \
private_adaptive_map_mod_ent = *private_adaptive_map_ent_pointer; \
if (private_adaptive_map_mod_ent.entry.status \
& CCC_ENTRY_OCCUPIED) { \
closure_parameter = private_adaptive_map_mod_ent.entry.type; \
closure_over_closure_parameter \
} \
} \
private_adaptive_map_mod_ent; \
}))
CCC_Adaptive_map_entry
Definition: private_adaptive_map.h:85
CCC_Adaptive_map_entry::entry
CCC_Entry entry
Definition: private_adaptive_map.h:89
CCC_Entry::type
void * type
Definition: types.h:137
CCC_Entry::status
CCC_Entry_status status
Definition: types.h:139
CCC_ENTRY_ARGUMENT_ERROR
@ CCC_ENTRY_ARGUMENT_ERROR
Definition: types.h:121
CCC_ENTRY_OCCUPIED
@ CCC_ENTRY_OCCUPIED
Definition: types.h:116

◆ CCC_private_adaptive_map_default

#define CCC_private_adaptive_map_default (   private_struct_name,
  private_node_node_field,
  private_key_node_field,
  private_comparator... 
)
Value:
(struct CCC_Adaptive_map) { \
.sizeof_type = sizeof(private_struct_name), \
.type_intruder_offset \
= offsetof(private_struct_name, private_node_node_field), \
.key_offset = offsetof(private_struct_name, private_key_node_field), \
.comparator = private_comparator, \
}
CCC_Adaptive_map
Definition: private_adaptive_map.h:56
CCC_Adaptive_map::type_intruder_offset
size_t type_intruder_offset
Definition: private_adaptive_map.h:64

All other fields default to NULL or 0.

◆ CCC_private_adaptive_map_for

#define CCC_private_adaptive_map_for (   private_struct_name,
  private_node_node_field,
  private_key_node_field,
  private_comparator... 
)
Value:
(struct CCC_Adaptive_map) { \
.root = NULL, .size = 0, .sizeof_type = sizeof(private_struct_name), \
.type_intruder_offset \
= offsetof(private_struct_name, private_node_node_field), \
.key_offset = offsetof(private_struct_name, private_key_node_field), \
.comparator = private_comparator, \
}

◆ CCC_private_adaptive_map_from

#define CCC_private_adaptive_map_from (   private_type_intruder_field_name,
  private_key_field_name,
  private_comparator,
  private_allocator,
  private_destructor,
  private_compound_literal_array... 
)

◆ CCC_private_adaptive_map_insert_and_copy_key

#define CCC_private_adaptive_map_insert_and_copy_key (   om_insert_entry,
  om_insert_entry_ret,
  key,
  private_allocator,
  type_compound_literal... 
)
Value:
(__extension__({ \
typeof(type_compound_literal) *private_adaptive_map_new_ins_base \
= CCC_private_adaptive_map_new( \
(&om_insert_entry), private_allocator \
); \
om_insert_entry_ret = (CCC_Entry){ \
.type = private_adaptive_map_new_ins_base, \
.status = CCC_ENTRY_INSERT_ERROR, \
}; \
if (private_adaptive_map_new_ins_base) { \
om_insert_entry_ret.status = CCC_ENTRY_VACANT; \
*((typeof(type_compound_literal) *) \
private_adaptive_map_new_ins_base) = type_compound_literal; \
*((typeof(key) *)CCC_private_adaptive_map_key_in_slot( \
om_insert_entry.map, private_adaptive_map_new_ins_base \
)) = key; \
(void)CCC_private_adaptive_map_insert( \
om_insert_entry.map, \
CCC_private_adaptive_map_node_in_slot( \
om_insert_entry.map, private_adaptive_map_new_ins_base \
) \
); \
} \
}))
CCC_private_adaptive_map_new
#define CCC_private_adaptive_map_new(adaptive_map_entry, private_allocator)
Definition: private_adaptive_map.h:221
CCC_private_adaptive_map_insert
void * CCC_private_adaptive_map_insert(struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *)
CCC_private_adaptive_map_key_in_slot
void * CCC_private_adaptive_map_key_in_slot(struct CCC_Adaptive_map const *, void const *)
CCC_private_adaptive_map_node_in_slot
struct CCC_Adaptive_map_node * CCC_private_adaptive_map_node_in_slot(struct CCC_Adaptive_map const *, void const *)
CCC_Entry
An Occupied or Vacant position in a searchable container.
Definition: types.h:135
CCC_ENTRY_VACANT
@ CCC_ENTRY_VACANT
Definition: types.h:114
CCC_ENTRY_INSERT_ERROR
@ CCC_ENTRY_INSERT_ERROR
Definition: types.h:119

◆ CCC_private_adaptive_map_insert_entry_with

#define CCC_private_adaptive_map_insert_entry_with (   adaptive_map_entry_pointer,
  private_allocator_pointer,
  type_compound_literal... 
)

◆ CCC_private_adaptive_map_insert_key_val

#define CCC_private_adaptive_map_insert_key_val (   adaptive_map_entry,
  new_data,
  type_compound_literal... 
)
Value:
(__extension__({ \
if (new_data) { \
*new_data = type_compound_literal; \
new_data = CCC_private_adaptive_map_insert( \
(adaptive_map_entry)->map, \
CCC_private_adaptive_map_node_in_slot( \
(adaptive_map_entry)->map, new_data \
) \
); \
} \
}))

◆ CCC_private_adaptive_map_insert_or_assign_with

#define CCC_private_adaptive_map_insert_or_assign_with (   adaptive_map_pointer,
  key,
  private_allocator_pointer,
  type_compound_literal... 
)

◆ CCC_private_adaptive_map_new

#define CCC_private_adaptive_map_new (   adaptive_map_entry,
  private_allocator 
)
Value:
(__extension__({ \
void *private_adaptive_map_ins_allocate_ret = NULL; \
if ((private_allocator)->allocate) { \
private_adaptive_map_ins_allocate_ret \
= (private_allocator) \
->allocate((CCC_Allocator_arguments){ \
.input = NULL, \
.bytes = (adaptive_map_entry)->map->sizeof_type, \
.context = (private_allocator)->context, \
}); \
} \
private_adaptive_map_ins_allocate_ret; \
}))
CCC_Allocator_arguments
A bundle of arguments to pass to the user-implemented Allocator_interface function interface....
Definition: types.h:278

◆ CCC_private_adaptive_map_or_insert_with

#define CCC_private_adaptive_map_or_insert_with (   adaptive_map_entry_pointer,
  private_allocator_pointer,
  type_compound_literal... 
)
Value:
(__extension__({ \
__auto_type private_or_ins_entry_pointer \
= (adaptive_map_entry_pointer); \
typeof(type_compound_literal) *private_or_ins_ret = NULL; \
CCC_Allocator const *const private_adaptive_map_allocator \
= (private_allocator_pointer); \
if (private_adaptive_map_allocator && private_or_ins_entry_pointer) { \
if (private_or_ins_entry_pointer->entry.status \
== CCC_ENTRY_OCCUPIED) { \
private_or_ins_ret = private_or_ins_entry_pointer->entry.type; \
} else { \
private_or_ins_ret = CCC_private_adaptive_map_new( \
private_or_ins_entry_pointer, \
private_adaptive_map_allocator \
); \
CCC_private_adaptive_map_insert_key_val( \
private_or_ins_entry_pointer, \
private_or_ins_ret, \
type_compound_literal \
); \
} \
} \
private_or_ins_ret; \
}))
CCC_Allocator
The type passed by reference to any container function that may need to allocate memory....
Definition: types.h:376

◆ CCC_private_adaptive_map_try_insert_with

#define CCC_private_adaptive_map_try_insert_with (   adaptive_map_pointer,
  key,
  private_allocator_pointer,
  type_compound_literal... 
)
Value:
(__extension__({ \
__auto_type private_try_ins_map_pointer = (adaptive_map_pointer); \
CCC_Entry private_adaptive_map_try_ins_ent_ret \
= {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
CCC_Allocator const *const private_adaptive_map_allocator \
= (private_allocator_pointer); \
if (private_adaptive_map_allocator && private_try_ins_map_pointer) { \
__auto_type private_adaptive_map_key = (key); \
struct CCC_Adaptive_map_entry private_adaptive_map_try_ins_ent \
= CCC_private_adaptive_map_entry( \
private_try_ins_map_pointer, \
(void *)&private_adaptive_map_key \
); \
if (!(private_adaptive_map_try_ins_ent.entry.status \
& CCC_ENTRY_OCCUPIED)) { \
CCC_private_adaptive_map_insert_and_copy_key( \
private_adaptive_map_try_ins_ent, \
private_adaptive_map_try_ins_ent_ret, \
private_adaptive_map_key, \
private_adaptive_map_allocator, \
type_compound_literal \
); \
} else if (private_adaptive_map_try_ins_ent.entry.status \
== CCC_ENTRY_OCCUPIED) { \
private_adaptive_map_try_ins_ent_ret \
= private_adaptive_map_try_ins_ent.entry; \
} \
} \
private_adaptive_map_try_ins_ent_ret; \
}))
CCC_private_adaptive_map_entry
struct CCC_Adaptive_map_entry CCC_private_adaptive_map_entry(struct CCC_Adaptive_map *, void const *)

Function Documentation

◆ CCC_private_adaptive_map_entry()

struct CCC_Adaptive_map_entry CCC_private_adaptive_map_entry ( struct CCC_Adaptive_map *  ,
void const *   
)

◆ CCC_private_adaptive_map_insert()

void * CCC_private_adaptive_map_insert ( struct CCC_Adaptive_map *  ,
struct CCC_Adaptive_map_node *   
)

◆ CCC_private_adaptive_map_key_in_slot()

void * CCC_private_adaptive_map_key_in_slot ( struct CCC_Adaptive_map const *  ,
void const *   
)

◆ CCC_private_adaptive_map_node_in_slot()

struct CCC_Adaptive_map_node * CCC_private_adaptive_map_node_in_slot ( struct CCC_Adaptive_map const *  ,
void const *   
)