Str Internals

After reading this chapter, you will be familiar with what a Str looks like in memory, what the time/space trade-offs are between Str and char*, and how Str supports features such as automatic memory management. If you are more interested in using Str than understanding how it works, (or if you find yourself getting bored) you can safely skip to chapter 4.

The first design challenge when creating Str was to create a memory structure that was space efficient but still met the goals of automatic memory management and efficient operations. Figure 3.1 shows the final design.

Figure 3.1: This figure shows the Str data structure in 3 different scenarios: an empty string, a basic string and a string with extra buffer available

Looking at figure 3.1:

• The top of the figure shows an empty string. An empty string consists of 8 bytes of data. The data field is a pointer to a buffer that holds a char* style array. In the empty string case, the length of the string is set to zero and the data field is set to NULL (0).

• The middle figure shows a simple string. In this case, data is pointing to string buffer data on the heap. In the size_and_flags field, we have the value 0x80000005. This means that the string is 5 bytes long and has the STR_ALLOCATED bit set. When STR_ALLOCATED is set, Str will automatically free(data) when it is destructed.

• The bottom figure shows a string with extra allocation space. This string is similar to the middle figure except that size_and_flags also has the STR_EXTRA_BUFFER bit set. When this bit is set, a 4-byte field named buff_size will immediately follow the terminating NULL in the string's data.

• The string length can be found in constant $O(1)$ time by masking off the flag bits from size_and_flags. This allows many string operations to operate efficiently as they do not have to walk the string to find its length.

• Even though a length field is provided, the string is always NULL-terminated. This allow for efficient conversion to the char* type.

• Note that, for clarity, the figures assume a big-endian architecture. In reality, the target platform determines the ordering of the size_and_flags and data bytes.