Þ   briarpig  » code  » vector

     Code below shows a template based vector class, similar to std::vector by design when method names are the same, but otherwise varying any way it suits me.

     When you port code using C++ std::vector to an app where no standard C++ libraries can be linked, you might be able to use cy::Vt below instead, if equivalent methods are supported. Public methods in cy::Vt are modeled on api in std::vector. But method names all have a v prefix.

     Nested classes start with V and otherwise have terse names. Abbreviations include: t for template, e for element, z for slice, p for pointer (ie iterator), r for reverse, k for const, q for quote, o for out stream, n for number (ie size), x for max (or example), i for integer, v for vector. (See also thorn names.)

     The purpose of cy::Vt is to replace std::vector (in code using a small part of the entire STL api in standard vectors) when standard C++ libraries cannot be used, and when C clients need full control over memory allocation.

     In particular, the purpose of cy::Vt is to ensure vector elements are properly constructed and destroyed, so any resources controlled are correctly managed. When you use in C++ in private implementations under a C api, it's sometimes awkward to use RAII (resource acquisition is initialization) style coding without a template based vector class focusing on object invariants of sequence elements.

     Specifically, cy::Vt is used in a row clone of deck which used std::vector in first drafts. Actual vector api used in deck provided a spec for what cy::Vt needed. (Anything else was overkill added for thinking purposes.)

     Vector elements are always constructed right after allocation, and destroyed right before deallocation. Unused vector elements are not maintained in a non-constructed state of raw space. This seems to use slightly more resources than necessary (assuming constructed objects are more costly)

     Maximum efficiency under all operations is not one of the invariants. Some operations (like erasing a single vector element) move all elements afterward, one at a time. Obviously this is rarely a good idea in code used frequently. So cy::Vt is intended mainly for use when editing is uncommon.

     Without templates, it's hard to maintain an invariant that allocated C++ objects are properly constructed when element types can change each time a collection instantiates.

     If you never wrote a template class, it might seem strange that all of each template is written as inline code. This interferes a lot with any habits and conventions you use for dividing code into inline methods and normal functions compiled separately. How should you deal with this? Don't worry about it. Assume compilers optimize results well enough.

     However, sometimes you can move high cost code out of a template into a class used by the template. Almost nothing like this appears in cy::Vt, unless you count constructors and destructors (and assignment operators) for element type E. Also, space allocation is farmed out to cy_pool.

     You may get a nagging feeling: complex inline methods calling other complex inline methods is wrong. But templates are always irritating that way. Relax! Worry about other things.

     Code without prefix cy_ appears in the cy namespace.

Vt «

     Here's the start of Vt. It's easy to miss because the nested classes inside appear flush left, the way you'd expect for code with global scope. (For example, Vcut is named Vt::Vcut, but inside Vt code Vcut is enough.)

     Template parameter E is the element type. It needs an empty constructor and a destructor because Vt calls them explicitly in _vnew() and _vdelete(). If you want an element to be a primitive type like an integer, just use a struct wrapper with constructor and destructor.

Vcut «

     Cut is a synonym for slice. See misc for code defining cy::Cut which clones yz from the slice thorn demo. Although Vt::Vcut is not used on this page, it would be used by hypothetical code slicing Vt vectors as subsets.

Ve «

     Ve is a vector element, or rather, points to one. The state is very simple: it's just a E pointer named p_e. The original thorn name was yvtp in the global scope. (This explains why methods begin with p for pointer/iterator.) All Vt iterators subclass Ve so they can inherit methods using that pointer.

     All the horrific api is just convenient access to the E pointer member p_e. This takes care of construction, assignment, and comparison of E pointers in iterators.

Vp «

     Vp is a forward iterator. (Thorn iterators are called pointers because they act just like pointers, thus the use of p.)

     Postfix operators are never honored in thorn and cy classes. Postfix does the same thing as prefix, instead of delaying the side effect until later. The main purpose of Vp is to define the value returned by vbegin() and vend().

     Implicitly, both Vt and iterators like Vp assume a basic part of Vt's contiguity model: all vector elements are contiguous. (In thorn, vectors are all contiguous, while an array with the same api as a vector can be discontiguous. Thus, in scatter/gather code, the term array denotes an api like a vector which deals in discontiguous members.) Because vector elements are contiguous, iterators can simply use pointers themselves to implement iteration. Yes, this is just as trivial as it seems.

Vrp «

     Vrp is a reverse iterator. It's exactly like Vp but increment is down and decrement up.

Vkp «

     Vkp below is a const iterator. It's exactly like Vp, except the E inside is consistently assumed immutable. The purpose of this is to induce compiler warnings when you inadvertantly try to alter an element in a const vector while iterating.

Vkrp «

     Vkrp below is a reverse const iterator. It's exactly like Vkp, but increment is down and decrement up.

typedef «

     Inside the Vt namespace, these typedefs can be used. Most of them allow you to use STL style iterator names. The use of sz_t to mean size_t is only for brevity.

members «

     State in Vt is simple: a vector of elements along with current logical and physical length, plus an allocation source. Iovec v_iov is the allocation when a pool is used.

     The oddest member is v_e0: it's a null element used to clobber removed elements, using a standard instance created with an empty constructor. (Because logically removed elements are not destroyed with a destructor, we need another way to release resources, if any, without making an element invalid.)

getters «

     You get get all the members, and you can set the value of v_e0 in case the empty constructor doesn't give you a value best suited for downgrading removed values.

slices «

     You can express a subset of Vt using vz(), which simply joins a pointer (in ref form) to start offset and length.

printing «

     This might be sufficient for printing needs. But I put more care into test classes like VtI32x.

alloc «

     Each time an element array is needed as unconstructed raw space, we ask the pool to allocate memory. Note the iovec returned might be bigger than the request, presumably because pool granularity is coarse.

     (But pool sample code shows a pool using malloc(); so tests on this page will get exactly what was requested.)

     Note the use of placement operator new (which returns the pointer arg unchanged) to construct each element in the vector. This idiom is used because you can only call constructors explicitly this way by using operator new.

free «

     Here we undo whatever happened in _vnew(). Each element is explicitly destroyed by calling the destructor.

start «

     The following init methods are called by constructors. (Note methods beginning with underscore are private api.)

capacity «

     Here's how you reserve minimum physical length:

     This internal _vmin() method reserves minimum physical capacity without saving any old elements. This is used when assignment replaces all old elements anyway.

internal assignment «

     This internal assignment copies a sequence of input elements while discarding all old members.

internal remove «

     Here's how you remove one or N vector elements. Note the use of diagrams to show cases for reference when reviewing the code. (I find it hard to write code without such figures.)

iterators «

     The following methods return iterators. Note end always returns an address one beyond the last element to be visited by the iterator starting at the opposite end.

     (Some folks note C systems do not guarantee an address exists, even logically, at a position one before a memory allocation. My response is simple: if a platform does not define that address, then screw that platform.)

out of bounds «

     If you try to access an element out of bounds (after the last used element), the following element is returned instead of, say, crashing. You should enable the assert when testing.

clear «

     Clearing a vector removes all members. Presumably you want all resources back too, so merely marking logical size as zero is not enough.

destroy «

     The destructor does the same thing as vclear() (and could use clear) but the vector is unusable afterward. If Vt had a magic number in a field, this is where you would write an invalid value like 0xdeadbeef.

construct «

     New vectors are constructed like this. Note the use of a global cy_pool instance when no pool is specified, causing all space to be allocated on the pool using malloc() and free().

index «

     This operator supports array access, returning a mutable element reference when the vector is not const:

compare «

     It appears I meant to support comparison one day:

modify «

     Assignment replaces vector content with new values.

elements «

     You can get the back element or the front, or any at a given index. If the element doesn't exists, you get whatever voob() returns for out-of-bounds.

population «

     These methods query logical vector size:

remove «

     You can remove vector elements many ways:

intersection «

     The following methods say whether two element sequences overlap physically in memory, using the iovecs involved to check for address overlaps. This appears in the api so you can avoid inserting content in a vector when source and destination overlap—don't do that. Vt doesn't support self insert with overlap.

insert «

     Here's how you add new elements via insert. When you add a single element, I make a local copy first to avoid pathological results when overlap occurs. (But if you insert a sequence of elements, you're on your own when it comes to overlap.)

     You can push and pop the back (the end easiest to change efficiently). The idea of max size in STL vectors is given barely serviceable support: just a plausible number.

sizing «

     You can reserve physical capacity ahead of use, or change the vector size to any value you like.

     If you resize a vector smaller and want removed elements to be clobbered with some value (instead of sitting unused) you can use this variant to write overwrite elements. Note this should still leave elements valid and constructed to satisfy an always constructed invariant.

streaming «

     You can use operator<<() to print. Note the C-based out stream api appears on sink.

test «

     I toss in a casual test method for many new classes.

I32x «

     The following example 32-bit integer class has an extra 32-bit tag field (for aggressive dynamic typing), and knows how to print itself. A vector class below uses this integer type.

     Code for dump and cite is minimal and simple:

VtI32x «

     The following example vector class contains instances of example 32-bit integer class I32x shown above. The main purpose of this VtI32x wrapper class is to provide printing support so the vector inside can be examined.

     The most interesting dump behavior occurs when v_verbose is true: then hex for the vector is dumped, including the "unused" part of the vector at the end.

I32xpv «

     Note I32xpv below is nearly identical to VtI32x above. When you look closely, you'll see VtI32x has an inline instance of Vt<I32x> while I32xpv has a reference to an vector elsewhere.

     This was an easy way to create a second wrapper for a single vector, so you could set the verbose flag differently in two places, then choose which way to print (verbose or not) by choosing either the I32xpv or VtI32x instance to print.

     Since printing code for I32xpv is identical to VtI32x, it's not shown here.

     Okay, let's use those example classes above to use vector methods and print the results afterward.

preamble «

     The main() for testing a cy class looks similar each time. Here's how we initialize a pool-based pool, and set up an out stream writing to stdout:

     Code above creates a sink instance named o (for out) writing to stdout, and gets a global pool pool instance named pool. The lat line of output should look as follows to reveal all vector allocated space has been freed:

     Those statistics mean all the allocations were freed, resulting in zero iovs now outstanding for a total of zero bytes now allocated. If the vector leaks, we'll see space sitting around when all the vectors are gone.

body «

     The rest of this sample code shows an assortment of vector calls and printing code in the body of the test.

     Code above says to use an instance of I32x with value 0xeeaaeeaa by default when clobbering removed elements. Output below shows nothing has yet been allocated in vector v:

     After appending a one value, 1, the vector looks like this:

     Integers appear in little endian format, including the tag in each I32x instance. Two extra instances contain -1 (0xffffffff) because that's what the I32x empty constructor uses.

     After appending appending a second value of 2 we get:

     ... which merely shows an another slot was used and filled with the new element.

     If we access the element at zero-based index 1 we see:

     But if we read past the end at index 10, we get out of bounds:

     Appending another element uses the last of existing capacity:

     Here we turn off verbose printing and add a fourth element. Now when we print, we see address v=300520 changed to v=3005d0 because a new vector was allocated:

     The loop above appends four more elements, which grows the vector again:

     The loop above iterates over elements, citing each:

     A similar loop with a reverse iterator prints:

     After popping the last vector member, we see 0xeeaaeeaa from v_e0 was use to set the old value.

     Code above inserts 0x44 after the fourth member:

     After erasing the member at zero-based index 1, we see the old second member is now absent:

     Here we construct a new vector using a subsequence of the old one as source elements to be copied. Note the use of I32xpv to refer to that vector indirectly when printing:

     The loop above uses a forward iterator to visit every element in new vector vag while adding 770 to each element, which shows the iterator provides mutable member access:

     Code above says to insert 99 three times after the first five existing members. Because the vector only had four members before, the insert occurs at end of vector:

     Above we insert a subset of new vag into old vector v starting after v's second member. Copied elems in vag start one after the first, ending two before the end. Afterward v looks like this:

     Finally, we erase all members after the third and before the last two, using 0xbbccddee to clobber removed elements:

     Here's a menu of pages on cy code.

• vector - std::vector clone
• bheap - binary min heap
• label - ascync descriptors
• misc - bunch of basic utils
• pool - C-based vats and pools
• deck - scatter/gather suite
• sink - C-based out stream api
• row - a new deck rewrite

     See license and copyright for code here. For more context, see the cy page.

     Compared to a thorn demo, I explain cy code less: I care little whether folks use or grasp cy source. But since I aim to get ideas across, I reveal a point to code constructs so you see intentions.

     If you ask: What was this for? That's the only question I address: why a thing was done. If you what to know how code works or what loose ends remain, figure it out.

     Sorry about the two space indent format. If you don't like it, fix it yourself.

     Library source code appears appears in amber (orange/brown):

     Source .cpp code appears in red:

     Sample test code is purple:

     Printed output on stdout is green:

     I know these aren't the best color cues. (Amber and green might appear the same hue to color blind folks. I have excellent color discrimination myself.)

     I first wrote cy::Vt (but named yvt in thorn) about four of five years ago, to replace std::vector in the thorn version of deck named yd. I tinkered with it a little in the last two years. I considered rewriting the guts as a btree for efficient scaling.

     This weekend (25apr2009) I added the use of cy_pool (see pool) to allow a C client to manage all memory.

     I wrote cy_pool pool api specifically to plug it into cy::Vt, with an assumption actual space might come from a fixed size memory pool (because I'll almost certainly use it that way). When memory is statically allocated in apps managing their own flow control, available memory fragments might come only in specific sizes. So cy_pool is able to return blocks of memory bigger than you requested, because it's the next size in a pool.

     This alters code in cy::Vt when it copes with bigger memory blocks returned.

     However, when no pool is provided, I left code in place calling global operators new and delete. You might not need it.

     This code has only been tested lightly. C-based pools for space allocation were hacked in immediately before this was written. Don't cut yourself on sharp edges. (I expect to test this more soon when a clone is used in prototype code at work.)

     A few test classes appear on this page: see I32x: an example 32-bit integer with aggressive tagging to see problems, and VtI32x: a vector of these with debug printing support. The C-based out stream api is cy_sink shown on the separate sink page.

     (Classes used only for testing show why much of cy code is a kludge: intent is to see whether code works.)

     You might see many synonyms for struct iovec, including cy_iovec, cy_iov, cy::Iov, cy::Iovec, etc. They all mean the same thing. Conversion cost is trivial. C++ iovs typically have constructors and operators converting between all of them. See run and iovec demoes for iov docs.