--- name: "wnbtr" section: "3" platform: "linux" package: "libwn-dev" version: "6.0-17" release: "Debian 4.0 (Etch)" platforms: ["linux"] url: "https://new.carta.tech/wnbtr" --- # wnbtr(3) generic sorted tree package ## NAME wn\_bverify, wn\_mkbtree, wn\_freebtree, wn\_bget, wn\_bins, wn\_bdel, wn\_bmove, wn\_bget\_index\_of\_handle, wn\_bget\_handle\_of\_index, wn\_bact, wn\_bcount - generic sorted tree package ## SYNOPSIS ``` #include WN_B_MIN WN_B_MAX WN_B_LT WN_B_GT WN_B_LE WN_B_GE WN_B_EQ wn_btree tree; wn_bhandle handle; ptr handle->key; ptr handle->contents; wn_mkbtree(*tree,pcompare_keys_func,palloc_copy_key_func,pfree_key_func) wn_btree tree; int (*pcompare_keys_func)(/*key1,key2*/); /* ptr key1,key2; */ void (*palloc_copy_key_func)(/*&out_key,in_key*/); /* ptr out_key,in_key */ void (*pfree_key_func)(/*key*/); /* ptr key; */ wn_freebtree(tree) wn_btree tree; wn_bget(&handle,tree,key,compare) wn_bhandle handle; wn_btree tree; ptr key; int compare; wn_bins(&handle,tree,key) wn_bhandle handle; wn_btree tree; ptr key; wn_bdel(handle,tree) wn_bhandle handle; wn_btree tree; wn_bmove(handle,tree,new_key); wn_bhandle handle; wn_btree tree; ptr new_key; wn_bget_index_of_handle(*index,tree,handle) int index; wn_btree tree; wn_bhandle handle; wn_bget_handle_of_index(*handle,tree,index) wn_bhandle handle; wn_btree tree; int index; wn_bact(tree,paction,low_key,low_compare,high_key,high_compare) wn_btree tree; void (*paction)(/*handle*/); ptr low_key,high_key; int low_compare,high_compare; int wn_bcount(tree) wn_btree tree; wn_bverify(tree) wn_btree tree; ``` ## DESCRIPTION A \ allows one to efficiently search a large set of keys for keys with a desired magnitude or range of magnitudes. This package implements a fully general sorted tree, which may be used as a priority queue, small database, sparse array, etc. However, this generality costs in both time and space; it is best to use one of the less general \>wn" packages if possible. If key ordering is unimportant, use [wnhtab(3)](/wnhtab/3.md) instead. If ordering is important, you might be able to use [wnsort(3)](/wnsort/3.md) instead, possibly preceded by [wnhtab(3)](/wnhtab/3.md). This package allows one to easily produce an efficient sorted tree (in this case, a balanced binary tree) for any kind of key. The type **wn\_btree** is the generic sorted tree type. This package provides routines to efficiently create, insert into, search, and delete from these generic sorted trees. **wn\_mkbtree** allocates a **wn\_btree** from the current memory group. All memory allocations and frees triggered by other **wnbtr** calls will use the same memory group as **wn\_mkbtree**. The function arguments tell **wn\_mkbtree** what kind of sorted tree to make. *pcompare\_keys\_func* returns an int \>, ==, or \< to 0, according to whether *key1* is \>, ==, or \< than *key2*. *palloc\_copy\_key\_func* is used to make a private copy of the key when an insert is done. *pfree\_key\_func* frees this private memory when a delete is done. *pfree\_key\_func* is frequently set to a do nothing function. Using these arguments to **wn\_mkbtree**, it is possible to make a sorted tree for any kind of key. Routines for frequently used kinds of keys, such as ints, doubles, and strings, are provided in \. **wn\_freebtree** frees \ into the memory group it was allocated from. **wn\_bget** gets the handle from *tree* whose key meets the specification of *key* and *compare*. If *tree* does not contain a handle whose key meets this specification, *handle* is set to **NULL**. *compare* must be one of **WN\_B\_MIN**, **WN\_B\_MAX**, **WN\_B\_LT**, **WN\_B\_GT**, **WN\_B\_LE**, **WN\_B\_GE**, or **WN\_B\_EQ**.\ If *compare* is **WN\_B\_MIN** , *key* is ignored and *handle* is set to the handle whose key is the smallest in *tree*.\ If *compare* is **WN\_B\_MAX** , *key* is ignored and *handle* is set to the handle whose key is the largest in *tree*.\ If *compare* is **WN\_B\_LT** , *handle* is set to the handle whose key is the largest less than *key*.\ If *compare* is **WN\_B\_GT** , *handle* is set to the handle whose key is the smallest greater than *key*.\ If *compare* is **WN\_B\_LE** , *handle* is set to the handle whose key is the largest less than or equal to *key*.\ If *compare* is **WN\_B\_GE** , *handle* is set to the handle whose key is the smallest greater than or equal to *key*.\ If *compare* is **WN\_B\_EQ** , *handle* is set to a handle whose key is equal to *key*. **wn\_bins** makes a handle in *tree* for *key*. This handle is placed in *handle*. The client program should place a pointer to any client data to be associated with *key* in *handle*-\>contents. The client program should save *handle* because many routines require *handle* rather than *key*. It is legal to have more than one handle with the same key. **wn\_bdel** deletes the handle *handle* from *tree*. **wn\_bmove** changes the key of *handle* to *new\_key* and reorganizes *tree* to reflect this change. It is a grave error to set *handle*-\>key directly, without using **wn\_bmove**. **wn\_bget\_index\_of\_handle** computes the number of handles with keys less than the key of *handle* and places the result in *index*. Handles with keys equal to the key of *handle* are placed in arbitrary order; some of these will also be counted. **wn\_bget\_handle\_of\_index** is the inverse of **wn\_bget\_index\_of\_handle**. It finds the handle whose key is larger than exactly *index* keys. **wn\_bact** calls (\**paction*)(/\**handle*\*/) for every handle in *tree* that is in the range specified, in increasing order. **wn\_bcount** returns the number of handles in *tree*. **wn\_bverify** checks that *tree* is not messed up in some way. ## RESOURCES **wn\_bget**, **wn\_bins**, **wn\_bdel**, **wn\_bmove**, **wn\_bget\_index\_of\_handle**, and **wn\_bget\_handle\_of\_index** require WORST and AVERAGE CASE: time = log(n)\ stack memory = 1\ dynamic memory = 0 **wn\_bact** requires WORST and AVERAGE CASE: time = log(n)\*\\ stack memory = log(n)\ dynamic memory = 0 **wn\_bcount** requires WORST and AVERAGE CASE: time = 1\ stack memory = 0\ dynamic memory = 0 The sorted tree uses memory WORST and AVERAGE CASE: dynamic memory = n In the above, n is the number of entries in the table. These requirements have worse constant factors than for similar operations in \ and "wnsort". ## DIAGNOSTICS **wn\_bact** crashes with a message if the range specified is not meaningful. **wn\_bverify** crashes with a message if *tree* is messed up. ## SEE ALSO [**wnbtrl**(3)](/wnbtrl/3.md), **wnsrtl**(3), **wnddtr**(3), [**wnhtab**(3)](/wnhtab/3.md), [**wnsort**(3)](/wnsort/3.md) *cc/low/examples.c* ## AUTHOR Will Naylor