source3/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_rbt.h"
  23 #include "../lib/util/rbtree.h"
  24
  25 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
  26
  27 struct db_rbt_ctx {
  28         struct rb_root tree;
  29 };
  30
  31 struct db_rbt_rec {
  32         struct db_rbt_ctx *db_ctx;
  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 *)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_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
  95         struct db_rbt_node *node;
  96
  97         struct rb_node ** p;
  98         struct rb_node * parent;
  99
 100         TDB_DATA this_key, this_val;
 101
 102         if (rec_priv->node != NULL) {
 103
 104                 /*
 105                  * The record was around previously
 106                  */
 107
 108                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
 109
 110                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
 111                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
 112                                   this_key.dsize) == 0);
 113
 114                 if (this_val.dsize >= data.dsize) {
 115                         /*
 116                          * The new value fits into the old space
 117                          */
 118                         memcpy(this_val.dptr, data.dptr, data.dsize);
 119                         rec_priv->node->valuesize = data.dsize;
 120                         return NT_STATUS_OK;
 121                 }
 122
 123                 /*
 124                  * We need to delete the key from the tree and start fresh,
 125                  * there's not enough space in the existing record
 126                  */
 127
 128                 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
 129
 130                 /*
 131                  * Keep the existing node around for a while: If the record
 132                  * existed before, we reference the key data in there.
 133                  */
 134         }
 135
 136         node = (struct db_rbt_node *)talloc_size(rec_priv->db_ctx,
 137                 offsetof(struct db_rbt_node, data) + rec->key.dsize
 138                 + data.dsize);
 139
 140         if (node == NULL) {
 141                 TALLOC_FREE(rec_priv->node);
 142                 return NT_STATUS_NO_MEMORY;
 143         }
 144
 145         ZERO_STRUCT(node->rb_node);
 146
 147         node->keysize = rec->key.dsize;
 148         node->valuesize = data.dsize;
 149
 150         db_rbt_parse_node(node, &this_key, &this_val);
 151
 152         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
 153         TALLOC_FREE(rec_priv->node);
 154
 155         memcpy(this_val.dptr, data.dptr, node->valuesize);
 156
 157         parent = NULL;
 158         p = &rec_priv->db_ctx->tree.rb_node;
 159
 160         while (*p) {
 161                 struct db_rbt_node *r;
 162                 TDB_DATA search_key, search_val;
 163                 int res;
 164
 165                 parent = (*p);
 166
 167                 r = db_rbt2node(*p);
 168
 169                 db_rbt_parse_node(r, &search_key, &search_val);
 170
 171                 res = db_rbt_compare(this_key, search_key);
 172
 173                 if (res == -1) {
 174                         p = &(*p)->rb_left;
 175                 }
 176                 else if (res == 1) {
 177                         p = &(*p)->rb_right;
 178                 }
 179                 else {
 180                         smb_panic("someone messed with the tree");
 181                 }
 182         }
 183
 184         rb_link_node(&node->rb_node, parent, p);
 185         rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
 186
 187         return NT_STATUS_OK;
 188 }
 189
 190 static NTSTATUS db_rbt_delete(struct db_record *rec)
 191 {
 192         struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 193
 194         if (rec_priv->node == NULL) {
 195                 return NT_STATUS_OK;
 196         }
 197
 198         rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
 199         TALLOC_FREE(rec_priv->node);
 200
 201         return NT_STATUS_OK;
 202 }
 203 struct db_rbt_search_result {
 204         TDB_DATA key;
 205         TDB_DATA val;
 206         struct db_rbt_node* node;
 207 };
 208
 209 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
 210                                    struct db_rbt_search_result *result)
 211 {
 212         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 213                 db->private_data, struct db_rbt_ctx);
 214
 215         struct rb_node *n;
 216         bool found = false;
 217         struct db_rbt_node *r = NULL;
 218         TDB_DATA search_key, search_val;
 219
 220         n = ctx->tree.rb_node;
 221
 222         while (n != NULL) {
 223                 int res;
 224
 225                 r = db_rbt2node(n);
 226
 227                 db_rbt_parse_node(r, &search_key, &search_val);
 228
 229                 res = db_rbt_compare(key, search_key);
 230
 231                 if (res == -1) {
 232                         n = n->rb_left;
 233                 }
 234                 else if (res == 1) {
 235                         n = n->rb_right;
 236                 }
 237                 else {
 238                         found = true;
 239                         break;
 240                 }
 241         }
 242         if (result != NULL) {
 243                 if (found) {
 244                         result->key = search_key;
 245                         result->val = search_val;
 246                         result->node = r;
 247                 } else {
 248                         ZERO_STRUCT(*result);
 249                 }
 250         }
 251         return found;
 252 }
 253
 254 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
 255                                              TALLOC_CTX *mem_ctx,
 256                                              TDB_DATA key)
 257 {
 258         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 259                 db_ctx->private_data, struct db_rbt_ctx);
 260
 261         struct db_rbt_rec *rec_priv;
 262         struct db_record *result;
 263         size_t size;
 264         bool found;
 265         struct db_rbt_search_result res;
 266
 267         found = db_rbt_search_internal(db_ctx, key, &res);
 268
 269         /*
 270          * In this low-level routine, play tricks to reduce the number of
 271          * tallocs to one. Not recommened for general use, but here it pays
 272          * off.
 273          */
 274
 275         size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
 276                 + sizeof(struct db_rbt_rec);
 277
 278         if (!found) {
 279                 /*
 280                  * We need to keep the key around for later store
 281                  */
 282                 size += key.dsize;
 283         }
 284
 285         result = (struct db_record *)talloc_size(mem_ctx, size);
 286         if (result == NULL) {
 287                 return NULL;
 288         }
 289
 290         rec_priv = (struct db_rbt_rec *)
 291                 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
 292         rec_priv->db_ctx = ctx;
 293
 294         result->store = db_rbt_store;
 295         result->delete_rec = db_rbt_delete;
 296         result->private_data = rec_priv;
 297
 298         rec_priv->node = res.node;
 299         result->value  = res.val;
 300
 301         if (found) {
 302                 result->key = res.key;
 303         }
 304         else {
 305                 result->key.dptr = (uint8 *)
 306                         ((char *)rec_priv + sizeof(*rec_priv));
 307                 result->key.dsize = key.dsize;
 308                 memcpy(result->key.dptr, key.dptr, key.dsize);
 309         }
 310
 311         return result;
 312 }
 313
 314 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
 315 {
 316         return db_rbt_search_internal(db, key, NULL);
 317 }
 318
 319 static int db_rbt_parse_record(struct db_context *db, TDB_DATA key,
 320                                int (*parser)(TDB_DATA key, TDB_DATA data,
 321                                              void *private_data),
 322                                void *private_data)
 323 {
 324         struct db_rbt_search_result res;
 325         bool found = db_rbt_search_internal(db, key, &res);
 326
 327         if (!found) {
 328                 return -1;
 329         }
 330         return parser(res.key, res.val, private_data);
 331 }
 332
 333 static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
 334                         TDB_DATA key, TDB_DATA *data)
 335 {
 336         uint8_t *result;
 337         struct db_rbt_search_result res;
 338
 339         bool found = db_rbt_search_internal(db, key, &res);
 340
 341         if (!found) {
 342                 *data = tdb_null;
 343                 return 0;
 344         }
 345
 346         result = (uint8_t*)talloc_memdup(mem_ctx, res.val.dptr, res.val.dsize);
 347         if (result == NULL) {
 348                 return -1;
 349         }
 350
 351         data->dptr = result;
 352         data->dsize = res.val.dsize;
 353         return 0;
 354 }
 355
 356 static int db_rbt_traverse_internal(struct rb_node *n,
 357                                     int (*f)(struct db_record *db,
 358                                              void *private_data),
 359                                     void *private_data)
 360 {
 361         struct db_rbt_node *r;
 362         struct db_record rec;
 363         int ret;
 364
 365         if (n == NULL) {
 366                 return 0;
 367         }
 368
 369         ret = db_rbt_traverse_internal(n->rb_left, f, private_data);
 370         if (ret != 0) {
 371                 return ret;
 372         }
 373
 374         r = db_rbt2node(n);
 375         ZERO_STRUCT(rec);
 376         db_rbt_parse_node(r, &rec.key, &rec.value);
 377
 378         ret = f(&rec, private_data);
 379         if (ret != 0) {
 380                 return ret;
 381         }
 382
 383         return db_rbt_traverse_internal(n->rb_right, f, private_data);
 384 }
 385
 386 static int db_rbt_traverse(struct db_context *db,
 387                            int (*f)(struct db_record *db,
 388                                     void *private_data),
 389                            void *private_data)
 390 {
 391         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 392                 db->private_data, struct db_rbt_ctx);
 393
 394         return db_rbt_traverse_internal(ctx->tree.rb_node, f, private_data);
 395 }
 396
 397 static int db_rbt_get_seqnum(struct db_context *db)
 398 {
 399         return 0;
 400 }
 401
 402 static int db_rbt_trans_dummy(struct db_context *db)
 403 {
 404         /*
 405          * Transactions are pretty pointless in-memory, just return success.
 406          */
 407         return 0;
 408 }
 409
 410 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
 411 {
 412         struct db_context *result;
 413
 414         result = talloc(mem_ctx, struct db_context);
 415
 416         if (result == NULL) {
 417                 return NULL;
 418         }
 419
 420         result->private_data = talloc_zero(result, struct db_rbt_ctx);
 421
 422         if (result->private_data == NULL) {
 423                 TALLOC_FREE(result);
 424                 return NULL;
 425         }
 426
 427         result->fetch_locked = db_rbt_fetch_locked;
 428         result->fetch = db_rbt_fetch;
 429         result->traverse = db_rbt_traverse;
 430         result->traverse_read = db_rbt_traverse;
 431         result->get_seqnum = db_rbt_get_seqnum;
 432         result->transaction_start = db_rbt_trans_dummy;
 433         result->transaction_commit = db_rbt_trans_dummy;
 434         result->transaction_cancel = db_rbt_trans_dummy;
 435         result->exists = db_rbt_exists;
 436         result->parse_record = db_rbt_parse_record;
 437
 438         return result;
 439 }