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 "../lib/util/rbtree.h"
  22
  23 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
  24
  25 struct db_rbt_ctx {
  26         struct rb_root tree;
  27 };
  28
  29 struct 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
  36 struct 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
  52 static 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
  62 static 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
  81 static 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
  90 static 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
 188 static 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
 202 static 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
 287 static 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
 338 static 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
 368 static 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
 379 static int db_rbt_get_seqnum(struct db_context *db)
 380 {
 381         return 0;
 382 }
 383
 384 static 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
 392 struct 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 }