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