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