Shared strings

Shared string trees, aka StrTrees or just string trees, allow you to cache frequently-repeated strings instead of having dozens or hundreds of copies of the same one. They are used for things like attribute and object names.

API

Use string trees by putting a #include "strtree.h" in your source if it isn't there already. String tree variables have the type StrTree. Unless otherwise mentioned,all string tree functions take a pointer to a StrTree as their last argument.

StrTree st_sample;

Before using one, it must be initialized by calling st_init().

st_init(&st_sample);

New strings are added to the tree with st_insert(). The string that it returns is the persistent one that should be saved by you.

Example:
mystruct->name = st_insert("FOO", &st_sample);

When done with a particular copy of a shared string, call st_delete().

Example:
st_delete(mystruct->name, &st_sample);

To test if a given string is in the tree, use st_find(). It returns a pointer to the shared string and NULL if not. This pointer should not be saved beyond the immediate function it's used in. Use st_insert() for that.

Implementation

The string tree is a red-black tree (Hence the name) of reference-counted strings. Every time a string is inserted, its count goes up, and when it's deleted, the count goes down. A string is removed from the tree when its count goes to 0. If a string's reference count goes to 127, it becomes a permanent entry and will never be deleted.

See the the documentation of strtree.c for more information.