source: vendor/3.5.0/source3/lib/dbwrap_rbt.c

Last change on this file was 414, checked in by Herwig Bauernfeind, 15 years ago

Samba 3.5.0: Initial import
File size: 8.7 KB
Line 
1/*
2 Unix SMB/CIFS implementation.
3 Database interface wrapper around red-black trees
4 Copyright (C) Volker Lendecke 2007, 2008
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#include "includes.h"
21#include "../lib/util/rbtree.h"
22
23#define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
24
25struct db_rbt_ctx {
26 struct rb_root tree;
27};
28
29struct db_rbt_rec {
30 struct db_rbt_ctx *db_ctx;
31 struct db_rbt_node *node;
32};
33
34/* The structure that ends up in the tree */
35
36struct db_rbt_node {
37 struct rb_node rb_node;
38 size_t keysize, valuesize;
39
40 /*
41 * key and value are appended implicitly, "data" is only here as a
42 * target for offsetof()
43 */
44
45 char data[1];
46};
47
48/*
49 * Hide the ugly pointer calculations in a function
50 */
51
52static struct db_rbt_node *db_rbt2node(struct rb_node *node)
53{
54 return (struct db_rbt_node *)
55 ((char *)node - offsetof(struct db_rbt_node, rb_node));
56}
57
58/*
59 * Compare two keys
60 */
61
62static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
63{
64 int res;
65
66 res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
67
68 if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
69 return -1;
70 }
71 if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
72 return 1;
73 }
74 return 0;
75}
76
77/*
78 * dissect a db_rbt_node into its implicit key and value parts
79 */
80
81static void db_rbt_parse_node(struct db_rbt_node *node,
82 TDB_DATA *key, TDB_DATA *value)
83{
84 key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
85 key->dsize = node->keysize;
86 value->dptr = key->dptr + node->keysize;
87 value->dsize = node->valuesize;
88}
89
90static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
91{
92 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
93 struct db_rbt_node *node;
94
95 struct rb_node ** p;
96 struct rb_node * parent;
97
98 TDB_DATA this_key, this_val;
99
100 if (rec_priv->node != NULL) {
101
102 /*
103 * The record was around previously
104 */
105
106 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
107
108 SMB_ASSERT(this_key.dsize == rec->key.dsize);
109 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
110 this_key.dsize) == 0);
111
112 if (this_val.dsize >= data.dsize) {
113 /*
114 * The new value fits into the old space
115 */
116 memcpy(this_val.dptr, data.dptr, data.dsize);
117 rec_priv->node->valuesize = data.dsize;
118 return NT_STATUS_OK;
119 }
120
121 /*
122 * We need to delete the key from the tree and start fresh,
123 * there's not enough space in the existing record
124 */
125
126 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
127
128 /*
129 * Keep the existing node around for a while: If the record
130 * existed before, we reference the key data in there.
131 */
132 }
133
134 node = (struct db_rbt_node *)talloc_size(rec_priv->db_ctx,
135 offsetof(struct db_rbt_node, data) + rec->key.dsize
136 + data.dsize);
137
138 if (node == NULL) {
139 TALLOC_FREE(rec_priv->node);
140 return NT_STATUS_NO_MEMORY;
141 }
142
143 ZERO_STRUCT(node->rb_node);
144
145 node->keysize = rec->key.dsize;
146 node->valuesize = data.dsize;
147
148 db_rbt_parse_node(node, &this_key, &this_val);
149
150 memcpy(this_key.dptr, rec->key.dptr, node->keysize);
151 TALLOC_FREE(rec_priv->node);
152
153 memcpy(this_val.dptr, data.dptr, node->valuesize);
154
155 parent = NULL;
156 p = &rec_priv->db_ctx->tree.rb_node;
157
158 while (*p) {
159 struct db_rbt_node *r;
160 TDB_DATA search_key, search_val;
161 int res;
162
163 parent = (*p);
164
165 r = db_rbt2node(*p);
166
167 db_rbt_parse_node(r, &search_key, &search_val);
168
169 res = db_rbt_compare(this_key, search_key);
170
171 if (res == -1) {
172 p = &(*p)->rb_left;
173 }
174 else if (res == 1) {
175 p = &(*p)->rb_right;
176 }
177 else {
178 smb_panic("someone messed with the tree");
179 }
180 }
181
182 rb_link_node(&node->rb_node, parent, p);
183 rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
184
185 return NT_STATUS_OK;
186}
187
188static NTSTATUS db_rbt_delete(struct db_record *rec)
189{
190 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
191
192 if (rec_priv->node == NULL) {
193 return NT_STATUS_OK;
194 }
195
196 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
197 TALLOC_FREE(rec_priv->node);
198
199 return NT_STATUS_OK;
200}
201
202static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
203 TALLOC_CTX *mem_ctx,
204 TDB_DATA key)
205{
206 struct db_rbt_ctx *ctx = talloc_get_type_abort(
207 db_ctx->private_data, struct db_rbt_ctx);
208
209 struct db_rbt_rec *rec_priv;
210 struct db_record *result;
211 struct rb_node *n;
212 size_t size;
213 bool found = false;
214 struct db_rbt_node *r = NULL;
215 TDB_DATA search_key = tdb_null, search_val = tdb_null;
216
217 n = ctx->tree.rb_node;
218
219 while (n != NULL) {
220 int res;
221
222 r = db_rbt2node(n);
223
224 db_rbt_parse_node(r, &search_key, &search_val);
225
226 res = db_rbt_compare(key, search_key);
227
228 if (res == -1) {
229 n = n->rb_left;
230 }
231 else if (res == 1) {
232 n = n->rb_right;
233 }
234 else {
235 found = true;
236 break;
237 }
238 }
239
240 /*
241 * In this low-level routine, play tricks to reduce the number of
242 * tallocs to one. Not recommened for general use, but here it pays
243 * off.
244 */
245
246 size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
247 + sizeof(struct db_rbt_rec);
248
249 if (!found) {
250 /*
251 * We need to keep the key around for later store
252 */
253 size += key.dsize;
254 }
255
256 result = (struct db_record *)talloc_size(mem_ctx, size);
257 if (result == NULL) {
258 return NULL;
259 }
260
261 rec_priv = (struct db_rbt_rec *)
262 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
263 rec_priv->db_ctx = ctx;
264
265 result->store = db_rbt_store;
266 result->delete_rec = db_rbt_delete;
267 result->private_data = rec_priv;
268
269 if (found) {
270 rec_priv->node = r;
271 result->key = search_key;
272 result->value = search_val;
273 }
274 else {
275 rec_priv->node = NULL;
276 result->key.dptr = (uint8 *)
277 ((char *)rec_priv + sizeof(*rec_priv));
278 result->key.dsize = key.dsize;
279 memcpy(result->key.dptr, key.dptr, key.dsize);
280
281 result->value = tdb_null;
282 }
283
284 return result;
285}
286
287static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
288 TDB_DATA key, TDB_DATA *data)
289{
290 struct db_rbt_ctx *ctx = talloc_get_type_abort(
291 db->private_data, struct db_rbt_ctx);
292
293 struct rb_node *n;
294 bool found = false;
295 struct db_rbt_node *r = NULL;
296 TDB_DATA search_key, search_val;
297 uint8_t *result;
298
299 n = ctx->tree.rb_node;
300
301 while (n != NULL) {
302 int res;
303
304 r = db_rbt2node(n);
305
306 db_rbt_parse_node(r, &search_key, &search_val);
307
308 res = db_rbt_compare(key, search_key);
309
310 if (res == -1) {
311 n = n->rb_left;
312 }
313 else if (res == 1) {
314 n = n->rb_right;
315 }
316 else {
317 found = true;
318 break;
319 }
320 }
321
322 if (!found) {
323 *data = tdb_null;
324 return 0;
325 }
326
327 result = (uint8 *)talloc_memdup(mem_ctx, search_val.dptr,
328 search_val.dsize);
329 if (result == NULL) {
330 return -1;
331 }
332
333 data->dptr = result;
334 data->dsize = search_val.dsize;
335 return 0;
336}
337
338static int db_rbt_traverse_internal(struct rb_node *n,
339 int (*f)(struct db_record *db,
340 void *private_data),
341 void *private_data)
342{
343 struct db_rbt_node *r;
344 struct db_record rec;
345 int ret;
346
347 if (n == NULL) {
348 return 0;
349 }
350
351 ret = db_rbt_traverse_internal(n->rb_left, f, private_data);
352 if (ret != 0) {
353 return ret;
354 }
355
356 r = db_rbt2node(n);
357 ZERO_STRUCT(rec);
358 db_rbt_parse_node(r, &rec.key, &rec.value);
359
360 ret = f(&rec, private_data);
361 if (ret != 0) {
362 return ret;
363 }
364
365 return db_rbt_traverse_internal(n->rb_right, f, private_data);
366}
367
368static int db_rbt_traverse(struct db_context *db,
369 int (*f)(struct db_record *db,
370 void *private_data),
371 void *private_data)
372{
373 struct db_rbt_ctx *ctx = talloc_get_type_abort(
374 db->private_data, struct db_rbt_ctx);
375
376 return db_rbt_traverse_internal(ctx->tree.rb_node, f, private_data);
377}
378
379static int db_rbt_get_seqnum(struct db_context *db)
380{
381 return 0;
382}
383
384static int db_rbt_trans_dummy(struct db_context *db)
385{
386 /*
387 * Transactions are pretty pointless in-memory, just return success.
388 */
389 return 0;
390}
391
392struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
393{
394 struct db_context *result;
395
396 result = talloc(mem_ctx, struct db_context);
397
398 if (result == NULL) {
399 return NULL;
400 }
401
402 result->private_data = TALLOC_ZERO_P(result, struct db_rbt_ctx);
403
404 if (result->private_data == NULL) {
405 TALLOC_FREE(result);
406 return NULL;
407 }
408
409 result->fetch_locked = db_rbt_fetch_locked;
410 result->fetch = db_rbt_fetch;
411 result->traverse = db_rbt_traverse;
412 result->traverse_read = db_rbt_traverse;
413 result->get_seqnum = db_rbt_get_seqnum;
414 result->transaction_start = db_rbt_trans_dummy;
415 result->transaction_commit = db_rbt_trans_dummy;
416 result->transaction_cancel = db_rbt_trans_dummy;
417
418 return result;
419}
Note: See TracBrowser for help on using the repository browser.