Return to dict.h CVS log

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

quagga

    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 2012/02/21 17:26:11 misho 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