I have implemented everything we have discussed today. The patch
versus the current master is attached so it can be reviewed.
The changes versus the previous draft can be summarized as follows:
* Bug fixes.
* Use _Atomic on GCC 4.9+.
* Implement a lightweight iterator type akin to the iterators of gl_list.
* Expose element initialization to the user so than an element can be
inserted in more than one hamt.
* Rename delete to remove.
* Improve documentation.
Future options for when the code has matured:
* Inline a number of subtrie procedures to get rid of forward
declarations to help compilers.
* Implement purely non-pure hamts to replace ordinary hash tables.
* Add _nx versions of the procedures that won't call xalloc_die.
Many thanks to Bruno for his support, guidance and his great suggestions.
Marc
Am So., 11. Okt. 2020 um 19:32 Uhr schrieb Marc Nieper-Wißkirchen
:
>
> Am So., 11. Okt. 2020 um 10:20 Uhr schrieb Marc Nieper-Wißkirchen
> :
> >
> > Am So., 11. Okt. 2020 um 03:28 Uhr schrieb Bruno Haible :
>
> [...]
>
> > > * hamt_lookup: If the caller is allowed to modify the payload stored in
> > > the
> > > returned entry, this function should return a 'Hamt_entry *', not a
> > > 'const Hamt_entry *'. Just like 'strchr' and 'strstr' return a 'char *',
> > > not a 'const char *'.
> >
> > Unless the caller knows what it does, modifying the payload is not a
> > good idea because the entry is shared between different hamts. If the
> > caller really wants to modify the payload, it has to do an explicit
> > type cast (which is safe).
>
> I have noticed a problem with the current design: While an element can
> be in more than one hamt (because copies of hamts are created through
> various operations), an element cannot be actively inserted in more
> than one hamt. The reason is that the reference counter of the element
> is initialized whenever the element is inserted.
>
> The way out is to expose the initialization function to the user, who
> becomes responsible for initializing each element exactly once.
>
> As soon as it is possible to insert an element more than once, another
> observation will be made: The insert procedure does not accept a
> pointer to a const element because it must be able to change the
> reference counter internally. Thus it is more convenient if procedures
> like hamt_lookup do not return const versions.
From ece7b9e3cd090e9c084efd72677669130e80dd9c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?=
Date: Sat, 10 Oct 2020 23:38:21 +0200
Subject: [PATCH] hamt: New module.
This module provides (persistent) hash array mapped tries.
* MODULES.html.sh: Add hamt.
* lib/hamt.c: New file.
* lib/hamt.h: New file.
* modules/hamt: New file.
* modules/hamt-tests: New file.
* tests/test-hamt.c: New file.
---
ChangeLog | 11 +
MODULES.html.sh|1 +
lib/hamt.c | 1083
lib/hamt.h | 253 +++
modules/hamt | 29 ++
modules/hamt-tests | 11 +
tests/test-hamt.c | 378
7 files changed, 1766 insertions(+)
create mode 100644 lib/hamt.c
create mode 100644 lib/hamt.h
create mode 100644 modules/hamt
create mode 100644 modules/hamt-tests
create mode 100644 tests/test-hamt.c
diff --git a/ChangeLog b/ChangeLog
index 22f79fb09..7263e628f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2020-10-11 Marc Nieper-Wißkirchen
+
+ hamt: New module.
+ This module provides (persistent) hash array mapped tries.
+ * MODULES.html.sh: Add hamt.
+ * lib/hamt.c: New file.
+ * lib/hamt.h: New file.
+ * modules/hamt: New file.
+ * modules/hamt-tests: New file.
+ * tests/test-hamt.c: New file.
+
2020-10-11 Bruno Haible
stdioext: Update comments regarding UnixWare.
diff --git a/MODULES.html.sh b/MODULES.html.sh
index 7e7cdae3e..2907eb741 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -2028,6 +2028,7 @@ func_all_modules ()
func_module hash-pjw
func_module hash-pjw-bare
func_module hash
+ func_module hamt
func_module readline
func_module readtokens
func_module readtokens0
diff --git a/lib/hamt.c b/lib/hamt.c
new file mode 100644
index 0..f92d9c4e8
--- /dev/null
+++ b/lib/hamt.c
@@ -0,0 +1,1083 @@
+/* (Persistent) hash array mapped tries.
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+ 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
