Gitiles
Code Review Sign In
gerrit.opencord.org / quagga / d319a3abbf6e6c310b6b6a6891ebe1957592f9a9 / . / isisd / dict.h
blob: 93edb7d6039b248759dad329f5b2d943d2fa5471 [file] [log] [blame]
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]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 *
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]17 * $Id: dict.h,v 1.3 2005/09/25 12:04:25 hasso Exp $
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]18 * $Name: $
19 */
20
21#ifndef DICT_H
22#define DICT_H
23
24#include <limits.h>
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]25
26/*
27 * Blurb for inclusion into C++ translation units
28 */
29
30#ifdef __cplusplus
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]31extern "C" {
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]32#endif
33
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]34typedef unsigned long dictcount_t;
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]35#define DICTCOUNT_T_MAX ULONG_MAX
36
37/*
38 * The dictionary is implemented as a red-black tree
39 */
40
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]41typedef enum { dnode_red, dnode_black } dnode_color_t;
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]42
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]43typedef struct dnode_t {
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]44 struct dnode_t *dict_left;
45 struct dnode_t *dict_right;
46 struct dnode_t *dict_parent;
47 dnode_color_t dict_color;
48 const void *dict_key;
49 void *dict_data;
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]50} dnode_t;
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]51
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]52typedef int (*dict_comp_t)(const void *, const void *);
53typedef dnode_t *(*dnode_alloc_t)(void *);
54typedef void (*dnode_free_t)(dnode_t *, void *);
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]55
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]56typedef struct dict_t {
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]57 dnode_t dict_nilnode;
58 dictcount_t dict_nodecount;
59 dictcount_t dict_maxcount;
60 dict_comp_t dict_compare;
61 dnode_alloc_t dict_allocnode;
62 dnode_free_t dict_freenode;
63 void *dict_context;
64 int dict_dupes;
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]65} dict_t;
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]66
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]67typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]68
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]69typedef struct dict_load_t {
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]70 dict_t *dict_dictptr;
71 dnode_t dict_nilnode;
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]72} dict_load_t;
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]73
hassoffe543a2005-09-25 12:04:25 +0000[diff] [blame]74extern dict_t *dict_create(dictcount_t, dict_comp_t);
75extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
76extern void dict_destroy(dict_t *);
77extern void dict_free_nodes(dict_t *);
78extern void dict_free(dict_t *);
79extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
80extern void dict_init_like(dict_t *, const dict_t *);
81extern int dict_verify(dict_t *);
82extern int dict_similar(const dict_t *, const dict_t *);
83extern dnode_t *dict_lookup(dict_t *, const void *);
84extern dnode_t *dict_lower_bound(dict_t *, const void *);
85extern dnode_t *dict_upper_bound(dict_t *, const void *);
86extern void dict_insert(dict_t *, dnode_t *, const void *);
87extern dnode_t *dict_delete(dict_t *, dnode_t *);
88extern int dict_alloc_insert(dict_t *, const void *, void *);
89extern void dict_delete_free(dict_t *, dnode_t *);
90extern dnode_t *dict_first(dict_t *);
91extern dnode_t *dict_last(dict_t *);
92extern dnode_t *dict_next(dict_t *, dnode_t *);
93extern dnode_t *dict_prev(dict_t *, dnode_t *);
94extern dictcount_t dict_count(dict_t *);
95extern int dict_isempty(dict_t *);
96extern int dict_isfull(dict_t *);
97extern int dict_contains(dict_t *, dnode_t *);
98extern void dict_allow_dupes(dict_t *);
99extern int dnode_is_in_a_dict(dnode_t *);
100extern dnode_t *dnode_create(void *);
101extern dnode_t *dnode_init(dnode_t *, void *);
102extern void dnode_destroy(dnode_t *);
103extern void *dnode_get(dnode_t *);
104extern const void *dnode_getkey(dnode_t *);
105extern void dnode_put(dnode_t *, void *);
106extern void dict_process(dict_t *, void *, dnode_process_t);
107extern void dict_load_begin(dict_load_t *, dict_t *);
108extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
109extern void dict_load_end(dict_load_t *);
110extern void dict_merge(dict_t *, dict_t *);
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]111
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]112#define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]113#define dict_count(D) ((D)->dict_nodecount)
114#define dict_isempty(D) ((D)->dict_nodecount == 0)
115#define dnode_get(N) ((N)->dict_data)
116#define dnode_getkey(N) ((N)->dict_key)
117#define dnode_put(N, X) ((N)->dict_data = (X))
jardineb5d44e2003-12-23 08:09:43 +0000[diff] [blame]118
119#ifdef __cplusplus
120}
121#endif
122
123#endif