tree.h 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
  1. /*
  2. * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
  3. *
  4. * This file is part of FFmpeg.
  5. *
  6. * FFmpeg is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU Lesser General Public
  8. * License as published by the Free Software Foundation; either
  9. * version 2.1 of the License, or (at your option) any later version.
  10. *
  11. * FFmpeg is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14. * Lesser General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU Lesser General Public
  17. * License along with FFmpeg; if not, write to the Free Software
  18. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19. */
  20. /**
  21. * @file
  22. * A tree container.
  23. * @author Michael Niedermayer <michaelni@gmx.at>
  24. */
  25. #ifndef AVUTIL_TREE_H
  26. #define AVUTIL_TREE_H
  27. /**
  28. * @addtogroup lavu_tree AVTree
  29. * @ingroup lavu_data
  30. *
  31. * Low complexity tree container
  32. *
  33. * Insertion, removal, finding equal, largest which is smaller than and
  34. * smallest which is larger than, all have O(log n) worst case complexity.
  35. * @{
  36. */
  37. struct AVTreeNode;
  38. extern const int av_tree_node_size;
  39. /**
  40. * Find an element.
  41. * @param root a pointer to the root node of the tree
  42. * @param next If next is not NULL, then next[0] will contain the previous
  43. * element and next[1] the next element. If either does not exist,
  44. * then the corresponding entry in next is unchanged.
  45. * @return An element with cmp(key, elem)==0 or NULL if no such element exists in
  46. * the tree.
  47. */
  48. void *av_tree_find(const struct AVTreeNode *root, void *key, int (*cmp)(void *key, const void *b), void *next[2]);
  49. /**
  50. * Insert or remove an element.
  51. * If *next is NULL, then the supplied element will be removed if it exists.
  52. * If *next is not NULL, then the supplied element will be inserted, unless
  53. * it already exists in the tree.
  54. * @param rootp A pointer to a pointer to the root node of the tree; note that
  55. * the root node can change during insertions, this is required
  56. * to keep the tree balanced.
  57. * @param next Used to allocate and free AVTreeNodes. For insertion the user
  58. * must set it to an allocated and zeroed object of at least
  59. * av_tree_node_size bytes size. av_tree_insert() will set it to
  60. * NULL if it has been consumed.
  61. * For deleting elements *next is set to NULL by the user and
  62. * av_tree_node_size() will set it to the AVTreeNode which was
  63. * used for the removed element.
  64. * This allows the use of flat arrays, which have
  65. * lower overhead compared to many malloced elements.
  66. * You might want to define a function like:
  67. * @code
  68. * void *tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
  69. * if(!*next) *next= av_mallocz(av_tree_node_size);
  70. * return av_tree_insert(rootp, key, cmp, next);
  71. * }
  72. * void *tree_remove(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b, AVTreeNode **next)){
  73. * av_freep(next);
  74. * return av_tree_insert(rootp, key, cmp, next);
  75. * }
  76. * @endcode
  77. * @return If no insertion happened, the found element; if an insertion or
  78. * removal happened, then either key or NULL will be returned.
  79. * Which one it is depends on the tree state and the implementation. You
  80. * should make no assumptions that it's one or the other in the code.
  81. */
  82. void *av_tree_insert(struct AVTreeNode **rootp, void *key, int (*cmp)(void *key, const void *b), struct AVTreeNode **next);
  83. void av_tree_destroy(struct AVTreeNode *t);
  84. /**
  85. * Apply enu(opaque, &elem) to all the elements in the tree in a given range.
  86. *
  87. * @param cmp a comparison function that returns < 0 for a element below the
  88. * range, > 0 for a element above the range and == 0 for a
  89. * element inside the range
  90. *
  91. * @note The cmp function should use the same ordering used to construct the
  92. * tree.
  93. */
  94. void av_tree_enumerate(struct AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem));
  95. /**
  96. * @}
  97. */
  98. #endif /* AVUTIL_TREE_H */