indexer.c revision 331769 
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
55static 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
81nomem:
82	errno = ENOMEM;
83	return -1;
84}
85
86int 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
102void *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
114void 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
123static 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
131nomem:
132	errno = ENOMEM;
133	return -1;
134}
135
136int 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
155void *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