summaryrefslogtreecommitdiffstats
path: root/src/H5TB.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5TB.c')
-rw-r--r--src/H5TB.c87
1 files changed, 52 insertions, 35 deletions
diff --git a/src/H5TB.c b/src/H5TB.c
index 6a9afcb..391101f 100644
--- a/src/H5TB.c
+++ b/src/H5TB.c
@@ -1,7 +1,18 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * Copyright by the Board of Trustees of the University of Illinois. *
+ * All rights reserved. *
+ * *
+ * This file is part of HDF5. The full HDF5 copyright notice, including *
+ * terms governing use, modification, and redistribution, is contained in *
+ * the files COPYING and Copyright.html. COPYING can be found at the root *
+ * of the source code distribution tree; Copyright.html can be found at the *
+ * root level of an installed copy of the electronic HDF5 document set and *
+ * is linked from the top-level documents page. It can also be found at *
+ * http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have *
+ * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
/*
- * Copyright (C) 2000-2001 NCSA
- * All rights reserved.
- *
* Programmer: Quincey Koziol <koziol@ncsa.uiuc.edu>
* Saturday, April 22, 2000
*
@@ -9,11 +20,13 @@
* Extended from (added threads to) Knuth 6.2.3, Algorithm A (AVL trees)
* Basic tree structure by Adel'son-Vel'skii and Landis
*
- * These routines are designed to allow use of a general-purpose balanced tree
- * implimentation. These trees are appropriate for maintaining in memory one
- * or more lists of items, each list sorted according to key values (key values
- * must form a "completely ordered set") where no two items in a single list
- * can have the same key value. The following operations are supported:
+ * These routines are designed to allow use of a general-purpose balanced
+ * tree implimentation. These trees are appropriate for maintaining in
+ * memory one or more lists of items, each list sorted according to key
+ * values (key values must form a "completely ordered set") where no two
+ * items in a single list can have the same key value. The following
+ * operations are supported:
+ *
* Create an empty list
* Add an item to a list
* Look up an item in a list by key value
@@ -21,32 +34,36 @@
* Delete an item from a list
* Find the first/last/next/previous item in a list
* Destroy a list
- * Each of the above operations requires Order(log(N)) time where N is the
- * number of items in the list (except for list creation which requires
- * constant time and list destruction which requires Order(N) time if the user-
- * supplied free-data-item or free-key-value routines require constant time).
- * Each of the above operations (except create and destroy) can be performed
- * on a subtree.
- *
- * Each node of a tree has associated with it a generic pointer (void *) which
- * is set to point to one such "item" and a generic pointer to point to that
- * item's "key value". The structure of the items and key values is up to the
- * user to define. The user must specify a method for comparing key values.
- * This routine takes three arguments, two pointers to key values and a third
- * integer argument. You can specify a routine that expects pointers to "data
- * items" rather than key values in which case the pointer to the key value in
- * each node will be set equal to the pointer to the data item.
- *
- * Since the "data item" pointer is the first field of each tree node, these
- * routines may be used without this "tbbt.h" file. For example, assume "ITM"
- * is the structre definition for the data items you want to store in lists:
+ *
+ * Each of the above operations requires Order(log(N)) time where N is
+ * the number of items in the list (except for list creation which
+ * requires constant time and list destruction which requires Order(N)
+ * time if the user- supplied free-data-item or free-key-value routines
+ * require constant time). Each of the above operations (except create
+ * and destroy) can be performed on a subtree.
+ *
+ * Each node of a tree has associated with it a generic pointer (void *)
+ * which is set to point to one such "item" and a generic pointer to
+ * point to that item's "key value". The structure of the items and key
+ * values is up to the user to define. The user must specify a method
+ * for comparing key values. This routine takes three arguments, two
+ * pointers to key values and a third integer argument. You can specify
+ * a routine that expects pointers to "data items" rather than key values
+ * in which case the pointer to the key value in each node will be set
+ * equal to the pointer to the data item.
+ *
+ * Since the "data item" pointer is the first field of each tree node,
+ * these routines may be used without this "tbbt.h" file. For example,
+ * assume "ITM" is the structre definition for the data items you want to
+ * store in lists:
+ *
* ITM ***H5TB_dmake( int (*cmp)(void *,void *,int), int arg );
* ITM **root= NULL; (* How to create an empty tree w/o H5TB_dmake() *)
* ITM **H5TB_dfind( ITM ***tree, void *key, ITM ***pp );
* ITM **H5TB_find( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
* ITM **H5TB_dless( ITM ***tree, void *key, ITM ***pp );
* ITM **H5TB_less( ITM **root, void *key, int (*cmp)(), int arg, ITM ***pp );
- * ITM **H5TB_indx( ITM **root, long indx );
+ * ITM **H5TB_index( ITM **root, long indx );
* ITM **H5TB_dins( ITM ***tree, ITM *item, void *key );
* ITM **H5TB_ins( ITM ***root, ITM *item, void *key, int (*cmp)(), int arg );
* ITM *H5TB_rem( ITM ***root, ITM **node, void **kp );
@@ -102,11 +119,11 @@ static int interface_initialize_g = 0;
* (H5TB_dfind, H5TB_dins, H5TB_dfree) on them.
* Examples:
* int keycmp();
- * H5TB_ROOT *root= H5TB_dmake( keycmp, (int)keysiz , 0);
+ * H5TB_TREE *tree = H5TB_dmake( keycmp, (int)keysiz , 0);
* or
- * void *root= H5TB_dmake( strcmp, 0 , 0);
+ * void *tree= H5TB_dmake( strcmp, 0 , 0);
* or
- * void *root= H5TB_dmake( keycmp, (int)keysiz , H5TB_FAST_HADDR_COMPARE);
+ * void *tree= H5TB_dmake( keycmp, (int)keysiz , H5TB_FAST_HADDR_COMPARE);
* or
* H5TB_NODE *root= NULL; (* Don't use H5TB_d* routines *)
*
@@ -124,10 +141,10 @@ static int interface_initialize_g = 0;
* kind of assumption). You can also use a key comparison routine that expects
* pointers to data items rather than key values.
*
- * The "fast compare" option is for keys of simple numeric types (currently
- * haddr_t and int) and avoids the function call for faster searches in
- * some cases. The key comparison routine is still required for some
- * insertion routines which use it.
+ * The "fast compare" option is for keys of simple numeric types
+ * (currently haddr_t and int) and avoids the function call for faster
+ * searches in some cases. The key comparison routine is still required
+ * for some insertion routines which use it.
*
* Most of the other routines expect a pointer to a root node of a tree, not
* a pointer to the tree's control structure (only H5TB_dfind(), H5TB_dins(),