x-alist.c File Reference

Association list and persistent BST operations. More...

#include "x-alist.h"
#include "x-eval.h"
#include "x-type/symbol.h"

Functions
x_obj_t *	x_alist_extend (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_alist_assoc (x_obj_t *p_base, x_obj_t *p_args)
x_obj_t *	x_alist_bst_lookup (x_obj_t *p_base, x_obj_t *p_tree, x_obj_t *p_sym)
static x_obj_t *	bst_pair (x_obj_t *p_base, x_obj_t *a, x_obj_t *b)
x_obj_t *	x_alist_bst_insert (x_obj_t *p_base, x_obj_t *p_tree, x_obj_t *p_entry)

Detailed Description

Association list and persistent BST operations.

Author

Jon Ruttan (jonru.nosp@m.ttan.nosp@m.@gmai.nosp@m.l.co.nosp@m.m)

Copyright

2021 Jon Ruttan @license MIT No Attribution (MIT-0)

Function Documentation

bst_pair()

static x_obj_t * bst_pair ( x_obj_t *  p_base, x_obj_t *  a, x_obj_t *  b  )

static

Create a SHARED pair immune to GC sweep.

BST nodes are structural – the global env tree lives for the base's lifetime and is reachable only through this tree, so its nodes must not be collected.

Parameters

p_base	x_obj_t* – Base (execution context)
a	x_obj_t* – First element
b	x_obj_t* – Rest element

Returns

x_obj_t* – New pair with X_OBJ_FLAG_SHARED set

x_alist_assoc()

x_obj_t * x_alist_assoc	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Linear alist lookup by pointer identity on the key's first field.

Walks the alist front-to-back, comparing (first (first (first entry))) against (first obj). Returns the first matching entry, or NULL.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – (key . (alist))

Returns

x_obj_t* – Matching alist entry, or NULL if not found

x_alist_bst_insert()

x_obj_t * x_alist_bst_insert	(	x_obj_t *	p_base,
		x_obj_t *	p_tree,
		x_obj_t *	p_entry
	)

In-place BST insert into the global env tree.

MUTATES the tree in place; every environment whose chain reaches the root sees the new entry, which is required: a top-level (def ...) must become visible to fn closures created before it. The key is the symbol object: an entry for the SAME object replaces the old one, and an entry for a same-spelled but different object – one interned in another base – is another name and gets its own node, to the right of the first, the side lookup takes for an equal spelling that is not the same object. The returned root equals the input root except when the tree was empty (the caller must then store the returned first node).

Note

NOT path-copying. The previous implementation returned a new root and left the old one unchanged; that made every closure created before an insertion silently miss any later top-level def, so it was replaced by in-place mutation (see the body comment below). New nodes are allocated via bst_pair(), which sets X_OBJ_FLAG_SHARED so the long-lived tree is never swept.

Parameters

p_base	x_obj_t* – Base (execution context)
p_tree	x_obj_t* – Existing BST root, or NULL for empty
p_entry	x_obj_t* – (symbol . value) entry to insert

Returns

x_obj_t* – The tree root (a fresh node only when p_tree was empty)

See also

x_alist_bst_lookup

x_env_bind

x_alist_bst_lookup()

x_obj_t * x_alist_bst_lookup	(	x_obj_t *	p_base,
		x_obj_t *	p_tree,
		x_obj_t *	p_sym
	)

BST lookup by symbol identity.

Searches the tree for the entry whose key IS p_sym. A hit is pointer equality and nothing else: names are found by identity, not by spelling, so a same-spelled symbol interned in another base is another name and misses. The spelling only steers the walk – smaller to the left, greater to the right, and an equal spelling that is not the same object counts as greater, which is where x_alist_bst_insert put it. Node structure: (entry . (left . right)).

Parameters

p_base	x_obj_t* – Base (execution context)
p_tree	x_obj_t* – BST root node, or NULL
p_sym	x_obj_t* – Symbol to look up

Returns

x_obj_t* – Matching alist entry, or NULL if not found

See also

x_alist_bst_insert

x_alist_extend()

x_obj_t * x_alist_extend	(	x_obj_t *	p_base,
		x_obj_t *	p_args
	)

Prepend an association to an alist.

Conses p_assoc onto the front of p_alist, returning the new list.

Parameters

p_base	x_obj_t* – Base (execution context)
p_args	x_obj_t* – (assoc . alist)

Returns

x_obj_t* – New alist with assoc prepended