← Back to branch summary

~ubuntu-branches/ubuntu/warty/quagga/warty

« back to all changes in this revision

Viewing changes to isisd/dict.h

  • Committer: Bazaar Package Importer
  • Author(s): Fabio M. Di Nitto
  • Date: 2004-06-29 09:50:59 UTC
  • Revision ID: james.westby@ubuntu.com-20040629095059-px1m2m108z4qw1mr
Tags: upstream-0.96.5
Import upstream version 0.96.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
isisd/dict.h
 
1
/*
 
2
 * Dictionary Abstract Data Type
 
3
 * Copyright (C) 1997 Kaz Kylheku <kaz@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.1.1.1 2003/12/23 08:09:48 jardin Exp $
 
18
 * $Name:  $
 
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