src/mcas/set_queue_adt.h

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