#ifndef HAVE_HTREE_H
/* ----------------------------------------------------------------- */    
/*  Copyright (c) 2007 by Richard Harter                             */
/*                                                                   */
/*  Permission is hereby granted, free of charge, to any person      */
/*  obtaining a copy of this software and associated documentation   */
/*  files (the "Software"), to deal in the Software without          */
/*  restriction, including without limitation the rights to use,     */
/*  copy, modify, merge, publish, distribute, sublicense, and/or     */
/*  sell copies of the Software, and to permit persons to whom the   */
/*  Software is furnished to do so, subject to the following         */
/*  conditions:                                                      */
/*                                                                   */
/*  The above copyright notice and this permission notice shall be   */
/*  included in all copies or substantial portions of the            */
/*  Software.                                                        */
/*                                                                   */
/*  Derivative works shall include a notice that the software is a   */
/*  modified version of the copyrighted software.                    */
/*                                                                   */
/*  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY        */
/*  KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE       */
/*  WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR          */
/*  PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR   */
/*  COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER      */
/*  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR             */
/*  OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE        */
/*  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.           */
/*                                                                   */
/* ----------------------------------------------------------------- */
/*                      Revision History                             */
/*                                                                   */
/*  April 22, 2007 - Base release 1.0.0                              */
/*                                                                   */
/* ----------------------------------------------------------------- */

#define HAVE_HTREE_H

#define HT_MAX_SMALL_STRING_SIZE 256

#define HT_ROOT struct ht_root
#define HT_NODE struct ht_node
#define HT_SIBS struct ht_sibs
#define HT_DATA struct ht_data
#define HT_BAGS struct ht_bags

#define ID_TYPE int

         
#define N_SIB_FREELISTS 6
#define BAG_SIZE 128

HT_DATA {
    int             len;    /* Length of the data item in bytes */
    unsigned char * data;   /* The data item in char array form */
    ID_TYPE         id;     /* A handle to be used elsewhere    */
};

HT_SIBS {
    HT_NODE * kids;         /* Array of children for a sibling  */
    HT_DATA   datum;        /* The siblings datum descriptor    */
    int       selector;     /* Datum char val at node's index   */
    HT_SIBS * link;         /* Link used for free list          */
};

HT_NODE {
    int       max_num_sibs; /* Size of space allocated for sibs */
    int       num_sibs;     /* Number of siblings in this node  */
    int       index;        /* Char position for this node      */
    HT_SIBS * sibs;         /* Array of siblings in this node   */
    HT_NODE * link;         /* Link use for free list           */
};



HT_BAGS {
    HT_BAGS * link;
    int       pos;
    void    * space;
};

HT_ROOT {
    HT_NODE * roots[HT_MAX_SMALL_STRING_SIZE + 1];
    HT_BAGS * sib_bags_header;
    int       sib_sizes     [N_SIB_FREELISTS];
    HT_SIBS * sib_freelists [N_SIB_FREELISTS];
    HT_BAGS * sib_bags      [N_SIB_FREELISTS];
    HT_BAGS * node_bags;
    HT_NODE * node_freelist;
};

HT_DATA * htree_find   (HT_ROOT *, HT_DATA *);
HT_DATA * htree_add    (HT_ROOT *, HT_DATA *, int);
int       htree_del    (HT_ROOT *, HT_DATA *);
int       htree_verify (int, unsigned char *, unsigned char *);

HT_ROOT * htree_init   (void);
int       htree_close  (HT_ROOT *);

void      htree_print_tree    (FILE *, int, int, HT_NODE *);
void      htree_print_forest  (FILE *, HT_ROOT *);

#endif