contrib/ofed/librdmacm/indexer.c

   1 /*
   2  * Copyright (c) 2011 Intel Corporation.  All rights reserved.
   3  *
   4  * This software is available to you under a choice of one of two
   5  * licenses.  You may choose to be licensed under the terms of the GNU
   6  * General Public License (GPL) Version 2, available from the file
   7  * COPYING in the main directory of this source tree, or the
   8  * OpenIB.org BSD license below:
   9  *
  10  *     Redistribution and use in source and binary forms, with or
  11  *     without modification, are permitted provided that the following
  12  *     conditions are met:
  13  *
  14  *      - Redistributions of source code must retain the above
  15  *        copyright notice, this list of conditions and the following
  16  *        disclaimer.
  17  *
  18  *      - Redistributions in binary form must reproduce the above
  19  *        copyright notice, this list of conditions and the following
  20  *        disclaimer in the documentation and/or other materials
  21  *        provided with the distribution.
  22  *
  23  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  24  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  25  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  26  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  27  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  28  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  29  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  30  * SOFTWARE.
  31  *
  32  */
  33
  34 #include <config.h>
  35
  36 #include <errno.h>
  37 #include <sys/types.h>
  38 #include <stdlib.h>
  39
  40 #include "indexer.h"
  41
  42 /*
  43  * Indexer - to find a structure given an index
  44  *
  45  * We store pointers using a double lookup and return an index to the
  46  * user which is then used to retrieve the pointer.  The upper bits of
  47  * the index are itself an index into an array of memory allocations.
  48  * The lower bits specify the offset into the allocated memory where
  49  * the pointer is stored.
  50  *
  51  * This allows us to adjust the number of pointers stored by the index
  52  * list without taking a lock during data lookups.
  53  */
  54
  55 static int idx_grow(struct indexer *idx)
  56 {
  57         union idx_entry *entry;
  58         int i, start_index;
  59
  60         if (idx->size >= IDX_ARRAY_SIZE)
  61                 goto nomem;
  62
  63         idx->array[idx->size] = calloc(IDX_ENTRY_SIZE, sizeof(union idx_entry));
  64         if (!idx->array[idx->size])
  65                 goto nomem;
  66
  67         entry = idx->array[idx->size];
  68         start_index = idx->size << IDX_ENTRY_BITS;
  69         entry[IDX_ENTRY_SIZE - 1].next = idx->free_list;
  70
  71         for (i = IDX_ENTRY_SIZE - 2; i >= 0; i--)
  72                 entry[i].next = start_index + i + 1;
  73
  74         /* Index 0 is reserved */
  75         if (start_index == 0)
  76                 start_index++;
  77         idx->free_list = start_index;
  78         idx->size++;
  79         return start_index;
  80
  81 nomem:
  82         errno = ENOMEM;
  83         return -1;
  84 }
  85
  86 int idx_insert(struct indexer *idx, void *item)
  87 {
  88         union idx_entry *entry;
  89         int index;
  90
  91         if ((index = idx->free_list) == 0) {
  92                 if ((index = idx_grow(idx)) <= 0)
  93                         return index;
  94         }
  95
  96         entry = idx->array[idx_array_index(index)];
  97         idx->free_list = entry[idx_entry_index(index)].next;
  98         entry[idx_entry_index(index)].item = item;
  99         return index;
 100 }
 101
 102 void *idx_remove(struct indexer *idx, int index)
 103 {
 104         union idx_entry *entry;
 105         void *item;
 106
 107         entry = idx->array[idx_array_index(index)];
 108         item = entry[idx_entry_index(index)].item;
 109         entry[idx_entry_index(index)].next = idx->free_list;
 110         idx->free_list = index;
 111         return item;
 112 }
 113
 114 void idx_replace(struct indexer *idx, int index, void *item)
 115 {
 116         union idx_entry *entry;
 117
 118         entry = idx->array[idx_array_index(index)];
 119         entry[idx_entry_index(index)].item = item;
 120 }
 121
 122
 123 static int idm_grow(struct index_map *idm, int index)
 124 {
 125         idm->array[idx_array_index(index)] = calloc(IDX_ENTRY_SIZE, sizeof(void *));
 126         if (!idm->array[idx_array_index(index)])
 127                 goto nomem;
 128
 129         return index;
 130
 131 nomem:
 132         errno = ENOMEM;
 133         return -1;
 134 }
 135
 136 int idm_set(struct index_map *idm, int index, void *item)
 137 {
 138         void **entry;
 139
 140         if (index > IDX_MAX_INDEX) {
 141                 errno = ENOMEM;
 142                 return -1;
 143         }
 144
 145         if (!idm->array[idx_array_index(index)]) {
 146                 if (idm_grow(idm, index) < 0)
 147                         return -1;
 148         }
 149
 150         entry = idm->array[idx_array_index(index)];
 151         entry[idx_entry_index(index)] = item;
 152         return index;
 153 }
 154
 155 void *idm_clear(struct index_map *idm, int index)
 156 {
 157         void **entry;
 158         void *item;
 159
 160         entry = idm->array[idx_array_index(index)];
 161         item = entry[idx_entry_index(index)];
 162         entry[idx_entry_index(index)] = NULL;
 163         return item;
 164 }