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 #if !defined(INDEXER_H) 35 #define INDEXER_H 36 37 #include <config.h> 38 #include <stddef.h> 39 #include <sys/types.h> 40 41 /* 42 * Indexer - to find a structure given an index. Synchronization 43 * must be provided by the caller. Caller must initialize the 44 * indexer by setting free_list and size to 0. 45 */ 46 47 union idx_entry { 48 void *item; 49 int next; 50 }; 51 52 #define IDX_INDEX_BITS 16 53 #define IDX_ENTRY_BITS 10 54 #define IDX_ENTRY_SIZE (1 << IDX_ENTRY_BITS) 55 #define IDX_ARRAY_SIZE (1 << (IDX_INDEX_BITS - IDX_ENTRY_BITS)) 56 #define IDX_MAX_INDEX ((1 << IDX_INDEX_BITS) - 1) 57 58 struct indexer 59 { 60 union idx_entry *array[IDX_ARRAY_SIZE]; 61 int free_list; 62 int size; 63 }; 64 65 #define idx_array_index(index) (index >> IDX_ENTRY_BITS) 66 #define idx_entry_index(index) (index & (IDX_ENTRY_SIZE - 1)) 67 68 int idx_insert(struct indexer *idx, void *item); 69 void *idx_remove(struct indexer *idx, int index); 70 void idx_replace(struct indexer *idx, int index, void *item); 71 72 static inline void *idx_at(struct indexer *idx, int index) 73 { 74 return (idx->array[idx_array_index(index)] + idx_entry_index(index))->item; 75 } 76 77 /* 78 * Index map - associates a structure with an index. Synchronization 79 * must be provided by the caller. Caller must initialize the 80 * index map by setting it to 0. 81 */ 82 83 struct index_map 84 { 85 void **array[IDX_ARRAY_SIZE]; 86 }; 87 88 int idm_set(struct index_map *idm, int index, void *item); 89 void *idm_clear(struct index_map *idm, int index); 90 91 static inline void *idm_at(struct index_map *idm, int index) 92 { 93 void **entry; 94 entry = idm->array[idx_array_index(index)]; 95 return entry[idx_entry_index(index)]; 96 } 97 98 static inline void *idm_lookup(struct index_map *idm, int index) 99 { 100 return ((index <= IDX_MAX_INDEX) && idm->array[idx_array_index(index)]) ? 101 idm_at(idm, index) : NULL; 102 } 103 104 typedef struct _dlist_entry { 105 struct _dlist_entry *next; 106 struct _dlist_entry *prev; 107 } dlist_entry; 108 109 static inline void dlist_init(dlist_entry *head) 110 { 111 head->next = head; 112 head->prev = head; 113 } 114 115 static inline int dlist_empty(dlist_entry *head) 116 { 117 return head->next == head; 118 } 119 120 static inline void dlist_insert_after(dlist_entry *item, dlist_entry *head) 121 { 122 item->next = head->next; 123 item->prev = head; 124 head->next->prev = item; 125 head->next = item; 126 } 127 128 static inline void dlist_insert_before(dlist_entry *item, dlist_entry *head) 129 { 130 dlist_insert_after(item, head->prev); 131 } 132 133 #define dlist_insert_head dlist_insert_after 134 #define dlist_insert_tail dlist_insert_before 135 136 static inline void dlist_remove(dlist_entry *item) 137 { 138 item->prev->next = item->next; 139 item->next->prev = item->prev; 140 } 141 142 #endif /* INDEXER_H */ 143