dbwrap: Add a comment explaining a restriction
[kai/samba-autobuild/.git] / lib / dbwrap / dbwrap_rbt.c
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 "dbwrap/dbwrap.h"
22 #include "dbwrap/dbwrap_private.h"
23 #include "dbwrap/dbwrap_rbt.h"
24 #include "../lib/util/rbtree.h"
25
26 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
27
28 struct db_rbt_ctx {
29         struct rb_root tree;
30 };
31
32 struct db_rbt_rec {
33         struct db_rbt_node *node;
34 };
35
36 /* The structure that ends up in the tree */
37
38 struct db_rbt_node {
39         struct rb_node rb_node;
40         size_t keysize, valuesize;
41
42         /*
43          * key and value are appended implicitly, "data" is only here as a
44          * target for offsetof()
45          */
46
47         char data[1];
48 };
49
50 /*
51  * Hide the ugly pointer calculations in a function
52  */
53
54 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
55 {
56         return (struct db_rbt_node *)
57                 ((char *)node - offsetof(struct db_rbt_node, rb_node));
58 }
59
60 /*
61  * Compare two keys
62  */
63
64 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
65 {
66         int res;
67
68         res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
69
70         if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
71                 return -1;
72         }
73         if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
74                 return 1;
75         }
76         return 0;
77 }
78
79 /*
80  * dissect a db_rbt_node into its implicit key and value parts
81  */
82
83 static void db_rbt_parse_node(struct db_rbt_node *node,
84                               TDB_DATA *key, TDB_DATA *value)
85 {
86         key->dptr = ((uint8_t *)node) + offsetof(struct db_rbt_node, data);
87         key->dsize = node->keysize;
88         value->dptr = key->dptr + node->keysize;
89         value->dsize = node->valuesize;
90 }
91
92 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
93 {
94         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
95                 rec->db->private_data, struct db_rbt_ctx);
96         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
97         struct db_rbt_node *node;
98
99         struct rb_node ** p;
100         struct rb_node * parent;
101
102         TDB_DATA this_key, this_val;
103
104         if (rec_priv->node != NULL) {
105
106                 /*
107                  * The record was around previously
108                  */
109
110                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
111
112                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
113                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
114                                   this_key.dsize) == 0);
115
116                 if (this_val.dsize >= data.dsize) {
117                         /*
118                          * The new value fits into the old space
119                          */
120                         memcpy(this_val.dptr, data.dptr, data.dsize);
121                         rec_priv->node->valuesize = data.dsize;
122                         return NT_STATUS_OK;
123                 }
124         }
125
126         node = (struct db_rbt_node *)talloc_size(db_ctx,
127                 offsetof(struct db_rbt_node, data) + rec->key.dsize
128                 + data.dsize);
129
130         if (node == NULL) {
131                 return NT_STATUS_NO_MEMORY;
132         }
133
134         if (rec_priv->node != NULL) {
135                 /*
136                  * We need to delete the key from the tree and start fresh,
137                  * there's not enough space in the existing record
138                  */
139
140                 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
141
142                 /*
143                  * Keep the existing node around for a while: If the record
144                  * existed before, we reference the key data in there.
145                  */
146         }
147
148         ZERO_STRUCT(node->rb_node);
149
150         node->keysize = rec->key.dsize;
151         node->valuesize = data.dsize;
152
153         db_rbt_parse_node(node, &this_key, &this_val);
154
155         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
156         TALLOC_FREE(rec_priv->node);
157         rec_priv->node = node;
158
159         memcpy(this_val.dptr, data.dptr, node->valuesize);
160
161         parent = NULL;
162         p = &db_ctx->tree.rb_node;
163
164         while (*p) {
165                 struct db_rbt_node *r;
166                 TDB_DATA search_key, search_val;
167                 int res;
168
169                 parent = (*p);
170
171                 r = db_rbt2node(*p);
172
173                 db_rbt_parse_node(r, &search_key, &search_val);
174
175                 res = db_rbt_compare(this_key, search_key);
176
177                 if (res == -1) {
178                         p = &(*p)->rb_left;
179                 }
180                 else if (res == 1) {
181                         p = &(*p)->rb_right;
182                 }
183                 else {
184                         smb_panic("someone messed with the tree");
185                 }
186         }
187
188         rb_link_node(&node->rb_node, parent, p);
189         rb_insert_color(&node->rb_node, &db_ctx->tree);
190
191         return NT_STATUS_OK;
192 }
193
194 static NTSTATUS db_rbt_delete(struct db_record *rec)
195 {
196         struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
197                 rec->db->private_data, struct db_rbt_ctx);
198         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
199
200         if (rec_priv->node == NULL) {
201                 return NT_STATUS_OK;
202         }
203
204         rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
205         TALLOC_FREE(rec_priv->node);
206
207         return NT_STATUS_OK;
208 }
209
210 static NTSTATUS db_rbt_store_deny(struct db_record *rec, TDB_DATA data, int flag)
211 {
212         return NT_STATUS_MEDIA_WRITE_PROTECTED;
213 }
214
215 static NTSTATUS db_rbt_delete_deny(struct db_record *rec)
216 {
217         return NT_STATUS_MEDIA_WRITE_PROTECTED;
218 }
219
220 struct db_rbt_search_result {
221         TDB_DATA key;
222         TDB_DATA val;
223         struct db_rbt_node* node;
224 };
225
226 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
227                                    struct db_rbt_search_result *result)
228 {
229         struct db_rbt_ctx *ctx = talloc_get_type_abort(
230                 db->private_data, struct db_rbt_ctx);
231
232         struct rb_node *n;
233         bool found = false;
234         struct db_rbt_node *r = NULL;
235         TDB_DATA search_key, search_val;
236
237         n = ctx->tree.rb_node;
238
239         while (n != NULL) {
240                 int res;
241
242                 r = db_rbt2node(n);
243
244                 db_rbt_parse_node(r, &search_key, &search_val);
245
246                 res = db_rbt_compare(key, search_key);
247
248                 if (res == -1) {
249                         n = n->rb_left;
250                 }
251                 else if (res == 1) {
252                         n = n->rb_right;
253                 }
254                 else {
255                         found = true;
256                         break;
257                 }
258         }
259         if (result != NULL) {
260                 if (found) {
261                         result->key = search_key;
262                         result->val = search_val;
263                         result->node = r;
264                 } else {
265                         ZERO_STRUCT(*result);
266                 }
267         }
268         return found;
269 }
270
271 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
272                                              TALLOC_CTX *mem_ctx,
273                                              TDB_DATA key)
274 {
275         struct db_rbt_rec *rec_priv;
276         struct db_record *result;
277         size_t size;
278         bool found;
279         struct db_rbt_search_result res;
280
281         found = db_rbt_search_internal(db_ctx, key, &res);
282
283         /*
284          * In this low-level routine, play tricks to reduce the number of
285          * tallocs to one. Not recommened for general use, but here it pays
286          * off.
287          */
288
289         size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
290                 + sizeof(struct db_rbt_rec);
291
292         if (!found) {
293                 /*
294                  * We need to keep the key around for later store
295                  */
296                 size += key.dsize;
297         }
298
299         result = (struct db_record *)talloc_size(mem_ctx, size);
300         if (result == NULL) {
301                 return NULL;
302         }
303
304         rec_priv = (struct db_rbt_rec *)
305                 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
306
307         result->store = db_rbt_store;
308         result->delete_rec = db_rbt_delete;
309         result->private_data = rec_priv;
310
311         rec_priv->node = res.node;
312         result->value  = res.val;
313
314         if (found) {
315                 result->key = res.key;
316         }
317         else {
318                 result->key.dptr = (uint8_t *)
319                         ((char *)rec_priv + sizeof(*rec_priv));
320                 result->key.dsize = key.dsize;
321                 memcpy(result->key.dptr, key.dptr, key.dsize);
322         }
323
324         return result;
325 }
326
327 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
328 {
329         return db_rbt_search_internal(db, key, NULL);
330 }
331
332 static int db_rbt_wipe(struct db_context *db)
333 {
334         struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
335                 db->private_data, struct db_rbt_ctx);
336         struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
337         if (new_ctx == NULL) {
338                 return -1;
339         }
340         db->private_data = new_ctx;
341         talloc_free(old_ctx);
342         return 0;
343 }
344
345 static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
346                                     void (*parser)(TDB_DATA key, TDB_DATA data,
347                                                    void *private_data),
348                                     void *private_data)
349 {
350         struct db_rbt_search_result res;
351         bool found = db_rbt_search_internal(db, key, &res);
352
353         if (!found) {
354                 return NT_STATUS_NOT_FOUND;
355         }
356         parser(res.key, res.val, private_data);
357         return NT_STATUS_OK;
358 }
359
360 static int db_rbt_traverse_internal(struct db_context *db,
361                                     struct rb_node *n,
362                                     int (*f)(struct db_record *db,
363                                              void *private_data),
364                                     void *private_data, uint32_t* count,
365                                     bool rw)
366 {
367         struct rb_node *rb_right;
368         struct rb_node *rb_left;
369         struct db_record rec;
370         struct db_rbt_rec rec_priv;
371         int ret;
372
373         if (n == NULL) {
374                 return 0;
375         }
376
377         rb_left = n->rb_left;
378         rb_right = n->rb_right;
379
380         ret = db_rbt_traverse_internal(db, rb_left, f, private_data, count, rw);
381         if (ret != 0) {
382                 return ret;
383         }
384
385         rec_priv.node = db_rbt2node(n);
386         /* n might be altered by the callback function */
387         n = NULL;
388
389         ZERO_STRUCT(rec);
390         rec.db = db;
391         rec.private_data = &rec_priv;
392         if (rw) {
393                 rec.store = db_rbt_store;
394                 rec.delete_rec = db_rbt_delete;
395         } else {
396                 rec.store = db_rbt_store_deny;
397                 rec.delete_rec = db_rbt_delete_deny;
398         }
399         db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
400
401         ret = f(&rec, private_data);
402         (*count) ++;
403         if (ret != 0) {
404                 return ret;
405         }
406
407         if (rec_priv.node != NULL) {
408                 /*
409                  * If the current record is still there
410                  * we should take the current rb_right.
411                  */
412                 rb_right = rec_priv.node->rb_node.rb_right;
413         }
414
415         return db_rbt_traverse_internal(db, rb_right, f, private_data, count, rw);
416 }
417
418 static int db_rbt_traverse(struct db_context *db,
419                            int (*f)(struct db_record *db,
420                                     void *private_data),
421                            void *private_data)
422 {
423         struct db_rbt_ctx *ctx = talloc_get_type_abort(
424                 db->private_data, struct db_rbt_ctx);
425         uint32_t count = 0;
426
427         int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
428                                            f, private_data, &count,
429                                            true /* rw */);
430         if (ret != 0) {
431                 return -1;
432         }
433         if (count > INT_MAX) {
434                 return -1;
435         }
436         return count;
437 }
438
439 static int db_rbt_traverse_read(struct db_context *db,
440                                 int (*f)(struct db_record *db,
441                                          void *private_data),
442                                 void *private_data)
443 {
444         struct db_rbt_ctx *ctx = talloc_get_type_abort(
445                 db->private_data, struct db_rbt_ctx);
446         uint32_t count = 0;
447
448         int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
449                                            f, private_data, &count,
450                                            false /* rw */);
451         if (ret != 0) {
452                 return -1;
453         }
454         if (count > INT_MAX) {
455                 return -1;
456         }
457         return count;
458 }
459
460 static int db_rbt_get_seqnum(struct db_context *db)
461 {
462         return 0;
463 }
464
465 static int db_rbt_trans_dummy(struct db_context *db)
466 {
467         /*
468          * Transactions are pretty pointless in-memory, just return success.
469          */
470         return 0;
471 }
472
473 static void db_rbt_id(struct db_context *db, const uint8_t **id, size_t *idlen)
474 {
475         *id = (uint8_t *)db;
476         *idlen = sizeof(struct db_context *);
477 }
478
479 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
480 {
481         struct db_context *result;
482
483         result = talloc_zero(mem_ctx, struct db_context);
484
485         if (result == NULL) {
486                 return NULL;
487         }
488
489         result->private_data = talloc_zero(result, struct db_rbt_ctx);
490
491         if (result->private_data == NULL) {
492                 TALLOC_FREE(result);
493                 return NULL;
494         }
495
496         result->fetch_locked = db_rbt_fetch_locked;
497         result->traverse = db_rbt_traverse;
498         result->traverse_read = db_rbt_traverse_read;
499         result->get_seqnum = db_rbt_get_seqnum;
500         result->transaction_start = db_rbt_trans_dummy;
501         result->transaction_commit = db_rbt_trans_dummy;
502         result->transaction_cancel = db_rbt_trans_dummy;
503         result->exists = db_rbt_exists;
504         result->wipe = db_rbt_wipe;
505         result->parse_record = db_rbt_parse_record;
506         result->id = db_rbt_id;
507         result->name = "dbwrap rbt";
508
509         return result;
510 }