 
   ## Dict-wide functions
 
-  defp dict_get(ordered(bucket: bucket), key) when is_list(bucket) do
+  defp dict_get(ordered(bucket: bucket), key) do
     :lists.keyfind(key, 1, bucket)
   end
 
-  defp dict_get(bucketed(buckets: buckets), key) do
+  defp dict_get(trie(root: root, depth: depth), key) do
+    :lists.keyfind(key, 1, node_bucket(root, depth, bucket_hash(key)))
+  end
+
+  defp dict_fold(ordered(bucket: bucket), acc, fun) do
+    bucket_fold(bucket, acc, fun)
+  end
+
+  defp dict_fold(trie(root: root, depth: depth), acc, fun) do
+    node_fold(root, depth, acc, fun, @node_size)
+  end
+
+  defp dict_put(ordered(size: @ordered_threshold, bucket: bucket), key, value) do
+    root = node_relocate(bucket, 0)
+    dict_put(trie(size: @ordered_threshold, root: root), key, value)
+  end
+
+  defp dict_put(ordered(size: size, bucket: bucket) = dict, key, value) do
+    { new, count } = bucket_put(bucket, key, value)
+    { ordered(dict, size: size + count, bucket: new), count }
+  end
+
+  defp dict_put(trie(root: root, depth: depth, size: size, expand_on: size, contract_on: contract_on) = dict, key, value) do
+    root = node_expand(root, depth, depth + 1)
+    dict = trie(dict, root: root, depth: depth + 1,
+      expand_on: size * @node_size, contract_on: contract_on * @node_size)
+    dict_put(dict, key, value)
+  end
+
+  defp dict_put(trie(root: root, size: size, depth: depth) = dict, key, value) do
     pos = bucket_hash(key)
-    :lists.keyfind(key, 1, elem(buckets, pos))
-  end
-
-  defp dict_get(segmented(segments: segments) = dict, key) do
-    slot   = bucket_slot(dict, key)
-    bucket = segments_get(segments, slot)
-    :lists.keyfind(key, 1, bucket)
-  end
-
-  defp dict_fold(ordered(bucket: bucket), acc, fun) when is_list(bucket) do
-    bucket_fold(bucket, acc, fun)
-  end
-
-  defp dict_fold(bucketed(buckets: segment), acc, fun) do
-    segment_fold(segment, acc, fun, @segment_size)
-  end
-
-  defp dict_fold(segmented(segments: segments), acc, fun) do
-    segments_fold(segments, acc, fun, tuple_size(segments))
-  end
-
-  defp dict_put(ordered(size: size, bucket: bucket) = dict, key, value) when is_list(bucket) do
-    case bucket_put(bucket, key, value) do
-      { new_bucket, 0 } ->
-        { ordered(dict, bucket: new_bucket), 0 }
-      { new_bucket, 1 } ->
-        if size == @ordered_threshold do
-          buckets = rehash_bucket(new_bucket, @segment_template)
-          { bucketed(size: size + 1, buckets: buckets), 1 }
-        else
-          { ordered(dict, size: size + 1, bucket: new_bucket), 1 }
-        end
-    end
-  end
-
-  defp dict_put(bucketed(buckets: buckets, size: size) = dict, key, value) do
-    pos = bucket_hash(key)
-    case bucket_put(elem(buckets, pos), key, value) do
-      { new_bucket, 0 } ->
-        { bucketed(dict, buckets: setelem(buckets, pos, new_bucket)), 0 }
-      { new_bucket, 1 } ->
-        if size == @bucketed_threshold do
-          { maybe_expand(segmented(size: size), { setelem(buckets, pos, new_bucket) }, 1), 1 }
-        else
-          { bucketed(dict, size: size + 1, buckets: setelem(buckets, pos, new_bucket)), 1 }
-        end
-    end
-  end
-
-  defp dict_put(segmented(segments: segments) = dict, key, value) do
-    slot = bucket_slot(dict, key)
-    { segments, count } = segments_update segments, slot, bucket_put(&1, key, value)
-    { maybe_expand(dict, segments, count), count }
+    { root, count } = node_put(root, depth, pos, key, value)
+    { trie(dict, size: size + count, root: root), count }
   end
 
   ## Bucket helpers

    end
  end

  def delete(bucketed(buckets: buckets, size: size) = dict, key) do
    pos = bucket_hash(key)
    case bucket_delete(elem(buckets, pos), key) do
      { _, 0 } ->
        dict
      { new_bucket, -1 } ->
        bucketed(dict, size: size - 1, buckets: setelem(buckets, pos, new_bucket))
    end
  end

  def delete(segmented(segments: segments) = dict, key) do
    slot = bucket_slot(dict, key)
    { segments, count } = segments_update segments, slot, bucket_delete(&1, key)
    maybe_contract dict, segments, count
  end

  @doc """


  # A dictionary (key-value) implementation based on dynamic hashing.
  #
  # This implementation is based on hash tries. We first start with
  # a set of 8 buckets and expand when the density is about 5 entries
  # per bucket. We use bit shifting to make rehashing faster on
  # expansion.
  #
  # However, compared to dict, it provides many enhancements:
  #
  # 1. HashDict buckets are ordered sets, this gives us faster access
  #    and modification times
  #
  # 2. It uses phash2 to calculate the hash (instead of phash)
  #
  # 3. The dictionary first starts with a single bucket, instead of
  #    a set of buckets with 16 buckets. This allow us to skip hashing
  #    altogher for small dictionaries, providing faster operations
  #    and reducing memory consumption
  #
  # 4. Once we reach 8 elements, the dictionary is promoted to a
  #    set of buckets

  # The ordered record contains a single bucket
  @ordered_threshold 8

  defrecordp :ordered,
    size: 0,
    bucket: []

  # The bucketed record contains a series of buckets.
  @expand_load 5
  @contract_load 2
  @node_bitmap 0b111
  @node_shift 3
  @node_size 8
  @node_template :erlang.make_tuple(@node_size, [])

  defrecordp :trie,
    size: 0,
    depth: 0,
    expand_on: @node_size * @expand_load,
    contract_on: @contract_load,
    root: @node_template

  import Bitwise

  # Let's inline common instructions
  @compile { :inline, bucket_hash: 1, bucket_index: 1, bucket_nth_index: 2, bucket_next: 1 }

  @doc """
  Creates a new empty dict.
