User space data

The "Unix way" would be to make it a file and/or a directory structure from user view, doing a driver that offers "open" "read", etc.

-Michael

Michael,

Are you referring to writing the binary tree to a file? Can you elaborate?

Thanks, Shobha.

Michael Schnell wrote:

Why not ?

The user program can do (e.g.) seek() and read()/write(). These calls are transferred 1:1 to the driver. So (AFAIK) a seek to n+1 and read a byte does not necessary need to offer the same byte as the second byte of two bytes read after seeking to n. Moreover the result of a read can change dynamically with any instance.

So a seek could provide a "tree address" of some kind (e.g. each bit a path though the binary tree) and a read could return the leaf data (maybe including some kind of linked list data (next/previous leaf) if useful).

Overwriting a leaf would be similar as reading, creating a new leaf might use seek(,,end).

Moreover there are ioctl() calls that can be used for configuration or other special purposes.

-Michael

Not quite the same thing, but SNOBOL (a very early string processing language, which pioneered what had become regular expressions) had user-definable, arbitrary data structures. Binary trees were easily doable...

In the above scenario, all you really need to provide is a direction to the next node/leaf. So a seek for a binary tree has 3 directions: parent, left child, right child, for a ternary tree it has 4 directions, and for an arbitrary n tree it has up to n+1 directions... Although that can be simplified to 4 by using parent, left sibling, right sibling, and child.

There is considerable prior art in implementing these kinds of data structures... So a bit of research might yield good results...

--Yan