Design of ustr, the micro string API - for C

• Non-Magic version of a ustr
• Magic/real version of ustr
• Unused bit patterns for a ustr
• English description of struct Ustr
• Number of options for strings

Non-Magic version of a ustr

/* As the saying goes:
 *   "you can tell a lot about the code from the data structure".
 *
 * So this is the non-magic version of struct Ustr:
 *
 * struct Ustr
 * {
 *   const char *ptr;
 *   size_t reference_count;
 *   size_t length;
 *   size_t size;
 *
 *   unsigned char flag_is_readonly            : 1;
 *   unsigned char flag_is_fixed               : 1;
 *   unsigned char flag_exact_byte_allocations : 1;
 *   unsigned char flag_has_enomem_error       : 1;
 *   unsigned char flag_fail_on_alloc          : 1;
 * };
 *
 * ...however this "eats" memory for "small" strings, which is one reason given
 * why people don't use a real string ADT.
 *
 */

Magic/real version of ustr

struct Ustr 
{
 unsigned char data[1];
 /* 0b_wxzy_nnoo =>
  * 
  *    w         = allocated
  *     x        = has size
  *      y       = round up allocations (off == exact allocations)
  *       z      = memory error
  *         nn   = refn
  *           oo = lenn
  *
  * Eg.
  *
  * 0b_0000_0000 ==
  *           "" ==
  * not allocated, [no size], [no round up allocs], no mem err, refn=0, lenn=0
  *
  * 0b1000_0001 ==
  *        0xA5 ==
  * allocated, no size, no round up allocs,         no mem err, refn=0, lenn=1
  *
  * 0b1010_0101 ==
  *        0xA5 ==
  * allocated, no size,    round up allocs,         no mem err, refn=1, lenn=1
  */
};

struct Ustrp
{ /* This is just used as a way to catch errors at compile time with static
   * typing. You might think we'd define Ustrp to be identical to Ustr, and
   * just cast however aliasing rules screw us over if we do that. */
  struct Ustr s;
};

Unused bit patterns for a ustr

/* Unused bit patterns for data[0]:
 *
 * 0bx0xx_x100 == lenn = 0
 * 0bx0xx_1x00
 * 0bx0x1_xx00
 * 0bx01x_xx00
 *              0bx1xx_xx00 => is used in sized
 * 0b10xx_xx00
 *
 * 0bx1xx_xx11 == 128bit size_t, yeh!
 * 0bx1xx_11xx
 *
 * 0b0xxx_x1xx == refn values for const/fixed
 * 0b0xxx_1xxx
 *
 * 0b00x1_xxxx == mem error for const
 * 0b001x_xxxx == not exact for const
 *
 */

English description of struct Ustr

This strucure is very magic, as an optimization "" is a valid "structure" for an empty string, ustr_len("") == 0, ustr_size("") == 0, ustr_cstr("") == "".

This also works for other "static data strings" if they start with the first four bits as 0 ... although for C const strings using this, the length has to be manually defined correctly at compile time.

However it is also a "space efficient" String ADT, with a managed length, _either_ with or without reference counts (so that ustr_dup() doesn't copy) and with or without a stored size (so growing/shrinking a lot doesn't cause lots of malloc/realloc usage). Note that for lengths of strings, or reference counts that need >= 8 bytes of storage the Ustr must contain a stored size.

It can also track memory allocation errors over multiple function calls.

If the first byte == 0, then it's "" as above.

Otherwise the first byte contains four flags, and 2 numbers (2 bits each).

The 1st flag says if the string is allocated. The 2nd flag says if it has a stored size. The 3rd flag says if it isn't using "exact allocations", if it is ustr_len() + ustr_overhead() == ustr_size_alloc(), otherwise there might be room to grow without doing a memory allocation call[1]. The 4th flag says if this Ustr has had a memory allocation error. The two numbers are the mappings for the length of the reference count, and the length of the length. Note that this mapping changes if the 2nd flag is set.

[1] There is an implied "size" of the string, based an how big it is. This is a concession for speed efficiency, although it only grows at 1.5x not 2x which is the norm. (again, to reduce memory waste). Again if this is too much overhead, just use exact sized allocations.

Also NOTE if the 1st and 2nd flags are set, this means that the Ustr is in fixed storge (like an auto array). Also if the 1st, 2nd and 3rd flags are set, this means that the Ustr is limited, Ie. it's in fixed storge and cannot grow (all allocation attempts will fail).

If there is any more data after the above declared one they have been allocated via. the "struct hack" method (search for more info).

Next, possibly, comes the reference count (of the given length[2]).

Next, if not "", comes the length of the data (of the given length[2]).

Next, if non-zero length, comes the data, which can include NIL bytes.

And finally, if not "", a NIL byte, to make sure it's always a valid C-Style string (although obviously any embeded NIL bytes will make it look shorter if something else just uses strlen(ustr_cstr())).

[2] The sizes can currently be 1, 2, 4 or 8 bytes. Depending on the mapping of the value in the first byte (length changes dynamically, as you add data).

Examples

The allocated string "a", using exact allocations and no reference counting, is the 4 bytes:

     {0x81, 0x01, 'a', 0x00}

The allocated string "ab", using non-exact allocations and 1 byte reference counting (shared by 13 users), is the 6 bytes (there is no waste due to non-exact allocations):

     {0xA5, 0x0D, 0x02, 'a', 'b', 0x00}

The allocated string "abcdefghijklmnop" (16 bytes, and a NIL), with non-exact allocations 2 byte reference counting (shared by 1,003 users), is the 24 bytes (with 3 bytes of "unused" space at the end):

     {0xA9, 0x03, 0xEB, 0x10, 'a', 'b', [...], 'o', 'p', 0x00, <x>, <x>, <x>}

Number of options for strings

This design allows 83 different combinations of options for your string types:

• Constant/read-only strings.: Ie.

  Ustr *s1 = USTR("");
  Ustr *s2 = USTR1(\x4, "abcd");
  

• Fixed/auto sized strings.: These can seamlessly convert into allocated strings, if you add too much data. Ie.

    char buf_s3[USTR_SIZE_FIXED(128)] = "x112233abcd";
    /*                  x       = the info byte
                         11     = reference count storage - always two bytes
                           22   = len storage  - always same size as the size
                             33 = size storage - uses 2, 4 or 8 bytes depending on sizeof() */
    Ustr *s3 = USTR_SC_INIT_AUTO(buf_s3, USTR_FALSE, 4); /* s3 is now the string "abcd" */
  

• Fixed/auto sized limited strings.: These will fail to go beyond their specified size (this failure can be checked with ustr_enomem(), just like allocated strings). Ie.

    char buf_s3[USTR_SIZE_FIXED(32)] = USTR_BEG_FIXED2 "abcd";
    Ustr *s3 = USTR_SC_INIT_AUTO(buf_s3, USTR_TRUE, 4); /* s3 is now the string "abcd" */
  

• Allocated, no reference counts: This is the lowest overhead, meaning that ustr_dup() etc. will always have to create a new string and do a copy. For this loss of functionality you gain a single byte. Although if you never share the strings and have very small string lengths this could be significant (0% overhead for an 8 byte string, total overhead being 37.5% or 50% with allocation rounding).
• Allocated, uint8_t reference counts: If you anticipate a low (1-255 users) amount of sharing, and a very low average string size. You can allocate just a single byte to the reference count (less than 10% overhead for an 8 byte string, total overhead being 50%).
• Allocated, uint16_t reference counts: This is what I'd consider "normal" usage, it allows a string to be duplicated at no cost upto 65,535 times, and the reference count is only going to take up 2 bytes (less than 20% overhead for an 8 byte string, total overhead being 62.5% or 100% with allocation rounding). Note this is the default allocation policy
• Allocated, uint32_t reference counts: This might be useful if you want to share the string in a lot of places, it allows a string to be duplicated at no cost upto 4,294,967,295 times, but the reference count is going to take up 4 bytes (less than 40% overhead for an 8 byte string, total overhead being 87.5% or 100% with allocation rounding).
• Allocated, uint64_t reference counts: This is available, allowing a string to be duplicated at no cost upto 18,446,744,073,709,551,615 times, but the reference count is going to take up 8 bytes (less than 100% overhead for an 8 byte string, total overhead being 137.5% or 200% with allocation rounding). Note that this is only allowed on a 64bit machine.
• Allocated, infinite reference count: If you have an allocates string which has any size of reference count you can call ustr_set_share() and the string will allow an infinite amount of duplication, but can never be free'd no matter how many times someone calls ustr_free(). The string can also not be altered anymore. Calling ustr_set_owner() returns the reference count to 1, and calling ustr_free_shared() will free the string.
• Pool allocated: If you use the ustrp_*() calls instead of ustr_*() calls, you will get strings allocated from a "pool" of memory which can be free'd at once (note that ustrp_free() probably does nothing, in this case).
• Allocated, with explicit size: For slightly extra overhead you can have explicitly sized allocated strings, these will have ustr_size() expand as needed ... but they will not implicitly reclaim that memory (you have to call ustr_realloc()). They are useful if you need to add significant amounts of data and then delete it before adding more.
• Allocated, with exact size: For slightly less extra overhead you can have exactly sized allocated strings, these do not add any extra space when the strings need to be resized. Thus if you need to store a 4 byte string, using uint16_t reference counts and no stored size, you will allocate 9 bytes instead of 12 bytes. However to then add a single byte the system allocation functions will need to be called.