src/mcas/set_adt.h

   1 /*
   2 Copyright (c) 2003, Keir Fraser All rights reserved.
   3
   4 Redistribution and use in source and binary forms, with or without
   5 modification, are permitted provided that the following conditions are
   6 met:
   7
   8     * Redistributions of source code must retain the above copyright
   9     * notice, this list of conditions and the following disclaimer.
  10     * Redistributions in binary form must reproduce the above
  11     * copyright notice, this list of conditions and the following
  12     * disclaimer in the documentation and/or other materials provided
  13     * with the distribution.  Neither the name of the Keir Fraser
  14     * nor the names of its contributors may be used to endorse or
  15     * promote products derived from this software without specific
  16     * prior written permission.
  17
  18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 /******************************************************************************
  32  * set_func.h
  33  *
  34  * Matt Benjamin <matt@linuxbox.com>
  35  *
  36  * Adapts MCAS set interface to use a pointer-key and typed comparison
  37  * function style (because often, your key isn't an integer).
  38  *
  39  * Caution, pointer values 0x0, 0x01, and 0x02 are reserved.  Fortunately,
  40  * no real pointer is likely to have one of these values.
  41  *
  42  */
  43
  44 #ifndef __SET_ADT_H__
  45 #define __SET_ADT_H__
  46
  47
  48 typedef void *setkey_t;
  49 typedef void *setval_t;
  50
  51
  52 #ifdef __SET_IMPLEMENTATION__
  53
  54 /*************************************
  55  * INTERNAL DEFINITIONS
  56  */
  57
  58 /* Fine for 2^NUM_LEVELS nodes. */
  59 #define NUM_LEVELS 20
  60
  61
  62 /* Internal key values with special meanings. */
  63 #define INVALID_FIELD   (0)     /* Uninitialised field value.     */
  64 #define SENTINEL_KEYMIN ( 1UL)  /* Key value of first dummy node. */
  65 #define SENTINEL_KEYMAX (~0UL)  /* Key value of last dummy node.  */
  66
  67
  68 /*
  69  * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES
  70  */
  71
  72 #ifdef WEAK_MEM_ORDER
  73
  74 /* Read field @_f into variable @_x. */
  75 #define READ_FIELD(_x,_f)                                       \
  76 do {                                                            \
  77     (_x) = (_f);                                                \
  78     if ( (_x) == INVALID_FIELD ) { RMB(); (_x) = (_f); }        \
  79     assert((_x) != INVALID_FIELD);                              \
  80 } while ( 0 )
  81
  82 #else
  83
  84 /* Read field @_f into variable @_x. */
  85 #define READ_FIELD(_x,_f) ((_x) = (_f))
  86
  87 #endif
  88
  89
  90 #else
  91
  92 /*************************************
  93  * PUBLIC DEFINITIONS
  94  */
  95
  96 /*
  97  * Key range accepted by set functions.
  98  * We lose three values (conveniently at top end of key space).
  99  *  - Known invalid value to which all fields are initialised.
 100  *  - Sentinel key values for up to two dummy nodes.
 101  */
 102 #define KEY_MIN  ( 0U)
 103 #define KEY_MAX  ((~0U) - 3)
 104
 105 typedef void set_t;             /* opaque */
 106
 107 /* Set element comparison function */
 108 typedef int (*osi_set_cmp_func) (const void *lhs, const void *rhs);
 109
 110 /* One-time initialize set adt package */
 111 void _init_set_subsystem(void);
 112
 113 /*
 114  * Allocate an empty set.
 115  *
 116  * @cmpf - function to compare two keys, it must return an integer
 117  *         less than, equal to, or greater than 0 if 1st argument
 118  *         orders less than, equal to, or greater than the 2nd, as
 119  *         in qsort(3)
 120  */
 121 set_t *set_alloc(osi_set_cmp_func cmpf);
 122
 123 /*
 124  * Add mapping (@k -> @v) into set @s. Return previous mapped value if
 125  * one existed, or NULL if no previous mapping for @k existed.
 126  *
 127  * If @overwrite is FALSE, then if a mapping already exists it is not
 128  * modified, and the existing value is returned unchanged. It is possible
 129  * to see if the value was changed by observing if the return value is NULL.
 130  */
 131 setval_t set_update(set_t * s, setkey_t k, setval_t v, int overwrite);
 132
 133 /*
 134  * Remove mapping for key @k from set @s. Return value associated with
 135  * removed mapping, or NULL is there was no mapping to delete.
 136  */
 137 setval_t set_remove(set_t * s, setkey_t k);
 138
 139 /*
 140  * Look up mapping for key @k in set @s. Return value if found, else NULL.
 141  */
 142 setval_t set_lookup(set_t * s, setkey_t k);
 143
 144
 145 #endif /* __SET_IMPLEMENTATION__ */
 146
 147
 148 #endif /* __SET_ADT_H__ */