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