Main Page Alphabetical List Data Structures File List Data Fields Globals

dt_node.h File Reference

Detailed Description

Public interface for in-memory handling of a DataTree structure.

Types of nodes in a datatree

In memory, a DataTree is handled as a tree of nodes, which are accessible through a dt_node* pointer. Each node can be either:

a leaf node containing a fixed-size chunk of data - created with dt_make_leaf()
an array of sub-nodes - created using dt_make_arr()
an record (or dictionary), where each sub-node is associated with a unique key - created using dt_make_rec()

Reference Counting: All nodes support reference-counting: multiple owners can share a node by calling dt_node_addref().
Newly created node have a reference count (or use count) initially set to 1.
Users of a node can release it by calling dt_node_release(). This will decrement the use count, and delete the node if the use count reaches zero.

Note:: If you share the ownership of nodes in your code, be aware that no copy-on-write is automatically supported: if you modify a record or array using one reference, all other pointers that refer to it will be affected.

Sub-Nodes

When a sub-node is added to an array or record, the caller transfers node ownership to the parent. That is, the parent will release the node (by calling dt_node_release) when it is destroyed.
This means that:

the caller who adds a node to a parent shall call dt_node_addref() if it wants to keep using the node after the parent has been released.
if the caller modifies the node after adding it to a parent, the node stored in the parent will itself be modified.

Note:: If a call that adds a sub-node to a parent fails and returns 0 (for example because of a memory error), the child node is still released.

Definition in file dt_node.h.

Go to the source code of this file.

Typedefs

typedef dt_node_ dt_node

Enumerations

enum dt_node_kind { dt_leaf_node, dt_arr_node, dt_rec_node }

A value that identifies the type of a node. More...

Functions

void dt_node_addref (dt_node *node)

Increment the use count of a node.

void dt_node_release (dt_node *node)

Decrement the use count of a node, and free the node if the count reaches zero.

enum dt_node_kind dt_node_get_kind (dt_node *node)

Returns the type of the node referred to by node.

dt_bool dt_leaf_get_data (dt_node const *leaf, dt_byte const **begin, size_t *len)

Access the data associated with a leaf node.

size_t dt_arr_get_size (dt_node const *arr)

Returns the number of sub-nodes available in an array node.

dt_node * dt_arr_get (dt_node const *arr, unsigned ind)

Returns the sub-node of the array node located at index ind.

dt_bool dt_arr_put (dt_node *arr, unsigned ind, dt_node *item)

Assign a new sub-node to a specified existing index within the array.

dt_bool dt_arr_append (dt_node *arr, dt_node *item)

Appends a new sub-node to the end of an array node.

size_t dt_rec_get_size (dt_node const *node)

Returns the number of sub-nodes available in the record node.

dt_node * dt_rec_get (dt_node const *rec, dt_byte const *key, size_t key_len)

Returns the sub-node of the record node which is associated with key (of length key_len).

dt_node * dt_rec_sget (dt_node const *rec, char const *key)

Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.

dt_bool dt_rec_put (dt_node *rec, dt_byte const *key, size_t key_len, dt_node *item)

Put a sub-node associated with key (of length key_len) in the record node.

dt_bool dt_rec_sput (dt_node *rec, char const *key, dt_node *item)

Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.

dt_node * dt_rec_get_nth (dt_node *rec, unsigned ind, dt_byte const **key, size_t *key_len)

Returns information about the ind -th item in the record node.

Typedef Documentation

typedef struct dt_node_ dt_node

Definition at line 46 of file dt_node.h.

Enumeration Type Documentation

enum dt_node_kind

A value that identifies the type of a node.

Enumeration values:

dt_leaf_node

dt_arr_node

dt_rec_node

Definition at line 44 of file dt_node.h.

Function Documentation

dt_bool dt_arr_append ( dt_node * arr,

dt_node * item

)

Appends a new sub-node to the end of an array node.

Parameters:

arr The array node in which an item is to be added.

item The node to be inserted, for which the caller gives up ownership. ( this means it must be newly created, or dt_node_addref() must have been called ).

Returns:
A non-zero value if node is an array and item was successfully inserted.
Zero if memory could not be allocated, node is not an array, or item is null.

Note:
In case of failure, a non-null item will have been disposed of by calling dt_node_release().

Definition at line 219 of file dt_node_impl.c.

dt_node* dt_arr_get ( dt_node const * arr,

unsigned ind

)

Returns the sub-node of the array node located at index ind.
A NULL return value indicates that node is not an array node or that ind is out-of-range.
Definition at line 183 of file dt_node_impl.c.

size_t dt_arr_get_size ( dt_node const * arr )

Returns the number of sub-nodes available in an array node.
A return value of zero indicates that the array is empty, or that arr is not an array node.
Definition at line 173 of file dt_node_impl.c.

dt_bool dt_arr_put ( dt_node * arr,

unsigned ind,

dt_node * item

)

Assign a new sub-node to a specified existing index within the array.

Parameters:

arr The array node in which an item is to be replaced

ind The index, within the array, where the node is to be replaced.

item The node to be inserted, for which the caller gives up ownership. ( this means it must be newly created, or dt_node_addref() must have been called ).

Returns:
A non-zero value if node is an array and ind is a valid index.
Zero if item could not be inserted, and has immediately been disposed of by calling dt_node_release().

Definition at line 195 of file dt_node_impl.c.

dt_bool dt_leaf_get_data ( dt_node const * leaf,

dt_byte const ** begin,

size_t * len

)

Access the data associated with a leaf node.

Parameters:

leaf The leaf node whose contents are being queried.

begin The address of a pointer which, upon successful exit, will point to the beginning of the data.

len The address of a variable which, upon successful exit, will be set to the length of the node's data.

Returns:
A non-zero value if the call was successful.
Zero will be returned if node is not a leaf node.

Definition at line 159 of file dt_node_impl.c.

dt_node* dt_make_arr ( )

Returns a new empty array node.

Definition at line 82 of file dt_node_impl.c.

dt_node* dt_make_leaf ( dt_byte const * begin,

size_t len

)

Returns a new leaf node containing the data starting at begin of length len.

Definition at line 44 of file dt_node_impl.c.

dt_node* dt_make_rec ( )

Returns a new empty record node.

Definition at line 63 of file dt_node_impl.c.

void dt_node_addref ( dt_node * node )

Increment the use count of a node.

Definition at line 102 of file dt_node_impl.c.

enum dt_node_kind dt_node_get_kind ( dt_node * node )

Returns the type of the node referred to by node.

Definition at line 152 of file dt_node_impl.c.

void dt_node_release ( dt_node * node )

Decrement the use count of a node, and free the node if the count reaches zero.
When the use count reaches zero, the memory allocated for the node is released, and dt_node_release is called for all the direct sub-nodes it might contain.
Definition at line 111 of file dt_node_impl.c.

dt_node* dt_rec_get ( dt_node const * rec,

dt_byte const * key,

size_t key_len

)

Returns the sub-node of the record node which is associated with key (of length key_len).
A NULL return value indicates that node is not an array node, or that the record does not contain a key matching (key,key_len).
Definition at line 303 of file dt_node_impl.c.

dt_node* dt_rec_get_nth ( dt_node * rec,

unsigned ind,

dt_byte const ** key,

size_t * key_len

)

Returns information about the ind -th item in the record node.

Returns:
The requested sub-node, or NULL if rec is not a record node or ind is out-of-range.

Parameters:

rec The record from which contents are queried

ind The index within rec of the record entry being queried.

key The optional address of a pointer which, if the return value is not NULL, will point to the beginning of the key associated with the node.

key_len The optional address of a size value which, if the return value is not NULL, will be set to the length of the key associated with the node.

Definition at line 386 of file dt_node_impl.c.

size_t dt_rec_get_size ( dt_node const * node )

Returns the number of sub-nodes available in the record node.
A return value of zero indicates that the record is empty, or that node is not an record node.
Definition at line 235 of file dt_node_impl.c.

dt_bool dt_rec_put ( dt_node * rec,

dt_byte const * key,

size_t key_len,

dt_node * item

)

Put a sub-node associated with key (of length key_len) in the record node.

Parameters:

rec The record in which the sub-node is to be placed.

key,key_len The addess and legth of the key data with which the item is to be associated.

item The sub-node to be added, for which the caller gives up ownership. ( this means it must be newly created, or dt_node_addref() must have been called ).

Returns:
A non-zero value if node is a record and item was successfully inserted.
Zero on failure, if memory could not be allocated or node is not a record -- in which case item will have been disposed of by calling dt_node_release().

Note:
If (key,key_len) was previously associated with another item, the previous item is replaced and released.

Definition at line 330 of file dt_node_impl.c.

dt_node* dt_rec_sget ( dt_node const * rec,

char const * key

)

Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.

Definition at line 320 of file dt_node_impl.c.

dt_bool dt_rec_sput ( dt_node * rec,

char const * key,

dt_node * item

)

Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.

Definition at line 379 of file dt_node_impl.c.

Generated on Sun Jun 1 16:35:38 2003 for datatree by

1.3.1


Typedefs
typedef dt_node_	dt_node
Enumerations
enum	dt_node_kind { dt_leaf_node, dt_arr_node, dt_rec_node }
	A value that identifies the type of a node. More...
Functions
void	dt_node_addref (dt_node *node)
	Increment the use count of a node.
void	dt_node_release (dt_node *node)
	Decrement the use count of a node, and free the node if the count reaches zero.
enum dt_node_kind	dt_node_get_kind (dt_node *node)
	Returns the type of the node referred to by node.
dt_bool	dt_leaf_get_data (dt_node const leaf, dt_byte const begin, size_t len)
	Access the data associated with a leaf node.
size_t	dt_arr_get_size (dt_node const *arr)
	Returns the number of sub-nodes available in an array node.
dt_node *	dt_arr_get (dt_node const *arr, unsigned ind)
	Returns the sub-node of the array node located at index ind.
dt_bool	dt_arr_put (dt_node arr, unsigned ind, dt_node item)
	Assign a new sub-node to a specified existing index within the array.
dt_bool	dt_arr_append (dt_node arr, dt_node item)
	Appends a new sub-node to the end of an array node.
size_t	dt_rec_get_size (dt_node const *node)
	Returns the number of sub-nodes available in the record node.
dt_node *	dt_rec_get (dt_node const rec, dt_byte const key, size_t key_len)
	Returns the sub-node of the record node which is associated with key (of length key_len).
dt_node *	dt_rec_sget (dt_node const rec, char const key)
	Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.
dt_bool	dt_rec_put (dt_node rec, dt_byte const key, size_t key_len, dt_node *item)
	Put a sub-node associated with key (of length key_len) in the record node.
dt_bool	dt_rec_sput (dt_node rec, char const key, dt_node *item)
	Identical to dt_rec_get(), but takes a zero-terminated string key to define the key.
dt_node *	dt_rec_get_nth (dt_node rec, unsigned ind, dt_byte const key, size_t key_len)
	Returns information about the ind -th item in the record node.