cons_node.c File Reference

Implements functions for manipulating cons nodes. More...

#include <cons_node.h>

Include dependency graph for cons_node.c:

Go to the source code of this file.

Macros
#define	NODE_FROM_CELL(_cell_)   ((struct cons_node *)((char *)(_cell_) - offsetof(struct cons_node, cell)))

Functions
static struct cons_node *	node_from_cell (struct cons *cell)
struct cons_node *	cons_car_node (struct cons_node *node)
	Accessor for the parent node (super-node) of a cons node.
struct cons_node *	cons_cdr_node (struct cons_node *node)
	Accessor for the next sibling node of a cons node.
struct cons_node *	cons_sub_node (struct cons_node *node)
	Accessor for the first child node (sub-node) of a cons node.
struct cons_node *	cons_node (struct cons_node *sub, struct cons_node *super)
	Constructs a cons node with the specified sub-node and new super-node.

Detailed Description

Implements functions for manipulating cons nodes.

This file implements functions for working with cons nodes, which are a specialised data structure built on top of cons cells. The functions allow for constructing a tree of cons nodes, where each node can have a parent (super-node) and a list of children (sub-nodes). The operations include linking and unlinking nodes in the tree structure, as well as accessing the parent and child nodes.

Definition in file cons_node.c.

Macro Definition Documentation

NODE_FROM_CELL

#define NODE_FROM_CELL

(

_cell_

)

((struct cons_node *)((char *)(_cell_) - offsetof(struct cons_node, cell)))

Definition at line 26 of file cons_node.c.

Function Documentation

cons_car_node()

struct cons_node * cons_car_node

(

struct cons_node *

node

)

Accessor for the parent node (super-node) of a cons node.

Parameters

node	The cons node to access.

Return values

Pointer

to the parent node, or NULL if there is no parent.

Retrieves the parent node from the car field of the cons cell.

Definition at line 36 of file cons_node.c.

{ return (struct cons_node *)cons_car(&node->cell); }

cons_cdr_node()

struct cons_node * cons_cdr_node

(

struct cons_node *

node

)

Accessor for the next sibling node of a cons node.

Parameters

node	The cons node to access.

Returns

Pointer to the next sibling node, or NULL if there is no next sibling node.

Note

The next sibling node is stored in the cdr field of the node's cell. Up-casts the cdr field of the cons cell to a pointer to a node.

Definition at line 38 of file cons_node.c.

{ return node_from_cell(cons_cdr(&node->cell)); }

cons_node()

struct cons_node * cons_node	(	struct cons_node *	sub,
		struct cons_node *	super
	)

Constructs a cons node with the specified sub-node and new super-node.

Parameters

sub	The sub-node to be linked.
super	The new super-node to be linked.

Returns

Pointer to the super cons node for chaining.

Definition at line 45 of file cons_node.c.

                                                                            {
  /*
   * Prevent a node from being its own super-node. Avoids creating a
   * cycle in the tree, which would lead to undefined behaviour when
   * traversing. If the sub-node is the same as the super-node, the
   * function does not modify the tree structure.
   */
  if (sub == super)
    return super;
  struct cons_node *car = cons_car_node(sub);
  if (car != NULL) {
    /*
     * The sub-node already has a super-node. Remove the sub-node from
     * the list of sub-nodes of the current super-node. Remove it even
     * if the current super-node is the same as the new super-node,
     * because the sub-node may be in a different position in the list
     * of sub-nodes of the new super-node when re-constructing the same
     * sub-super linkage.
     */
    (void)cons_remove(&car->head, &sub->cell);
    cons_rplaca(&sub->cell, NULL);
  }
  if (super != NULL) {
    /*
     * The new super-node is not NULL. Prepend the sub-node to the list
     * of sub-nodes of the new super-node. Set the car field of the
     * sub-node to point to the new super-node.
     *
     * This could be redundant if the sub-node is already a sub-node of
     * the new super-node, but it is simpler to just do it
     * unconditionally than to check for that case.
     */
    (void)cons(&super->head, &sub->cell);
    cons_rplaca(&sub->cell, super);
  }
  return super;
}

cons_sub_node()

struct cons_node * cons_sub_node

(

struct cons_node *

node

)

Accessor for the first child node (sub-node) of a cons node.

Parameters

node	The cons node to access.

Returns

Pointer to the first child node, or NULL if there are no child nodes.

Note

The first child node is stored in the head field of the cons node. Up-casts the head field to a pointer to a node.

Definition at line 40 of file cons_node.c.

{ return node_from_cell(node->head); }

node_from_cell()

static struct cons_node * node_from_cell ( struct cons *  cell )

inlinestatic

Definition at line 34 of file cons_node.c.

{ return CONS_NOT_NIL_P(cell) ? NODE_FROM_CELL(cell) : NULL; }