Hi,

>I'm wondering how you decide between this array and a linked-list. The
>memory waste seems to be quite significant and an arena based
>linked-list should be much more efficient?

In my opinion it depends on how exactly you use the data later which
data structure is more efficient, but just regarding the memory
overhead it's worth keeping in mind that linked lists always have a
per-node overhead.

With a dynamic array that grows by a factor of 2, the memory overhead
is also a factor of 2, because all previous sizes are still around. If
the elements are 32bit ints as in the example, then that's probably not

---
 stdlib/collections/avl.nuj | 189 +++++++++++++++++++++++++++++++++++++
 tests/suite/avl-trees.nuj  |  20 ++++
 2 files changed, 209 insertions(+)
 create mode 100644 stdlib/collections/avl.nuj
 create mode 100644 tests/suite/avl-trees.nuj

diff --git a/stdlib/collections/avl.nuj b/stdlib/collections/avl.nuj
new file mode 100644
index 0000000..46be92c
--- /dev/null
+++ b/stdlib/collections/avl.nuj
@@ -0,0 +1,189 @@
+;; An avl tree is a balanced binary tree that stores a set of ordered keys.
[message trimmed]

This adds a hash table based lookup for symbols.  The existing structure
for symbols remains unchanged, and the hash table is merely added on
top.  That is, lSymbolList stores the actual symbols, lSymbolIndex
stores positions in lSymbolList.  lSymbolBackIndex goes in the opposite
direction, mapping positions in lSymbolList to positions in lSymbolIndex
which is needed to properly clean up the index in lSymbolFree.
lSymbolIndex can get away with a single int per slot in the hash table.
If the value is == 0, the slot is empty, if it's < 0 the symbol in the
slot was freed (and the slot can be reused), if it's > 0 the symbol in
the slot is in use.
In total lSymbolIndex and lSymbolBackIndex store 2 * SYM_MAX ints,
meaning they need 131kb of memory.
---
 lib/allocation/symbol.c | 73 ++++++++++++++++++++++++++++++++++++++---
[message trimmed]

---
 stdlib/collections/lists.nuj | 22 ++++++++++++++++++++++
 stdlib/tests/tests.nuj       | 10 ++++++++++
 2 files changed, 32 insertions(+)

diff --git a/stdlib/collections/lists.nuj b/stdlib/collections/lists.nuj
index 746debf..f1c7d3d 100644
--- a/stdlib/collections/lists.nuj
+++ b/stdlib/collections/lists.nuj
@@ -120,3 +120,25 @@
                               [set! next [cons [car l] next]]]
 			  [cdr! l]]
 		   [cons top [list/sort next]]]]]
+
[message trimmed]