开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多国语言处理 > 信息检索与抽取 > 查看源码
avltr.h
资源名称：swarm-2.2.tar.gz　[点击查看]
上传用户：shenzhenrh
上传日期：2013-05-12
资源大小：2904k
文件大小：4k
源码类别：

信息检索与抽取

开发平台：

Unix_Linux

avltr.h：源码内容
  1. /* libavl - manipulates AVL trees.
  2.    Copyright (C) 1998, 1999 Free Software Foundation, Inc.
  4.    This program is free software; you can redistribute it and/or
  5.    modify it under the terms of the GNU General Public License as
  6.    published by the Free Software Foundation; either version 2 of the
  7.    License, or (at your option) any later version.
  9.    This program is distributed in the hope that it will be useful, but
  10.    WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12.    General Public License for more details.
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  17.    02111-1307, USA.
  19.    The author may be contacted at <pfaffben@pilot.msu.edu> on the
  20.    Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
  21.    through more mundane means. */
  23. /* This is file avltr.h in libavl. */
  25. #if !avltr_h
  26. #define avltr_h 1
  28. /* The default maximum height of 32 allows for AVL trees having
  29.    between 5,704,880 and 4,294,967,295 nodes, depending on order of
  30.    insertion.  You may change this compile-time constant as you
  31.    wish. */
  32. #ifndef AVL_MAX_HEIGHT
  33. #define AVL_MAX_HEIGHT 32
  34. #endif
  36. /* Structure for a node in a right-threaded AVL tree. */
  37. typedef struct avltr_node
  38.   {
  39.     void *data; /* Pointer to data. */
  40.     struct avltr_node *link[2]; /* Subtrees or threads. */
  41.     signed char bal; /* Balance factor. */
  42.     char cache; /* Used during insertion. */
  43.     char pad; /* Reserved for fully threaded trees. */
  44.     signed char rtag; /* Right thread tag. */
  45.   }
  46. avltr_node;
  48. /* Used for traversing a right-threaded AVL tree. */
  49. typedef struct avltr_traverser
  50.   {
  51.     int init; /* Initialized? */
  52.     const avltr_node *p; /* Last node returned. */
  53.   }
  54. avltr_traverser;
  56. /* Initializer for avltr_traverser. */
  57. #define AVLTR_TRAVERSER_INIT {0}
  59. /* Function types. */
  60. #if !AVL_FUNC_TYPES
  61. #define AVL_FUNC_TYPES 1
  62. typedef int (*avl_comparison_func) (const void *a, const void *b, void *param);
  63. typedef void (*avl_node_func) (void *data, void *param);
  64. typedef void *(*avl_copy_func) (void *data, void *param);
  65. #endif
  67. /* Structure which holds information about a threaded AVL tree. */
  68. typedef struct avltr_tree
  69.   {
  70.     avltr_node root; /* Tree root node. */
  71.     avl_comparison_func cmp; /* Used to compare keys. */
  72.     int count; /* Number of nodes in the tree. */
  73.     void *param; /* Arbitary user data. */
  74.   }
  75. avltr_tree;
  77. /* General functions. */
  78. avltr_tree *avltr_create (avl_comparison_func, void *param);
  79. void avltr_destroy (avltr_tree *, avl_node_func);
  80. void avltr_free (avltr_tree *);
  81. int avltr_count (const avltr_tree *);
  82. avltr_tree *avltr_copy (const avltr_tree *, avl_copy_func);
  83. struct avl_tree;
  84. avltr_tree *avltr_thread (struct avl_tree *);
  85. struct avl_tree *avltr_unthread (avltr_tree *);
  87. /* Walk the tree. */
  88. void avltr_walk (const avltr_tree *, avl_node_func, void *param);
  89. void *avltr_traverse (const avltr_tree *, avltr_traverser *);
  90. #define avlt_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
  91. void **avltr_next (const avltr_tree *tree, void **item);
  93. /* Search for a given item. */
  94. void **avltr_probe (avltr_tree *, void *);
  95. void *avltr_delete (avltr_tree *, const void *);
  96. void **avltr_find (const avltr_tree *, const void *);
  97. void **avltr_find_close (const avltr_tree *, const void *);
  99. #if __GCC__ >= 2
  100. extern inline void *
  101. avltr_insert (avltr_tree *tree, void *item)
  102. {
  103.   void **p = avltr_probe (tree, item);
  104.   return (*p == item) ? NULL : *p;
  105. }
  107. extern inline void *
  108. avltr_replace (avltr_tree *tree, void *item)
  109. {
  110.   void **p = avltr_probe (tree, item);
  111.   if (*p == item)
  112.     return NULL;
  113.   else
  114.     {
  115.       void *r = *p;
  116.       *p = item;
  117.       return r;
  118.     }
  119. }
  120. #else /* not gcc */
  121. void *avltr_insert (avltr_tree *tree, void *item);
  122. void *avltr_replace (avltr_tree *tree, void *item);
  123. #endif /* not gcc */
  125. /* Easy assertions on insertion & deletion. */
  126. #ifndef NDEBUG
  127. #define avltr_force_insert(A, B)
  128. do
  129.   {
  130.             void *r = avltr_insert (A, B);
  131.     assert (r == NULL);
  132.   }
  133. while (0)
  134. void *avltr_force_delete (avltr_tree *, void *);
  135. #else
  136. #define avltr_force_insert(A, B)
  137. avltr_insert (A, B)
  138. #define avltr_force_delete(A, B)
  139. avltr_delete (A, B)
  140. #endif
  142. #endif /* avltr_h */