flecs_datastructures_overview.c

// Summary of Flecs data structures
// This is a non-exhaustive overview of flecs datastructures. Things have been ommitted/have different names for clarity.


// --- DATASTRUCTURES

// A sparse set is a map-like structure that guarantees O(1) lookup times (as opposed to O(1) on average for maps) at the cost of
// requiring more RAM (more info on the general idea of sparse sets: https://www.geeksforgeeks.org/sparse-set/)
struct ecs_sparse_t { };

// A map is a structure that allows for O(1) lookups on average (similar to an std::unordered_map). The map only supports 
// uint64_t keys and uses a bitshift as hashing function.
struct ecs_map_t { };


// --- CORE TYPES

// An entity id is a 64 bit id
typedef uint64_t ecs_entity_t;

// An ecs_id_t encodes an id that can be added to an entity. For regular components this is the same as the entity id for
// that component, for relations the id can encode up to 2 component ids.
typedef uint64_t ecs_id_t;


// --- TABLE (ARCHETYPE) TYPES

// A storage contains the array with component data. The component data array is type erased, as the ECS cannot know 
// about application types beforehand.
struct ecs_storage_t {
  vector<T> component_data;
};

// Edge in the table graph that allows for finding the next table in an add/remove operation in constant time
struct ecs_table_edge_t {
  ecs_table_t *add;    // The table with the component added
  ecs_table_t *remove; // The table with the component removed
};

// A table is the Flecs implementation of an archetype. It stores component data for all entities with a certain combination
// of components.
struct ecs_table_t {
  int32_t table_id;
  vector<ecs_id_t> type; // Array with component ids
  vector<ecs_entity_t> entities; // Array with entity ids in table
  vector<ecs_storage_t> columns; // Component data. Each component has its own array (SoA)
  map<ecs_id_t, ecs_table_edge_t> edges; // Traverse to the next table by adding/removing a component
};


// --- ENTITY LOOKUP STRUCTURES

// This type is used to keep track of where an entity is stored
struct ecs_record_t {
  ecs_table_t *table; // The table where the entity is stored
  int32_t row; // The row (index in the component arrays) where the entity's data is
};


// The entity index makes it possible to find where an entity is stored from its entity id
ecs_sparse_t<ecs_entity_t, ecs_record_t> entity_index;


// --- TABLE LOOKUP STRUCTURES

// An id record stores a map with all tables for a specific component id
struct ecs_id_record_t {
  map<table_id, ecs_table_record_t> table_index;
};

// A table record is used to find where in a table a component is stored
struct ecs_table_record_t {
  int32_t column; // The column of the id (component) in the table
};

// The id index enables finding all tables for a given component id
map<ecs_id_t, ecs_id_record_t> id_index;


// --- COMMON OPERATIONS

// Test if entity "e" has component "comp"
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[comp];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;

// Get component "comp" for entity "e"
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[comp];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return r->table->columns[tr->column].component_data[r->row];

// Test if entity "e" has pair (Likes, Apples)
ecs_id_t pair = ecs_pair(Likes, Apples);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;

// Test if entity "e" has pair (Likes, *)
ecs_id_t pair = ecs_pair(Likes, EcsWildcard);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;

// Find all instances of pair (Likes, *) for entity "e"
ecs_id_t pair = ecs_pair(Likes, EcsWildcard);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
for (i = tr->column; i < (tr->column + tr->count); i ++) {
  yield r->table->type[i];
}

// Find all entities for component "comp"
ecs_id_record_t *idr = id_index[comp];
for (table : idr->table_index) {
  for (e : table->entities) {
    yield e;
  }
}


// Find all entities for components "pos, vel"
ecs_id_record_t *idr_pos = id_index[pos];
ecs_id_record_t *idr_vel = id_index[vel];

for (table : idr_pos->table_index) {
  if (!idr_vel->table_index.has(table->id)) {
    continue;
  }
  for (e : table->entities) {
    yield e;
  }
}

// Find all entities for wildcard (Likes, *), (Eats, Apples)
ecs_id_t pair_likes = ecs_pair(Likes, EcsWildcard);
ecs_id_t pair_eats = ecs_pair(Eats, Apples);
ecs_id_record_t *idr_likes = id_index[pair_likes];
ecs_id_record_t *idr_eats = id_index[pair_eats];

for (table : idr_likes->table_index) {
  if (!idr_eats->table_index.has(table->id)) {
    continue;
  }
  for (e : table->entities) {
    yield e;
  }
}

// Delete all entities with (ChildOf, parent)
ecs_id_t pair_childof = ecs_pair(EcsChildOf, parent);
ecs_id_record_t *idr_childof = id_index[pair_childof];
for (table : idr_childof->table_index) {
  delete(table);
}
id_index.erase(pair_childof);