← Back to branch summary

~ubuntu-branches/ubuntu/hardy/luatex/hardy

« back to all changes in this revision

Viewing changes to src/texk/web2c/luatexdir/avl.h

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Preining
  • Date: 2007-09-24 12:56:11 UTC
  • Revision ID: james.westby@ubuntu.com-20070924125611-a8ge689azbptxvla
Tags: upstream-0.11.2
Import upstream version 0.11.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/texk/web2c/luatexdir/avl.h
 
1
/* Produced by texiweb from libavl.w. */
 
2
 
 
3
/* libavl - library for manipulation of binary trees.
 
4
   Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc.
 
5
 
 
6
   This program is free software; you can redistribute it and/or
 
7
   modify it under the terms of the GNU General Public License as
 
8
   published by the Free Software Foundation; either version 2 of the
 
9
   License, or (at your option) any later version.
 
10
 
 
11
   This program is distributed in the hope that it will be useful, but
 
12
   WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
14
   See the GNU General Public License for more details.
 
15
 
 
16
   You should have received a copy of the GNU General Public License
 
17
   along with this program; if not, write to the Free Software
 
18
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 
19
   02111-1307, USA.
 
20
 
 
21
   The author may be contacted at <blp@gnu.org> on the Internet, or
 
22
   write to Ben Pfaff, Stanford University, Computer Science Dept., 353
 
23
   Serra Mall, Stanford CA 94305, USA.
 
24
*/
 
25
 
 
26
#ifndef AVL_H
 
27
#define AVL_H 1
 
28
 
 
29
#include <stddef.h>
 
30
 
 
31
/* Function types. */
 
32
typedef int avl_comparison_func (const void *avl_a, const void *avl_b,
 
33
                                 void *avl_param);
 
34
typedef void avl_item_func (void *avl_item, void *avl_param);
 
35
typedef void *avl_copy_func (void *avl_item, void *avl_param);
 
36
 
 
37
#ifndef LIBAVL_ALLOCATOR
 
38
#define LIBAVL_ALLOCATOR
 
39
/* Memory allocator. */
 
40
struct libavl_allocator
 
41
  {
 
42
    void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size);
 
43
    void (*libavl_free) (struct libavl_allocator *, void *libavl_block);
 
44
  };
 
45
#endif
 
46
 
 
47
/* Default memory allocator. */
 
48
extern struct libavl_allocator avl_allocator_default;
 
49
void *avl_malloc (struct libavl_allocator *, size_t);
 
50
void avl_free (struct libavl_allocator *, void *);
 
51
 
 
52
/* Maximum AVL height. */
 
53
#ifndef AVL_MAX_HEIGHT
 
54
#define AVL_MAX_HEIGHT 32
 
55
#endif
 
56
 
 
57
/* Tree data structure. */
 
58
struct avl_table
 
59
  {
 
60
    struct avl_node *avl_root;          /* Tree's root. */
 
61
    avl_comparison_func *avl_compare;   /* Comparison function. */
 
62
    void *avl_param;                    /* Extra argument to |avl_compare|. */
 
63
    struct libavl_allocator *avl_alloc; /* Memory allocator. */
 
64
    size_t avl_count;                   /* Number of items in tree. */
 
65
    unsigned long avl_generation;       /* Generation number. */
 
66
  };
 
67
 
 
68
/* An AVL tree node. */
 
69
struct avl_node
 
70
  {
 
71
    struct avl_node *avl_link[2];  /* Subtrees. */
 
72
    void *avl_data;                /* Pointer to data. */
 
73
    signed char avl_balance;       /* Balance factor. */
 
74
  };
 
75
 
 
76
/* AVL traverser structure. */
 
77
struct avl_traverser
 
78
  {
 
79
    struct avl_table *avl_table;        /* Tree being traversed. */
 
80
    struct avl_node *avl_node;          /* Current node in tree. */
 
81
    struct avl_node *avl_stack[AVL_MAX_HEIGHT];
 
82
                                        /* All the nodes above |avl_node|. */
 
83
    size_t avl_height;                  /* Number of nodes in |avl_parent|. */
 
84
    unsigned long avl_generation;       /* Generation number. */
 
85
  };
 
86
 
 
87
/* Table functions. */
 
88
struct avl_table *avl_create (avl_comparison_func *, void *,
 
89
                              struct libavl_allocator *);
 
90
struct avl_table *avl_copy (const struct avl_table *, avl_copy_func *,
 
91
                            avl_item_func *, struct libavl_allocator *);
 
92
void avl_destroy (struct avl_table *, avl_item_func *);
 
93
void **avl_probe (struct avl_table *, void *);
 
94
void *avl_insert (struct avl_table *, void *);
 
95
void *avl_replace (struct avl_table *, void *);
 
96
void *avl_delete (struct avl_table *, const void *);
 
97
void *avl_find (const struct avl_table *, const void *);
 
98
void avl_assert_insert (struct avl_table *, void *);
 
99
void *avl_assert_delete (struct avl_table *, void *);
 
100
 
 
101
#define avl_count(table) ((size_t) (table)->avl_count)
 
102
 
 
103
/* Table traverser functions. */
 
104
void avl_t_init (struct avl_traverser *, struct avl_table *);
 
105
void *avl_t_first (struct avl_traverser *, struct avl_table *);
 
106
void *avl_t_last (struct avl_traverser *, struct avl_table *);
 
107
void *avl_t_find (struct avl_traverser *, struct avl_table *, void *);
 
108
void *avl_t_insert (struct avl_traverser *, struct avl_table *, void *);
 
109
void *avl_t_copy (struct avl_traverser *, const struct avl_traverser *);
 
110
void *avl_t_next (struct avl_traverser *);
 
111
void *avl_t_prev (struct avl_traverser *);
 
112
void *avl_t_cur (struct avl_traverser *);
 
113
void *avl_t_replace (struct avl_traverser *, void *);
 
114
 
 
115
#endif /* avl.h */