Logo Search packages:      
Sourcecode: likewise-open version File versions  Download package

dbwrap_rbt.c

/*
   Unix SMB/CIFS implementation.
   Database interface wrapper around red-black trees
   Copyright (C) Volker Lendecke 2007, 2008

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "includes.h"
#include "rbtree.h"

#define ALIGN(_size_) (((_size_)+15)&~15)

struct db_rbt_ctx {
      struct rb_root tree;
};

struct db_rbt_rec {
      struct db_rbt_ctx *db_ctx;
      struct db_rbt_node *node;
};

/* The structure that ends up in the tree */

struct db_rbt_node {
      struct rb_node rb_node;
      size_t keysize, valuesize;

      /*
       * key and value are appended implicitly, "data" is only here as a
       * target for offsetof()
       */

      char *data;
};

/*
 * Hide the ugly pointer calculations in a function
 */

static struct db_rbt_node *db_rbt2node(struct rb_node *node)
{
      return (struct db_rbt_node *)
            ((char *)node - offsetof(struct db_rbt_node, rb_node));
}

/*
 * Compare two keys
 */

static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
{
      int res;

      res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));

      if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
            return -1;
      }
      if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
            return 1;
      }
      return 0;
}

/*
 * dissect a db_rbt_node into its implicit key and value parts
 */

static void db_rbt_parse_node(struct db_rbt_node *node,
                        TDB_DATA *key, TDB_DATA *value)
{
      key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
      key->dsize = node->keysize;
      value->dptr = key->dptr + node->keysize;
      value->dsize = node->valuesize;
}

static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
{
      struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
      struct db_rbt_node *node;

      struct rb_node ** p;
      struct rb_node * parent;

      TDB_DATA this_key, this_val;

      if (rec_priv->node != NULL) {

            /*
             * The record was around previously
             */

            db_rbt_parse_node(rec_priv->node, &this_key, &this_val);

            SMB_ASSERT(this_key.dsize == rec->key.dsize);
            SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
                          this_key.dsize) == 0);

            if (this_val.dsize >= data.dsize) {
                  /*
                   * The new value fits into the old space
                   */
                  memcpy(this_val.dptr, data.dptr, data.dsize);
                  rec_priv->node->valuesize = data.dsize;
                  return NT_STATUS_OK;
            }

            /*
             * We need to delete the key from the tree and start fresh,
             * there's not enough space in the existing record
             */

            rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);

            /*
             * Keep the existing node around for a while: If the record
             * existed before, we reference the key data in there.
             */
      }

      node = (struct db_rbt_node *)SMB_MALLOC(
            offsetof(struct db_rbt_node, data) + rec->key.dsize
            + data.dsize);

      if (node == NULL) {
            SAFE_FREE(rec_priv->node);
            return NT_STATUS_NO_MEMORY;
      }

      ZERO_STRUCT(node->rb_node);

      node->keysize = rec->key.dsize;
      node->valuesize = data.dsize;

      db_rbt_parse_node(node, &this_key, &this_val);

      memcpy(this_key.dptr, rec->key.dptr, node->keysize);
      SAFE_FREE(rec_priv->node);

      memcpy(this_val.dptr, data.dptr, node->valuesize);

      parent = NULL;
      p = &rec_priv->db_ctx->tree.rb_node;

      while (*p) {
            struct db_rbt_node *r;
            TDB_DATA search_key, search_val;
            int res;

            parent = (*p);

            r = db_rbt2node(*p);

            db_rbt_parse_node(r, &search_key, &search_val);

            res = db_rbt_compare(this_key, search_key);

            if (res == -1) {
                  p = &(*p)->rb_left;
            }
            else if (res == 1) {
                  p = &(*p)->rb_right;
            }
            else {
                  smb_panic("someone messed with the tree");
            }
      }

      rb_link_node(&node->rb_node, parent, p);
      rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);

      return NT_STATUS_OK;
}

static NTSTATUS db_rbt_delete(struct db_record *rec)
{
      struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;

      if (rec_priv->node == NULL) {
            return NT_STATUS_OK;
      }

      rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
      SAFE_FREE(rec_priv->node);

      return NT_STATUS_OK;
}

static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
                                   TALLOC_CTX *mem_ctx,
                                   TDB_DATA key)
{
      struct db_rbt_ctx *ctx = talloc_get_type_abort(
            db_ctx->private_data, struct db_rbt_ctx);

      struct db_rbt_rec *rec_priv;
      struct db_record *result;
      struct rb_node *n;
      size_t size;
      bool found = false;
      struct db_rbt_node *r = NULL;
      TDB_DATA search_key = tdb_null, search_val = tdb_null;

      n = ctx->tree.rb_node;

      while (n != NULL) {
            int res;

            r = db_rbt2node(n);

            db_rbt_parse_node(r, &search_key, &search_val);

            res = db_rbt_compare(key, search_key);

            if (res == -1) {
                  n = n->rb_left;
            }
            else if (res == 1) {
                  n = n->rb_right;
            }
            else {
                  found = true;
                  break;
            }
      }

      /*
       * In this low-level routine, play tricks to reduce the number of
       * tallocs to one. Not recommened for general use, but here it pays
       * off.
       */

      size = ALIGN(sizeof(struct db_record)) + sizeof(struct db_rbt_rec);

      if (!found) {
            /*
             * We need to keep the key around for later store
             */
            size += key.dsize;
      }

      result = (struct db_record *)talloc_size(mem_ctx, size);
      if (result == NULL) {
            return NULL;
      }

      rec_priv = (struct db_rbt_rec *)
            ((char *)result + ALIGN(sizeof(struct db_record)));
      rec_priv->db_ctx = ctx;

      result->store = db_rbt_store;
      result->delete_rec = db_rbt_delete;
      result->private_data = rec_priv;

      if (found) {
            rec_priv->node = r;
            result->key = search_key;
            result->value = search_val;
      }
      else {
            rec_priv->node = NULL;
            result->key.dptr = (uint8 *)
                  ((char *)rec_priv + sizeof(*rec_priv));
            result->key.dsize = key.dsize;
            memcpy(result->key.dptr, key.dptr, key.dsize);

            result->value = tdb_null;
      }

      return result;
}

static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
                  TDB_DATA key, TDB_DATA *data)
{
      struct db_rbt_ctx *ctx = talloc_get_type_abort(
            db->private_data, struct db_rbt_ctx);

      struct rb_node *n;
      bool found = false;
      struct db_rbt_node *r = NULL;
      TDB_DATA search_key, search_val;
      uint8_t *result;

      n = ctx->tree.rb_node;

      while (n != NULL) {
            int res;

            r = db_rbt2node(n);

            db_rbt_parse_node(r, &search_key, &search_val);

            res = db_rbt_compare(key, search_key);

            if (res == -1) {
                  n = n->rb_left;
            }
            else if (res == 1) {
                  n = n->rb_right;
            }
            else {
                  found = true;
                  break;
            }
      }

      if (!found) {
            *data = tdb_null;
            return 0;
      }

      result = (uint8 *)talloc_memdup(mem_ctx, search_val.dptr,
                              search_val.dsize);
      if (result == NULL) {
            return -1;
      }

      data->dptr = result;
      data->dsize = search_val.dsize;
      return 0;
}


static int db_rbt_traverse(struct db_context *db,
                     int (*f)(struct db_record *db,
                            void *private_data),
                     void *private_data)
{
      /*
       * Nobody uses this so far, and unused code is broken code :-)
       */
      return -1;
}

static int db_rbt_get_seqnum(struct db_context *db)
{
      return 0;
}

struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
{
      struct db_context *result;

      result = talloc(mem_ctx, struct db_context);

      if (result == NULL) {
            return NULL;
      }

      result->private_data = TALLOC_ZERO_P(result, struct db_rbt_ctx);

      if (result->private_data == NULL) {
            TALLOC_FREE(result);
            return NULL;
      }

      result->fetch_locked = db_rbt_fetch_locked;
      result->fetch = db_rbt_fetch;
      result->traverse = db_rbt_traverse;
      result->traverse_read = db_rbt_traverse;
      result->get_seqnum = db_rbt_get_seqnum;

      return result;
}

Generated by  Doxygen 1.6.0   Back to index