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