L4Re/departure

Annotated libext2fs/lib/libsupport/dict.h

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