1321936Shselasky/* 2321936Shselasky * Copyright (c) 2011 Intel Corporation. All rights reserved. 3321936Shselasky * 4321936Shselasky * This software is available to you under a choice of one of two 5321936Shselasky * licenses. You may choose to be licensed under the terms of the GNU 6321936Shselasky * General Public License (GPL) Version 2, available from the file 7321936Shselasky * COPYING in the main directory of this source tree, or the 8321936Shselasky * OpenIB.org BSD license below: 9321936Shselasky * 10321936Shselasky * Redistribution and use in source and binary forms, with or 11321936Shselasky * without modification, are permitted provided that the following 12321936Shselasky * conditions are met: 13321936Shselasky * 14321936Shselasky * - Redistributions of source code must retain the above 15321936Shselasky * copyright notice, this list of conditions and the following 16321936Shselasky * disclaimer. 17321936Shselasky * 18321936Shselasky * - Redistributions in binary form must reproduce the above 19321936Shselasky * copyright notice, this list of conditions and the following 20321936Shselasky * disclaimer in the documentation and/or other materials 21321936Shselasky * provided with the distribution. 22321936Shselasky * 23321936Shselasky * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24321936Shselasky * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25321936Shselasky * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26321936Shselasky * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27321936Shselasky * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28321936Shselasky * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29321936Shselasky * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30321936Shselasky * SOFTWARE. 31321936Shselasky * 32321936Shselasky */ 33321936Shselasky 34321936Shselasky#if !defined(INDEXER_H) 35321936Shselasky#define INDEXER_H 36321936Shselasky 37321936Shselasky#include <config.h> 38321936Shselasky#include <stddef.h> 39321936Shselasky#include <sys/types.h> 40321936Shselasky 41321936Shselasky/* 42321936Shselasky * Indexer - to find a structure given an index. Synchronization 43321936Shselasky * must be provided by the caller. Caller must initialize the 44321936Shselasky * indexer by setting free_list and size to 0. 45321936Shselasky */ 46321936Shselasky 47321936Shselaskyunion idx_entry { 48321936Shselasky void *item; 49321936Shselasky int next; 50321936Shselasky}; 51321936Shselasky 52321936Shselasky#define IDX_INDEX_BITS 16 53321936Shselasky#define IDX_ENTRY_BITS 10 54321936Shselasky#define IDX_ENTRY_SIZE (1 << IDX_ENTRY_BITS) 55321936Shselasky#define IDX_ARRAY_SIZE (1 << (IDX_INDEX_BITS - IDX_ENTRY_BITS)) 56321936Shselasky#define IDX_MAX_INDEX ((1 << IDX_INDEX_BITS) - 1) 57321936Shselasky 58321936Shselaskystruct indexer 59321936Shselasky{ 60321936Shselasky union idx_entry *array[IDX_ARRAY_SIZE]; 61321936Shselasky int free_list; 62321936Shselasky int size; 63321936Shselasky}; 64321936Shselasky 65321936Shselasky#define idx_array_index(index) (index >> IDX_ENTRY_BITS) 66321936Shselasky#define idx_entry_index(index) (index & (IDX_ENTRY_SIZE - 1)) 67321936Shselasky 68321936Shselaskyint idx_insert(struct indexer *idx, void *item); 69321936Shselaskyvoid *idx_remove(struct indexer *idx, int index); 70321936Shselaskyvoid idx_replace(struct indexer *idx, int index, void *item); 71321936Shselasky 72321936Shselaskystatic inline void *idx_at(struct indexer *idx, int index) 73321936Shselasky{ 74321936Shselasky return (idx->array[idx_array_index(index)] + idx_entry_index(index))->item; 75321936Shselasky} 76321936Shselasky 77321936Shselasky/* 78321936Shselasky * Index map - associates a structure with an index. Synchronization 79321936Shselasky * must be provided by the caller. Caller must initialize the 80321936Shselasky * index map by setting it to 0. 81321936Shselasky */ 82321936Shselasky 83321936Shselaskystruct index_map 84321936Shselasky{ 85321936Shselasky void **array[IDX_ARRAY_SIZE]; 86321936Shselasky}; 87321936Shselasky 88321936Shselaskyint idm_set(struct index_map *idm, int index, void *item); 89321936Shselaskyvoid *idm_clear(struct index_map *idm, int index); 90321936Shselasky 91321936Shselaskystatic inline void *idm_at(struct index_map *idm, int index) 92321936Shselasky{ 93321936Shselasky void **entry; 94321936Shselasky entry = idm->array[idx_array_index(index)]; 95321936Shselasky return entry[idx_entry_index(index)]; 96321936Shselasky} 97321936Shselasky 98321936Shselaskystatic inline void *idm_lookup(struct index_map *idm, int index) 99321936Shselasky{ 100321936Shselasky return ((index <= IDX_MAX_INDEX) && idm->array[idx_array_index(index)]) ? 101321936Shselasky idm_at(idm, index) : NULL; 102321936Shselasky} 103321936Shselasky 104321936Shselaskytypedef struct _dlist_entry { 105321936Shselasky struct _dlist_entry *next; 106321936Shselasky struct _dlist_entry *prev; 107321936Shselasky} dlist_entry; 108321936Shselasky 109321936Shselaskystatic inline void dlist_init(dlist_entry *head) 110321936Shselasky{ 111321936Shselasky head->next = head; 112321936Shselasky head->prev = head; 113321936Shselasky} 114321936Shselasky 115321936Shselaskystatic inline int dlist_empty(dlist_entry *head) 116321936Shselasky{ 117321936Shselasky return head->next == head; 118321936Shselasky} 119321936Shselasky 120321936Shselaskystatic inline void dlist_insert_after(dlist_entry *item, dlist_entry *head) 121321936Shselasky{ 122321936Shselasky item->next = head->next; 123321936Shselasky item->prev = head; 124321936Shselasky head->next->prev = item; 125321936Shselasky head->next = item; 126321936Shselasky} 127321936Shselasky 128321936Shselaskystatic inline void dlist_insert_before(dlist_entry *item, dlist_entry *head) 129321936Shselasky{ 130321936Shselasky dlist_insert_after(item, head->prev); 131321936Shselasky} 132321936Shselasky 133321936Shselasky#define dlist_insert_head dlist_insert_after 134321936Shselasky#define dlist_insert_tail dlist_insert_before 135321936Shselasky 136321936Shselaskystatic inline void dlist_remove(dlist_entry *item) 137321936Shselasky{ 138321936Shselasky item->prev->next = item->next; 139321936Shselasky item->next->prev = item->prev; 140321936Shselasky} 141321936Shselasky 142321936Shselasky#endif /* INDEXER_H */ 143