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 25struct db_rbt_ctx { 26 struct rb_root tree; 27}; 28 29struct 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 36struct 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 52static 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 62static 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 81static 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 90static 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 188static 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 202static 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 287static 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 338static 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 368static 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 379static int db_rbt_get_seqnum(struct db_context *db) 380{ 381 return 0; 382} 383 384static 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 392struct 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} 420