ctdb-common: Add db_hash abstraction

A hash table implemented using in-memory tdb backend.

Signed-off-by: Amitay Isaacs <amitay@gmail.com>
Reviewed-by: Martin Schwenke <martin@meltin.net>

2 files changed, 427 insertions, 0 deletions

diff --git a/ctdb/common/db_hash.c b/ctdb/common/db_hash.c
new file mode 100644
index 00000000000..6a23337e516
--- /dev/null
+++ b/ctdb/common/db_hash.c
@@ -0,0 +1,268 @@
+/*
+   Using tdb as a hash table
+
+   Copyright (C) Amitay Isaacs  2015
+
+   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 "replace.h"
+#include "system/filesys.h"
+
+#include <talloc.h>
+#include <tdb.h>
+
+#include "common/db_hash.h"
+
+struct db_hash_context {
+	struct tdb_context *db;
+};
+
+
+static int db_hash_destructor(struct db_hash_context *dh)
+{
+	if (dh->db != NULL) {
+		tdb_close(dh->db);
+		dh->db = NULL;
+	}
+	return 0;
+}
+
+int db_hash_init(TALLOC_CTX *mem_ctx, const char *name, int hash_size,
+		 enum db_hash_type type, struct db_hash_context **result)
+{
+	struct db_hash_context *dh;
+	int tdb_flags = TDB_INTERNAL | TDB_DISALLOW_NESTING;
+
+	dh = talloc_zero(mem_ctx, struct db_hash_context);
+	if (dh == NULL) {
+		return ENOMEM;
+	}
+
+	if (type == DB_HASH_COMPLEX) {
+		tdb_flags |= TDB_INCOMPATIBLE_HASH;
+	}
+
+	dh->db = tdb_open(name, hash_size, tdb_flags, O_RDWR|O_CREAT, 0);
+	if (dh->db == NULL) {
+		talloc_free(dh);
+		return ENOMEM;
+	}
+
+	talloc_set_destructor(dh, db_hash_destructor);
+	*result = dh;
+	return 0;
+}
+
+static int db_hash_map_tdb_error(struct db_hash_context *dh)
+{
+	enum TDB_ERROR tdb_err;
+	int ret;
+
+	tdb_err = tdb_error(dh->db);
+	switch (tdb_err) {
+		case TDB_SUCCESS:
+			ret = 0; break;
+		case TDB_ERR_OOM:
+			ret = ENOMEM; break;
+		case TDB_ERR_EXISTS:
+			ret = EEXIST; break;
+		case TDB_ERR_NOEXIST:
+			ret = ENOENT; break;
+		case TDB_ERR_EINVAL:
+			ret = EINVAL; break;
+		default:
+			ret = EIO; break;
+	}
+	return ret;
+}
+
+int db_hash_insert(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		   uint8_t *databuf, size_t datalen)
+{
+	TDB_DATA key, data;
+	int ret;
+
+	if (dh == NULL) {
+		return EINVAL;
+	}
+
+	key.dptr = keybuf;
+	key.dsize = keylen;
+
+	data.dptr = databuf;
+	data.dsize = datalen;
+
+	ret = tdb_store(dh->db, key, data, TDB_INSERT);
+	if (ret != 0) {
+		ret = db_hash_map_tdb_error(dh);
+	}
+	return ret;
+}
+
+int db_hash_add(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		uint8_t *databuf, size_t datalen)
+{
+	TDB_DATA key, data;
+	int ret;
+
+	if (dh == NULL) {
+		return EINVAL;
+	}
+
+	key.dptr = keybuf;
+	key.dsize = keylen;
+
+	data.dptr = databuf;
+	data.dsize = datalen;
+
+	ret = tdb_store(dh->db, key, data, TDB_REPLACE);
+	if (ret != 0) {
+		ret = db_hash_map_tdb_error(dh);
+	}
+	return ret;
+}
+
+int db_hash_delete(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen)
+{
+	TDB_DATA key;
+	int ret;
+
+	key.dptr = keybuf;
+	key.dsize = keylen;
+
+	if (dh == NULL) {
+		return EINVAL;
+	}
+
+	ret = tdb_delete(dh->db, key);
+	if (ret != 0) {
+		ret = db_hash_map_tdb_error(dh);
+	}
+	return ret;
+}
+
+struct db_hash_fetch_state {
+	db_hash_record_parser_fn parser;
+	void *private_data;
+};
+
+static int db_hash_fetch_parser(TDB_DATA key, TDB_DATA data, void *private_data)
+{
+	struct db_hash_fetch_state *state =
+		(struct db_hash_fetch_state *)private_data;
+	int ret;
+
+	ret = state->parser(key.dptr, key.dsize, data.dptr, data.dsize,
+			    state->private_data);
+	return ret;
+}
+
+int db_hash_fetch(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		  db_hash_record_parser_fn parser, void *private_data)
+{
+	struct db_hash_fetch_state state;
+	TDB_DATA key;
+	int ret;
+
+	if (dh == NULL || parser == NULL) {
+		return EINVAL;
+	}
+
+	state.parser = parser;
+	state.private_data = private_data;
+
+	key.dptr = keybuf;
+	key.dsize = keylen;
+
+	ret = tdb_parse_record(dh->db, key, db_hash_fetch_parser, &state);
+	if (ret == -1) {
+		return ENOENT;
+	}
+	return ret;
+}
+
+int db_hash_exists(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen)
+{
+	TDB_DATA key;
+	int ret;
+
+	if (dh == NULL) {
+		return EINVAL;
+	}
+
+	key.dptr = keybuf;
+	key.dsize = keylen;
+
+	ret = tdb_exists(dh->db, key);
+	if (ret == 1) {
+		/* Key found */
+		ret = 0;
+	} else {
+		ret = db_hash_map_tdb_error(dh);
+		if (ret == 0) {
+			ret = ENOENT;
+		}
+	}
+	return ret;
+}
+
+struct db_hash_traverse_state {
+	db_hash_record_parser_fn parser;
+	void *private_data;
+};
+
+static int db_hash_traverse_parser(struct tdb_context *tdb,
+				   TDB_DATA key, TDB_DATA data,
+				   void *private_data)
+{
+	struct db_hash_traverse_state *state =
+		(struct db_hash_traverse_state *)private_data;
+
+	return state->parser(key.dptr, key.dsize, data.dptr, data.dsize,
+			     state->private_data);
+}
+
+int db_hash_traverse(struct db_hash_context *dh,
+		     db_hash_record_parser_fn parser, void *private_data,
+		     int *count)
+{
+	struct db_hash_traverse_state state;
+	int ret;
+
+	if (dh == NULL) {
+		return EINVAL;
+	}
+
+	/* Special case, for counting records */
+	if (parser == NULL) {
+		ret = tdb_traverse_read(dh->db, NULL, NULL);
+	} else {
+		state.parser = parser;
+		state.private_data = private_data;
+
+		ret = tdb_traverse_read(dh->db, db_hash_traverse_parser, &state);
+	}
+
+	if (ret == -1) {
+		ret = db_hash_map_tdb_error(dh);
+	} else {
+		if (count != NULL) {
+			*count = ret;
+		}
+		ret = 0;
+	}
+
+	return ret;
+}
diff --git a/ctdb/common/db_hash.h b/ctdb/common/db_hash.h
new file mode 100644
index 00000000000..8f0e50bb4cf
--- /dev/null
+++ b/ctdb/common/db_hash.h
@@ -0,0 +1,159 @@
+/*
+   Using tdb as a hash table
+
+   Copyright (C) Amitay Isaacs  2015
+
+   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/>.
+*/
+
+#ifndef __CTDB_DB_HASH_H__
+#define __CTDB_DB_HASH_H__
+
+#include <talloc.h>
+#include <tdb.h>
+
+/**
+ * @file db_hash.h
+ *
+ * @brief Use tdb database as a hash table
+ *
+ * This uses in-memory tdb databases to create a fixed sized hash table.
+ */
+
+/**
+ * @brief Hash type to indicate the hashing function to use.
+ *
+ * DB_HASH_SIMPLE uses default hashing function
+ * DB_HASH_COMPLEX uses jenkins hashing function
+ */
+enum db_hash_type {
+	DB_HASH_SIMPLE,
+	DB_HASH_COMPLEX,
+};
+
+/**
+ * @brief Parser callback function called when fetching a record
+ *
+ * This function is called when fetching a record. This function should
+ * not modify key and data arguments.
+ *
+ * The function should return 0 on success and errno on error.
+ */
+typedef int (*db_hash_record_parser_fn)(uint8_t *keybuf, size_t keylen,
+					uint8_t *databuf, size_t datalen,
+					void *private_data);
+
+/**
+ * @brief Abstract structure representing tdb hash table
+ */
+struct db_hash_context;
+
+/**
+ * @brief Initialize tdb hash table
+ *
+ * This returns a new tdb hash table context which is a talloc context.  Freeing
+ * this context will free all the memory associated with the hash table.
+ *
+ * @param[in] mem_ctx Talloc memory context
+ * @param[in] name The name for the hash table
+ * @param[in] hash_size The size of the hash table
+ * @param[in] type The type of hashing function to use
+ * @param[out] result The new db_hash_context structure
+ * @return 0 on success, errno on failure
+ */
+int db_hash_init(TALLOC_CTX *mem_ctx, const char *name, int hash_size,
+		 enum db_hash_type type, struct db_hash_context **result);
+
+/**
+ * @brief Insert a record into the hash table
+ *
+ * The key and data can be any binary data.  Insert only if the record does not
+ * exist.  If the record already exists, return error.
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] keybuf The key buffer
+ * @param[in] keylen The key length
+ * @param[in] databuf The data buffer
+ * @param[in] datalen The data length
+ * @return 0 on success, errno on failure
+ */
+int db_hash_insert(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		   uint8_t *databuf, size_t datalen);
+
+/**
+ * @brief Add a record into the hash table
+ *
+ * The key and data can be any binary data.  If the record does not exist,
+ * insert the record.  If the record already exists, replace the record.
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] keybuf The key buffer
+ * @param[in] keylen The key length
+ * @param[in] databuf The data buffer
+ * @param[in] datalen The data length
+ * @return 0 on success, errno on failure
+ */
+int db_hash_add(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		uint8_t *databuf, size_t datalen); 
+/**
+ * @brief Delete a record from the hash table
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] keybuf The key buffer
+ * @param[in] keylen The key length
+ * @return 0 on success, errno on failure
+ */
+int db_hash_delete(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen);
+
+/**
+ * @brief Fetch a record from the hash table
+ *
+ * The key and data can be any binary data.
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] keybuf The key buffer
+ * @param[in] keylen The key length
+ * @param[in] parser Function called when the matching record is found
+ * @param[in] private_data Private data to parser function
+ * @return 0 on success, errno on failure
+ */
+int db_hash_fetch(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen,
+		  db_hash_record_parser_fn parser, void *private_data);
+
+/**
+ * @brief Check if a record exists in the hash table
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] keybuf The key buffer
+ * @param[in] keylen The key length
+ * @return 0 if the record exists, errno on failure
+ */
+int db_hash_exists(struct db_hash_context *dh, uint8_t *keybuf, size_t keylen);
+
+/**
+ * @brief Traverse the database
+ *
+ * The parser function should non-zero value to stop traverse.
+ *
+ * @param[in] dh The tdb hash table context
+ * @param[in] parser Function called for each record
+ * @param[in] private_data Private data to parser function
+ * @param[out] count Number of records traversed
+ * @return 0 on success, errno on failure
+ */
+int db_hash_traverse(struct db_hash_context *dh,
+		     db_hash_record_parser_fn parser, void *private_data,
+		     int *count);
+
+#endif /* __CTDB_DB_HASH_H__ */