---

4.1.2.7 Front Coded Radix Tree Associative Array

The radix tree associative array replaces the last trie levels with front coded sequences of strings. The suffixes that don’t fit the front coded sections and the internal path segments are stored instead pointers, where they are short enough (just as for the inlined radix tree associative array).

More specifically, what the front coded string sequences are to replace are those subtrees on the fringe that have a (leaf) population lower than a builtin threshold (16 or a similar value).

The design does improve on memory usage, it does not on speed. Only on sparse key distributions is the front coded radix tree faster than the more regular radix trees. The memory usage reductions are also greatest for sparse distributions, with no improvements to be observed for very dense distributions.

The larger the front coded string sequences are allowed, the bigger are the memory saves, and up to a point, the speed gains.

General library:

See String Key Pointer Value Array Library.

• The fast associative array constructor routine:

  int x1f4_fast_sgdeck(void *, unsigned, struct x1f4_sgdeck_type *);
  

• The find plain search routine:

  int x1f4_find_sgpath(void *, const char *, unsigned, const void **);
  

• The fini associative array regular destructor routine:

  int x1f4_fini_sgdeck(void **);
  

• The flat associative array destructor routine:

  int x1f4_flat_sgdeck(void *);
  

• The init associative array regular constructor routine:

  int x1f4_init_sgdeck(void **, unsigned, struct x1f4_sgdeck_type *);
  

• The list data traversal routine:

  int x1f4_list_sgdeck
      (void *, void *, int (*)(void *, const char *, unsigned), char *);
  

• The post plain data insertion routine:

  int x1f4_post_sgpath(void *, const char *, unsigned, const void *);