1
0

bintree.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495
  1. /**
  2. \ingroup lub
  3. \defgroup lub_bintree bintree
  4. @{
  5. \brief This interface provides a facility which enables a client to
  6. order and access a set of arbitary data in a binary "tree"
  7. Each "tree" is defined by a number of "clientnodes" which are
  8. ordered according to a client defined "key".
  9. A "clientkey" is a client specific entity which can be compared
  10. with a "clientnode" to determine which is the "greatest". In order
  11. to do this the client needs provide a comparison function for
  12. comparing a "clientnode" with a "clientkey", and a function to
  13. convert a "clientnode" into a "clientkey".
  14. The client is responsible for providing each "clientnode" in a
  15. tree. This will typically contain some client specific data, but
  16. will also need to contain a bintree "node" which is used to
  17. structurally relate each node to one another in the tree. A
  18. specific "node" may only belong to one tree at a time, but an
  19. individual "clientnode" may contain multiple of these if necessary.
  20. \par Implementation
  21. The implementation of this interface uses a top-down splaying algorithm.
  22. \par
  23. "Splay trees", or "self-adjusting search trees" are a simple and
  24. efficient data structure for storing an ordered set. The data
  25. structure consists of a binary tree, without parent pointers, and
  26. no additional fields. It allows searching, insertion, deletion,
  27. deletemin, deletemax, splitting, joining, and many other
  28. operations, all with amortized logarithmic performance. Since the
  29. trees adapt to the sequence of requests, their performance on real
  30. access patterns is typically even better. Splay trees are
  31. described in a number of texts and papers [1,2,3,4,5].
  32. \par
  33. The code here is adapted from simple top-down splay, at the bottom
  34. of page 669 of [3]. It can be obtained via anonymous ftp from
  35. spade.pc.cs.cmu.edu in directory /usr/sleator/public.
  36. \par
  37. The chief modification here is that the splay operation works even
  38. if the item being splayed is not in the tree, and even if the tree
  39. root of the tree is NULL. So the line:
  40. \par
  41. t = splay(i, t);
  42. \par
  43. causes it to search for item with key i in the tree rooted at t.
  44. If it's there, it is splayed to the root. If it isn't there,
  45. then the node put at the root is the last one before NULL that
  46. would have been reached in a normal binary search for i. (It's a
  47. neighbor of i in the tree.) This allows many other operations to
  48. be easily implemented.
  49. \par
  50. [1] "Fundamentals of data structures in C", Horowitz, Sahni,
  51. and Anderson-Freed, Computer Science Press, pp 542-547.
  52. \par
  53. [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
  54. Harper Collins, 1991, pp 243-251.
  55. \par
  56. [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
  57. JACM Volume 32, No 3, July 1985, pp 652-686.
  58. \par
  59. [4] "Data Structure and Algorithm Analysis", Mark Weiss,
  60. Benjamin Cummins, 1992, pp 119-130.
  61. \par
  62. [5] "Data Structures, Algorithms, and Performance", Derick Wood,
  63. Addison-Wesley, 1993, pp 367-375.
  64. \par
  65. The splay function is based on one written by Daniel Sleator, which is released
  66. in the public domain.
  67. \author Graeme McKerrell
  68. \date Created On : Fri Jan 23 12:50:18 2004
  69. \version TESTED
  70. */
  71. /*---------------------------------------------------------------
  72. HISTORY
  73. 7-Dec-2004 Graeme McKerrell
  74. Updated to use the "lub" prefix
  75. 27-Feb-2004 Graeme McKerrell
  76. updated to simplify node initialisation
  77. 9-Feb-2004 Graeme McKerrell
  78. updated to make the comparision function compare a "clientnode" and
  79. "key"
  80. Updated getkey() function to fill out a provides "key" from a "clientnode"
  81. 23-Jan-2004 Graeme McKerrell
  82. Initial version
  83. --------------------------------------------------------------
  84. Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  85. **************************************************************** */
  86. #ifndef _lub_bintree_h
  87. #define _lub_bintree_h
  88. #include <stddef.h>
  89. /****************************************************************
  90. * TYPE DEFINITIONS
  91. **************************************************************** */
  92. /**
  93. * This type represents a bintree "node".
  94. * Typically the client will have a "clientnode" structure which
  95. * contains it's data. A bintree "node" is made one of the data
  96. * elements of that structure. When the tree is initialised the
  97. * client provides the offset into the structure of the
  98. * "node" which is to be used for that tree.
  99. */
  100. typedef struct lub_bintree_node_s lub_bintree_node_t;
  101. /**
  102. * CLIENTS MUSTN'T TOUCH THE CONTENTS OF THIS STRUCTURE
  103. */
  104. struct lub_bintree_node_s
  105. {
  106. /** internal */lub_bintree_node_t *left;
  107. /** internal */lub_bintree_node_t *right;
  108. };
  109. /**
  110. * This type defines a callback function which will compare two "keys"
  111. * with each other
  112. *
  113. * \param clientnode the client node to compare
  114. * \param clientkey the key to compare with a node
  115. *
  116. * \return
  117. * <0 if clientnode < clientkey;
  118. * 0 if clientnode == clientkey;
  119. * >0 if clientnode > clientkey
  120. */
  121. typedef int
  122. lub_bintree_compare_fn(const void *clientnode,
  123. const void *clientkey);
  124. /**
  125. * This is used to size the key storage area for an opaque key.
  126. * If any client requires a greater storage size then this will need to
  127. * be increased.
  128. */
  129. #define lub_bintree_MAX_KEY_STORAGE (200)
  130. /**
  131. * This is used to declare an opaque key structure
  132. * Typically a client would declare their own non-opaque structure
  133. * which they would fill out appropriately
  134. */
  135. typedef struct lub_bintree_key_s lub_bintree_key_t;
  136. /**
  137. * CLIENTS MUSTN'T TOUCH THE CONTENTS OF THIS STRUCTURE
  138. */
  139. struct lub_bintree_key_s
  140. {
  141. /** internal */char storage[lub_bintree_MAX_KEY_STORAGE];
  142. /** internal */int magic;
  143. };
  144. /**
  145. * This type defines a callback function which will convert a client's "node"
  146. * into a search "key"
  147. *
  148. * \param clientnode the node from which to derive a key
  149. * \param key a reference to the key to fill out
  150. *
  151. * \return
  152. * A "key" which corresponds the "node" in this view
  153. */
  154. typedef void
  155. lub_bintree_getkey_fn(const void *clientnode,
  156. lub_bintree_key_t *key);
  157. /**
  158. * This type represents an binary tree instance
  159. */
  160. typedef struct lub_bintree_s lub_bintree_t;
  161. /**
  162. * CLIENTS MUSTN'T TOUCH THE CONTENTS OF THIS STRUCTURE
  163. */
  164. struct lub_bintree_s
  165. {
  166. /** internal */lub_bintree_node_t *root;
  167. /** internal */size_t node_offset;
  168. /** internal */lub_bintree_compare_fn *compareFn;
  169. /** internal */lub_bintree_getkey_fn *getkeyFn;
  170. };
  171. /**
  172. * This is used to perform iterations of a tree
  173. */
  174. typedef struct lub_bintree_iterator_s lub_bintree_iterator_t;
  175. /**
  176. * CLIENTS MUSTN'T TOUCH THE CONTENTS OF THIS STRUCTURE
  177. */
  178. struct lub_bintree_iterator_s
  179. {
  180. /** internal */lub_bintree_t *tree;
  181. /** internal */lub_bintree_key_t key;
  182. };
  183. /****************************************************************
  184. * BINTREE OPERATIONS
  185. **************************************************************** */
  186. /**
  187. * This operation initialises an instance of a binary tree.
  188. *
  189. * \pre none
  190. *
  191. * \post The tree is ready to have client nodes inserted.
  192. */
  193. extern void
  194. lub_bintree_init(
  195. /**
  196. * the "tree" instance to initialise
  197. */
  198. lub_bintree_t *tree,
  199. /**
  200. * the offset of the bintree "node" structure within the
  201. * "clientnode" structure. This is typically passed
  202. * using the offsetof() macro.
  203. */
  204. size_t node_offset,
  205. /**
  206. * a comparison function for comparing a "clientnode"
  207. * with a "clientkey"
  208. */
  209. lub_bintree_compare_fn compareFn,
  210. /**
  211. * a function which will fill out a "key" from a clientnode
  212. */
  213. lub_bintree_getkey_fn getkeyFn
  214. );
  215. /**
  216. * This operation is called to initialise a "clientnode" ready for
  217. * insertion into a tree. This is only required once after the memory
  218. * for a node has been allocated.
  219. *
  220. * \pre none
  221. *
  222. * \post The node is ready to be inserted into a tree.
  223. */
  224. extern void
  225. lub_bintree_node_init(
  226. /**
  227. * the bintree node to initialise
  228. */
  229. lub_bintree_node_t *node
  230. );
  231. /*****************************************
  232. * NODE MANIPULATION OPERATIONS
  233. ***************************************** */
  234. /**
  235. * This operation adds a client node to the specified tree.
  236. *
  237. * \pre The tree must be initialised
  238. * \pre The clientnode must be initialised
  239. *
  240. * \return
  241. * 0 if the "clientnode" is added correctly to the tree.
  242. * If another "clientnode" already exists in the tree with the same key, then
  243. * -1 is returned, and the tree remains unchanged.
  244. *
  245. * \post If the bintree "node" is already part of a tree, then an
  246. * assert will fire.
  247. */
  248. extern int
  249. lub_bintree_insert(
  250. /**
  251. * the "tree" instance to invoke this operation upon
  252. */
  253. lub_bintree_t *tree,
  254. /**
  255. * a pointer to a client node. NB the tree can find the
  256. * necessary lub_BintreeNodeT from it's stored offset.
  257. */
  258. void *clientnode
  259. );
  260. /**
  261. * This operation removes a "clientnode" from the specified "tree"
  262. *
  263. * \pre The tree must be initialised
  264. * \pre The clientnode must be initialised
  265. *
  266. * \post The "clientnode" will no longer be part of the specified tree, and will be
  267. * made available for re-insertion
  268. * \post If the clientnode is not present in the specified tree, then an
  269. * assert will fire.
  270. */
  271. extern void
  272. lub_bintree_remove(
  273. /**
  274. * the "tree" instance to invoke this operation upon
  275. */
  276. lub_bintree_t *tree,
  277. /**
  278. * the node to remove
  279. */
  280. void *clientnode
  281. );
  282. /*****************************************
  283. * NODE RETRIEVAL OPERATIONS
  284. ***************************************** */
  285. /**
  286. * This operation returns the first "clientnode" present in the specified "tree"
  287. *
  288. * \pre The tree must be initialised
  289. *
  290. * \return
  291. * "clientnode" instance or NULL if no nodes are present in this tree.
  292. */
  293. extern void *
  294. lub_bintree_findfirst(
  295. /**
  296. * the "tree" instance to invoke this operation upon
  297. */
  298. lub_bintree_t *tree
  299. );
  300. /**
  301. * This operation returns the last "clientnode" present in the specified "tree"
  302. *
  303. * \pre The tree must be initialised
  304. *
  305. * \return
  306. * "clientnode" instance or NULL if no nodes are present in this tree.
  307. */
  308. extern void *
  309. lub_bintree_findlast(
  310. /**
  311. * the "tree" instance to invoke this operation upon
  312. */
  313. lub_bintree_t *tree
  314. );
  315. /**
  316. * This operation searches the specified "tree" for a "clientnode" which matches the
  317. * specified "key"
  318. *
  319. * \pre The tree must be initialised
  320. *
  321. * \return
  322. * "clientnode" instance or NULL if no node is found.
  323. */
  324. extern void *
  325. lub_bintree_find(
  326. /**
  327. * the "tree" instance to invoke this operation upon
  328. */
  329. lub_bintree_t *tree,
  330. /**
  331. * the "key" to search with
  332. */
  333. const void *key
  334. );
  335. /**
  336. * This operation searches the specified "tree" for a "clientnode" which is
  337. * the one which logically follows the specified "key"
  338. *
  339. * A "clientnode" with the specified "key" doesn't need to be in the tree.
  340. *
  341. * \pre The tree must be initialised
  342. *
  343. * \return
  344. * "clientnode" instance or NULL if no node is found.
  345. */
  346. extern void *
  347. lub_bintree_findnext(
  348. /**
  349. * the "tree" instance to invoke this operation upon
  350. */
  351. lub_bintree_t *tree,
  352. /**
  353. * the "key" to search with
  354. */
  355. const void *key
  356. );
  357. /**
  358. * This operation searches the specified "tree" for a "clientnode" which is
  359. * the one which logically preceeds the specified "key"
  360. *
  361. * A "clientnode" with the specified "key" doesn't need to be in the tree.
  362. *
  363. * \pre The tree must be initialised
  364. *
  365. * \return
  366. * "clientnode" instance or NULL if no node is found.
  367. */
  368. extern void *
  369. lub_bintree_findprevious(
  370. /**
  371. * the "tree" instance to invoke this operation upon
  372. */
  373. lub_bintree_t *tree,
  374. /**
  375. * the "key" to search with
  376. */
  377. const void *key
  378. );
  379. /*****************************************
  380. * ITERATION OPERATIONS
  381. ***************************************** */
  382. /**
  383. * This operation initialises an iterator. This can then be
  384. * subsequently used for iterating through a tree. This will work
  385. * even if the "clientnode" which defined the current iterator has been
  386. * removed before the next iterator operation.
  387. *
  388. * \pre The tree must be initialised
  389. * \pre The clientnode must be initialised and valid at the time of this call
  390. *
  391. * \post The interator instance will be updated to reference the position in the tree for the clientnode.
  392. */
  393. extern void
  394. lub_bintree_iterator_init(
  395. /**
  396. * the iterator instance to initialise
  397. */
  398. lub_bintree_iterator_t *iter,
  399. /**
  400. * the tree to associate with this iterator
  401. */
  402. lub_bintree_t *tree,
  403. /**
  404. * the starting point for the iteration
  405. */
  406. const void *clientnode
  407. );
  408. /**
  409. * This operation returns the next "clientnode" in an iteration.
  410. *
  411. * \pre The interator instance must have been initialised
  412. *
  413. * \return
  414. * "clientnode" instance or NULL if the iteration has reached the end of the
  415. * tree.
  416. *
  417. * \post The interator instance will be updated to reference the position in the tree for the returned value.
  418. */
  419. extern void *
  420. lub_bintree_iterator_next(
  421. /**
  422. * the iterator instance to invoke this operation upon.
  423. */
  424. lub_bintree_iterator_t *iter
  425. );
  426. /**
  427. * This operation returns the previous "clientnode" in an iteration.
  428. *
  429. * \pre The interator instance must have been initialised
  430. *
  431. * \return
  432. * "clientnode" instance or NULL if the iteration has reached the beginning
  433. * of the tree.
  434. *
  435. * \post The interator instance will be updated to reference the position in the tree for the returned value.
  436. */
  437. extern void *
  438. lub_bintree_iterator_previous(
  439. /**
  440. * the iterator instance to invoke this operation upon.
  441. */
  442. lub_bintree_iterator_t *iter
  443. );
  444. /**
  445. * This operation dumps the node list of the specified tree to stdout
  446. *
  447. * \pre The tree must be initialised
  448. *
  449. * \post The structure of the tree will be unaltered.
  450. */
  451. extern void
  452. lub_bintree_dump(
  453. /**
  454. * the "tree" instance to invoke this operation upon
  455. */
  456. lub_bintree_t *tree
  457. );
  458. #endif /* _lub_bintree_h */
  459. /** @} */