src/mcas/set.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 #ifndef __SET_H__
  32 #define __SET_H__
  33
  34
  35 typedef unsigned long setkey_t;
  36 typedef void         *setval_t;
  37
  38
  39 #ifdef __SET_IMPLEMENTATION__
  40
  41 /*************************************
  42  * INTERNAL DEFINITIONS
  43  */
  44
  45 /* Fine for 2^NUM_LEVELS nodes. */
  46 #define NUM_LEVELS 20
  47
  48
  49 /* Internal key values with special meanings. */
  50 #define INVALID_FIELD   (0)    /* Uninitialised field value.     */
  51 #define SENTINEL_KEYMIN ( 1UL) /* Key value of first dummy node. */
  52 #define SENTINEL_KEYMAX (~0UL) /* Key value of last dummy node.  */
  53
  54
  55 /*
  56  * Used internally be set access functions, so that callers can use
  57  * key values 0 and 1, without knowing these have special meanings.
  58  */
  59 #define CALLER_TO_INTERNAL_KEY(_k) ((_k) + 2)
  60
  61
  62 /*
  63  * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES
  64  */
  65
  66 #ifdef WEAK_MEM_ORDER
  67
  68 /* Read field @_f into variable @_x. */
  69 #define READ_FIELD(_x,_f)                                       \
  70 do {                                                            \
  71     (_x) = (_f);                                                \
  72     if ( (_x) == INVALID_FIELD ) { RMB(); (_x) = (_f); }        \
  73     assert((_x) != INVALID_FIELD);                              \
  74 } while ( 0 )
  75
  76 #else
  77
  78 /* Read field @_f into variable @_x. */
  79 #define READ_FIELD(_x,_f) ((_x) = (_f))
  80
  81 #endif
  82
  83
  84 #else
  85
  86 /*************************************
  87  * PUBLIC DEFINITIONS
  88  */
  89
  90 /*
  91  * Key range accepted by set functions.
  92  * We lose three values (conveniently at top end of key space).
  93  *  - Known invalid value to which all fields are initialised.
  94  *  - Sentinel key values for up to two dummy nodes.
  95  */
  96 #define KEY_MIN  ( 0U)
  97 #define KEY_MAX  ((~0U) - 3)
  98
  99 typedef void set_t; /* opaque */
 100
 101 void _init_set_subsystem(void);
 102
 103 /*
 104  * Allocate an empty set.
 105  */
 106 set_t *set_alloc(void);
 107
 108 /*
 109  * Add mapping (@k -> @v) into set @s. Return previous mapped value if
 110  * one existed, or NULL if no previous mapping for @k existed.
 111  *
 112  * If @overwrite is FALSE, then if a mapping already exists it is not
 113  * modified, and the existing value is returned unchanged. It is possible
 114  * to see if the value was changed by observing if the return value is NULL.
 115  */
 116 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite);
 117
 118 /*
 119  * Remove mapping for key @k from set @s. Return value associated with
 120  * removed mapping, or NULL is there was no mapping to delete.
 121  */
 122 setval_t set_remove(set_t *s, setkey_t k);
 123
 124 /*
 125  * Look up mapping for key @k in set @s. Return value if found, else NULL.
 126  */
 127 setval_t set_lookup(set_t *s, setkey_t k);
 128
 129 #endif /* __SET_IMPLEMENTATION__ */
 130
 131
 132 #endif /* __SET_H__ */