avlgen

Documentation

Overview

Avlgen is a tool to automatically generate code for embedded AVL trees in structs. The purpose is to be able to store structs in an ordered tree without any additional memory allocation. All the data needed to store a struct in the tree is part of the struct.

Avlgen is invoked on a package directory, examines the package and finds structs with fields that contain a special tag and generates the necessary code for those structs in the same package.

For example:

package foo

//go:generate avlgen .
type str struct {
	key string
	tl  tlink `avlgen:"strTree"`
}

func (a *str)cmp(b *str) (bool, bool) {
	return a.key == b.key, a.key < b.key
}

This will generate a file called "foo_trees.go" with the type "strTree", and some access methods. You can now manage str structs like this:

st := strTree{}
st.insert(&str{ key: "a" })
st.insert(&str{ key: "b" })
s := st.lookup(&str{ key: "c" })
st.delete(s)
if st.first().key != "a" {
	panic("a")
}
if st.last().key != "b" {
	panic("b")
}

The "tlink" part is a type name of the type that avlgen will generate and must be unique for each tree, but otherwise can be any string. The same goes for its name in the struct. This is the part that embeds the tree in the struct.

This is the simplest possible tree and is already relatively useful especially since the struct "str" can contain any data. Of course, things can be improved with some configuration. Insert, lookup and delete won't perform any memory allocations.

The default comparison function is a receiver of the type of the tree elements called "cmp". We can change its name by just adding a bit more information to the tag:

type str struct {
	key string
	tl tlink `avlgen:"strTree,cmp:cmpKeys"`
}

Now we expect there to be a "cmpKeys" function instead of "cmp". The compare function returns two booleans: if the two values are equal or if the first value is "less" than the other value. You're free to define "less" in whatever way you wish as long as it is transitive (if a > b and b > c then a > c).

The next useful feature is obvious from the above "lookup" example. It's quite wasteful to allocate a fake struct to perform lookups just because our compare function only understands how to compare two element structs.

type str struct {
	key string
	tl tlink `avlgen:"strTree,cmpval:cmpk(string)"`
}
func (a *str)cmpk(b string) (bool, bool) {
	return a.key == b, a.key < b
}

This allows us to generate special functions lookupVal and deleteVal:

s := lookupVal("foobar")
tr.deleteVal("foobar")

The type (string in this case) can be anything, of course. It's specified in the tag and the code is generated correctly for any key types (it shouldn't be too hard to add multiple arguments to the cmpk/lookupVal functions in case of more complex keys, but this isn't implemented yet).

There is obviously no "insertVal" function since it is expected that structs are much more complex than this example.

When "cmpval" is specified we also implement two more functions: searchValLEQ and searchValGEQ. They behave like lookup, but in case there's no equal element, they return the nearest less than (LEQ) or greater than (GEQ) node.

The big selling point of trees is that they are ordered, but this is useless unless we can actually see the elements in order. The previously mentioned "first" and "last" functions will only get us so far. We add iterators by adding "iter" to the tag:

type str struct {
	key string
	tl tlink `avlgen:"strTree,iter"`
}

A new function becomes generated now:

(*strTree).iter(start,end *str, incs, ince bool) *strTreeIter

"start" and "end" specify on which nodes the iteration should start and end. "incs" and "ince" specify if the start and respectively end nodes should be included in the iteration (even though it's not strictly necessary to provide all functionality, it makes life much easier in certain situations and it is trivial to implement). If "start" or "end" are nil the iteration starts/end at the first/last element in the tree.

The iterator then can be used like this:

it := tr.iter(nil, nil, true, true)
for it.next() {
	n := it.value()
	something(n)
}

The iterator will automatically detect if the start element is bigger than the end element and will perform the iteration backwards.

If the tree has the "cmpval" function specified, we also get a convenience function:

(*<tree type>).iterVal(start,end <cmpval type>, edgeStart, edgeEnd, incs, ince bool) *<iter type>

This will create an iterator over all elements where "start >= el" and "el <= end". "incs" and "ince" change the operators to ">" and "<" respectively. "edgeStart" and "edgeEnd" tell the function to ignore the start/end arguments and start/end at the edge of the tree.

By default all functions to access the tree are unexported, this can be changed by adding "export" to the tag.

Generated functions can be disabled (not generated) if you're fighting for a coverage high score. This can be done by adding "no:<func>" to the tag. So for example "no:lookup" won't generate the lookup function. Use on own peril. Some functions are used internally by others and no effort is made to prevent breakage caused by disabling something that is used.