zelaven
/
RDIC
1
0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
39 Commits
1 Branch
992 KiB
 
 
Branch: master
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
RDIC/rdic.h

435 lines
11 KiB
Raw Permalink Blame History

typedef struct RDIC_Node RDIC_Node;
struct RDIC_Node {
unsigned int generation;
RDIC_Node *parent; // Ease of access.
RDIC_Node *sibling;
RDIC_Node *first_child;
//RDIC_Node *last_child; // Ease of access.
//RDIC_Node *previous_sibling; // Ease of access.
#if 0
NOTE(Zelaven):
Pre-order traversal is self-then-first_child.
Post-order traversal is first_child-then-self.
The sibling always comes last.
#endif
};
typedef struct {
RDIC_Node *node;
unsigned int generation;
} RDIC_Node_Reference;
// IDEA(Zelaven): Can the node reference hold only the pointer, and the pointed-to node hold a back-pointer to the reference?
// There is only one valid reference at a time, so the reference validity should be easy to determine without use of generations.
// NOTE(Zelaven): This idea is bad because it assumes that a reference won't be reallocated. Generations are much more reliable.
typedef struct {
RDIC_Node *head;
} RDIC_Freelist;
typedef struct {
RDIC_Node *root;
RDIC_Freelist *freelist;
RDIC_Node *current_parent;
RDIC_Node *frame_current_node;
} RDIC_Context;
static inline int rdic_node_references_equal(
RDIC_Node_Reference n,
RDIC_Node_Reference m)
{
return (n.node == m.node) && (n.generation == m.generation);
}
static inline int rdic_node_reference_valid(
RDIC_Node_Reference n)
{
return (n.node != NULL) && (n.generation == n.node->generation);
}
enum {
RDIC_GET_NODE__NODES_COLLECTED = 1 << 0,
RDIC_GET_NODE__NODE_ALLOCATED = 1 << 1,
RDIC_GET_NODE__OUT_OF_FREELIST = 1 << 2,
};
void rdic_cull_subtrees(
RDIC_Context context[static 1],
RDIC_Node *subtree);
RDIC_Node_Reference rdic_context_start_frame(
RDIC_Context context[static 1],
RDIC_Node_Reference last_root);
int rdic_context_finish_frame(
RDIC_Context context[static 1]);
RDIC_Node_Reference rdic_get_node(
RDIC_Context context[static 1],
RDIC_Node_Reference node_reference,
int *out_flags); // NOTE(Zelaven): NULL-safe.
void rdic_push_parent(
RDIC_Context context[static 1],
RDIC_Node_Reference parent);
int rdic_pop_parent(
RDIC_Context context[static 1]);
#ifndef NULL
#warning "NULL not defined. Please define NULL or include stddef."
#define NULL ((void*)0)
#endif
#ifdef RDIC_IMPLEMENTATION
// TODO(Zelaven): Offer a macro that enables runtime NULL-guards.
// ---
/* *** Information for those reading this source ***
* Procedure parameters such as `RDIC_Context context[static 1]` may look
* strange, but they aren't as evil as they look. Arrays degrade to pointers,
* and the static keyword simply requires that the array has a minimum size. In
* this case we use this to pass a pointer that may not be NULL. Note that this
* is just a compile time check and guard clauses for runtime NULL can still
* make plenty of sense.
*/
void rdic_cull_subtrees(
RDIC_Context context[static 1],
RDIC_Node *subtree)
{
assert(context != NULL);
// NOTE(Zelaven):
// This code collects an entire subtree.
// It requires that the initial node has a NULL sibling to limit its
// operation to only the subtree.
// The way it operates is that it uses the parent pointers to maintain a
// stack of "collect later" whenever a node in the tree has a sibling.
// When a subtree is finished it "pops" an element from the stack and
// continues collection from there.
RDIC_Node *current = subtree;
// NOTE(Zelaven): Top of our "stack" of "collect later".
RDIC_Node *stashed = NULL;
while(current != NULL)
{
RDIC_Node *next = NULL;
if(current->first_child != NULL)
{
if(current->sibling != NULL)
{
// Has both a child and a sibling - we need to save one for later.
// We "push" the sibling onto our "stack".
current->sibling->parent = stashed;
stashed = current->sibling;
}
// We always take the child as the next node.
next = current->first_child;
}
else if(current->sibling != NULL)
{
// No child but we have a sibling, then we just continue with the sibling.
next = current->sibling;
}
else
{
// A node with no child and no sibling. Time to "pop" from out "stack".
next = stashed;
if(stashed != NULL)
{
stashed = stashed->parent;
}
}
current->sibling = context->freelist->head;
current->generation += 1; // Invalidate references.
context->freelist->head = current;
current = next;
}
}
// ---
RDIC_Node_Reference rdic_context_start_frame(
RDIC_Context context[static 1],
RDIC_Node_Reference last_root)
{
RDIC_Node_Reference node_reference = last_root;
int need_new_node = (last_root.node == NULL)
|| (last_root.generation != last_root.node->generation);
int can_get_node_from_freelist =
(context->freelist == NULL || context->freelist->head == NULL);
if(need_new_node && can_get_node_from_freelist)
{
return (RDIC_Node_Reference){0};
}
if(need_new_node)
{
RDIC_Node_Reference result;
result.node = context->freelist->head;
result.generation = result.node->generation;
context->freelist->head = context->freelist->head->sibling;
RDIC_Node *root = result.node;
root->sibling = NULL;
root->parent = root;
node_reference = result;
}
context->frame_current_node = node_reference.node;
context->root = node_reference.node;
context->current_parent = context->root;
return node_reference;
}
// TODO(Zelaven): This is almost 1-1 with pop_parent, so consider compression.
// TODO(Zelaven): pop parents until it gets to a node that is a child of the
// root. This is so that all the stragglers of partial parents can be collected.
int rdic_context_finish_frame(
RDIC_Context context[static 1])
{
assert(context->current_parent == context->root);
RDIC_Node *last_root_child = NULL;
RDIC_Node *first_straggler = NULL;
if(context->frame_current_node == context->root)
{
last_root_child = context->root->first_child;
first_straggler = last_root_child;
}
else
{
last_root_child = context->frame_current_node;
first_straggler = last_root_child->sibling;
last_root_child->sibling = NULL;
}
int nodes_collected = 0;
if(last_root_child == NULL)
{
return 0;
}
assert(last_root_child->parent == context->root);
if(first_straggler != NULL)
{
rdic_cull_subtrees(context, first_straggler);
RDIC_Node *root = context->root;
if(first_straggler == root->first_child)
{
root->first_child = NULL;
}
nodes_collected = RDIC_GET_NODE__NODES_COLLECTED;
}
return nodes_collected;
}
// ---
RDIC_Node_Reference rdic_get_node(
RDIC_Context context[static 1],
RDIC_Node_Reference node_reference,
int *out_flags) // NOTE(Zelaven): NULL-safe.
{
//assert(context->current_parent != NULL);
if(context->current_parent == NULL)
{
return (RDIC_Node_Reference){0};
}
int reference_is_valid =
(node_reference.node != NULL)
&& (node_reference.generation == node_reference.node->generation);
int first_node_of_parent =
(context->current_parent == context->frame_current_node);
// NOTE(Zelaven): If the node is being moved to another parent, then we want
// to invalidate it to ensure consistent behavior.
reference_is_valid =
reference_is_valid
&& (context->current_parent == node_reference.node->parent);
if(!reference_is_valid && context->freelist->head == NULL)
{
if(out_flags != NULL)
{
*out_flags = RDIC_GET_NODE__OUT_OF_FREELIST;
}
return (RDIC_Node_Reference){0};
}
if(reference_is_valid)
{
RDIC_Node *subroot_to_cull = NULL;
if(first_node_of_parent)
{
// NOTE(Zelaven): Here I need to collect any preceding stale nodes.
subroot_to_cull = context->current_parent->first_child;
context->frame_current_node = node_reference.node;
context->current_parent->first_child = node_reference.node;
}
else
{
// NOTE(Zelaven): Skip (and collect) nodes between last and new nodes.
subroot_to_cull = context->frame_current_node->sibling;
context->frame_current_node->sibling = node_reference.node;
context->frame_current_node = node_reference.node;
}
if(subroot_to_cull != node_reference.node)
{
if(out_flags != NULL)
{
*out_flags = RDIC_GET_NODE__NODES_COLLECTED;
}
}
while(subroot_to_cull != node_reference.node)
{
// NOTE(Zelaven): Here we want to cull a subtree at a time because we are
// only skipping a certain quantity subtrees.
// TODO(Zelaven): Would it be preferable to "detach" the last node to cull
// and just to a single call to rdic_cull_subtrees?
// It really depends on what is faster, so that is profiling territory.
RDIC_Node *current = subroot_to_cull;
subroot_to_cull = subroot_to_cull->sibling;
current->sibling = NULL;
rdic_cull_subtrees(context, current);
}
}
else if(!reference_is_valid)
{
RDIC_Node_Reference new_reference = {0};
{ // Make new node
// NOTE(Zelaven): We guard against empty freelist, so this is safe.
RDIC_Node_Reference result = {0};
result.node = context->freelist->head;
result.generation = result.node->generation;
context->freelist->head = context->freelist->head->sibling;
// TODO(Zelaven): Should the various fields be filled out here, or outside?
// What will be the strategy to avoid redundant work?
// Doing it here certainly could avoid redundant work, assuming that all
// the styling and other fields will stay stable across frames.
// That will likely be the common case, but it may be necessary to expose
// reference_is_valid to the caller, so that the caller can decide if it
// should be used to avoid redundancy of work, whatever that means for
// the given node.
// I suppose that the caller can already determine that by comparing the
// last_reference with the new_reference, and if they are different then
// all work must be done.
new_reference = result;
}
RDIC_Node *new_node = new_reference.node;
if(first_node_of_parent)
{
RDIC_Node *parent = context->current_parent;
RDIC_Node *former_first_child = parent->first_child;
parent->first_child = new_node;
new_node->sibling = former_first_child;
new_node->parent = parent;
}
else
{
RDIC_Node *current = context->frame_current_node;
RDIC_Node *old_sibling = current->sibling;
current->sibling = new_node;
new_node->sibling = old_sibling;
new_node->parent = context->current_parent;
}
new_node->first_child = NULL;
context->frame_current_node = new_node;
node_reference = new_reference;
if(out_flags != NULL)
{
*out_flags = RDIC_GET_NODE__NODE_ALLOCATED;
}
}
return node_reference;
}
// ---
void rdic_push_parent(
RDIC_Context context[static 1],
RDIC_Node_Reference parent)
{
//assert(parent.node != NULL);
if(parent.node == NULL)
{
return;
}
context->current_parent = parent.node;
}
int rdic_pop_parent(
RDIC_Context context[static 1])
{
RDIC_Node *current_parent = context->current_parent;
RDIC_Node *last_child = NULL;
RDIC_Node *first_straggler = NULL;
if(context->frame_current_node == context->current_parent)
{
last_child = current_parent->first_child;
first_straggler = last_child;
}
else
{
last_child = context->frame_current_node;
first_straggler = last_child->sibling;
last_child->sibling = NULL;
}
int nodes_collected = 0;
if(last_child != NULL)
{
assert(last_child->parent == context->current_parent);
if(first_straggler != NULL)
{
rdic_cull_subtrees(context, first_straggler);
if(first_straggler == current_parent->first_child)
{
current_parent->first_child = NULL;
}
nodes_collected = RDIC_GET_NODE__NODES_COLLECTED;
}
}
context->frame_current_node = context->current_parent;
context->current_parent = context->current_parent->parent;
assert(context->current_parent != NULL);
return nodes_collected;
}
#endif /* RDIC_IMPLEMENTATION */