code.grnet.gr Git - archipelago/blob - xseg/xtypes/xpool.c

   1 /*
   2  * Copyright 2012 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  11  *   2. Redistributions in binary form must reproduce the above
  12  *      copyright notice, this list of conditions and the following
  13  *      disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and
  30  * documentation are those of the authors and should not be
  31  * interpreted as representing official policies, either expressed
  32  * or implied, of GRNET S.A.
  33  */
  34
  35 #include <xtypes/xpool.h>
  36
  37 static inline int __validate_idx(struct xpool *xp, xpool_index idx)
  38 {
  39         struct xpool_node *node = XPTR(&xp->mem)+idx;
  40         return (idx < xp->size && node->prev != NoIndex);
  41 }
  42
  43 void __xpool_clear(struct xpool *xp)
  44 {
  45         uint64_t i;
  46         uint64_t size = xp->size;
  47         struct xpool_node *mem = XPTR(&xp->mem);
  48
  49         xp->list = NoIndex;
  50         for (i = 1; i < size; i++) {
  51                 mem[i-1].prev = NoIndex;
  52                 mem[i-1].next = i;
  53         }
  54         mem[size-1].prev = NoIndex;
  55         mem[size-1].next = NoIndex;
  56         xp->free = 0;
  57 }
  58
  59 void xpool_clear(struct xpool *xp, uint32_t who)
  60 {
  61         xlock_acquire(&xp->lock, who);
  62         __xpool_clear(xp);
  63         xlock_release(&xp->lock);
  64 }
  65
  66 void xpool_init(struct xpool *xp, uint64_t size, struct xpool_node* mem)
  67 {
  68         xp->size = size;
  69         XPTRSET(&xp->mem, mem);
  70         xlock_release(&xp->lock);
  71         __xpool_clear(xp);
  72 }
  73
  74 xpool_index __xpool_add(struct xpool *xp, xpool_data data)
  75 {
  76         struct xpool_node *new, *list, *prev;
  77         xpool_index idx;
  78
  79         idx = xp->free;
  80         if (idx == NoIndex){
  81                 return NoIndex;
  82         }
  83         new = XPTR(&xp->mem) + idx;
  84         xp->free = new->next;
  85         new->data = data;
  86
  87         if (xp->list != NoIndex) {
  88                 list = XPTR(&xp->mem) + xp->list;
  89                 new->next = xp->list;
  90                 new->prev = list->prev;
  91
  92                 prev = XPTR(&xp->mem) + list->prev;
  93                 prev->next = idx;
  94                 list->prev = idx;
  95         } else {
  96                 new->next = idx;
  97                 new->prev = idx;
  98                 xp->list =idx;
  99         }
 100         /*
 101         idx = xp->list;
 102         list = XPTR(&xp->mem) + idx;
 103         printf("xpool data: %llu(%llu), ", xp->list, list->data );
 104         do {
 105         idx = list->next;
 106         list = XPTR(&xp->mem) + idx;
 107         printf("%llu(%llu), ", idx, list->data);
 108         }while(idx != xp->list);
 109         printf("\n");
 110         */
 111
 112         return idx;
 113 }
 114
 115 xpool_index xpool_add(struct xpool *xp, xpool_data data, uint32_t who)
 116 {
 117         xpool_index idx;
 118         xlock_acquire(&xp->lock, who);
 119         idx = __xpool_add(xp, data);
 120         xlock_release(&xp->lock);
 121         return idx;
 122 }
 123 /*
 124 xpool_index xpool_add(struct xpool *xp, xpool_data data)
 125 {
 126         struct xpool_node *new, *list, *free, *next, *prev;
 127         //acquire lock
 128         xlock_acquire(&xp->lock, 1);
 129         free = XPTR(&xp->free);
 130         list = XPTR(&xp->list);
 131         new = free;
 132         if (new == NULL){
 133                 xlock_release(&xp->lock);
 134                 return NoIndex;
 135         }
 136         free = XPTR(&new->next);
 137         XPTRSET(&xp->free, free);
 138         if (list) {
 139                 //new->next = xp->list;
 140                 XPTRSET(&new->next, list);
 141
 142                 prev = XPTR(&list->prev);
 143                 XPTRSET(&new->prev, prev);
 144                 //new->prev = xp->list->prev;
 145
 146                 next = XPTR(&prev->next);
 147                 XPTRSET(&prev->next, new);
 148                 //xp->list->prev->next = new;
 149
 150                 XPTRSET(&list->prev, new);
 151                 //xp->list->prev = new;
 152         } else {
 153                 XPTRSET(&new->next ,new);
 154                 //new->next = new;
 155                 XPTRSET(&new->prev, new);
 156                 //new->prev = new;
 157                 XPTRSET(&xp->list, new);
 158                 //xp->list = new;
 159         }
 160         new->data = data;
 161         //release lock
 162         xlock_release(&xp->lock);
 163         return (new - XPTR(&xp->mem));
 164 }
 165 */
 166 /*
 167 xpool_index xpool_remove(struct xpool *xp, xpool_index idx, xpool_data *data)
 168 {
 169         struct xpool_node *node, *list, *free, *prev, *next;
 170         //acquire lock
 171         xlock_acquire(&xp->lock, 1);
 172         if (!__validate_idx(xp, idx)){ // idx < xp->size && node->prev != NULL
 173                 xlock_release(&xp->lock);
 174                 return NoIndex;
 175         }
 176         node = XPTR(&xp->mem) + idx;
 177         *data = node->data;
 178         list = XPTR(&xp->list);
 179         free = XPTR(&xp->free);
 180         next = XPTR(&node->next);
 181         prev = XPTR(&node->prev);
 182         if (node == list){
 183                 if (node == next)
 184                         XPTRSET(&xp->list, NULL);
 185                         //xp->list = NULL;
 186                 else
 187                         XPTRSET(&xp->list, next);
 188                         //xp->list = node->next;
 189         }
 190         XPTRSET(&prev->next, next);
 191         //node->prev->next = node->next;
 192         XPTRSET(&next->prev, prev);
 193         //node->next->prev = node->prev;
 194         XPTRSET(&node->prev, NULL);
 195         //node->prev = NULL;
 196         XPTRSET(&node->next, free);
 197         //node->next = xp->free;
 198         free = node;
 199         XPTRSET(&xp->free, free);
 200         //xp->free = node;
 201
 202         //release lock
 203         xlock_release(&xp->lock);
 204         return idx;
 205 }
 206 */
 207 xpool_index __xpool_remove(struct xpool *xp, xpool_index idx, xpool_data *data)
 208 {
 209         struct xpool_node *node, *prev, *next;
 210         if (!__validate_idx(xp, idx)){ // idx < xp->size && node->prev != NULL
 211                 return NoIndex;
 212         }
 213         node = XPTR(&xp->mem) + idx;
 214         *data = node->data;
 215
 216         if (idx == xp->list){
 217                 if ( idx == node->next)
 218                         xp->list = NoIndex;
 219                 else
 220                         xp->list = node->next;
 221         }
 222         prev = XPTR(&xp->mem) + node->prev;
 223         prev->next = node->next;
 224
 225         next = XPTR(&xp->mem) + node->next;
 226         next->prev = node->prev;
 227
 228         node->prev = NoIndex;
 229         node->next = xp->free;
 230         xp->free = idx;
 231         return idx;
 232 }
 233
 234 xpool_index xpool_remove(struct xpool *xp, xpool_index idx, xpool_data *data, uint32_t who)
 235 {
 236         xpool_index ret;
 237         xlock_acquire(&xp->lock, who);
 238         ret = __xpool_remove(xp, idx, data);
 239         xlock_release(&xp->lock);
 240         return ret;
 241 }
 242
 243 xpool_index __xpool_peek(struct xpool *xp, xpool_data *data)
 244 {
 245         struct xpool_node *list;
 246         xpool_index ret;
 247         if (xp->list == NoIndex){
 248                 return NoIndex;
 249         }
 250         ret = xp->list;
 251         list = XPTR(&xp->mem) + xp->list;
 252         *data = list->data;
 253         return ret;
 254 }
 255
 256 xpool_index xpool_peek(struct xpool *xp, xpool_data *data, uint32_t who)
 257 {
 258         xpool_index ret;
 259         xlock_acquire(&xp->lock, who);
 260         ret = __xpool_peek(xp, data);
 261         xlock_release(&xp->lock);
 262         return ret;
 263 }
 264
 265 xpool_index __xpool_peek_idx(struct xpool *xp, xpool_index idx, xpool_data *data)
 266 {
 267         struct xpool_node *node;
 268         if (!__validate_idx(xp, idx)){
 269                 return NoIndex;
 270         }
 271         node = XPTR(&xp->mem) + idx;
 272         *data = node->data;
 273         return idx;
 274 }
 275
 276 xpool_index xpool_peek_idx(struct xpool *xp, xpool_index idx, xpool_data *data, uint32_t who)
 277 {
 278         xpool_index ret;
 279         xlock_acquire(&xp->lock, who);
 280         ret = __xpool_peek_idx(xp,idx,data);
 281         xlock_release(&xp->lock);
 282         return ret;
 283 }
 284
 285 xpool_index __xpool_peek_and_fwd(struct xpool *xp, xpool_data *data)
 286 {
 287         struct xpool_node *list;
 288         xpool_index ret;
 289         if (xp->list == NoIndex){
 290                 return NoIndex;
 291         }
 292         ret = xp->list;
 293         list = XPTR(&xp->mem) + xp->list;
 294         *data = list->data;
 295         xp->list = list->next;
 296         return ret;
 297 }
 298
 299 xpool_index xpool_peek_and_fwd(struct xpool *xp, xpool_data *data, uint32_t who)
 300 {
 301         xpool_index ret;
 302         xlock_acquire(&xp->lock, who);
 303         ret = __xpool_peek_and_fwd(xp,data);
 304         xlock_release(&xp->lock);
 305         return ret;
 306 }
 307
 308 /*
 309 xpool_index xpool_peek_and_fwd(struct xpool *xp, xpool_data *data)
 310 {
 311         struct xpool_node *list, *next;
 312         //acquire lock
 313         xlock_acquire(&xp->lock, 1);
 314         list = XPTR(&xp->list);
 315         if (!list){
 316                 xlock_release(&xp->lock);
 317                 return NoIndex;
 318         }
 319         *data = list->data;
 320         next = XPTR(&list->next);
 321         XPTRSET(&xp->list, next);
 322         //xp->list = xp->list->next;
 323         //release lock
 324         xlock_release(&xp->lock);
 325         return (list - XPTR(&xp->mem));
 326 }
 327 */
 328
 329 xpool_index __xpool_set_idx(struct xpool *xp, xpool_index idx, xpool_data data)
 330 {
 331         struct xpool_node *node;
 332         if (!__validate_idx(xp, idx)){
 333                 return NoIndex;
 334         }
 335         node = XPTR(&xp->mem) + idx;
 336         node->data = data;
 337         return idx;
 338 }
 339
 340 xpool_index xpool_set_idx(struct xpool *xp, xpool_index idx, xpool_data data, uint32_t who)
 341 {
 342         xpool_index ret;
 343         xlock_acquire(&xp->lock, who);
 344         ret = __xpool_set_idx(xp, idx, data);
 345         xlock_release(&xp->lock);
 346         return ret;
 347 }
 348
 349
 350 #ifdef __KERNEL__
 351 #include <linux/module.h>
 352 #include <xtypes/xpool_exports.h>
 353 #endif