safe functions in RowHandle

As I'm updating the error reporting in the Perl methods, there is one more class that has grown the safe (non-confessing functions). In RowHandle now the method

$row = $rh->getRow();

confesses if the RowHandle is NULL. The method

$row = $rh->getRowSafe();

returns an undef in this situation, just like getRow() used to, only now it doesn't set the text in $! any more. A consequence is that some of the Aggregator examples that branch directly on checking whether a row handle contains NULL, now had to be changed to use getRowSafe().

The method

$result = $rh->isInTable();

has also been updated for the case when it contains a NULL: now it simply returns 0 (instead of undef) and doesn't set the text in $!.

Rhref constructor directly from fields

I've been writing more C++ unit tests, and I've come up with one more convenience constructor for Rhref:

Rhref(Table *t, FdataVec &data);

It takes directly the field values, constructs a row out of them, then constructs a handle for that row.

The usage is pretty easy:

Rhref rh1(t, dv);

SortedIndexType, row handle section and sequences

Now we get to an advanced feature that has been mentioned before in the description of the row handles but is not accessible from Perl. A row handle contains a chunk of memory for every index type in the table. It is called a "row handle section". At the very least this chunk of memory contains the iterator in an index of that type, which allows to navigate through the table and to delete the row handles from the table efficiently.

But an index may request more memory (the same fixed amount for each row handle) to store some row-specific information. For example, the Hashed index stores the value of the hash in its section, and uses this value for the efficient comparisons.

A sort condition may request and use memory in this section of a SortedIndexType. It is done by defining a few more virtual methods that handle the row section.

I could have showed an example of the Hashed index re-implementation through the Sorted interface, but it's kind of boring, since you could as well look directly at the source code of the HashedIndexType. Instead I want to show a different kind of index that doesn't use the data in the rows for comparison at all but keeps the rows in the order they were inserted. Like a more expensive variety of FIFO index type. It's also a bit of a preview of a future feature. It assigns a new auto-generated sequence number to each row handle, and uses that sequence number for ordering. Later you can find the row handle quickly if you know its sequence number. If a table may contain multiple copies of a row, the sequence numbers allow you to tell, which copy you are dealing with. It comes handy for such things as results of joins without a natural primary key. Of course, the usefulness of this preview is limited by the fact that there is no place for the sequence numbers in the rowops, and thus there is no way to propagate the sequence numbers in the model. That would have to be addressed before it becomes a full feature.

Now, you might ask, why not just add an extra field and put the sequence number in there? Sure, that would work too, and also solve the issue with the propagation in the rowops. However this means that as a row goes through a table, it gets copied to set the sequence number in it, which is less efficient. So ultimately keeping the sequence numbers "on the side" is more beneficial.

Now, to the implementation:

class SeqSortCondition : public SortedIndexCondition
{
protected:
    class SeqRhSection : public TreeIndexType::BasicRhSection
    {
    public:
        SeqRhSection(int64_t val) :
            seq_(val)
        { }

        int64_t seq_; // the sequence number of this row handle
    };

public:
    SeqSortCondition() :
        seq_(0)
    { }

    virtual void initialize(Erref &errors, TableType *tabtype, SortedIndexType *indtype)
    {
        SortedIndexCondition::initialize(errors, tabtype, indtype);
        seq_ = 0;
    }

    virtual bool equals(const SortedIndexCondition *sc) const
    {
        return true;
    }

    virtual bool match(const SortedIndexCondition *sc) const
    {
        return true;
    }

    virtual void printTo(string &res, const string &indent = "", const string &subindent = "  ") const
    {
        res.append("Sequenced");
    }

    virtual SortedIndexCondition *copy() const
    {
        return new SeqSortCondition(*this);
    }

    virtual size_t sizeOfRhSection() const
    {
        return sizeof(SeqRhSection);
    }

    virtual void initRowHandleSection(RowHandle *rh) const
    {
        // initialize the Seq part, the general Sorted index
        // will initialize the iterator
        SeqRhSection *rs = rh->get<SeqRhSection>(rhOffset_);
        new(rs) SeqRhSection(seq_++);
    }

    virtual void clearRowHandleSection(RowHandle *rh) const
    {
        // clear the iterator by calling its destructor
        SeqRhSection *rs = rh->get<SeqRhSection>(rhOffset_);
        rs->~SeqRhSection();
    }

    virtual void copyRowHandleSection(RowHandle *rh, const RowHandle *fromrh) const
    {
        SeqRhSection *rs = rh->get<SeqRhSection>(rhOffset_);
        SeqRhSection *fromrs = fromrh->get<SeqRhSection>(rhOffset_);

        // initialize the iterator by calling its copy constructor inside the placement,
        // the sequence number gets copied too
        new(rs) SeqRhSection(*fromrs);
    }

    // Helper method to read the sequence from the row handle,
    // can also be used by the end-user. The row handle must as usual
    // belong to this table.
    int64_t getSeq(const RowHandle *rh) const
    {
        return rh->get<SeqRhSection>(rhOffset_)->seq_;
    }
    // Helper method to set the sequence in the row handle.
    // May be used only on the rows that are not in table.
    void setSeq(const RowHandle *rh, int64_t val) const
    {
        if (rh->isInTable()) {
            throw Exception("Attempted to change the sequence on a row in table.", true);
        }
        rh->get<SeqRhSection>(rhOffset_)->seq_ = val;
    }

    virtual bool operator() (const RowHandle *rh1, const RowHandle *rh2) const
    {
        return getSeq(rh1) < getSeq(rh2);
    }

    mutable int64_t seq_; // the next sequence number to assign
};

    ...
     Autoref<IndexType> it = new SortedIndexType(new SeqSortCondition());
    ...

The nested class SeqRhSection defines the structure of this index's section. For the sort condition it must always inherit from TreeIndexType::BasicRhSection, to get the iterator part from it. Any extra fields are owned by the sort condition.

The SeqSortCondition contains the sequence number generator seq_ (not to be confused with the same-named field seq_ in SeqRhSection), that gets initialized to 0, and will be incremented from there. Since each sorted index type has its own copy of the condition, and each table type gets its own sorted index type, each of them will be counting independently. However there is a bit of a catch when multiple tables get created from the same table type: they will all share the same copy of the sort condition, and thus the same sequence number generator. In practice it should not be a problem, as long as all of the tables are in the same thread. If they are in different threads, a synchronization would be needed around the sequence generator increment. Or better, make a copy of the table type for each thread and avoid the synchronization issues.

The equals() and match() always return true because there is nothing configurable in this sort condition.

The new features start at sizeOfRhSection(). The size of each row handle in a table type is the same, and is computed by asking every index type in it at initialization time and adding up the totals (plus alignment and some fixed amount of basic data). sizeOfRhSection() does its part by telling the caller the size of SeqRhSection.

Then each row handle section must provide the ways to construct and destruct it. Naturally, to save space, a section must have no virtual table, so like for the rows, a separate method in the index type acts as its virtual destructor. And there is no such thing as a virtual constructor in C++, which gets simulater through more methods in the index type. The SortedIndexType delegates most of this work to the sort condition in it. The basic constructor is initRowHandleSection(), the copy constructor is copyRowHandleSection(), and the destructor is clearRowHandleSection().

Each of them gets the location of this index type's section in the row handle with

SeqRhSection *rs = rh->get<SeqRhSection>(rhOffset_);

The field rhOffset_ gets initialized by the SortedIndexType machinery before either of these methods gets ever called. Here rs points to the raw bytes, on which the placement constructors and the explicit destructor are called.

The methods getSeq() and setSeq() are not virtual, they are unique to this SeqSortCondition. They allow to read the sequence from a row handle or set the sequence in it. Naturally, the sequence number may be changed only when the row handle is not in the table yet, or it would mess up the indexing horribly. It's OK to throw the exceptions from setSeq() and getSeq() since they are called directly from the used code and won't confuse any Triceps code along the way.

If you want to find a row handle in the table by its sequence number, you start with creating a new row handle (which can even use an empty row). That new row handle will have a new sequence number assigned to it, but it doesn't matter, because next you call setSeq() and overwrite it with your desired number. Then you use this row handle to call find() or delete() on the table as usual. Like this:

Rhref rh1(table, r1);
sc->setSeq(rh1, desired_number);

Or to read the number, you do:

int64_t seq = sc->getSeq(rh);

Here sc is the exact initialized sort condition from the actual table type. If you use a wrong or uninitialized one, the rhOffset_ in it will likely be wrong, and will cause all kinds of memory corruption. You can get the sort condition from a table type like this:

    Autoref<SortedIndexType> ixt = dynamic_cast<SortedIndexType *>(tt->findSubIndex("primary"));
    Autoref<SeqSortCondition> sc = dynamic_cast<SeqSortCondition *>(ixt->getCondition());

You don't have to use the dynamic cast but it's safer, and since you'd normally do it once at the model setup time and then just keep using the value, there is no noticeable performance penalty for it.

The full example can be found in svn in cpp/type/test/t_xSortedIndex.cpp, and will be also included in version 1.1.

TableType, and a little of RowHandleType

The TableType describes the type of a table, defined in type/TableType.h. In the C++ API it's built very similar to the current Perl API, by constructing a bare object, then adding information to it, and finally initializing it. The Perl API will eventually change to something more Perl-like, the C++ API will stay this way.

The creation goes like this:

Autoref<TableType> tt = (new TableType(rt1))
    ->addSubIndex("primary", it
    )->addSubIndex("secondary", itcopy
    );
tt->initialize();
if (tt->getErrors()->hasError())
    throw Exception(tt->getErrors());

In reality the index types would also be constructed as a part of this long statement but here for clarity they are assumed to be pre-created as it and itcopy.

After a table type has been initialized, nothing can be added to it any more. Just as in the Perl API, the addSubIndex() adds not its argument index type object but its deep copy. When the table type gets initialized, these index types get tied to it.

Note that the operator new has to be in parenthesis to get the priorities right. It's kind of annoying, so the better-looking equivalent way to do it is to use the static method make():

Autoref<TableType> tt = TableType::make(rt1)
    ->addSubIndex("primary", it
    )->addSubIndex("secondary", itcopy
    );

The methods involved are:

TableType(Onceref<RowType> rt);
static TableType *make(Onceref<RowType> rt);
TableType *addSubIndex(const string &name, IndexType *index);
void initialize();

The working of the addSubIndex() is such that it doesn't put the argument object into any kind of Autoref. Because of that it's able to pass that pointer right through to its result for chaining. It doesn't check anything and can't throw any exceptions. So the TableType object created by the constructor gets through the chain of addSubIndex() without having any counted references to it created, its reference count stays at 0. Only when the result of the chain is assigned to an Autoref, the first reference gets created. Obviously, this chain must not be interrupted by any exceptions or the memory will leak. Any detected errors must be collected in the embedded error objects, that will be read after initialization.

The result of initialization is void for a good reason too: you can't include it into this chain. Before the initialization is called, the TableType object must be properly held by a counted reference.

Though this whole thing was written before I've added exceptions to Triceps, and it was one of the earliest things written. Now I'm contemplating that there might be some ways to improve on it.

It's safe to call initialize() multiple times, the repeated calls will simply have no effect.

The ways to look at the contents of the table type are:

bool isInitialized() const;

Checks whether the table type has been initialized.

const RowType *rowType() const;

Returns the row type of the table type. Since the table type is not expected to be destroyed immediately, it's OK to return a plain pointer.

IndexType *findSubIndex(const string &name) const;

Find the index by name. Returns NULL is not found.  This looks only for the top-level indexes, to find the nested indexes, a the similar calls have to be continued on the further levels. At the moment there is no call to resolve a whole index path.

IndexType *findSubIndexById(IndexType::IndexId it) const;

Finds the first index type of a particular kind (or NULL if none found). The ids are like IndexType::IT_HASHED, IndexType::IT_FIFO, IndexType::IT_SORTED.

IndexType *getFirstLeaf() const;

Finds the first leaf index type. This call does search through the whole depth of the index tree for the first leaf index.

const IndexTypeVec &getSubIndexes() const;

Returns the vector with all the top-level index type references. The vector is read-only, you must not change it. Before the table type is initialized, you can actually modify the indexes in it, after initialization they are not modifiable any more.

Ultimately, the TableType is used to construct the tables. The factory method is:

Onceref<Table> makeTable(Unit *unit, Gadget::EnqMode emode, const string &name) const;

This creates a table with the given name in a given unit. The enqueuing mode controls how the rowops get enqueued to the table's output label. The best practice is to always use Table::EM_CALL, because this configuration element didn't prove itself particualrly useful, and will be going away in the future versions, becoming hardcoded to EM_CALL.

Obviously, if the initialization of a TableType has returned errors, that type can not be used to create tables, or everything will crash.

Finally, there is a call that you don't need to use:

RowHandleType *rhType() const;

Like everything else, the RowHandles have a type. But this type is very much internal, and it know very little about the row handles. All it knows is how much memory to allocate when constructing a new RowHandle. The rest of the knowledge about the RowHandles is placed inside the Table. So, a Table acts among the other things as a type for its RowHandles.

Reference to a RowHandle

The row handles have the requirements very similar to the rows. They get created by the million, so the efficiency is important. They contain data that has to be properly destroyed. For example, when an additive Perl aggregator stores its last state, it 's stored in a row handle.

So they are handled similarly to the rows. they don't have a virtual destructor but rely on the Table that owns them to destroy them right. The special reference type for them is Rhref, defined in mem/Rhref.h (the RowHandle itself is defined in table/Table.h).

It follows in the exact same mold as Rowref, only uses the Table instead of a RowType:

Rhref(Table *t, RowHandle *r = NULL);
void assign(Table *t, RowHandle *r);

The rest of comparisons, assignments etc. work the same.

An important point is that a Rhref contains an Autoref to the table, safely holding the table in place while the Rhref is alive. So does the Rowref with the RowType as well, I just forgot to mention it before.

To find out the table of a Rhref, use:

Table *t = rhr.getTable();

Why is the value returned a simple pointer to the table and not an Autoref or Onceref? Basically, because it's the cheapest way and because the row handle is not likely to go anywhere. Nobody is likely to construct a RowHandle only to get the table from it and have it immediately destroyed. And even if someone does something of the sort

Autoref<table> t = RowHandle(t_orig, rh).getTable();

then the table itself is likely to not go anywhere, there is still likely to be another reference to the table that will still hold it in place. If there isn't then of course all bets are off, and t will end up with a dead reference to corrupted memory. Just exercise a little care, and everything will be fine. The same reasoning was used for the argument of the RowHandle constructor being also a table pointer, not an Autoref or Onceref.

An Rhref may also be conveniently used to construct a RowHandle for a Row:

Rhref(Table *t, Row *row);

In fact, this is the official way to construct a RowHandle. The Rowref has a similar method to construct the rows from raw data but the data is much more complex, so I've left its description until later.

more updates

Some more stuff has been getting cleaned up:

$unit->setTracer($tracer);

now confesses on errors, so the problem with its error checking is fixed.

The tables now allow to create rowops of rows of all matching types, not only of the equal types. The approach with matching types was not consistent with what the labels did, so I've changed it.

The TableType now has the method

$tt->getRowType() 

that has the name consistent with the tables and labels. The old method rowType() also still exists.

The Opt::ck_ref() now also accepts the subclasses of the defined classes.

The new helper Fields::isStringType() has been added.

There also have been some major addition of the examples:

I've added a pretty big example of the main loop that includes the full socket handling in the chapter on Scheduling. It's not exactly production-ready but gives some idea.

Another addition in the chapter on Scheduling is an example of a topological loop that computes the Fibonacci numbers.

Many new examples have been added to the chapter on Templates.

RowHandle reference

A RowHandle is essentially the glue that keeps a row in the table. A row's handle keeps the position of the row in the table and allows to navigate from it in the direction of every index. It also keeps the helper information for the indexes. For example, the Hashed index calculates the has value for the row's fields once and remembers it in the handle. The table operates always on the handles, never directly on the rows. The table methods that accept rows as arguments, implicitly wrap then into handles before doing any operations.

A row handle always belongs to a particular table, and can not be mixed between the tables, even if the tables are of the same type. Even before a row handle has been inserted into the table and after it has been removed, it still belongs to that table and can not be inserted into any other one.

Just as the tables are single-threaded, the row handles are single-threaded.

A RowHandle is created by the table's factory

$rh = $table->makeRowHandle($row) or die "$!";

The newly created row handle is not inserted in the table. To find out, whether the row handle is actually inserted in the table, use

$result = $rh->isInTable();

As a special case, a row handle may be null. It pretty much means that there is only the Perl wrapper layer of RowHandle but no actual RowHandle under it. This happens to be much more convenient than dealing with undefined values at Perl level. The null row handles are returned by the certain table calls to indicate that the requested data was not found in the table. A row handle can be checked for being null:

$result = $rh->isNull();

A null row handle may also be explicitly created with

$rh = $table->makeNullRowHandle();

As usual, the row handle references can be compared for the sameness of the actual row handle they contain:

$result = $rh1->same($rh2);

The row can be extracted from the row handle:

$row = $rh->getRow() or die "$!";

If the row handle is null, getRow() will return an undef and an error message.

The rest of the row handle methods are just a syntactic sugar for the table's iteration methods:

$rh = $rh->next();
$rh = $rh->nextIdx($idxType);
$rh = $rh->firstOfGroupIdx($idxType);
$rh = $rh->nextGroupIdx($idxType);

They work in exactly the same way as the table methods.

Table reference

The tables are created from table types:

$t = $unit->makeTable($tabType, $enqMode, "tableName") or die "$!";

The table type must be initialized before it can be used to create tables. The tables are strictly single-threaded.

The enqueueing mode can be specified as a string or Triceps constant. However in the modern reality you should use "EM_CALL" or &Triceps::EM_CALL. This argument is likely to be removed altogether in the future and become fixed to EM_CALL. The table name will be used for the error messages and to create the table labels.

The references to the tables can be as usual compared for sameness by

$result = $t1->same($t2);

Each table creates an input label, an output label, and a label for each aggregator defined in its type. They can be reached with:

$lb = $t->getInputLabel();
$lb = $t->getOutputLabel();
$lb = $t->getAggregatorLabel("aggName") or die "$!";

With an invalid name, getAggregatorLabel() returns an error. The table can also return its type, unit, row type, name :

$tt = $t->getType();
$u = $t->getUnit();
$rt = $t-> getRowType();
$name = $t->getName();

The number of rows in the table is read with

$result = $t->size();

The table stores rows wrapped in the row handles. The row handles are created with:

$rh = $t->makeRowHandle($row) or die "$!";
$rh = $t->makeNullRowHandle();

The row must be of a matching type. A null row handle is a handle without a row in it. It can not be placed into a table but this kind of row handle gets returned by table operations to indicate things not found. In case if you want to full some of your code by slipping it a null handle, makeNullRowHandle() provides a way to do it. The row handles belong to a particular table and can not be mixed between them, even if the tables are of the same type.

The table operations can be done by either sending the rowops to the table's input label or by calling the operations directly.

$result =$t->insert($row_or_rh [, $copyTray]) or die "$!";

Insert a row or row handle into the table.  The row handle must not be in the table before the call, it may be either freshly created or previously removed from the table. If a row is used as an argument, it is internally wrapped in a fresh row handle, and then that row handle inserted. An insert may trigger the replacement policy in the table's indexes and have some rows removed before the insert is done. The optional copy tray can be used to collect a copy of all the row updates that happen in the table as a result of the insert, both on the table output label and on all its aggregator labels. Returns 1 on success, 0 if the insert can not be done (the row handle is already in the table or null), undef and an error message on an incorrect argument.

$result = $t->remove($rh [, $copyTray]) or die "$!";

Removes a row handle from the table. The row handle must be previously inserted in the table, and either found in it or a reference to it remembered from before. An attempt to remove a newly created row handle will have no effect. The optional copy tray works in the same way as for insert(). The result is 1 on success (even if the row handle was not in the table), or undef and error message on an incorrect argument.

$result= $t->deleteRow($row [, $copyTray]) or die "$!";

Finds the handle of the matching row by the table's first leaf index and removes it. Returns 1 on success, 0 if the row was not found, undef and error message on an incorrect argument. Unlike insert(), the deletion methods for a row handle and a row are named differently to emphasize their difference. The method remove() must get a reference to the exactly same row handle that was previously inserted. The method deleteRow() does not have to get the same row as was previously inserted, instead it will find a row handle of the row that has the same key as the argument, according to the first leaf index. deleteRow() never deletes more than one row. If the index contains multiple matching rows (for example, if the first leaf is a FIFO index), only one of them will be removed, usually the first one (the exact choice depends on what row gets found by the index).

The row handles can be found in the table by indexes:

$rh = $t->find($row_or_rh);
$rh = $t->findIdx($idxType, $row_or_rh);

The default find() works using the first leaf index type, i.e. the following two areequivalent

$t->find($r)
$t->findIdx($t->getType()->getFirstLeaf(), $r)

but the find() version is slightly more efficient because it handles the index types inside the C++ code and does not create the Perl wrappers for them. The index type in all the table operations must be exactly one from the table's type, and not a copy. Since when a table type is constructed, the index types are copied into it, the only way to find the correct index type is to construct the whole table type and then get the index type from it using findSubIdx().

The find() operation is also used internally by deleteRow() and to process the rowops received at the table's input label.

If a row is used as an argument for find, a temporary row handle is internally created for it, and then the find is performed on it. Note that if you have a row handle that is already in the table, there is generally no use calling find on it, you will just get the same row handle back (well, except for the case of multi-valued indexes, then you will get back some matching row handle, usually the first one, which may be the same or not). The normal use is to create a new row handle, and then find a match for it.

If the matching row is not found, find methods would return a null row handle. They return undef and an error message on an argument error.

A findIdx() with a non-leaf index argument is a special case: it returns the first row handle of the group that has the key matching the argument. The order of "first" in this case is defined according to that index'es first leaf sub-index.

There also are convenience methods that construct a row from the field arguments and then find it:

$rh = $t->findBy("fieldName" => $fieldValue, ...);
$rh = $t->findIdxBy($idxType, "fieldName" => $fieldValue, ...);

If the row creation fails, these methods die.

The table can be iterated using the methods

$rh = $t->begin();
$rh = $t->next($rh); 
$rh = $t->beginIdx($idxType);
$rh = $t->nextIdx($idxType, $rh);

As usual, the versions without an explicit index type use the first leaf index type. The begin methods return the first row handle according to an index'es order, the next methods advance to the next row handle. When the end of the table is reached, these methods return a null row handle. The next methods return a null row handle if their argument row handle is a null or not in the table. So, if you iterate and remove the row handles, make sure to advance the iterator first and only then remove the current row handle.

If the index argument is non-leaf, it's equivalent to its first leaf.

To iterate through only a group, use findIdx() on the parent index type of the group to find the first row of the group. Then things become tricky: take the first index type one level below it to determine the iteration order (a group may have multiple indexes in it, defining different iteration orders). Use that index type with the usual nextIdx() to advance the iterator. However the end of the group will not be signaled by a null row handle. Instead first find the end marker handle of the group by using

$endrh = $t->nextGroupIdx($subIdxType, $firstrh);

Th $subIdxType here is the same index as used for nextIdx(). Then each row handle can be compared with the end marker with $rh->same($endrh).

The value $endrh is actually the first row handle of the next group, so it can also be used to jump quickly to the next group, and essentially iterate by groups. After the last group, nextGroupIdx() will return a null row handle. Which is OK for iteration, because at the end of the last group nextIdx() will also return a null row handle.

What if a group has a whole sub-tree of indexes in it, and you want to iterate it by the order of not the first sub-index? Still use findIdx() in the same way to find a row handle in the desired group. But then convert it to the first row handle in the desired order:

$beginrh = $t->firstOfGroupIdx($subIdxType, $rh);

After that proceed as before: get the end marker with nextGroupIdx() on the same sub-index, and iterate with nextIdx() on it.

This group iteration is somewhat messy and tricky, and maybe something better can be done with it in the future. If you look closely, you can also see that it doesn't allow to iterate the groups in every possible order. For example, if you have an index type hierarchy

A
+-B
| +-D
| | +-G
| | +-H 
| +-E 
+-C

and you want to iterate on the group inside B, you can go in the order of D or G (which is the same as D, since G is the first leaf of D) or of E, but you can not go in the order of H. But for most of the practical purposes it should be good enough.

A window is a FIFO

A fairly typical situation in the CEP world is when a model needs to keep a limited history of events. For a simple example, let's discuss, how to remember the last two trades per stock symbol. The size of two has been chosen to keep the sample input and outputs small.

This is normally called a window logic, with a sliding window. You can think of it in a mechanical analogy: as the trades become available, they get printed on a long tape. However the tape is covered with a masking plate. The plate has a window cut in it that lets you see only the last two trades.

Some CEP systems have the special data structures that implement this logic, that are called windows. Triceps has a feature on a table instead that makes a table work as a window. It's not unique in this department: for example Coral8 does the opposite, calls everything a window, even if some windows are really tables in every regard but name.

In Triceps it's done like this (the usual preamble is not shown):

my $uTrades = Triceps::Unit->new("uTrades") or die "$!";
my $rtTrade = Triceps::RowType->new(
  id => "int32", # trade unique id
  symbol => "string", # symbol traded
  price => "float64",
  size => "float64", # number of shares traded
) or die "$!";

my $ttWindow = Triceps::TableType->new($rtTrade)
  ->addSubIndex("bySymbol",
    Triceps::IndexType->newHashed(key => [ "symbol" ])
      ->addSubIndex("last2",
        Triceps::IndexType->newFifo(limit => 2)
      )
  )
or die "$!";
$ttWindow->initialize() or die "$!";
my $tWindow = $uTrades->makeTable($ttWindow,
  &Triceps::EM_CALL, "tWindow") or die "$!";

# remember the index type by symbol, for searching on it
my $itSymbol = $ttWindow->findSubIndex("bySymbol") or die "$!";
# remember the FIFO index, for finding the start of the group
my $itLast2 = $itSymbol->findSubIndex("last2") or die "$!";

# print out the changes to the table as they happen
my $lbWindowPrint = $uTrades->makeLabel($rtTrade, "lbWindowPrint",
  undef, sub { # (label, rowop)
    print($_[1]->printP(), "\n"); # print the change
  }) or die "$!";
$tWindow->getOutputLabel()->chain($lbWindowPrint) or die "$!";
while(<STDIN>) {
  chomp;
  my $rTrade = $rtTrade->makeRowArray(split(/,/)) or die "$!";
  my $rhTrade = $tWindow->makeRowHandle($rTrade) or die "$!";
  $tWindow->insert($rhTrade) or die "$!"; # return of 0 is an error here
  # There are two ways to find the first record for this
  # symbol. Use one way for the symbol AAA and the other for the rest.
  my $rhFirst;
  if ($rTrade->get("symbol") eq "AAA") {
    $rhFirst = $tWindow->findIdx($itSymbol, $rTrade) or die "$!";
  } else  {
    # $rhTrade is now in the table but it's the last record
    $rhFirst = $rhTrade->firstOfGroupIdx($itLast2) or die "$!";
  }
  my $rhEnd = $rhFirst->nextGroupIdx($itLast2) or die "$!";
  print("New contents:\n");
  for (my $rhi = $rhFirst;
      !$rhi->same($rhEnd); $rhi = $rhi->nextIdx($itLast2)) {
    print("  ", $rhi->getRow()->printP(), "\n");
  }
}

This example reads the trade records in CSV format, inserts them into the table, and then prints the actual modifications reported by the table and the new state of the window for this symbol. Here is a sample log, with the input lines shown in italic:

1,AAA,10,10
tWindow.out OP_INSERT id="1" symbol="AAA" price="10" size="10" 
New contents:
  id="1" symbol="AAA" price="10" size="10" 
2,BBB,100,100
tWindow.out OP_INSERT id="2" symbol="BBB" price="100" size="100" 
New contents:
  id="2" symbol="BBB" price="100" size="100" 
3,AAA,20,20
tWindow.out OP_INSERT id="3" symbol="AAA" price="20" size="20" 
New contents:
  id="1" symbol="AAA" price="10" size="10" 
  id="3" symbol="AAA" price="20" size="20" 
4,BBB,200,200
tWindow.out OP_INSERT id="4" symbol="BBB" price="200" size="200" 
New contents:
  id="2" symbol="BBB" price="100" size="100" 
  id="4" symbol="BBB" price="200" size="200" 
5,AAA,30,30
tWindow.out OP_DELETE id="1" symbol="AAA" price="10" size="10" 
tWindow.out OP_INSERT id="5" symbol="AAA" price="30" size="30" 
New contents:
  id="3" symbol="AAA" price="20" size="20" 
  id="5" symbol="AAA" price="30" size="30" 
6,BBB,300,300
tWindow.out OP_DELETE id="2" symbol="BBB" price="100" size="100" 
tWindow.out OP_INSERT id="6" symbol="BBB" price="300" size="300" 
New contents:
  id="4" symbol="BBB" price="200" size="200" 
  id="6" symbol="BBB" price="300" size="300" 

The first thing to notice in the code is that the table type has two indexes (strictly speaking, index types,  but most of the time they can be called indexes without creating a confusion) in it. Unlike your typical database, the indexes in this example are nested.

TableType
+-IndexType Hash "bySymbol"
  +-IndexType Fifo "last2"

If you look closely, you can see, that the first call addSubIndex() adds an index type to the table type, while the textually second addSubIndex() adds an index to the previous index.

The same can also be written out in multiple separate calls:

$itLast2 =Triceps::IndexType->newFifo(limit => 2);
$itSymbol =  Triceps::IndexType->newHashed(key => [ "symbol" ]);
$itSymbol->addSubIndex("last2", $itLast2);
$ttWindow = Triceps::TableType->new($rtTrade);
$ttWindow->addSubIndex("bySymbol", $itSymbol);

I'm not perfectly happy with the way the table types are constructed with the index types right now, since the parenthesis levels have turned out a bit hard to track. This is another example of following the C++ API in Perl that didn't work out too well, and it will change in the future. But for now please bear with it.

The index nesting is kind of intuitively clear, but the details may take some time to get your head wrapped around them. You can think of it as the inner index type creating the miniature tables that hold the rows, and then the outer index holding not individual rows but those miniature tables. So, to find the rows in the table you go through two levels of indexes: first through the outer index, and then through the inner one. The table takes care of these details and makes them transparent, unless you want to stop your search at an intermediate level: such as, to find all the transactions with a given symbol, you need to do a search in the outer index, but then from that point iterate through the inner index. Then you obviously have to tell the table, where do you want to stop.

The outer index is the hash index that we've seen before, the inner index is a FIFO index. A FIFO index doesn't have any key, it just keeps the rows in the order they were inserted. You can search in a FIFO index but most of the time it's not the best idea: since it has no keys, it searches linearly through all its rows until it finds an exact match (or runs out of rows). It's a reasonable last-resort way but it's not fast and in many cases not what you want. Remember that the method deleteRow() and sending the OP_DELETE to the table's input label invoke find(), which would cause the linear search on the FIFO indexes. So when you use a FIFO index, it's usually better to find the row handle you want to delete in some other way and then call remove() on it, or use another approach that will be shown later. Or just keep inserting the rows and never delete them, like this example does.

Note that a FIFO index may contain multiple copies of an exact same row. It doesn't care, it just keeps whatever rows were given to it in whatever order they were given.

By default a FIFO index just keeps whatever rows come to it. However it may have a few options. Setting the option "limit" limits the number of rows stored in the index (not per the whole table but per one of those "miniature tables"). When you try to insert one more row, the oldest row gets thrown out, and the limit stays unbroken. That's what creates the window behavior: keep the most recent N rows.

If you look at the sample output, you can see that inserting the rows with ids 1-4 generates only the insert events on the table. But the rows 5 and 6 start overflowing their FIFO indexes, and cause the oldest row to be automatically deleted before completing the insert of the new one.

A FIFO index doesn't have to be nested inside a hash index. If you put a FIFO index at the top level, it will control the whole table. So it would be not 2 last record per key but 2 last records inserted in the whole table.

Continuing the example, the table gets created, and then the index types get extracted back from the table type. Now, why not just write out the table type creation as shown above and remember the index references? At some point in the past this actually would have worked but not any more. It has to do with the way the table type and its index types are connected. It's occasionally convenient to create one index type and then reuse it in multiple table types. However for the whole thing to work, the index type must be tied to its particular table type. This tying together happens when the table type is initialized. If you put the same index type into two table types, when the first table type is initialized, the index type will get tied to it. The second table type would then fail to initialize because an index in it is already tied elsewhere. To get around this dilemma,  now when you call addSubIndex(), it doesn't add the original index type, instead it makes a copy of it. That copy then gets tied with the table type and gets returned back with findSubIndex(). And the further table methods that take an index type argument absolutely require that the index type be tied to the table type. If you try to pass a seemingly the same index type that has not been tied, or has been tied to a different table type, that is an error. There is no interdependency between the methods makeTable() and findSubIndex(), they can be done in either order.

The label $lbWindowPrint is used to show the changes reported by the table's output label. That's where the output lines with OP_INSERT and OP_DELETE come from.

And then the main loop starts. It reads the trade records in the simple CSV format, and for simplicity acts directly on the table, bypassing the scheduler. After the row is inserted, the contents of its index group (that "miniature table") gets printed. The insertion could as well have been done with passing directly the row reference, without explicitly creating a handle. But that handle will be used to demonstrate an interesting point.

To print the contents of an index group, we need to find its boundaries. In Triceps these boundaries are expressed as the first row handle of the group, and as the row handle right after the group. There is an internal logic to that, and it will be explained later, but for now just take it on faith.

With the information we have, there are two ways to find the first row of the group:

• With the table's method findIdx(). It's very much like find(), only it has an extra argument of a specific index type. If the index type given has no further nesting in it, findIdx() works exactly like find(). In fact, find() is exactly such a special case of findIdx() with a hardcoded index type. If you use an index type with further nesting under it, findIdx() will return the handle of the first row in the group under it (or, as usual, a NULL row handle if not found).
• If we create the row handle explicitly before inserting it into the table, as was done in the example, that will be the exact row handle inserted into the table. Not a copy or anything but this particular row handle. After a row handle gets inserted into the table, it knows its position in the indexes. And we still have a reference to it. So then we can use this knowledge to jump to the first row handle in the group with firstOfGroupIdx(). It also takes an index type but in this case it's the type that controls the group, the FIFO index in out case.

The example shows both way. As a demonstration, it uses the first way if the symbol name is "AAA" and the second way for all the other rows.

The end boundary is found by calling nextGroupIdx() on the first row's handle. The handle of the newly inserted row could have been used for nextGroupIdx() just as well. Since both belong to the same group, the result is exactly the same.

And finally a loop runs the iteration on the group. Note that the end condition comparison is done with same(), to compare the real row handle references and not just their Perl-level wrappers. The stepping is done with nextIdx(), with is exactly like next() but according to a particular index, the FIFO one. This has actually been done purely to show off this method. In this particular case the result produced by next(), nextIdx() on the FIFO index type and nextIdx() on the index type with nesting is exactly the same. We'll come to the reasons of that yet.

As you aggregate through the group, you could do some manual aggregation along the way. For example, find the average price of the last two trades, and then do something useful with it.

P.S. The RowHandle methods firstOfGroupIdx(), nextGroupIdx(), nextIdx() as shown here are available in version 1.0. In 0.99 they are the methods on the table, like $tWindow->firstOfGroupIdx($itLast2, $rhTrade).

iterating more like an iterator

I've started writing about why the call to move the iterator to the next row has to be done as $table->next($rh) and not just $rh->next(). A look in the code has shown that there really aren't any.

Or, more exactly, the reasons are purely historical: The method was written as a direct mirror of the one in C++, and in C++ the RowHandle does not have enough information for that. But in the Perl API the row handle object carries extra information for the type safety: the reference to a table that can be handily reused for the other purposes.

This situation has had upset me much, and I've set at once to rectify it. So, now you can call directly:

$rh = $rh->next();

Obviously, it's not in the 0.99 package, but it will be in 1.0.

And while I'm at it, let me also explain why the C++ interface is different. Remember that every row in the table has a row handle. This makes the large tables sensitive to the size of row handles. If a table as a million rows, every extra byte in the row handle means extra megabyte of memory used. Finding the next row for iteration does require a pointer to the table, and that would be extra 8 bytes per each handle. I kind of try to resist the temptations of premature optimization, except where it's absolutely straightforward, and this is one of the straightforward cases.

However in the Perl APIs the objects are not direct references to the C++ objects. They are wrappers that carry the extra information for the safe type-checking (on the other hand, the C++ API is unsafe and assumes that the caller knows what he is doing). Memory-wise this is not much overhead, since normally not many objects are referred from Perl at the same time. And once a row handle is placed into the table, it does not bring its Perl wrapper there with it.

A closer look at RowHandles

A few uses of the RowHandles have been shown by now. So, what is a RowHandle? As Captain Obvious would say, RowHandle is a class (or package, in Perl terms) implementing a row handle.

A RowHandle keeps a table's service information (including the index data) for a single data row, including of course a reference to the row itself. Each row is stored in the table through its handle. A RowHandle always belongs to a particular table, the RowHandles can not be shared nor moved between two tables, even if the tables are of the same type. Obviously, since the tables are single-threaded, the RowHandles may not be shared between the threads either.

However a RowHandle may exist without being inserted into a table. In this case it still belongs to that table but is not included in the index, and will be destroyed as soon as all the references to it disappear.

The insertion of a row into a table actually happens in two steps:

• A RowHandle is created for a row.
• This new handle is inserted into the table.

This is done with the following code:

$rh = $table->makeRowHandle($row) or die "$!";
$result = $table->insert($rh);
die "$!" unless defined $result;

Only it just so happens that to make life easier, the method $table->insert() has been made to accept either a row handle or directly a row. If it finds a row, it makes a handle for it behind the curtains and then proceeds with the insertion of that handle. Passing a row directly is also more efficient because the row handle creation then happens entirely in the C++ code, without surfacing into Perl.

A handle can be created for any row of an equal type.

The insert() method has three possibilities of the return code: undef means that some major logical error has occurred (such as an attempt to insert a row of a wrong type), 1 means that the row has been inserted successfully, and 0 means that the row has been rejected. An attempt to insert a NULL handle or a handle that is already in the table will cause a rejection. Also the table's index may reject a row with duplicate key (though right now this option is not implemented, and the hash index silently replaces the old row with the new one).

There is a method to find out if a row handle is in the table or not:

$result = $rh->isInTable();

Though it's used mostly for debugging, when some strange things start going on.

The method find() is similar to insert(): the "proper" way is to give it a row handle, but the more efficient way is to give it a row, and it will create the handle for it as needed before performing a search.

Now you might wonder: huh, find() takes a row handle and returns a row handle? What's the point? Why not just use the first row handle? Well, those are different handles:

• The argument handle is normally not in the table. It's created brand new from a row that contains the keys that you want to find, just for the purpose of searching.
• The returned handle is always in the table (of course, unless it's NULL). It can be further used to extract back the row data, and/or for iteration.

Though nothing really prevents you from searching for a handle that is already in the table. You'll just get back the same handle, after gratuitously spending some CPU time. (There are exceptions to this, with the more complex indexes that will be described later).

Why do you need to create new a row handle just for the search? Due to the internal mechanics of the implementation. A handle stores the helper information for the index. For example, the hash index calculates the hash value of all  the row's key fields once and stores it in the row handle. Despite it being called a hash index, it really stores the data in a tree, with the hash value used to speed up the comparisons for the tree order. It's much easier to make both the insert() and find() work with the hash value and record reference stored in the same way than to implement them differently. Because of this, find() uses an exactly same row handle argument format as insert().

Can you create multiple row handles referring to the same row? Sure, knock yourself out. From the table's perspective it's the same thing as multiple row handles to multiple copied of the row with the same values in them, only using less memory.

There is more to the row handles than has been touched upon yet. It will all be revealed when more of the table features are described.

Deleting a row

Deleting a row from a table through the input label is simple: send a rowop with OP_DELETE, it will find the row and delete it. That's not even interesting for an example: same code as for the insert, different opcode. In the procedural way the same can be done with the method deleteRow(). The added code for "Hello, table" is:

    elsif ($data[0] =~ /^delete$/i) {
      my $res = $tCount->deleteRow($rtCount->makeRowHash(
        address => $data[1],
      ));
      die "$!" unless defined $res;
      print("Address '", $data[1], "' is not found\n") unless $res;
    }

The result allows to differentiate between 3 cases: row found and deleted (1), row not found (0), a grossly misformatted call (undef). If the absence of the row doesn't matter, it could be written in an one-liner form:

die "$!" unless defined $tCount->deleteRow(...);

However we already find the row handle in advance. For this case a more efficient form is available:

    elsif ($data[0] =~ /^remove$/i) {
      if (!$rhFound->isNull()) {
        $tCount->remove($rhFound) or die "$!";
      } else {
        print("Address '", $data[1], "' is not found\n");
      }
    }

It removes a specific row handle from the table. In whichever way you find it, you can remove it. Removing a NULL handle would be an error.

After a handle is removed from the table, it continues to exist, as long as there are references to it. It could even be inserted back into the table. However until (and unless) it's inserted back, it can not be used for iteration any more. Calling $table->next() on a handle that is not in the table would just return a NULL handle.

So, as an example, here is the implementation of the command "clear" for "Hello, table" that clears all the table contents:

    elsif ($data[0] =~ /^clear$/i) {
      my $rhi = $tCount->begin(); 
      while (!$rhi->isNull()) {
        my $rhnext = $tCount->next($rhi);
        $tCount->remove($rhi) or die("$!");
        $rhi = $rhnext;
      }     
    }

Note that it first remembers the next row for iteration and only then removes the current row.

There isn't any method to delete multiple rows at once. Every row has to be deleted by itself. Though of course nothing prevents anyone from writing a function  that would delete multiple or all rows. Such library functions will grow over time.

Iteration through a table

Let's add a dump of the table contents to the "Hello, table" example, either one of them. For that, the code needs to go through every record in the table:

    elsif ($data[0] =~ /^dump$/i) {
      for (my $rhi = $tCount->begin();
          !$rhi->isNull(); $rhi = $tCount->next($rhi)) {
        print($rhi->getRow->printP(), "\n");
      }    
    }

This code would work in either version of the example, updated either procedurally or through the input label. Here is an example of its output:

address="world" count="1"
address="table" count="2"

As you can see, the row handle works kind of like an STL iterator.  Well, not quite like an STL iterator: you can't just increase it, you have to ask the table to give you the next one.

The order of the rows in the printout is the same as the order of rows in the table's index. Which is no particular order, since it's a hashed index. As long as you stay with the same 64-bit AMD64 architecture (with LSB-first byte order), it will stay the same on different runs. But switching to a 32-bit machine or to an MSB-first byte order (such as a SPARC, if you can still find one) will change the hash calculation, and with it the resulting row order.

At the moment Triceps doesn't have an index that would keep the rows in a defined sorting order. It's not by design, it's just a result of the corner-cutting. A sorted index will be added in the future.

The some goes for the iteration order: right now the iteration can only be done in the forward order. The backward iteration is in the plans but not implemented yet.

Hello, tables!

The tables are the basic units of statekeeping in Triceps. Let's start with a basic example.

use Triceps;

my $hwunit = Triceps::Unit->new("hwunit") or die "$!";
my $rtCount = Triceps::RowType->new(
  address => "string",
  count => "int32",
) or die "$!";

my $ttCount = Triceps::TableType->new($rtCount)
  ->addSubIndex("byAddress", 
    Triceps::IndexType->newHashed(key => [ "address" ])
  ) 
or die "$!";
$ttCount->initialize() or die "$!";

my $tCount = $hwunit->makeTable($ttCount, &Triceps::EM_CALL, "tCount") or die "$!";

while(<STDIN>) {
  chomp;
  my @data = split(/\W+/);

  # the common part: find if there already is a count for this address
  my $pattern = $rtCount->makeRowHash(
    address => $data[1]
  ) or die "$!";
  my $rhFound = $tCount->find($pattern) or die "$!";
  my $cnt = 0;
  if (!$rhFound->isNull()) { 
    $cnt = $rhFound->getRow()->get("count");
  } 

  if ($data[0] =~ /^hello$/i) { 
    my $new = $rtCount->makeRowHash(
      address => $data[1],
      count => $cnt+1,
    ) or die "$!";
    $tCount->insert($new) or die "$!";
  } elsif ($data[0] =~ /^count$/i) { 
    print("Received '", $data[1], "' ", $cnt + 0, " times\n");
  } else { 
    print("Unknown command '$data[0]'\n");
  } 
}

What happens here? The code reads the lines from standard input, uses the first word as a command and the second work as a key. It counts, how many times each key has been hello-ed, and prints this count back on the command "count".

Here the table is read and modified using the direct procedural calls. As you can see, there isn't even any need for unit scheduling and such.  There is a scheduler-based interface too, it will be shown later.  But in many cases the direct access is easier. Indeed, this particular example could have been implemented with the plain Perl hashes. Nothing wrong with that either. Well, at some future point the tables will be supporting the on-disk persistence, but no reason to bother much about that now: things are likely to change a dozen times yet before that happens. Feel free to just use the Perl data structures if they make the code easier.

A table is created through a table type. This allows to stamp out duplicate tables of the same type, which can get handy when the multithreading will be added. A table is local to a thread. A table type can be shared between threads. So the only way to look up something directly in another thread's table is to keep its local copy, which can be easily done by creating a copy table from the same type.


In reality, right now all the business with table types separated from the tables is more pain than gain. It not only adds extra steps but also makes difficult to define a template that acts on a table by defining extra features on it. Something will be done about it, I have a few ideas.

The table type gets first created and configured, then initialized. After a table type is initialized, it can not be changed any more. That's the point of the initialization call: tell the table that all the configuration has been done, and it can go immutable now. A table type must be fully initialized in one thread before it can be shared with other threads. The historic reason for this API is that it mirrors the C++ API, which has turned out not to look that good in Perl. It's another candidate for a change.

A table type gets the row type and at least one index. Here it's a hashed index by the field address. The table is then created from the table type, enqueueing mode (just use EM_CALL always, this argument will be removed in the future), and given a name.

The rows can then be inserted into the table (and removed, not shown in this example). The default behavior of the hashed index is to replace the old row if a new row with the same key is inserted.

The search in the table is done by creating a sample row with the key fields set, and then calling find() on it. Which returns a RowHandle object. A RowHandle is essentially an iterator in the table. Even if the row is not found, a RowHandle will be still returned but it will be null, which is checked for by $rh->isNull().

This is just the tip of the iceberg. The tables in Triceps have a lot more features.