3 Functions for maintaining handles on objects. */
6 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
7 * Copyright (c) 1999-2003 by Internet Software Consortium
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
19 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * Internet Systems Consortium, Inc.
23 * Redwood City, CA 94063
27 * This software has been written for Internet Systems Consortium
28 * by Ted Lemon in cooperation with Vixie Enterprises and Nominum, Inc.
29 * To learn more about Internet Systems Consortium, see
30 * ``http://www.isc.org/''. To learn more about Vixie Enterprises,
31 * see ``http://www.vix.com''. To learn more about Nominum, Inc., see
32 * ``http://www.nominum.com''.
35 #include <omapip/omapip_p.h>
37 /* The handle table is a hierarchical tree designed for quick mapping
38 of handle identifiers to objects. Objects contain their own handle
39 identifiers if they have them, so the reverse mapping is also
40 quick. The hierarchy is made up of table objects, each of which
41 has 120 entries, a flag indicating whether the table is a leaf
42 table or an indirect table, the handle of the first object covered
43 by the table and the first object after that that's *not* covered
44 by the table, a count of how many objects of either type are
45 currently stored in the table, and an array of 120 entries pointing
46 either to objects or tables.
48 When we go to add an object to the table, we look to see if the
49 next object handle to be assigned is covered by the outermost
50 table. If it is, we find the place within that table where the
51 next handle should go, and if necessary create additional nodes in
52 the tree to contain the new handle. The pointer to the object is
53 then stored in the correct position.
55 Theoretically, we could have some code here to free up handle
56 tables as they go out of use, but by and large handle tables won't
57 go out of use, so this is being skipped for now. It shouldn't be
58 too hard to implement in the future if there's a different
61 omapi_handle_table_t
*omapi_handle_table
;
62 omapi_handle_t omapi_next_handle
= 1; /* Next handle to be assigned. */
64 static isc_result_t
omapi_handle_lookup_in (omapi_object_t
**,
66 omapi_handle_table_t
*);
67 static isc_result_t
omapi_object_handle_in_table (omapi_handle_t
,
68 omapi_handle_table_t
*,
70 static isc_result_t
omapi_handle_table_enclose (omapi_handle_table_t
**);
72 isc_result_t
omapi_object_handle (omapi_handle_t
*h
, omapi_object_t
*o
)
81 if (!omapi_handle_table
) {
82 omapi_handle_table
= dmalloc (sizeof *omapi_handle_table
, MDL
);
83 if (!omapi_handle_table
)
84 return ISC_R_NOMEMORY
;
85 memset (omapi_handle_table
, 0, sizeof *omapi_handle_table
);
86 omapi_handle_table
-> first
= 0;
87 omapi_handle_table
-> limit
= OMAPI_HANDLE_TABLE_SIZE
;
88 omapi_handle_table
-> leafp
= 1;
91 /* If this handle doesn't fit in the outer table, we need to
92 make a new outer table. This is a while loop in case for
93 some reason we decide to do disjoint handle allocation,
94 where the next level of indirection still isn't big enough
95 to enclose the next handle ID. */
97 while (omapi_next_handle
>= omapi_handle_table
-> limit
) {
98 omapi_handle_table_t
*new;
100 new = dmalloc (sizeof *new, MDL
);
102 return ISC_R_NOMEMORY
;
103 memset (new, 0, sizeof *new);
105 new -> limit
= (omapi_handle_table
-> limit
*
106 OMAPI_HANDLE_TABLE_SIZE
);
108 new -> children
[0].table
= omapi_handle_table
;
109 omapi_handle_table
= new;
112 /* Try to cram this handle into the existing table. */
113 status
= omapi_object_handle_in_table (omapi_next_handle
,
114 omapi_handle_table
, o
);
115 /* If it worked, return the next handle and increment it. */
116 if (status
== ISC_R_SUCCESS
) {
117 *h
= omapi_next_handle
;
119 return ISC_R_SUCCESS
;
121 if (status
!= ISC_R_NOSPACE
)
124 status
= omapi_handle_table_enclose (&omapi_handle_table
);
125 if (status
!= ISC_R_SUCCESS
)
128 status
= omapi_object_handle_in_table (omapi_next_handle
,
129 omapi_handle_table
, o
);
130 if (status
!= ISC_R_SUCCESS
)
132 *h
= omapi_next_handle
;
135 return ISC_R_SUCCESS
;
138 static isc_result_t
omapi_object_handle_in_table (omapi_handle_t h
,
139 omapi_handle_table_t
*table
,
142 omapi_handle_table_t
*inner
;
143 omapi_handle_t scale
, index
;
146 if (table
-> first
> h
|| table
-> limit
<= h
)
147 return ISC_R_NOSPACE
;
149 /* If this is a leaf table, just stash the object in the
150 appropriate place. */
151 if (table
-> leafp
) {
152 status
= (omapi_object_reference
153 (&table
-> children
[h
- table
-> first
].object
,
155 if (status
!= ISC_R_SUCCESS
)
158 return ISC_R_SUCCESS
;
161 /* Scale is the number of handles represented by each child of this
162 table. For a leaf table, scale would be 1. For a first level
163 of indirection, 120. For a second, 120 * 120. Et cetera. */
164 scale
= (table
-> limit
- table
-> first
) / OMAPI_HANDLE_TABLE_SIZE
;
166 /* So the next most direct table from this one that contains the
167 handle must be the subtable of this table whose index into this
168 table's array of children is the handle divided by the scale. */
169 index
= (h
- table
-> first
) / scale
;
170 inner
= table
-> children
[index
].table
;
172 /* If there is no more direct table than this one in the slot
173 we came up with, make one. */
175 inner
= dmalloc (sizeof *inner
, MDL
);
177 return ISC_R_NOMEMORY
;
178 memset (inner
, 0, sizeof *inner
);
179 inner
-> first
= index
* scale
+ table
-> first
;
180 inner
-> limit
= inner
-> first
+ scale
;
181 if (scale
== OMAPI_HANDLE_TABLE_SIZE
)
183 table
-> children
[index
].table
= inner
;
186 status
= omapi_object_handle_in_table (h
, inner
, o
);
187 if (status
== ISC_R_NOSPACE
) {
188 status
= (omapi_handle_table_enclose
189 (&table
-> children
[index
].table
));
190 if (status
!= ISC_R_SUCCESS
)
193 return omapi_object_handle_in_table
194 (h
, table
-> children
[index
].table
, o
);
199 static isc_result_t
omapi_handle_table_enclose (omapi_handle_table_t
**table
)
201 omapi_handle_table_t
*inner
= *table
;
202 omapi_handle_table_t
*new;
203 int index
, base
, scale
;
205 /* The scale of the table we're enclosing is going to be the
206 difference between its "first" and "limit" members. So the
207 scale of the table enclosing it is going to be that multiplied
208 by the table size. */
209 scale
= (inner
-> first
- inner
-> limit
) * OMAPI_HANDLE_TABLE_SIZE
;
211 /* The range that the enclosing table covers is going to be
212 the result of subtracting the remainder of dividing the
213 enclosed table's first entry number by the enclosing
214 table's scale. If handle IDs are being allocated
215 sequentially, the enclosing table's "first" value will be
216 the same as the enclosed table's "first" value. */
217 base
= inner
-> first
- inner
-> first
% scale
;
219 /* The index into the enclosing table at which the enclosed table
220 will be stored is going to be the difference between the "first"
221 value of the enclosing table and the enclosed table - zero, if
222 we are allocating sequentially. */
223 index
= (base
- inner
-> first
) / OMAPI_HANDLE_TABLE_SIZE
;
225 new = dmalloc (sizeof *new, MDL
);
227 return ISC_R_NOMEMORY
;
228 memset (new, 0, sizeof *new);
230 new -> limit
= base
+ scale
;
231 if (scale
== OMAPI_HANDLE_TABLE_SIZE
)
233 new -> children
[index
].table
= inner
;
235 return ISC_R_SUCCESS
;
238 isc_result_t
omapi_handle_lookup (omapi_object_t
**o
, omapi_handle_t h
)
240 return omapi_handle_lookup_in (o
, h
, omapi_handle_table
);
243 static isc_result_t
omapi_handle_lookup_in (omapi_object_t
**o
,
245 omapi_handle_table_t
*table
)
248 omapi_handle_table_t
*inner
;
249 omapi_handle_t scale
, index
;
251 if (!table
|| table
-> first
> h
|| table
-> limit
<= h
)
252 return ISC_R_NOTFOUND
;
254 /* If this is a leaf table, just grab the object. */
255 if (table
-> leafp
) {
257 if (!table
-> children
[h
- table
-> first
].object
)
258 return ISC_R_NOTFOUND
;
259 return omapi_object_reference
260 (o
, table
-> children
[h
- table
-> first
].object
,
264 /* Scale is the number of handles represented by each child of this
265 table. For a leaf table, scale would be 1. For a first level
266 of indirection, 120. For a second, 120 * 120. Et cetera. */
267 scale
= (table
-> limit
- table
-> first
) / OMAPI_HANDLE_TABLE_SIZE
;
269 /* So the next most direct table from this one that contains the
270 handle must be the subtable of this table whose index into this
271 table's array of children is the handle divided by the scale. */
272 index
= (h
- table
-> first
) / scale
;
273 inner
= table
-> children
[index
].table
;
275 return omapi_handle_lookup_in (o
, h
, table
-> children
[index
].table
);
278 /* For looking up objects based on handles that have been sent on the wire. */
279 isc_result_t
omapi_handle_td_lookup (omapi_object_t
**obj
,
280 omapi_typed_data_t
*handle
)
284 if (handle
-> type
== omapi_datatype_int
)
285 h
= handle
-> u
.integer
;
286 else if (handle
-> type
== omapi_datatype_data
&&
287 handle
-> u
.buffer
.len
== sizeof h
) {
288 memcpy (&h
, handle
-> u
.buffer
.value
, sizeof h
);
291 return ISC_R_INVALIDARG
;
292 return omapi_handle_lookup (obj
, h
);