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 47union 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 58struct 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 68int idx_insert(struct indexer *idx, void *item); 69void *idx_remove(struct indexer *idx, int index); 70void idx_replace(struct indexer *idx, int index, void *item); 71 72static 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 83struct index_map 84{ 85 void **array[IDX_ARRAY_SIZE]; 86}; 87 88int idm_set(struct index_map *idm, int index, void *item); 89void *idm_clear(struct index_map *idm, int index); 90 91static 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 98static 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 104typedef struct _dlist_entry { 105 struct _dlist_entry *next; 106 struct _dlist_entry *prev; 107} dlist_entry; 108 109static inline void dlist_init(dlist_entry *head) 110{ 111 head->next = head; 112 head->prev = head; 113} 114 115static inline int dlist_empty(dlist_entry *head) 116{ 117 return head->next == head; 118} 119 120static 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 128static 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 136static 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