x-alist.h File Reference

Association list interface. More...

#include "x-obj.h"

Go to the source code of this file.

Functions
Linear Association List
Extend and search association lists using linear traversal.
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)
BST Association List
Binary-search-tree index over alist entries, keyed by symbol pointer. Node structure: (entry . (left . right)).
x_obj_t *	x_alist_bst_lookup (x_obj_t *p_base, x_obj_t *p_tree, x_obj_t *p_sym)
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 interface.

Provides linear and BST-backed association list operations for the environment model. An alist is a list of (key . value) entries; the BST variant indexes those entries by symbol pointer for faster lookup.

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

x_alist_assoc()

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

Look up a symbol in an alist by linear scan.

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
	)

Insert an entry into a BST alist.

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
	)

Find an entry in a BST alist by symbol pointer.

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 entry to an alist.

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