diff options
author | Joe Thornber <ejt@redhat.com> | 2018-05-11 06:10:01 +0100 |
---|---|---|
committer | Joe Thornber <ejt@redhat.com> | 2018-05-11 06:10:01 +0100 |
commit | 576dd1fc41259a9ed3d95b2385305fc035058618 (patch) | |
tree | e549d2b60ac5482d7adf76a5b355eaca8cbd91b8 /base/memory | |
parent | 3b02b35c3eef04ddc62302328323d7874f6b9daa (diff) | |
download | lvm2-576dd1fc41259a9ed3d95b2385305fc035058618.tar.gz |
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.
Diffstat (limited to 'base/memory')
-rw-r--r-- | base/memory/container_of.h | 23 | ||||
-rw-r--r-- | base/memory/zalloc.h | 31 |
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 |