RDIC/rdic.h

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 */