3 Functions for maintaining handles on objects. */
6 * Copyright (c) 1999-2000 Internet Software Consortium.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of The Internet Software Consortium nor the names
19 * of its contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
23 * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
24 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26 * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * This software has been written for the Internet Software Consortium
37 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
38 * To learn more about the Internet Software Consortium, see
39 * ``http://www.isc.org/''. To learn more about Vixie Enterprises,
40 * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
41 * ``http://www.nominum.com''.
44 #include <omapip/omapip_p.h>
46 /* The handle table is a hierarchical tree designed for quick mapping
47 of handle identifiers to objects. Objects contain their own handle
48 identifiers if they have them, so the reverse mapping is also
49 quick. The hierarchy is made up of table objects, each of which
50 has 120 entries, a flag indicating whether the table is a leaf
51 table or an indirect table, the handle of the first object covered
52 by the table and the first object after that that's *not* covered
53 by the table, a count of how many objects of either type are
54 currently stored in the table, and an array of 120 entries pointing
55 either to objects or tables.
57 When we go to add an object to the table, we look to see if the
58 next object handle to be assigned is covered by the outermost
59 table. If it is, we find the place within that table where the
60 next handle should go, and if necessary create additional nodes in
61 the tree to contain the new handle. The pointer to the object is
62 then stored in the correct position.
64 Theoretically, we could have some code here to free up handle
65 tables as they go out of use, but by and large handle tables won't
66 go out of use, so this is being skipped for now. It shouldn't be
67 too hard to implement in the future if there's a different
70 omapi_handle_table_t *omapi_handle_table;
71 omapi_handle_t omapi_next_handle = 1; /* Next handle to be assigned. */
73 static isc_result_t omapi_handle_lookup_in (omapi_object_t **,
75 omapi_handle_table_t *);
76 static isc_result_t omapi_object_handle_in_table (omapi_handle_t,
77 omapi_handle_table_t *,
79 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **);
81 isc_result_t omapi_object_handle (omapi_handle_t *h, omapi_object_t *o)
91 if (!omapi_handle_table) {
92 omapi_handle_table = dmalloc (sizeof *omapi_handle_table, MDL);
93 if (!omapi_handle_table)
94 return ISC_R_NOMEMORY;
95 memset (omapi_handle_table, 0, sizeof *omapi_handle_table);
96 omapi_handle_table -> first = 0;
97 omapi_handle_table -> limit = OMAPI_HANDLE_TABLE_SIZE;
98 omapi_handle_table -> leafp = 1;
101 /* If this handle doesn't fit in the outer table, we need to
102 make a new outer table. This is a while loop in case for
103 some reason we decide to do disjoint handle allocation,
104 where the next level of indirection still isn't big enough
105 to enclose the next handle ID. */
107 while (omapi_next_handle >= omapi_handle_table -> limit) {
108 omapi_handle_table_t *new;
110 new = dmalloc (sizeof *new, MDL);
112 return ISC_R_NOMEMORY;
113 memset (new, 0, sizeof *new);
115 new -> limit = (omapi_handle_table -> limit *
116 OMAPI_HANDLE_TABLE_SIZE);
118 new -> children [0].table = omapi_handle_table;
119 omapi_handle_table = new;
122 /* Try to cram this handle into the existing table. */
123 status = omapi_object_handle_in_table (omapi_next_handle,
124 omapi_handle_table, o);
125 /* If it worked, return the next handle and increment it. */
126 if (status == ISC_R_SUCCESS) {
127 *h = omapi_next_handle;
129 return ISC_R_SUCCESS;
131 if (status != ISC_R_NOSPACE)
134 status = omapi_handle_table_enclose (&omapi_handle_table);
135 if (status != ISC_R_SUCCESS)
138 status = omapi_object_handle_in_table (omapi_next_handle,
139 omapi_handle_table, o);
140 if (status != ISC_R_SUCCESS)
142 *h = omapi_next_handle;
145 return ISC_R_SUCCESS;
148 static isc_result_t omapi_object_handle_in_table (omapi_handle_t h,
149 omapi_handle_table_t *table,
152 omapi_handle_table_t *inner;
153 omapi_handle_t scale, index;
156 if (table -> first > h || table -> limit <= h)
157 return ISC_R_NOSPACE;
159 /* If this is a leaf table, just stash the object in the
160 appropriate place. */
161 if (table -> leafp) {
162 status = (omapi_object_reference
163 (&table -> children [h - table -> first].object,
165 if (status != ISC_R_SUCCESS)
168 return ISC_R_SUCCESS;
171 /* Scale is the number of handles represented by each child of this
172 table. For a leaf table, scale would be 1. For a first level
173 of indirection, 120. For a second, 120 * 120. Et cetera. */
174 scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
176 /* So the next most direct table from this one that contains the
177 handle must be the subtable of this table whose index into this
178 table's array of children is the handle divided by the scale. */
179 index = (h - table -> first) / scale;
180 inner = table -> children [index].table;
182 /* If there is no more direct table than this one in the slot
183 we came up with, make one. */
185 inner = dmalloc (sizeof *inner, MDL);
187 return ISC_R_NOMEMORY;
188 memset (inner, 0, sizeof *inner);
189 inner -> first = index * scale + table -> first;
190 inner -> limit = inner -> first + scale;
191 if (scale == OMAPI_HANDLE_TABLE_SIZE)
193 table -> children [index].table = inner;
196 status = omapi_object_handle_in_table (h, inner, o);
197 if (status == ISC_R_NOSPACE) {
198 status = (omapi_handle_table_enclose
199 (&table -> children [index].table));
200 if (status != ISC_R_SUCCESS)
203 return omapi_object_handle_in_table
204 (h, table -> children [index].table, o);
209 static isc_result_t omapi_handle_table_enclose (omapi_handle_table_t **table)
211 omapi_handle_table_t *inner = *table;
212 omapi_handle_table_t *new;
213 int index, base, scale;
215 /* The scale of the table we're enclosing is going to be the
216 difference between its "first" and "limit" members. So the
217 scale of the table enclosing it is going to be that multiplied
218 by the table size. */
219 scale = (inner -> first - inner -> limit) * OMAPI_HANDLE_TABLE_SIZE;
221 /* The range that the enclosing table covers is going to be
222 the result of subtracting the remainder of dividing the
223 enclosed table's first entry number by the enclosing
224 table's scale. If handle IDs are being allocated
225 sequentially, the enclosing table's "first" value will be
226 the same as the enclosed table's "first" value. */
227 base = inner -> first - inner -> first % scale;
229 /* The index into the enclosing table at which the enclosed table
230 will be stored is going to be the difference between the "first"
231 value of the enclosing table and the enclosed table - zero, if
232 we are allocating sequentially. */
233 index = (base - inner -> first) / OMAPI_HANDLE_TABLE_SIZE;
235 new = dmalloc (sizeof *new, MDL);
237 return ISC_R_NOMEMORY;
238 memset (new, 0, sizeof *new);
240 new -> limit = base + scale;
241 if (scale == OMAPI_HANDLE_TABLE_SIZE)
243 new -> children [index].table = inner;
245 return ISC_R_SUCCESS;
248 isc_result_t omapi_handle_lookup (omapi_object_t **o, omapi_handle_t h)
250 return omapi_handle_lookup_in (o, h, omapi_handle_table);
253 static isc_result_t omapi_handle_lookup_in (omapi_object_t **o,
255 omapi_handle_table_t *table)
258 omapi_handle_table_t *inner;
259 omapi_handle_t scale, index;
261 if (!table || table -> first > h || table -> limit <= h)
262 return ISC_R_NOTFOUND;
264 /* If this is a leaf table, just grab the object. */
265 if (table -> leafp) {
267 if (!table -> children [h - table -> first].object)
268 return ISC_R_NOTFOUND;
269 return omapi_object_reference
270 (o, table -> children [h - table -> first].object,
274 /* Scale is the number of handles represented by each child of this
275 table. For a leaf table, scale would be 1. For a first level
276 of indirection, 120. For a second, 120 * 120. Et cetera. */
277 scale = (table -> limit - table -> first) / OMAPI_HANDLE_TABLE_SIZE;
279 /* So the next most direct table from this one that contains the
280 handle must be the subtable of this table whose index into this
281 table's array of children is the handle divided by the scale. */
282 index = (h - table -> first) / scale;
283 inner = table -> children [index].table;
285 return omapi_handle_lookup_in (o, h, table -> children [index].table);
288 /* For looking up objects based on handles that have been sent on the wire. */
289 isc_result_t omapi_handle_td_lookup (omapi_object_t **obj,
290 omapi_typed_data_t *handle)
295 if (handle -> type == omapi_datatype_int)
296 h = handle -> u.integer;
297 else if (handle -> type == omapi_datatype_data &&
298 handle -> u.buffer.len == sizeof h) {
299 memcpy (&h, handle -> u.buffer.value, sizeof h);
302 return ISC_R_INVALIDARG;
303 return omapi_handle_lookup (obj, h);