radix-tree: First drop of radix tree.

An implementation of an adaptive radix tree.  Has the following nice
properties:

  - At least as fast as the hash table
  - Uses less memory
  - You don't need to give an expected size when you create
  - It scales nicely (ie. no large reallocations like the hash table).
  - You can iterate the keys in lexicographical order.

Only insert and lookup are implemented so far.  Plus there's a lot
more performance to come.

2 files changed, 54 insertions, 0 deletions

diff --git a/base/memory/container_of.h b/base/memory/container_of.h
new file mode 100644
index 000000000..4e4c662bf
--- /dev/null
+++ b/base/memory/container_of.h
@@ -0,0 +1,23 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+// 
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#ifndef BASE_MEMORY_CONTAINER_OF_H
+#define BASE_MEMORY_CONTAINER_OF_H
+
+//----------------------------------------------------------------
+
+#define container_of(v, t, head) \
+    ((t *)((const char *)(v) - (const char *)&((t *) 0)->head))
+
+//----------------------------------------------------------------
+
+#endif
diff --git a/base/memory/zalloc.h b/base/memory/zalloc.h
new file mode 100644
index 000000000..d2ef827d6
--- /dev/null
+++ b/base/memory/zalloc.h
@@ -0,0 +1,31 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+// 
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#ifndef BASE_MEMORY_ZALLOC_H
+#define BASE_MEMORY_ZALLOC_H
+
+#include <stdlib.h>
+#include <string.h>
+
+//----------------------------------------------------------------
+
+static inline void *zalloc(size_t len)
+{
+	void *ptr = malloc(len);
+	if (ptr)
+		memset(ptr, 0, len);
+	return ptr;
+}
+
+//----------------------------------------------------------------
+
+#endif