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
   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 "rbtree.h"
  22
  23 struct db_rbt_ctx {
  24         struct rb_root tree;
  25 };
  26
  27 struct db_rbt_rec {
  28         struct db_rbt_ctx *db_ctx;
  29         struct db_rbt_node *node;
  30 };
  31
  32 /* The structure that ends up in the tree */
  33
  34 struct db_rbt_node {
  35         struct rb_node rb_node;
  36         size_t keysize, valuesize;
  37
  38         /*
  39          * key and value are appended implicitly, "data" is only here as a
  40          * target for offsetof()
  41          */
  42
  43         char data[];
  44 };
  45
  46 /*
  47  * dissect a db_rbt_node into its implicit key and value parts
  48  */
  49
  50 static void db_rbt_parse_node(struct db_rbt_node *node,
  51                               TDB_DATA *key, TDB_DATA *value)
  52 {
  53         key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
  54         key->dsize = node->keysize;
  55         value->dptr = key->dptr + node->keysize;
  56         value->dsize = node->valuesize;
  57 }
  58
  59 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
  60 {
  61         struct db_rbt_rec *rec_priv = talloc_get_type_abort(
  62                 rec->private_data, struct db_rbt_rec);
  63
  64         struct db_rbt_node *node;
  65
  66         struct rb_node ** p;
  67         struct rb_node * parent;
  68
  69         TDB_DATA this_key, this_val;
  70
  71         if (rec_priv->node != NULL) {
  72
  73                 /*
  74                  * The record was around previously
  75                  */
  76
  77                 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
  78
  79                 SMB_ASSERT(this_key.dsize == rec->key.dsize);
  80                 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
  81                                   this_key.dsize) == 0);
  82
  83                 if (this_val.dsize >= data.dsize) {
  84                         /*
  85                          * The new value fits into the old space
  86                          */
  87                         memcpy(this_val.dptr, data.dptr, data.dsize);
  88                         rec_priv->node->valuesize = data.dsize;
  89                         return NT_STATUS_OK;
  90                 }
  91
  92                 /*
  93                  * We need to delete the key from the tree and start fresh,
  94                  * there's not enough space in the existing record
  95                  */
  96
  97                 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
  98                 SAFE_FREE(rec_priv->node);
  99         }
 100
 101         node = (struct db_rbt_node *)SMB_MALLOC(
 102                 offsetof(struct db_rbt_node, data) + rec->key.dsize
 103                 + data.dsize);
 104
 105         if (node == NULL) {
 106                 return NT_STATUS_NO_MEMORY;
 107         }
 108
 109         ZERO_STRUCT(node->rb_node);
 110
 111         node->keysize = rec->key.dsize;
 112         node->valuesize = data.dsize;
 113
 114         db_rbt_parse_node(node, &this_key, &this_val);
 115
 116         memcpy(this_key.dptr, rec->key.dptr, node->keysize);
 117         memcpy(this_val.dptr, data.dptr, node->valuesize);
 118
 119         parent = NULL;
 120         p = &rec_priv->db_ctx->tree.rb_node;
 121
 122         while (*p) {
 123                 struct db_rbt_node *r;
 124                 TDB_DATA search_key, search_val;
 125                 int res;
 126
 127                 parent = (*p);
 128
 129                 r = (struct db_rbt_node *)
 130                         ((char *)(*p) - offsetof(struct db_rbt_node, rb_node));
 131
 132                 db_rbt_parse_node(r, &search_key, &search_val);
 133
 134                 res = memcmp(this_key.dptr, search_key.dptr,
 135                              MIN(this_key.dsize, search_key.dsize));
 136
 137                 if ((res < 0)
 138                     || ((res == 0)
 139                         && (this_key.dsize < search_key.dsize))) {
 140                         p = &(*p)->rb_left;
 141                 }
 142                 else if ((res > 0)
 143                          || ((res == 0)
 144                              && (this_key.dsize > search_key.dsize))) {
 145                         p = &(*p)->rb_right;
 146                 }
 147                 else {
 148                         smb_panic("someone messed with the tree");
 149                 }
 150         }
 151
 152         rb_link_node(&node->rb_node, parent, p);
 153         rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
 154
 155         return NT_STATUS_OK;
 156 }
 157
 158 static NTSTATUS db_rbt_delete(struct db_record *rec)
 159 {
 160         struct db_rbt_rec *rec_priv = talloc_get_type_abort(
 161                 rec->private_data, struct db_rbt_rec);
 162
 163         if (rec_priv->node == NULL) {
 164                 return NT_STATUS_OK;
 165         }
 166
 167         rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
 168         SAFE_FREE(rec_priv->node);
 169
 170         return NT_STATUS_OK;
 171 }
 172
 173 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
 174                                              TALLOC_CTX *mem_ctx,
 175                                              TDB_DATA key)
 176 {
 177         struct db_rbt_ctx *ctx = talloc_get_type_abort(
 178                 db_ctx->private_data, struct db_rbt_ctx);
 179
 180         struct db_rbt_rec *rec_priv;
 181         struct db_record *result;
 182         struct rb_node *n;
 183
 184         result = talloc(mem_ctx, struct db_record);
 185
 186         if (result == NULL) {
 187                 return NULL;
 188         }
 189
 190         rec_priv = talloc(result, struct db_rbt_rec);
 191
 192         if (rec_priv == NULL) {
 193                 TALLOC_FREE(result);
 194                 return NULL;
 195         }
 196
 197         rec_priv->db_ctx = ctx;
 198
 199         result->store = db_rbt_store;
 200         result->delete_rec = db_rbt_delete;
 201         result->private_data = rec_priv;
 202
 203         n = ctx->tree.rb_node;
 204
 205         while (n != NULL) {
 206                 struct db_rbt_node *r;
 207                 TDB_DATA search_key, search_val;
 208                 int res;
 209
 210                 r = (struct db_rbt_node *)
 211                         ((char *)n - offsetof(struct db_rbt_node, rb_node));
 212
 213                 db_rbt_parse_node(r, &search_key, &search_val);
 214
 215                 res = memcmp(key.dptr, search_key.dptr,
 216                              MIN(key.dsize, search_key.dsize));
 217
 218                 if ((res < 0)
 219                     || ((res == 0) && (key.dsize < search_key.dsize))) {
 220                         n = n->rb_left;
 221                 }
 222                 else if ((res > 0)
 223                          || ((res == 0) && (key.dsize > search_key.dsize))) {
 224                         n = n->rb_right;
 225                 }
 226                 else {
 227                         rec_priv->node = r;
 228                         result->key = search_key;
 229                         result->value = search_val;
 230                         return result;
 231                 }
 232         }
 233
 234         result->key.dsize = key.dsize;
 235         result->key.dptr = (uint8_t *)talloc_memdup(
 236                 result, key.dptr, key.dsize);
 237
 238         if (result->key.dptr == NULL) {
 239                 TALLOC_FREE(result);
 240                 return NULL;
 241         }
 242
 243         rec_priv->node = NULL;
 244         result->value.dsize = 0;
 245         result->value.dptr = NULL;
 246         return result;
 247 }
 248
 249 static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
 250                         TDB_DATA key, TDB_DATA *data)
 251 {
 252         struct db_record *rec;
 253
 254         if (!(rec = db->fetch_locked(db, mem_ctx, key))) {
 255                 return -1;
 256         }
 257
 258         data->dsize = rec->value.dsize;
 259         data->dptr = (uint8 *)talloc_memdup(mem_ctx, rec->value.dptr,
 260                                             rec->value.dsize);
 261         TALLOC_FREE(rec);
 262         return 0;
 263 }
 264
 265
 266 static int db_rbt_traverse(struct db_context *db,
 267                            int (*f)(struct db_record *db,
 268                                     void *private_data),
 269                            void *private_data)
 270 {
 271         return -1;
 272 }
 273
 274 static int db_rbt_get_seqnum(struct db_context *db)
 275 {
 276         return 0;
 277 }
 278
 279 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
 280 {
 281         struct db_context *result;
 282
 283         result = talloc(mem_ctx, struct db_context);
 284
 285         if (result == NULL) {
 286                 return NULL;
 287         }
 288
 289         result->private_data = TALLOC_ZERO_P(result, struct db_rbt_ctx);
 290
 291         if (result->private_data == NULL) {
 292                 TALLOC_FREE(result);
 293                 return NULL;
 294         }
 295
 296         result->fetch_locked = db_rbt_fetch_locked;
 297         result->fetch = db_rbt_fetch;
 298         result->traverse = db_rbt_traverse;
 299         result->traverse_read = db_rbt_traverse;
 300         result->get_seqnum = db_rbt_get_seqnum;
 301
 302         return result;
 303 }