Return to dict.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / isisd

Annotation of embedaddon/quagga/isisd/dict.h, revision 1.1.1.2

1.1       misho       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.3 2005/09/25 12:04:25 hasso Exp $
                     18:  * $Name:  $
                     19:  */
                     20: 
                     21: #ifndef DICT_H
                     22: #define DICT_H
                     23: 
                     24: #include <limits.h>
                     25: 
                     26: /*
                     27:  * Blurb for inclusion into C++ translation units
                     28:  */
                     29: 
                     30: #ifdef __cplusplus
                     31: extern "C" {
                     32: #endif
                     33: 
                     34: typedef unsigned long dictcount_t;
                     35: #define DICTCOUNT_T_MAX ULONG_MAX
                     36: 
                     37: /*
                     38:  * The dictionary is implemented as a red-black tree
                     39:  */
                     40: 
                     41: typedef enum { dnode_red, dnode_black } dnode_color_t;
                     42: 
                     43: typedef struct dnode_t {
                     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;
                     50: } dnode_t;
                     51: 
                     52: typedef int (*dict_comp_t)(const void *, const void *);
                     53: typedef dnode_t *(*dnode_alloc_t)(void *);
                     54: typedef void (*dnode_free_t)(dnode_t *, void *);
                     55: 
                     56: typedef struct dict_t {
                     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;
                     65: } dict_t;
                     66: 
                     67: typedef void (*dnode_process_t)(dict_t *, dnode_t *, void *);
                     68: 
                     69: typedef struct dict_load_t {
                     70:     dict_t *dict_dictptr;
                     71:     dnode_t dict_nilnode;
                     72: } dict_load_t;
                     73: 
                     74: extern dict_t *dict_create(dictcount_t, dict_comp_t);
                     75: extern void dict_set_allocator(dict_t *, dnode_alloc_t, dnode_free_t, void *);
                     76: extern void dict_destroy(dict_t *);
                     77: extern void dict_free_nodes(dict_t *);
                     78: extern void dict_free(dict_t *);
                     79: extern dict_t *dict_init(dict_t *, dictcount_t, dict_comp_t);
                     80: extern void dict_init_like(dict_t *, const dict_t *);
                     81: extern int dict_verify(dict_t *);
                     82: extern int dict_similar(const dict_t *, const dict_t *);
                     83: extern dnode_t *dict_lookup(dict_t *, const void *);
                     84: extern dnode_t *dict_lower_bound(dict_t *, const void *);
                     85: extern dnode_t *dict_upper_bound(dict_t *, const void *);
                     86: extern void dict_insert(dict_t *, dnode_t *, const void *);
                     87: extern dnode_t *dict_delete(dict_t *, dnode_t *);
                     88: extern int dict_alloc_insert(dict_t *, const void *, void *);
                     89: extern void dict_delete_free(dict_t *, dnode_t *);
                     90: extern dnode_t *dict_first(dict_t *);
                     91: extern dnode_t *dict_last(dict_t *);
                     92: extern dnode_t *dict_next(dict_t *, dnode_t *);
                     93: extern dnode_t *dict_prev(dict_t *, dnode_t *);
                     94: extern dictcount_t dict_count(dict_t *);
                     95: extern int dict_isempty(dict_t *);
                     96: extern int dict_isfull(dict_t *);
                     97: extern int dict_contains(dict_t *, dnode_t *);
                     98: extern void dict_allow_dupes(dict_t *);
                     99: extern int dnode_is_in_a_dict(dnode_t *);
                    100: extern dnode_t *dnode_create(void *);
                    101: extern dnode_t *dnode_init(dnode_t *, void *);
                    102: extern void dnode_destroy(dnode_t *);
                    103: extern void *dnode_get(dnode_t *);
                    104: extern const void *dnode_getkey(dnode_t *);
                    105: extern void dnode_put(dnode_t *, void *);
                    106: extern void dict_process(dict_t *, void *, dnode_process_t);
                    107: extern void dict_load_begin(dict_load_t *, dict_t *);
                    108: extern void dict_load_next(dict_load_t *, dnode_t *, const void *);
                    109: extern void dict_load_end(dict_load_t *);
                    110: extern void dict_merge(dict_t *, dict_t *);
                    111: 
                    112: #define dict_isfull(D) ((D)->dict_nodecount == (D)->dict_maxcount)
                    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))
                    118: 
                    119: #ifdef __cplusplus
                    120: }
                    121: #endif
                    122: 
                    123: #endif