Home | History | Annotate | Download | only in support
      1 /*
      2  * Dictionary Abstract Data Type
      3  * Copyright (C) 1997 Kaz Kylheku <kaz (at) ashi.footprints.net>
      4  *
      5  * Free Software License:
      6  *
      7  * All rights are reserved by the author, with the following exceptions:
      8  * Permission is granted to freely reproduce and distribute this software,
      9  * possibly in exchange for a fee, provided that this copyright notice appears
     10  * intact. Permission is also granted to adapt this software to produce
     11  * derivative works, as long as the modified versions carry this copyright
     12  * notice and additional notices stating that the work has been modified.
     13  * This source code may be translated into executable form and incorporated
     14  * into proprietary software; there is no requirement for such software to
     15  * contain a copyright notice related to this source.
     16  *
     17  * $Id: dict.h,v 1.22.2.6 2000/11/13 01:36:44 kaz Exp $
     18  * $Name: kazlib_1_20 $
     19  */
     20 
     21 #ifndef DICT_H
     22 #define DICT_H
     23 
     24 #include <limits.h>
     25 #ifdef KAZLIB_SIDEEFFECT_DEBUG
     26 #include "sfx.h"
     27 #endif
     28 
     29 /*
     30  * Blurb for inclusion into C++ translation units
     31  */
     32 
     33 #ifdef __cplusplus
     34 extern "C" {
     35 #endif
     36 
     37 typedef unsigned long dictcount_t;
     38 #define DICTCOUNT_T_MAX ULONG_MAX
     39 
     40 /*
     41  * The dictionary is implemented as a red-black tree
     42  */
     43 
     44 typedef enum { dnode_red, dnode_black } dnode_color_t;
     45 
     46 typedef struct dnode_t {
     47 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
     48     struct dnode_t *dict_left;
     49     struct dnode_t *dict_right;
     50     struct dnode_t *dict_parent;
     51     dnode_color_t dict_color;
     52     const void *dict_key;
     53     void *dict_data;
     54 #else
     55     int dict_dummy;
     56 #endif
     57 } dnode_t;
     58 
     59 typedef int (*dict_comp_t)(const void *, const void *);
     60 typedef dnode_t *(*dnode_alloc_t)(void *);
     61 typedef void (*dnode_free_t)(dnode_t *, void *);
     62 
     63 typedef struct dict_t {
     64 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
     65     dnode_t dict_nilnode;
     66     dictcount_t dict_nodecount;
     67     dictcount_t dict_maxcount;
     68     dict_comp_t dict_compare;
     69     dnode_alloc_t dict_allocnode;
     70     dnode_free_t dict_freenode;
     71     void *dict_context;
     72     int dict_dupes;
     73 #else
     74     int dict_dummmy;
     75 #endif
     76 } dict_t;
     77 
     78 typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
     79 
     80 typedef struct dict_load_t {
     81 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
     82     dict_t *dict_dictptr;
     83     dnode_t dict_nilnode;
     84 #else
     85     int dict_dummmy;
     86 #endif
     87 } dict_load_t;
     88 
     89 extern dict_t *dict_create(dictcount_t, dict_comp_t);
     90 extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
     91 extern void dict_destroy(dict_t *);
     92 extern void dict_free_nodes(dict_t *);
     93 extern void dict_free(dict_t *);
     94 extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
     95 extern void dict_init_like(dict_t *, const dict_t *);
     96 extern int dict_verify(dict_t *);
     97 extern int dict_similar(const dict_t *, const dict_t *);
     98 extern dnode_t *dict_lookup(dict_t *, const void *);
     99 extern dnode_t *dict_lower_bound(dict_t *, const void *);
    100 extern dnode_t *dict_upper_bound(dict_t *, const void *);
    101 extern void dict_insert(dict_t *, dnode_t *, const void *);
    102 extern dnode_t *dict_delete(dict_t *, dnode_t *);
    103 extern int dict_alloc_insert(dict_t *, const void *, void *);
    104 extern void dict_delete_free(dict_t *, dnode_t *);
    105 extern dnode_t *dict_first(dict_t *);
    106 extern dnode_t *dict_last(dict_t *);
    107 extern dnode_t *dict_next(dict_t *, dnode_t *);
    108 extern dnode_t *dict_prev(dict_t *, dnode_t *);
    109 extern dictcount_t dict_count(dict_t *);
    110 extern int dict_isempty(dict_t *);
    111 extern int dict_isfull(dict_t *);
    112 extern int dict_contains(dict_t *, dnode_t *);
    113 extern void dict_allow_dupes(dict_t *);
    114 extern int dnode_is_in_a_dict(dnode_t *);
    115 extern dnode_t *dnode_create(void *);
    116 extern dnode_t *dnode_init(dnode_t *, void *);
    117 extern void dnode_destroy(dnode_t *);
    118 extern void *dnode_get(dnode_t *);
    119 extern const void *dnode_getkey(dnode_t *);
    120 extern void dnode_put(dnode_t *, void *);
    121 extern void dict_process(dict_t *, void *, dnode_process_t);
    122 extern void dict_load_begin(dict_load_t *, dict_t *);
    123 extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
    124 extern void dict_load_end(dict_load_t *);
    125 extern void dict_merge(dict_t *, dict_t *);
    126 
    127 #if defined(DICT_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
    128 #ifdef KAZLIB_SIDEEFFECT_DEBUG
    129 #define dict_isfull(D) (SFX_CHECK(D)->dict_nodecount == (D)->dict_maxcount)
    130 #else
    131 #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
    132 #endif
    133 #define dict_count(D) ((D)->dict_nodecount)
    134 #define dict_isempty(D) ((D)->dict_nodecount == 0)
    135 #define dnode_get(N) ((N)->dict_data)
    136 #define dnode_getkey(N) ((N)->dict_key)
    137 #define dnode_put(N, X) ((N)->dict_data = (X))
    138 #endif
    139 
    140 #ifdef __cplusplus
    141 }
    142 #endif
    143 
    144 #endif
    145