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 } 165