Handle

A Handle<T,C> is essentially a wrapper to an imperative T** data member intended for use by a container of type C. The handle knows the size of the pointer block, and has the facilities to free and reallocate a larger such block as needed. The related container of type C, by the same token, must provide a replication operation copy() which accepts two handles source and target and copies all the T* values from the first to the second.

More literally, a handle is an imperative quintuple:

Handle(Copy, Cont, Data, Exp2, Used)

where Copy is the Copier singleton, for allocation and reallocation; Cont, the container of type C responsible for the copy update after reallocation; Data, a T** pointer to a region of size $2^{Exp2}$; and Used, the largest offset from the base of Data yet having been bound to an application-defined value.

The Handle<> interface provides read access via T* operator[](nat), and write access using void bind(nat, T* e). Access is checked, and, letting N stand for Maps::Size, Table C.3 gives the four cases for an index i to bind() for a handle with size n.


Table C.3: Case analysis for Handle::bind()
  description action
1 $0 <= i < n $ Data[Used..i] := 0
    Data[i] := e
    Used := max(Used, i)
2 $n <= i < 2n, 2n <= N $ enlarge and copy Data, and bind as in 1
3 $n <= i < 2n, 2n > N $ throw an exception
4 $2n <= i $ throw an exception


Although test code may allow initialization in order to simplify debugging, for the finished component, blocks will not be initialized when first allocated, in order to minimize the time cost of dynamic allocation for large containers. Conversely, the handle must ensure that the unassigned region [0..Used] is initialized, which is the reason for the incremental initialization in the bind() operator (and operator[], as well).

As a result, though access time is still constant time for sequentially filled vectors, it is only amortized constant time for hash tables. In practice this isn't very important, for a number of reasons, and for the application programmer who disagrees, it is easy enough to choose a small initial block size.

Handle creation is performed by the friend Copier on behalf of related containers. The size parameter Exp2 is interpreted as a request for a block of size $2^{Exp2}$, so that Exp2 should be the log base 2 of the desired block size. The size parameter is of type unsigned character, or Char, to remind the application programmer that the size parameter is not interpreted as the absolute block size. The value of the size parameter is restricted to fall in 0, 31, else an exception is thrown, and the actual size of the allocated block is furthur clamped between $2^6$ and some implementation defined limit, typically the memory allocator map size, at the time of this writing 0x1000000, or $2^24$, around 16 meg.


Table C.4: Frequency and other statistics for instances of Handle $<$$>$
frequency object size word size floor ratio factor
132 4 4 1 1
48 1 4 0 1
1 12 4 3 4


Bill Pippin 2010-01-14