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 "private_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
 
union  CCC_Adaptive_map_entry_wrap
 

Macros

#define CCC_private_adaptive_map_initialize( private_struct_name, private_node_node_field, private_key_node_field, private_key_comparator, private_allocate, private_context_data)
 
#define CCC_private_adaptive_map_from( private_type_intruder_field_name, private_key_field_name, private_compare, private_allocate, private_destroy, private_context_data, private_compound_literal_array...)
 
#define CCC_private_adaptive_map_new(adaptive_map_entry)
 
#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, type_compound_literal...)
 
#define CCC_private_adaptive_map_and_modify_with(adaptive_map_entry_pointer, type_name, closure_over_T...)
 
#define CCC_private_adaptive_map_or_insert_with(adaptive_map_entry_pointer, type_compound_literal...)
 
#define CCC_private_adaptive_map_insert_entry_with(adaptive_map_entry_pointer, type_compound_literal...)
 
#define CCC_private_adaptive_map_try_insert_with(adaptive_map_pointer, key, type_compound_literal...)
 
#define CCC_private_adaptive_map_insert_or_assign_with( adaptive_map_pointer, key, 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,
  type_name,
  closure_over_T... 
)
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->private; \
if (private_adaptive_map_mod_ent.entry.status \
& CCC_ENTRY_OCCUPIED) \
{ \
type_name *const T = private_adaptive_map_mod_ent.entry.type; \
if (T) \
{ \
closure_over_T \
} \
} \
} \
private_adaptive_map_mod_ent; \
}))
CCC_Adaptive_map_entry
Definition: private_adaptive_map.h:93
CCC_Adaptive_map_entry::entry
struct CCC_Entry entry
Definition: private_adaptive_map.h:97
CCC_Entry::type
void * type
Definition: private_types.h:55
CCC_Entry::status
enum CCC_Entry_status status
Definition: private_types.h:57

◆ CCC_private_adaptive_map_from

#define CCC_private_adaptive_map_from (   private_type_intruder_field_name,
  private_key_field_name,
  private_compare,
  private_allocate,
  private_destroy,
  private_context_data,
  private_compound_literal_array... 
)

◆ CCC_private_adaptive_map_initialize

#define CCC_private_adaptive_map_initialize (   private_struct_name,
  private_node_node_field,
  private_key_node_field,
  private_key_comparator,
  private_allocate,
  private_context_data 
)
Value:
{ \
.root = NULL, \
.allocate = (private_allocate), \
.compare = (private_key_comparator), \
.context = (private_context_data), \
.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), \
}

◆ 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,
  type_compound_literal... 
)
Value:
(__extension__({ \
typeof(type_compound_literal) *private_adaptive_map_new_ins_base \
= CCC_private_adaptive_map_new((&om_insert_entry)); \
om_insert_entry_ret = (struct CCC_Entry){ \
.type = private_adaptive_map_new_ins_base, \
.status = CCC_ENTRY_INSERT_ERROR, \
}; \
if (private_adaptive_map_new_ins_base) \
{ \
*((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)
Definition: private_adaptive_map.h:211
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
Definition: private_types.h:53

◆ CCC_private_adaptive_map_insert_entry_with

#define CCC_private_adaptive_map_insert_entry_with (   adaptive_map_entry_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,
  type_compound_literal... 
)

◆ CCC_private_adaptive_map_new

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

◆ CCC_private_adaptive_map_or_insert_with

#define CCC_private_adaptive_map_or_insert_with (   adaptive_map_entry_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; \
if (private_or_ins_entry_pointer) \
{ \
if (private_or_ins_entry_pointer->private.entry.status \
== CCC_ENTRY_OCCUPIED) \
{ \
private_or_ins_ret \
= private_or_ins_entry_pointer->private.entry.type; \
} \
else \
{ \
private_or_ins_ret = CCC_private_adaptive_map_new( \
&private_or_ins_entry_pointer->private); \
CCC_private_adaptive_map_insert_key_val( \
&private_or_ins_entry_pointer->private, \
private_or_ins_ret, type_compound_literal); \
} \
} \
private_or_ins_ret; \
}))

◆ CCC_private_adaptive_map_try_insert_with

#define CCC_private_adaptive_map_try_insert_with (   adaptive_map_pointer,
  key,
  type_compound_literal... 
)
Value:
(__extension__({ \
__auto_type private_try_ins_map_pointer = (adaptive_map_pointer); \
struct CCC_Entry private_adaptive_map_try_ins_ent_ret \
= {.status = CCC_ENTRY_ARGUMENT_ERROR}; \
if (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, 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 *   
)