"Fossies" - the Fresh Open Source Software Archive

Member "getdp-3.1.0-source/Common/avl.h" (23 Feb 2019, 3860 Bytes) of package /linux/privat/getdp-3.1.0-source.tgz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "avl.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.0.4_vs_3.1.0.

    1 // GetDP - Copyright (C) 1997-2019 P. Dular and C. Geuzaine, University of Liege
    2 //
    3 // See the LICENSE.txt file for license information. Please report all
    4 // issues on https://gitlab.onelab.info/getdp/getdp/issues.
    5 
    6 #ifndef AVL_H
    7 #define AVL_H
    8 
    9 /*
   10  * avl package
   11  *
   12  * Copyright (c) 1988-1993, The Regents of the University of California.
   13  *
   14  * Permission to use, copy, modify, and distribute this software and its
   15  * documentation for any purpose and without fee is hereby granted, provided
   16  * that the above copyright notice appear in all copies and that both that
   17  * copyright notice and this permission notice appear in supporting
   18  * documentation, and that the name of the University of California not
   19  * be used in advertising or publicity pertaining to distribution of
   20  * the software without specific, written prior permission.  The University
   21  * of California makes no representations about the suitability of this
   22  * software for any purpose.  It is provided "as is" without express or
   23  * implied warranty.
   24  *
   25  * THE UNIVERSITY OF CALIFORNIA DISCLAIMS ALL WARRANTIES WITH REGARD TO
   26  * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
   27  * FITNESS, IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE FOR
   28  * ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
   29  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
   30  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
   31  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
   32  */
   33 
   34 // Modified for Gmsh (C++, 64 bits, ...)
   35 
   36 typedef struct avl_node_struct avl_node;
   37 struct avl_node_struct {
   38   avl_node *left, *right;
   39   void *key;
   40   void *value;
   41   int height;
   42 };
   43 
   44 
   45 typedef struct avl_tree_struct avl_tree;
   46 struct avl_tree_struct {
   47   avl_node *root;
   48   int (*compar)(const void *key1, const void *key2);
   49   int num_entries;
   50   int modified;
   51 };
   52 
   53 
   54 typedef struct avl_generator_struct avl_generator;
   55 struct avl_generator_struct {
   56   avl_tree *tree;
   57   avl_node **nodelist;
   58   int count;
   59 };
   60 
   61 
   62 #define AVL_FORWARD     0
   63 #define AVL_BACKWARD    1
   64 
   65 #define AVL_MOST_LEFT   0
   66 #define AVL_MOST_RIGHT  1
   67 
   68 #define avl_is_member(tree, key)   avl_lookup(tree, key, (void **) 0)
   69 #define NIL(type)            (type *) 0
   70 
   71 #define avl_foreach_item(table, gen, dir, key_p, value_p)               \
   72     for(gen = avl_init_gen(table, dir);                                 \
   73             avl_gen(gen, key_p, value_p) || (avl_free_gen(gen),0);)
   74 
   75 
   76 inline void avl_walk_forward(avl_node *node, void (*func)(void *key, void *value))
   77 {
   78   if (node != NIL(avl_node)) {
   79     avl_walk_forward(node->left, func);
   80     (*func)(node->key, node->value);
   81     avl_walk_forward(node->right, func);
   82   }
   83 }
   84 
   85 inline void avl_walk_backward(avl_node *node, void (*func)(void *key, void *value))
   86 {
   87   if (node != NIL(avl_node)) {
   88     avl_walk_backward(node->right, func);
   89     (*func)(node->key, node->value);
   90     avl_walk_backward(node->left, func);
   91   }
   92 }
   93 
   94 inline void avl_foreach(avl_tree *tree, void (*func)(void *key, void *value), int direction)
   95 {
   96   if (direction == AVL_FORWARD) {
   97     avl_walk_forward(tree->root, func);
   98   } else {
   99     avl_walk_backward(tree->root, func);
  100   }
  101 }
  102 
  103 avl_tree *avl_init_table(int (*compar)(const void *key1, const void *key2));
  104 int avl_lookup(avl_tree *tree, void *key, void **value_p);
  105 int avl_insert(avl_tree *tree, void *key, void *value);
  106 int avl_delete(avl_tree *tree, void **key_p, void **value_p);
  107 void avl_free_table(avl_tree *tree, void (*key_free)(void *key), void (*value_free)(void *value));
  108 int avl_count(avl_tree *tree);
  109 int avl_check_tree(avl_tree *tree);
  110 int avl_extremum(avl_tree *tree, int side, void **value_p);
  111 
  112 avl_generator *avl_init_gen(avl_tree *tree, int dir);
  113 int avl_gen(avl_generator *gen, void **key_p, void **value_p);
  114 void avl_free_gen(avl_generator *gen);
  115 
  116 int avl_numcmp(const void *x, const void*y);
  117 
  118 #endif