claude is gud

1 files changed, 1026 insertions, 0 deletions

diff --git a/vere/pkg/ur/hashcons.c b/vere/pkg/ur/hashcons.c
new file mode 100644
index 0000000..ea2338b
--- /dev/null
+++ b/vere/pkg/ur/hashcons.c
@@ -0,0 +1,1026 @@
+/// @file
+
+#include "hashcons.h"
+
+#include <assert.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "defs.h"
+#include "murmur3.h"
+
+//  declarations of inline functions
+//
+uint64_t
+ur_met0_bytes_unsafe(uint64_t len, uint8_t *byt);
+
+static void*
+_oom(const char* cap, void* v)
+{
+  if ( !v ) {
+    fprintf(stderr,
+            "ur: hashcons: %s: allocation failed, out of memory\r\n", cap);
+    abort();
+  }
+
+  return v;
+}
+
+void
+ur_dict32_grow(ur_root_t *r, ur_dict32_t *dict, uint64_t prev, uint64_t size)
+{
+  ur_pail32_t *buckets, *old_buckets = dict->buckets;
+  uint8_t *fills, *old_fills = dict->fills;
+  uint64_t old_size = dict->size;
+  uint64_t  i, next = prev + size;
+
+  buckets = _oom("dict32_grow", calloc(next, sizeof(*buckets)));
+  fills = _oom("dict32_grow", calloc(next, sizeof(*fills)));
+
+  if ( old_buckets ) {
+    for ( i = 0; i < old_size; i++ ) {
+      ur_pail32_t *old_bucket = &(old_buckets[i]);
+      uint8_t     j, old_fill = old_fills[i];
+
+      for ( j = 0; j < old_fill; j++ ) {
+        uint32_t val = old_bucket->vals[j];
+        ur_nref  ref = old_bucket->refs[j];
+        ur_mug   mug = ur_nref_mug(r, ref);
+
+        uint64_t        idx = ( mug % next );
+        ur_pail32_t *bucket = &(buckets[idx]);
+        uint8_t    new_fill = fills[idx];
+
+        if ( ur_pail_max == new_fill ) {
+          free(buckets);
+          free(fills);
+          return ur_dict32_grow(r, dict, size, next);
+        }
+
+        bucket->refs[new_fill] = ref;
+        bucket->vals[new_fill] = val;
+        fills[idx] = 1 + new_fill;
+      }
+    }
+
+    free(old_buckets);
+    free(old_fills);
+  }
+
+  dict->prev = size;
+  dict->size = next;
+  dict->fills = fills;
+  dict->buckets = buckets;
+}
+
+ur_bool_t
+ur_dict32_get(ur_root_t *r, ur_dict32_t *dict, ur_nref ref, uint32_t *out)
+{
+  ur_mug   mug = ur_nref_mug(r, ref);
+  uint64_t idx = ( mug % dict->size );
+
+  ur_pail32_t *bucket = &(dict->buckets[idx]);
+  uint8_t     i, fill = dict->fills[idx];
+
+  for ( i = 0; i < fill; i++ ) {
+    if ( ref == bucket->refs[i] ) {
+      *out = bucket->vals[i];
+      return 1;
+    }
+  }
+
+  return 0;
+}
+
+void
+ur_dict32_put(ur_root_t *r, ur_dict32_t *dict, ur_nref ref, uint32_t val)
+{
+  ur_mug mug = ur_nref_mug(r, ref);
+
+  while ( 1 ) {
+    uint64_t        idx = ( mug % dict->size );
+    ur_pail32_t *bucket = &(dict->buckets[idx]);
+    uint8_t     i, fill = dict->fills[idx];
+
+    for ( i = 0; i < fill; i++ ) {
+      if ( ref == bucket->refs[i] ) {
+        bucket->vals[i] = val;
+        return;
+      }
+    }
+
+    if ( ur_pail_max == fill ) {
+      ur_dict32_grow(r, dict, dict->prev, dict->size);
+      continue;
+    }
+
+    bucket->refs[fill] = ref;
+    bucket->vals[fill] = val;
+    dict->fills[idx] = 1 + fill;
+    break;
+  }
+}
+
+void
+ur_dict32_wipe(ur_dict32_t *dict)
+{
+  uint8_t  *fills = dict->fills;
+  uint64_t   size = dict->size;
+
+  memset(fills, 0, sizeof(*fills) * size);
+}
+
+void
+ur_dict64_grow(ur_root_t *r, ur_dict64_t *dict, uint64_t prev, uint64_t size)
+{
+  ur_pail64_t *buckets, *old_buckets = dict->buckets;
+  uint8_t         *fills, *old_fills = dict->fills;
+  uint64_t old_size = dict->size;
+  uint64_t  i, next = prev + size;
+
+  buckets = _oom("dict64_grow", calloc(next, sizeof(*buckets)));
+  fills   = _oom("dict64_grow", calloc(next, sizeof(*fills)));
+
+  if ( old_buckets ) {
+    for ( i = 0; i < old_size; i++ ) {
+      ur_pail64_t *old_bucket = &(old_buckets[i]);
+      uint8_t     j, old_fill = old_fills[i];
+
+      for ( j = 0; j < old_fill; j++ ) {
+        uint64_t val = old_bucket->vals[j];
+        ur_nref  ref = old_bucket->refs[j];
+        ur_mug   mug = ur_nref_mug(r, ref);
+
+        uint64_t        idx = ( mug % next );
+        ur_pail64_t *bucket = &(buckets[idx]);
+        uint8_t    new_fill = fills[idx];
+
+        if ( ur_pail_max == new_fill ) {
+          free(buckets);
+          free(fills);
+          return ur_dict64_grow(r, dict, size, next);
+        }
+
+        bucket->refs[new_fill] = ref;
+        bucket->vals[new_fill] = val;
+        fills[idx] = 1 + new_fill;
+      }
+    }
+
+    free(old_buckets);
+    free(old_fills);
+  }
+
+  dict->prev = size;
+  dict->size = next;
+  dict->fills = fills;
+  dict->buckets = buckets;
+}
+
+ur_bool_t
+ur_dict64_get(ur_root_t *r, ur_dict64_t *dict, ur_nref ref, uint64_t *out)
+{
+  ur_mug   mug = ur_nref_mug(r, ref);
+  uint64_t idx = ( mug % dict->size );
+
+  ur_pail64_t *bucket = &(dict->buckets[idx]);
+  uint8_t     i, fill = dict->fills[idx];
+
+  for ( i = 0; i < fill; i++ ) {
+    if ( ref == bucket->refs[i] ) {
+      *out = bucket->vals[i];
+      return 1;
+    }
+  }
+
+  return 0;
+}
+
+void
+ur_dict64_put(ur_root_t *r, ur_dict64_t *dict, ur_nref ref, uint64_t val)
+{
+  ur_mug mug = ur_nref_mug(r, ref);
+
+  while ( 1 ) {
+    uint64_t        idx = ( mug % dict->size );
+    ur_pail64_t *bucket = &(dict->buckets[idx]);
+    uint8_t     i, fill = dict->fills[idx];
+
+    for ( i = 0; i < fill; i++ ) {
+      if ( ref == bucket->refs[i] ) {
+        bucket->vals[i] = val;
+        return;
+      }
+    }
+
+    if ( ur_pail_max == fill ) {
+      ur_dict64_grow(r, dict, dict->prev, dict->size);
+      continue;
+    }
+
+    bucket->refs[fill] = ref;
+    bucket->vals[fill] = val;
+    dict->fills[idx] = 1 + fill;
+    break;
+  }
+}
+
+void
+ur_dict64_wipe(ur_dict64_t *dict)
+{
+  uint8_t *fills = dict->fills;
+  uint64_t  size = dict->size;
+
+  memset(fills, 0, sizeof(*fills) * size);
+}
+
+void
+ur_dict_grow(ur_root_t *r, ur_dict_t *dict, uint64_t prev, uint64_t size)
+{
+  ur_pail_t *buckets, *old_buckets = dict->buckets;
+  uint8_t       *fills, *old_fills = dict->fills;
+  uint64_t old_size = dict->size;
+  uint64_t  i, next = prev + size;
+
+  buckets = _oom("dict_grow", calloc(next, sizeof(*buckets)));
+  fills = _oom("dict_grow", calloc(next, sizeof(*fills)));
+
+  if ( old_buckets ) {
+    for ( i = 0; i < old_size; i++ ) {
+      ur_pail_t *old_bucket = &(old_buckets[i]);
+      uint8_t   j, old_fill = old_fills[i];
+
+      for ( j = 0; j < old_fill; j++ ) {
+        ur_nref ref = old_bucket->refs[j];
+        ur_mug  mug = ur_nref_mug(r, ref);
+
+        uint64_t      idx = ( mug % next );
+        ur_pail_t *bucket = &(buckets[idx]);
+        uint8_t  new_fill = fills[idx];
+
+        if ( ur_pail_max == new_fill ) {
+          free(buckets);
+          free(fills);
+          return ur_dict_grow(r, dict, size, next);
+        }
+
+        bucket->refs[new_fill] = ref;
+        fills[idx] = 1 + new_fill;
+      }
+    }
+
+    free(old_buckets);
+    free(old_fills);
+  }
+
+  dict->prev = size;
+  dict->size = next;
+  dict->fills = fills;
+  dict->buckets = buckets;
+}
+
+ur_bool_t
+ur_dict_get(ur_root_t *r, ur_dict_t *dict, ur_nref ref)
+{
+  ur_mug   mug = ur_nref_mug(r, ref);
+  uint64_t idx = ( mug % dict->size );
+
+  ur_pail_t *bucket = &(dict->buckets[idx]);
+  uint8_t   i, fill = dict->fills[idx];
+
+  for ( i = 0; i < fill; i++ ) {
+    if ( ref == bucket->refs[i] ) {
+      return 1;
+    }
+  }
+
+  return 0;
+}
+
+void
+ur_dict_put(ur_root_t *r, ur_dict_t *dict, ur_nref ref)
+{
+  ur_mug mug = ur_nref_mug(r, ref);
+
+  while ( 1 ) {
+    uint64_t      idx = ( mug % dict->size );
+    ur_pail_t *bucket = &(dict->buckets[idx]);
+    uint8_t   i, fill = dict->fills[idx];
+
+    for ( i = 0; i < fill; i++ ) {
+      if ( ref == bucket->refs[i] ) {
+        return;
+      }
+    }
+
+    if ( ur_pail_max == fill ) {
+      ur_dict_grow(r, dict, dict->prev, dict->size);
+      continue;
+    }
+
+    bucket->refs[fill] = ref;
+    dict->fills[idx] = 1 + fill;
+    break;
+  }
+}
+
+void
+ur_dict_wipe(ur_dict_t *dict)
+{
+  uint8_t  *fills = dict -> fills;
+  uint64_t   size = dict->size;
+
+  memset(fills, 0, sizeof(*fills) * size);
+}
+
+void
+ur_dict_free(ur_dict_t *dict)
+{
+  free(dict->buckets);
+  free(dict->fills);
+  dict->buckets = 0;
+}
+
+ur_mug
+ur_mug_bytes(const uint8_t *byt, uint64_t len)
+{
+  uint32_t seed = 0xcafebabe;
+  uint8_t     i = 0;
+
+  while ( i < 8 ) {
+    ur_mug   mug;
+    uint32_t raw;
+    MurmurHash3_x86_32(byt, len, seed, &raw);
+    mug = (raw >> 31) ^ ( ur_mask_31(raw) );
+
+    if ( 0 == mug ) {
+      seed++; i++;
+    }
+    else {
+      return mug;
+    }
+  }
+
+  return (ur_mug)0x7fff;
+}
+
+ur_mug
+ur_mug32(uint32_t x)
+{
+  uint8_t byt[4] = {
+    ur_mask_8(x >>  0),
+    ur_mask_8(x >>  8),
+    ur_mask_8(x >> 16),
+    ur_mask_8(x >> 24)
+  };
+
+  return ur_mug_bytes(byt, ur_met3_32(x));
+}
+
+ur_mug
+ur_mug64(uint64_t x)
+{
+  uint8_t byt[8] = {
+    ur_mask_8(x >>  0),
+    ur_mask_8(x >>  8),
+    ur_mask_8(x >> 16),
+    ur_mask_8(x >> 24),
+    ur_mask_8(x >> 32),
+    ur_mask_8(x >> 40),
+    ur_mask_8(x >> 48),
+    ur_mask_8(x >> 56)
+  };
+
+  return ur_mug_bytes(byt, ur_met3_64(x));
+}
+
+ur_mug
+ur_mug_both(ur_mug hed, ur_mug tal)
+{
+  uint32_t  seed = 0xdeadbeef;
+  uint8_t    len = 4 + ur_bloq_up3(ur_met0_32(tal));
+  uint8_t      i = 0;
+  uint8_t byt[8] = {
+    ur_mask_8(hed >>  0),
+    ur_mask_8(hed >>  8),
+    ur_mask_8(hed >> 16),
+    ur_mask_8(hed >> 24),
+    ur_mask_8(tal >>  0),
+    ur_mask_8(tal >>  8),
+    ur_mask_8(tal >> 16),
+    ur_mask_8(tal >> 24)
+  };
+
+  while ( i < 8 ) {
+    ur_mug   mug;
+    uint32_t raw;
+    MurmurHash3_x86_32(byt, len, seed, &raw);
+    mug = (raw >> 31) ^ ( ur_mask_31(raw) );
+
+    if ( 0 == mug ) {
+      seed++; i++;
+    }
+    else {
+      return mug;
+    }
+  }
+
+  return (ur_mug)0xfffe;
+}
+
+ur_mug
+ur_nref_mug(ur_root_t *r, ur_nref ref)
+{
+  switch ( ur_nref_tag(ref) ) {
+    default: assert(0);
+
+    case ur_direct: return ur_mug64(ref);
+    case ur_iatom:  return r->atoms.mugs[ur_nref_idx(ref)];
+    case ur_icell:  return r->cells.mugs[ur_nref_idx(ref)];
+  }
+}
+
+ur_bool_t
+ur_deep(ur_nref ref)
+{
+  return ur_icell == ur_nref_tag(ref);
+}
+
+ur_nref
+ur_head(ur_root_t *r, ur_nref ref)
+{
+  assert( ur_deep(ref) );
+  return r->cells.heads[ur_nref_idx(ref)];
+}
+
+ur_nref
+ur_tail(ur_root_t *r, ur_nref ref)
+{
+  assert( ur_deep(ref) );
+  return r->cells.tails[ur_nref_idx(ref)];
+}
+
+void
+ur_atoms_grow(ur_atoms_t *atoms)
+{
+  uint64_t   prev = atoms->prev;
+  uint64_t   size = atoms->size;
+  uint64_t   next = prev + size;
+  uint8_t **bytes = atoms->bytes;
+  uint64_t  *lens = atoms->lens;
+  ur_mug    *mugs = atoms->mugs;
+
+  atoms->bytes = _oom("atoms_grow", malloc(next * ( sizeof(*atoms->bytes)
+                                                  + sizeof(*atoms->lens)
+                                                  + sizeof(*atoms->mugs) )));
+  atoms->lens  = (void*)((char*)atoms->bytes + (next * sizeof(*atoms->bytes)));
+  atoms->mugs  = (void*)((char*)atoms->lens  + (next * sizeof(*atoms->lens)));
+
+  if ( bytes ) {
+    memcpy(atoms->bytes, bytes, size * (sizeof(*bytes)));
+    memcpy(atoms->lens,   lens, size * (sizeof(*lens)));
+    memcpy(atoms->mugs,   mugs, size * (sizeof(*mugs)));
+
+    free(bytes);
+  }
+
+  atoms->prev = size;
+  atoms->size = next;
+}
+
+void
+ur_cells_grow(ur_cells_t *cells)
+{
+  uint64_t  prev = cells->prev;
+  uint64_t  size = cells->size;
+  uint64_t  next = prev + size;
+  ur_nref *heads = cells->heads;
+  ur_nref *tails = cells->tails;
+  ur_mug   *mugs = cells->mugs;
+
+  cells->heads = _oom("cells_grow", malloc(next * ( sizeof(*cells->heads)
+                                                  + sizeof(*cells->heads)
+                                                  + sizeof(*cells->mugs) )));
+  cells->tails = (void*)((char*)cells->heads + (next * sizeof(*cells->heads)));
+  cells->mugs  = (void*)((char*)cells->tails + (next * sizeof(*cells->tails)));
+
+  if ( heads ) {
+    memcpy(cells->heads, heads, size * (sizeof(*heads)));
+    memcpy(cells->tails, tails, size * (sizeof(*tails)));
+    memcpy(cells->mugs,   mugs, size * (sizeof(*mugs)));
+
+    free(heads);
+  }
+
+  cells->prev = size;
+  cells->size = next;
+}
+
+void
+ur_bytes(ur_root_t *r, ur_nref ref, uint8_t **byt, uint64_t *len)
+{
+  assert( !ur_deep(ref) );
+  switch ( ur_nref_tag(ref) ) {
+    default: assert(0);
+
+    case ur_direct: {
+      *len = ur_met3_64(ref);
+      //  XX little-endian
+      //
+      *byt = (uint8_t*)&ref;
+    } break;
+
+    case ur_iatom: {
+      uint64_t idx = ur_nref_idx(ref);
+      *len = r->atoms.lens[idx];
+      *byt = r->atoms.bytes[idx];
+    } break;
+  }
+}
+
+uint64_t
+ur_met(ur_root_t *r, uint8_t bloq, ur_nref ref)
+{
+  uint64_t m_bit;
+
+  //  XX return bool for cells, length in out parameter
+  //
+  assert( !ur_deep(ref) );
+
+  if ( ur_direct == ur_nref_tag(ref) ) {
+    m_bit = ur_met0_64(ref);
+  }
+  else {
+    uint64_t idx = ur_nref_idx(ref);
+    uint64_t len = r->atoms.lens[idx];
+    uint8_t *byt = r->atoms.bytes[idx];
+
+    m_bit = ur_met0_bytes_unsafe(len, byt);
+  }
+
+  switch ( bloq ) {
+    case 0: return m_bit;
+    case 1: return ur_bloq_up1(m_bit);
+    case 2: return ur_bloq_up2(m_bit);
+    case 3: return ur_bloq_up3(m_bit);
+
+    default: {
+      uint64_t m_byt = ur_bloq_up3(m_bit);
+      uint8_t    off = (bloq - 3);
+      return (m_byt + ((1ULL << off) - 1)) >> off;
+    }
+  }
+}
+
+static ur_nref
+_coin_unsafe(ur_atoms_t *atoms, ur_mug mug, uint64_t len, uint8_t *byt)
+{
+  uint64_t fill = atoms->fill;
+  ur_tag    tag = ur_iatom;
+  ur_nref   tom = ( fill | ((uint64_t)tag << 62) );
+
+  //  XX necessary?
+  //
+  assert( 62 >= ur_met0_64(fill) );
+
+  atoms->bytes[fill] = byt;
+  atoms->lens[fill]  = len;
+  atoms->mugs[fill]  = mug;
+  atoms->fill = 1 + fill;
+
+  return tom;
+}
+
+static ur_nref
+_cons_unsafe(ur_cells_t *cells, ur_mug mug, ur_nref hed, ur_nref tal)
+{
+  uint64_t fill = cells->fill;
+  ur_tag    tag = ur_icell;
+  ur_nref   cel = ( fill | ((uint64_t)tag << 62) );
+
+  //  XX necessary?
+  //
+  assert( 62 >= ur_met0_64(fill) );
+
+  cells->mugs[fill]  = mug;
+  cells->heads[fill] = hed;
+  cells->tails[fill] = tal;
+  cells->fill = 1 + fill;
+
+  return cel;
+}
+
+ur_nref
+ur_coin_bytes_unsafe(ur_root_t *r, uint64_t len, uint8_t *byt)
+{
+  ur_atoms_t *atoms = &(r->atoms);
+  ur_dict_t   *dict = &(atoms->dict);
+  ur_mug        mug = ur_mug_bytes(byt, len);
+
+  while ( 1 ) {
+    uint64_t      idx = ( mug % dict->size );
+    ur_pail_t *bucket = &(dict->buckets[idx]);
+    uint8_t i, b_fill = dict->fills[idx];
+    ur_nref tom;
+
+    for ( i = 0; i < b_fill; i++ ) {
+      uint8_t *t_byt;
+      uint64_t t_len;
+      tom = bucket->refs[i];
+
+      ur_bytes(r, tom, &t_byt, &t_len);
+
+      if (  (t_len == len)
+         && (0 == memcmp(t_byt, byt, len)) )
+      {
+        return tom;
+      }
+    }
+
+    if ( ur_pail_max == b_fill ) {
+      ur_dict_grow(r, dict, dict->prev, dict->size);
+      continue;
+    }
+
+    if ( atoms->fill == atoms->size ) {
+      ur_atoms_grow(atoms);
+    }
+
+    tom = _coin_unsafe(atoms, mug, len, byt);
+
+    bucket->refs[b_fill] = tom;
+    dict->fills[idx] = 1 + b_fill;
+
+    return tom;
+  }
+}
+
+ur_nref
+ur_coin_bytes(ur_root_t *r, uint64_t len, uint8_t *byt)
+{
+  //  strip trailing zeroes
+  //
+  while ( len && !byt[len - 1] ) {
+    len--;
+  }
+
+  //  produce a direct atom if possible
+  //
+  if ( 62 >= ur_met0_bytes_unsafe(len, byt) ) {
+    uint64_t i, direct = 0;
+
+    for ( i = 0; i < len; i++ ) {
+      direct |= byt[i] << (8 * i);
+    }
+
+    return (ur_nref)direct;
+  }
+  else {
+    uint8_t *copy = _oom("coin_bytes", malloc(len));
+    memcpy(copy, byt, len);
+
+    return ur_coin_bytes_unsafe(r, len, copy);
+  }
+}
+
+ur_nref
+ur_coin64(ur_root_t *r, uint64_t n)
+{
+  if ( ur_direct == ur_nref_tag(n) ) {
+    return n;
+  }
+  else {
+    uint8_t *byt;
+    assert( 8 == ur_met3_64(n) );
+
+    byt = _oom("coin64", malloc(8));
+
+    byt[0] = ur_mask_8(n);
+    byt[1] = ur_mask_8(n >>  8);
+    byt[2] = ur_mask_8(n >> 16);
+    byt[3] = ur_mask_8(n >> 24);
+    byt[4] = ur_mask_8(n >> 32);
+    byt[5] = ur_mask_8(n >> 40);
+    byt[6] = ur_mask_8(n >> 48);
+    byt[7] = ur_mask_8(n >> 56);
+
+    return ur_coin_bytes_unsafe(r, 8, byt);
+  }
+}
+
+ur_nref
+ur_cons(ur_root_t *r, ur_nref hed, ur_nref tal)
+{
+  ur_cells_t *cells = &(r->cells);
+  ur_dict_t   *dict = &(cells->dict);
+  ur_mug mug        = ur_mug_both(ur_nref_mug(r, hed),
+                                  ur_nref_mug(r, tal));
+
+  while ( 1 ) {
+    uint64_t      idx = ( mug % dict->size );
+    ur_pail_t *bucket = &(dict->buckets[idx]);
+    uint8_t i, b_fill = dict->fills[idx];
+    ur_nref cel;
+
+    for ( i = 0; i < b_fill; i++ ) {
+      cel = bucket->refs[i];
+
+      if (  (hed == ur_head(r, cel))
+         && (tal == ur_tail(r, cel)) )
+      {
+        return cel;
+      }
+    }
+
+    if ( ur_pail_max == b_fill ) {
+      ur_dict_grow(r, dict, dict->prev, dict->size);
+      continue;
+    }
+
+    if ( cells->fill == cells->size ) {
+      ur_cells_grow(cells);
+    }
+
+    cel = _cons_unsafe(cells, mug, hed, tal);
+
+    bucket->refs[b_fill] = cel;
+    dict->fills[idx] = 1 + b_fill;
+
+    return cel;
+  }
+}
+
+static void
+_print_memory(FILE *f, const char *c, uint64_t bytes)
+{
+  if ( !bytes ) {
+    fprintf(f, "%s: B/0\r\n", c);
+  }
+  else {
+    uint32_t g = (bytes / 1000000000);
+    uint32_t m = (bytes % 1000000000) / 1000000;
+    uint32_t k = (bytes % 1000000) / 1000;
+    uint32_t b = (bytes % 1000);
+
+    if ( g ) {
+      fprintf(f, "%s: GB/%d.%03d.%03d.%03d\r\n", c, g, m, k, b);
+    }
+    else if ( m ) {
+      fprintf(f, "%s: MB/%d.%03d.%03d\r\n", c, m, k, b);
+    }
+    else if ( k ) {
+      fprintf(f, "%s: KB/%d.%03d\r\n", c, k, b);
+    }
+    else if ( b ) {
+      fprintf(f, "%s: B/%d\r\n", c, b);
+    }
+  }
+}
+
+static uint64_t
+_dict_info(FILE *f, ur_dict_t *dict)
+{
+  uint64_t data = dict->size * sizeof(*dict->buckets);
+  _print_memory(f, "    dict", data);
+  return data;
+}
+
+static uint64_t
+_atoms_info(FILE *f, ur_atoms_t *atoms)
+{
+  uint64_t total = 0;
+  uint64_t  size = atoms->size;
+  uint64_t  fill = atoms->fill;
+  uint64_t  refs = size * ( sizeof(*atoms->bytes)
+                          + sizeof(*atoms->lens)
+                          + sizeof(*atoms->mugs) );
+  uint64_t i, data = 0;
+
+  fprintf(f, "  atoms (%" PRIu64 "):\r\n", fill);
+
+  _print_memory(f, "    refs", refs);
+  total += refs;
+
+  for ( i = 0; i < fill; i++ ) {
+    data += atoms->lens[i];
+  }
+  _print_memory(f, "    data", data);
+  total += data;
+
+  total += _dict_info(f, &(atoms->dict));
+  _print_memory(f, "  total", total);
+  return total;
+}
+
+static uint64_t
+_cells_info(FILE *f, ur_cells_t *cells)
+{
+  uint64_t total = 0;
+  uint64_t  size = cells->size;
+  uint64_t  fill = cells->fill;
+  uint64_t  refs = size * ( sizeof(*cells->heads)
+                          + sizeof(*cells->heads)
+                          + sizeof(*cells->mugs) );
+
+  fprintf(f, "  cells (%" PRIu64 "):\r\n", fill);
+
+  _print_memory(f, "    refs", refs);
+  total += refs;
+
+  total += _dict_info(f, &(cells->dict));
+  _print_memory(f, "  total", total);
+  return total;
+}
+
+void
+ur_root_info(FILE *f, ur_root_t *r)
+{
+  uint64_t total = 0;
+
+  fprintf(stderr, "hash-cons arena:\r\n");
+
+  {
+    uint64_t root = sizeof(*r);
+    _print_memory(f, "  root", root);
+    total += root;
+  }
+
+  total += _atoms_info(f, &(r->atoms));
+  total += _cells_info(f, &(r->cells));
+
+  _print_memory(f, "total", total);
+}
+
+static void
+_atoms_free(ur_atoms_t *atoms)
+{
+  uint8_t  **bytes = atoms->bytes;
+  uint64_t i, fill = atoms->fill;
+
+  for ( i = 0; i < fill; i++ ) {
+    free(bytes[i]);
+  }
+
+  ur_dict_free(&(atoms->dict));
+  free(bytes);
+}
+
+static void
+_cells_free(ur_cells_t *cells)
+{
+  ur_dict_free(&(cells->dict));
+  free(cells->heads);
+}
+
+void
+ur_root_free(ur_root_t *r)
+{
+  _atoms_free(&(r->atoms));
+  _cells_free(&(r->cells));
+  free(r);
+}
+
+ur_root_t*
+ur_root_init(void)
+{
+  ur_root_t *r = _oom("root_init", calloc(1, sizeof(*r)));
+
+  {
+    ur_dict_t *dict;
+
+    //  allocate atom storage
+    //
+    r->atoms.prev = ur_fib11;
+    r->atoms.size = ur_fib12;
+    ur_atoms_grow(&(r->atoms));
+
+    //  allocate atom hashtable
+    //
+    dict = &(r->atoms.dict);
+    ur_dict_grow(r, dict, ur_fib11, ur_fib12);
+
+    //  allocate cell storage
+    //
+    r->cells.prev = ur_fib11;
+    r->cells.size = ur_fib12;
+    ur_cells_grow(&(r->cells));
+
+    //  allocate cell hashtable
+    //
+    dict = &(r->cells.dict);
+    ur_dict_grow(r, dict, ur_fib11, ur_fib12);
+  }
+
+  return r;
+}
+
+void
+ur_nvec_free(ur_nvec_t *v)
+{
+  free(v->refs);
+}
+
+void
+ur_nvec_init(ur_nvec_t *v, uint64_t size)
+{
+  v->fill = 0;
+  v->refs = _oom("nvec_init", calloc(size, sizeof(ur_nref)));
+}
+
+/*
+**  define opaque struct ur_walk_fore_s (ie, ur_walk_fore_t)
+*/
+struct ur_walk_fore_s {
+  ur_root_t  *r;
+  uint32_t prev;
+  uint32_t size;
+  ur_nref  *top;
+};
+
+ur_walk_fore_t*
+ur_walk_fore_init_with(ur_root_t    *r,
+                       uint32_t s_prev,
+                       uint32_t s_size)
+{
+  ur_walk_fore_t *w = _oom("walk_fore", malloc(sizeof(*w)));
+  w->top = _oom("walk_fore", malloc(s_size * sizeof(*w->top)));
+  w->prev = s_prev;
+  w->size = s_size;
+  w->r    = r;
+
+  return w;
+}
+
+ur_walk_fore_t*
+ur_walk_fore_init(ur_root_t *r)
+{
+  return ur_walk_fore_init_with(r, ur_fib10, ur_fib11);
+}
+
+void
+ur_walk_fore_with(ur_walk_fore_t *w,
+                  ur_nref       ref,
+                  void           *v,
+                  void       (*atom)(ur_root_t*, ur_nref, void*),
+                  ur_bool_t  (*cell)(ur_root_t*, ur_nref, void*))
+{
+  ur_root_t  *r = w->r;
+  uint32_t fill = 1;
+
+  *w->top = ref;
+
+  do {
+    //  visit atom, pop stack
+    //
+    if ( !ur_deep(ref) ) {
+      atom(r, ref, v);
+      fill--;
+    }
+    //  visit cell, pop stack if false
+    //
+    else if ( !cell(r, ref, v) ) {
+      fill--;
+    }
+    //  push the tail, continue into the head
+    //
+    else {
+      w->top[fill++] = ur_tail(r, ref);
+
+      //  reallocate "stack" if full
+      //
+      if ( w->size == fill ) {
+        uint32_t next = w->prev + w->size;
+        w->top  = _oom("walk_fore", realloc(w->top, next * sizeof(*w->top)));
+        w->prev = w->size;
+        w->size = next;
+      }
+
+      w->top[fill] = ur_head(r, ref);
+    }
+
+    ref = w->top[fill];
+  } while ( fill );
+}
+
+void
+ur_walk_fore_done(ur_walk_fore_t *w)
+{
+  free(w->top);
+  free(w);
+}
+
+void
+ur_walk_fore(ur_root_t *r,
+             ur_nref  ref,
+             void      *v,
+             void      (*atom)(ur_root_t*, ur_nref, void*),
+             ur_bool_t (*cell)(ur_root_t*, ur_nref, void*))
+{
+  ur_walk_fore_t *w = ur_walk_fore_init(r);
+  ur_walk_fore_with(w, ref, v, atom, cell);
+  ur_walk_fore_done(w);
+}