1d6b92ffaSHans Petter Selasky /*
2d6b92ffaSHans Petter Selasky * Copyright (c) 2011 Intel Corporation. All rights reserved.
3d6b92ffaSHans Petter Selasky *
4d6b92ffaSHans Petter Selasky * This software is available to you under a choice of one of two
5d6b92ffaSHans Petter Selasky * licenses. You may choose to be licensed under the terms of the GNU
6d6b92ffaSHans Petter Selasky * General Public License (GPL) Version 2, available from the file
7d6b92ffaSHans Petter Selasky * COPYING in the main directory of this source tree, or the
8d6b92ffaSHans Petter Selasky * OpenIB.org BSD license below:
9d6b92ffaSHans Petter Selasky *
10d6b92ffaSHans Petter Selasky * Redistribution and use in source and binary forms, with or
11d6b92ffaSHans Petter Selasky * without modification, are permitted provided that the following
12d6b92ffaSHans Petter Selasky * conditions are met:
13d6b92ffaSHans Petter Selasky *
14d6b92ffaSHans Petter Selasky * - Redistributions of source code must retain the above
15d6b92ffaSHans Petter Selasky * copyright notice, this list of conditions and the following
16d6b92ffaSHans Petter Selasky * disclaimer.
17d6b92ffaSHans Petter Selasky *
18d6b92ffaSHans Petter Selasky * - Redistributions in binary form must reproduce the above
19d6b92ffaSHans Petter Selasky * copyright notice, this list of conditions and the following
20d6b92ffaSHans Petter Selasky * disclaimer in the documentation and/or other materials
21d6b92ffaSHans Petter Selasky * provided with the distribution.
22d6b92ffaSHans Petter Selasky *
23d6b92ffaSHans Petter Selasky * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
24d6b92ffaSHans Petter Selasky * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
25d6b92ffaSHans Petter Selasky * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
26d6b92ffaSHans Petter Selasky * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
27d6b92ffaSHans Petter Selasky * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
28d6b92ffaSHans Petter Selasky * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
29d6b92ffaSHans Petter Selasky * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30d6b92ffaSHans Petter Selasky * SOFTWARE.
31d6b92ffaSHans Petter Selasky *
32d6b92ffaSHans Petter Selasky */
33d6b92ffaSHans Petter Selasky
34d6b92ffaSHans Petter Selasky #include <config.h>
35d6b92ffaSHans Petter Selasky
36d6b92ffaSHans Petter Selasky #include <errno.h>
37d6b92ffaSHans Petter Selasky #include <sys/types.h>
38d6b92ffaSHans Petter Selasky #include <stdlib.h>
39d6b92ffaSHans Petter Selasky
40d6b92ffaSHans Petter Selasky #include "indexer.h"
41d6b92ffaSHans Petter Selasky
42d6b92ffaSHans Petter Selasky /*
43d6b92ffaSHans Petter Selasky * Indexer - to find a structure given an index
44d6b92ffaSHans Petter Selasky *
45d6b92ffaSHans Petter Selasky * We store pointers using a double lookup and return an index to the
46d6b92ffaSHans Petter Selasky * user which is then used to retrieve the pointer. The upper bits of
47d6b92ffaSHans Petter Selasky * the index are itself an index into an array of memory allocations.
48d6b92ffaSHans Petter Selasky * The lower bits specify the offset into the allocated memory where
49d6b92ffaSHans Petter Selasky * the pointer is stored.
50d6b92ffaSHans Petter Selasky *
51d6b92ffaSHans Petter Selasky * This allows us to adjust the number of pointers stored by the index
52d6b92ffaSHans Petter Selasky * list without taking a lock during data lookups.
53d6b92ffaSHans Petter Selasky */
54d6b92ffaSHans Petter Selasky
idx_grow(struct indexer * idx)55d6b92ffaSHans Petter Selasky static int idx_grow(struct indexer *idx)
56d6b92ffaSHans Petter Selasky {
57d6b92ffaSHans Petter Selasky union idx_entry *entry;
58d6b92ffaSHans Petter Selasky int i, start_index;
59d6b92ffaSHans Petter Selasky
60d6b92ffaSHans Petter Selasky if (idx->size >= IDX_ARRAY_SIZE)
61d6b92ffaSHans Petter Selasky goto nomem;
62d6b92ffaSHans Petter Selasky
63d6b92ffaSHans Petter Selasky idx->array[idx->size] = calloc(IDX_ENTRY_SIZE, sizeof(union idx_entry));
64d6b92ffaSHans Petter Selasky if (!idx->array[idx->size])
65d6b92ffaSHans Petter Selasky goto nomem;
66d6b92ffaSHans Petter Selasky
67d6b92ffaSHans Petter Selasky entry = idx->array[idx->size];
68d6b92ffaSHans Petter Selasky start_index = idx->size << IDX_ENTRY_BITS;
69d6b92ffaSHans Petter Selasky entry[IDX_ENTRY_SIZE - 1].next = idx->free_list;
70d6b92ffaSHans Petter Selasky
71d6b92ffaSHans Petter Selasky for (i = IDX_ENTRY_SIZE - 2; i >= 0; i--)
72d6b92ffaSHans Petter Selasky entry[i].next = start_index + i + 1;
73d6b92ffaSHans Petter Selasky
74d6b92ffaSHans Petter Selasky /* Index 0 is reserved */
75d6b92ffaSHans Petter Selasky if (start_index == 0)
76d6b92ffaSHans Petter Selasky start_index++;
77d6b92ffaSHans Petter Selasky idx->free_list = start_index;
78d6b92ffaSHans Petter Selasky idx->size++;
79d6b92ffaSHans Petter Selasky return start_index;
80d6b92ffaSHans Petter Selasky
81d6b92ffaSHans Petter Selasky nomem:
82d6b92ffaSHans Petter Selasky errno = ENOMEM;
83d6b92ffaSHans Petter Selasky return -1;
84d6b92ffaSHans Petter Selasky }
85d6b92ffaSHans Petter Selasky
idx_insert(struct indexer * idx,void * item)86d6b92ffaSHans Petter Selasky int idx_insert(struct indexer *idx, void *item)
87d6b92ffaSHans Petter Selasky {
88d6b92ffaSHans Petter Selasky union idx_entry *entry;
89d6b92ffaSHans Petter Selasky int index;
90d6b92ffaSHans Petter Selasky
91d6b92ffaSHans Petter Selasky if ((index = idx->free_list) == 0) {
92d6b92ffaSHans Petter Selasky if ((index = idx_grow(idx)) <= 0)
93d6b92ffaSHans Petter Selasky return index;
94d6b92ffaSHans Petter Selasky }
95d6b92ffaSHans Petter Selasky
96d6b92ffaSHans Petter Selasky entry = idx->array[idx_array_index(index)];
97d6b92ffaSHans Petter Selasky idx->free_list = entry[idx_entry_index(index)].next;
98d6b92ffaSHans Petter Selasky entry[idx_entry_index(index)].item = item;
99d6b92ffaSHans Petter Selasky return index;
100d6b92ffaSHans Petter Selasky }
101d6b92ffaSHans Petter Selasky
idx_remove(struct indexer * idx,int index)102d6b92ffaSHans Petter Selasky void *idx_remove(struct indexer *idx, int index)
103d6b92ffaSHans Petter Selasky {
104d6b92ffaSHans Petter Selasky union idx_entry *entry;
105d6b92ffaSHans Petter Selasky void *item;
106d6b92ffaSHans Petter Selasky
107d6b92ffaSHans Petter Selasky entry = idx->array[idx_array_index(index)];
108d6b92ffaSHans Petter Selasky item = entry[idx_entry_index(index)].item;
109d6b92ffaSHans Petter Selasky entry[idx_entry_index(index)].next = idx->free_list;
110d6b92ffaSHans Petter Selasky idx->free_list = index;
111d6b92ffaSHans Petter Selasky return item;
112d6b92ffaSHans Petter Selasky }
113d6b92ffaSHans Petter Selasky
idx_replace(struct indexer * idx,int index,void * item)114d6b92ffaSHans Petter Selasky void idx_replace(struct indexer *idx, int index, void *item)
115d6b92ffaSHans Petter Selasky {
116d6b92ffaSHans Petter Selasky union idx_entry *entry;
117d6b92ffaSHans Petter Selasky
118d6b92ffaSHans Petter Selasky entry = idx->array[idx_array_index(index)];
119d6b92ffaSHans Petter Selasky entry[idx_entry_index(index)].item = item;
120d6b92ffaSHans Petter Selasky }
121d6b92ffaSHans Petter Selasky
122d6b92ffaSHans Petter Selasky
idm_grow(struct index_map * idm,int index)123d6b92ffaSHans Petter Selasky static int idm_grow(struct index_map *idm, int index)
124d6b92ffaSHans Petter Selasky {
125d6b92ffaSHans Petter Selasky idm->array[idx_array_index(index)] = calloc(IDX_ENTRY_SIZE, sizeof(void *));
126d6b92ffaSHans Petter Selasky if (!idm->array[idx_array_index(index)])
127d6b92ffaSHans Petter Selasky goto nomem;
128d6b92ffaSHans Petter Selasky
129d6b92ffaSHans Petter Selasky return index;
130d6b92ffaSHans Petter Selasky
131d6b92ffaSHans Petter Selasky nomem:
132d6b92ffaSHans Petter Selasky errno = ENOMEM;
133d6b92ffaSHans Petter Selasky return -1;
134d6b92ffaSHans Petter Selasky }
135d6b92ffaSHans Petter Selasky
idm_set(struct index_map * idm,int index,void * item)136d6b92ffaSHans Petter Selasky int idm_set(struct index_map *idm, int index, void *item)
137d6b92ffaSHans Petter Selasky {
138d6b92ffaSHans Petter Selasky void **entry;
139d6b92ffaSHans Petter Selasky
140d6b92ffaSHans Petter Selasky if (index > IDX_MAX_INDEX) {
141d6b92ffaSHans Petter Selasky errno = ENOMEM;
142d6b92ffaSHans Petter Selasky return -1;
143d6b92ffaSHans Petter Selasky }
144d6b92ffaSHans Petter Selasky
145d6b92ffaSHans Petter Selasky if (!idm->array[idx_array_index(index)]) {
146d6b92ffaSHans Petter Selasky if (idm_grow(idm, index) < 0)
147d6b92ffaSHans Petter Selasky return -1;
148d6b92ffaSHans Petter Selasky }
149d6b92ffaSHans Petter Selasky
150d6b92ffaSHans Petter Selasky entry = idm->array[idx_array_index(index)];
151d6b92ffaSHans Petter Selasky entry[idx_entry_index(index)] = item;
152d6b92ffaSHans Petter Selasky return index;
153d6b92ffaSHans Petter Selasky }
154d6b92ffaSHans Petter Selasky
idm_clear(struct index_map * idm,int index)155d6b92ffaSHans Petter Selasky void *idm_clear(struct index_map *idm, int index)
156d6b92ffaSHans Petter Selasky {
157d6b92ffaSHans Petter Selasky void **entry;
158d6b92ffaSHans Petter Selasky void *item;
159d6b92ffaSHans Petter Selasky
160d6b92ffaSHans Petter Selasky entry = idm->array[idx_array_index(index)];
161d6b92ffaSHans Petter Selasky item = entry[idx_entry_index(index)];
162d6b92ffaSHans Petter Selasky entry[idx_entry_index(index)] = NULL;
163d6b92ffaSHans Petter Selasky return item;
164d6b92ffaSHans Petter Selasky }
165