Martin Pool's blog

Mail me RSS Bazaar distcc Canonical is hiring! flickr

Vstr string library

From James Antill, Vstr, a fast and secure C string library.

Vstr is a string library, it's designed so you can work optimally with readv()/writev() for input/output. This means that, for instance, you can readv() data to the end of the string and writev() data from the beginning of the string without having to allocate or move memory. It also means that the library is completely happy with data that has multiple zero bytes in it.

This design constraint means that unlike most string libraries Vstr doesn't have an internal representation of the string where everything can be accessed from a single (char *) pointer in C, the internal representation is of multiple "blocks" or nodes each carrying some of the data for the string. This model of representing the data also means that as a string gets bigger the Vstr memory usage only goes up linearly and has no inherent copying (due to other string libraries increasing space for the string via. realloc() the memory usage can be triple the required size and require a complete copy of the string).

It also means that adding, substituting or moving data anywhere in the string can be optimized a lot, to require O(1) copying instead of O(n). Speaking of O(1), it's worth remembering that if you have a Vstr string with caching it is O(1) to get all the data to the writev() system call (the cat example below shows an example of this, the write call is always constant time.

Also, notes on Fast, scalable and simple ... reliable Network IO. (Is there any such thing? Read it and find out.)

posted Mon 15 Dec 2003 in /software/lib | link

Copyright (C) 1999-2007 Martin Pool.