source: subversion/utils/osm2pgsql/avl.h @ 2159

Last change on this file since 2159 was 1718, checked in by jonb, 13 years ago

Improved version of osm2pgsql. Adds 'natural' attribute. Some alogorithm improvments to reduce run time. Optional duplicate way detection (at expense of RAM usage).

File size: 4.4 KB
Line 
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. */
32typedef int avl_comparison_func (const void *avl_a, const void *avl_b,
33                                 void *avl_param);
34typedef void avl_item_func (void *avl_item, void *avl_param);
35typedef void *avl_copy_func (void *avl_item, void *avl_param);
36
37#ifndef LIBAVL_ALLOCATOR
38#define LIBAVL_ALLOCATOR
39/* Memory allocator. */
40struct 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. */
48extern struct libavl_allocator avl_allocator_default;
49void *avl_malloc (struct libavl_allocator *, size_t);
50void 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. */
58struct 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. */
69struct 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. */
77struct 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. */
88struct avl_table *avl_create (avl_comparison_func *, void *,
89                              struct libavl_allocator *);
90struct avl_table *avl_copy (const struct avl_table *, avl_copy_func *,
91                            avl_item_func *, struct libavl_allocator *);
92void avl_destroy (struct avl_table *, avl_item_func *);
93void **avl_probe (struct avl_table *, void *);
94void *avl_insert (struct avl_table *, void *);
95void *avl_replace (struct avl_table *, void *);
96void *avl_delete (struct avl_table *, const void *);
97void *avl_find (const struct avl_table *, const void *);
98void avl_assert_insert (struct avl_table *, void *);
99void *avl_assert_delete (struct avl_table *, void *);
100
101#define avl_count(table) ((size_t) (table)->avl_count)
102
103/* Table traverser functions. */
104void avl_t_init (struct avl_traverser *, struct avl_table *);
105void *avl_t_first (struct avl_traverser *, struct avl_table *);
106void *avl_t_last (struct avl_traverser *, struct avl_table *);
107void *avl_t_find (struct avl_traverser *, struct avl_table *, void *);
108void *avl_t_insert (struct avl_traverser *, struct avl_table *, void *);
109void *avl_t_copy (struct avl_traverser *, const struct avl_traverser *);
110void *avl_t_next (struct avl_traverser *);
111void *avl_t_prev (struct avl_traverser *);
112void *avl_t_cur (struct avl_traverser *);
113void *avl_t_replace (struct avl_traverser *, void *);
114
115#endif /* avl.h */
Note: See TracBrowser for help on using the repository browser.