diff options
Diffstat (limited to 'avl-1.4.0/avltr.h')
| -rw-r--r-- | avl-1.4.0/avltr.h | 142 |
1 files changed, 0 insertions, 142 deletions
diff --git a/avl-1.4.0/avltr.h b/avl-1.4.0/avltr.h deleted file mode 100644 index 27465ef..0000000 --- a/avl-1.4.0/avltr.h +++ /dev/null @@ -1,142 +0,0 @@ -/* libavl - manipulates AVL trees. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. - - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of the - License, or (at your option) any later version. - - This program is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. - - The author may be contacted at <pfaffben@pilot.msu.edu> on the - Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA - through more mundane means. */ - -/* This is file avltr.h in libavl. */ - -#if !avltr_h -#define avltr_h 1 - -/* The default maximum height of 32 allows for AVL trees having - between 5,704,880 and 4,294,967,295 nodes, depending on order of - insertion. You may change this compile-time constant as you - wish. */ -#ifndef AVL_MAX_HEIGHT -#define AVL_MAX_HEIGHT 32 -#endif - -/* Structure for a node in a right-threaded AVL tree. */ -typedef struct avltr_node - { - void *data; /* Pointer to data. */ - struct avltr_node *link[2]; /* Subtrees or threads. */ - signed char bal; /* Balance factor. */ - char cache; /* Used during insertion. */ - char pad; /* Reserved for fully threaded trees. */ - signed char rtag; /* Right thread tag. */ - } -avltr_node; - -/* Used for traversing a right-threaded AVL tree. */ -typedef struct avltr_traverser - { - int init; /* Initialized? */ - const avltr_node *p; /* Last node returned. */ - } -avltr_traverser; - -/* Initializer for avltr_traverser. */ -#define AVLTR_TRAVERSER_INIT {0} - -/* Function types. */ -#if !AVL_FUNC_TYPES -#define AVL_FUNC_TYPES 1 -typedef int (*avl_comparison_func) (const void *a, const void *b, void *param); -typedef void (*avl_node_func) (void *data, void *param); -typedef void *(*avl_copy_func) (void *data, void *param); -#endif - -/* Structure which holds information about a threaded AVL tree. */ -typedef struct avltr_tree - { - avltr_node root; /* Tree root node. */ - avl_comparison_func cmp; /* Used to compare keys. */ - int count; /* Number of nodes in the tree. */ - void *param; /* Arbitary user data. */ - } -avltr_tree; - -/* General functions. */ -avltr_tree *avltr_create (avl_comparison_func, void *param); -void avltr_destroy (avltr_tree *, avl_node_func); -void avltr_free (avltr_tree *); -int avltr_count (const avltr_tree *); -avltr_tree *avltr_copy (const avltr_tree *, avl_copy_func); -struct avl_tree; -avltr_tree *avltr_thread (struct avl_tree *); -struct avl_tree *avltr_unthread (avltr_tree *); - -/* Walk the tree. */ -void avltr_walk (const avltr_tree *, avl_node_func, void *param); -void *avltr_traverse (const avltr_tree *, avltr_traverser *); -#define avlt_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0) -void **avltr_next (const avltr_tree *tree, void **item); - -/* Search for a given item. */ -void **avltr_probe (avltr_tree *, void *); -void *avltr_delete (avltr_tree *, const void *); -void **avltr_find (const avltr_tree *, const void *); -void **avltr_find_close (const avltr_tree *, const void *); - -#if __GCC__ >= 2 -extern inline void * -avltr_insert (avltr_tree *tree, void *item) -{ - void **p = avltr_probe (tree, item); - return (*p == item) ? NULL : *p; -} - -extern inline void * -avltr_replace (avltr_tree *tree, void *item) -{ - void **p = avltr_probe (tree, item); - if (*p == item) - return NULL; - else - { - void *r = *p; - *p = item; - return r; - } -} -#else /* not gcc */ -void *avltr_insert (avltr_tree *tree, void *item); -void *avltr_replace (avltr_tree *tree, void *item); -#endif /* not gcc */ - -/* Easy assertions on insertion & deletion. */ -#ifndef NDEBUG -#define avltr_force_insert(A, B) \ - do \ - { \ - void *r = avltr_insert (A, B); \ - assert (r == NULL); \ - } \ - while (0) -void *avltr_force_delete (avltr_tree *, void *); -#else -#define avltr_force_insert(A, B) \ - avltr_insert (A, B) -#define avltr_force_delete(A, B) \ - avltr_delete (A, B) -#endif - -#endif /* avltr_h */ |