/*
* Copyright (c) 1985 Corporation for Research and Educational Networking
* Copyright (c) 1988 University of Illinois Board of Trustees, Steven
* Dorner, and Paul Pomes
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the Corporation for
* Research and Educational Networking (CREN), the University of
* Illinois at Urbana, and their contributors.
* 4. Neither the name of CREN, the University nor the names of their
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE TRUSTEES AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE TRUSTEES OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* @(#)$Id: bintree.h,v 1.12 1994/03/11 23:29:48 paul Exp $
*/
#ifndef BINTREE_H
#define BINTREE_H
#define LBSIZE 1024 /* the size of a leaf */
#define MATCH 0
#define NO_MATCH 1
#define CONTINUE -1
#define KEY_SIZE 4 /* the number of characters kept in NODEs */
#define DATA_SIZE (LBSIZE-2*sizeof(IDX)-sizeof(long)) /* free space in leaf */
#define NODE_SIZE sizeof(NODE)
#define IDX_SIZE sizeof(IDX)
#define META_CHAR "*?[]"
typedef long IDX; /* index pointer size */
/*
* Bintree maintains (along with maket) a four-tiered structure consisting
* of a header, nodes, leaves, and items.
*
* ITEMS contain the entries from the hash table (.idx); the string and
* the hash index are kept in each ITEM.
*
* LEAVES contain one or more items, in sorted order, and are linked
* together. All the keys in the hash table may be examined in sorted
* order by traversing the leaves in order and the items in order within
* the leaves.
*
* NODES contain the first four characters of a key, and left and right
* pointers. These pointers point to other nodes when positive, or leaves
* when negative.
*
* The QHEADER has some statistics, as well as pointers to the head node
* and first and last leaves.
*
* All pointers are stored as indices, and must be multiplied by the
* appropriate size to get disk addresses.
*
* Leaves (and hence items) and the header are kept in the .seq file.
* Nodes are kept in the .bdx file.
*
* Steve Dorner, Computing Services Office, University of Illinois, 4/88
*/
/*
* NODEs are used for quick indexing into the leaf list. They are
* created in maket.c, and reside in the .bdx file.
*/
struct node
{
IDX l_ptr; /* if your name is <= key */
char key[KEY_SIZE]; /* greatest key in l_ptr subtree */
IDX r_ptr; /* if your name is > key */
};
typedef struct node NODE;
/*
* a sorted set of keys from the index; linked together to form a sorted
* list of entire index. kept in the .seq file.
*/
struct leaf
{
IDX leaf_no; /* this leaf's index */
IDX next; /* pointer to next leaf */
int n_bytes; /* number of bytes in data */
char data[DATA_SIZE]; /* data--zero or more ITEMs */
};
typedef struct leaf LEAF;
/*
* this structure is used when building the .bdx (node) file
*/
struct leaf_des
{
IDX leaf_no; /* start of leaf string */
char max_key[KEY_SIZE]; /* biggest key in leaf string */
};
typedef struct leaf_des LEAF_DES;
/*
* the basic unit. contains a single key from the index. multiple ITEMs
* are kept in each leaf.
*/
union item
{
struct
{
IDX p_number;
char p_key[256];
} pair;
char raw[260];
};
typedef union item ITEM;
