<p>laforge <strong>submitted</strong> this change.</p><p><a href="https://gerrit.osmocom.org/c/libosmocore/+/21547">View Change</a></p><div style="white-space:pre-wrap">Approvals:
Jenkins Builder: Verified
laforge: Looks good to me, approved
</div><pre style="font-family: monospace,monospace; white-space: pre-wrap;">Add hlist and hashtable from Linux kernel<br><br>For more than a decade we've used the linuxlist.h for double-linked<br>lists. Let's also add the hlist (double-linked lists with single<br>pointer sized head, and the hashtable that builds on top of it.<br><br>This reflects the versions included in Linux 5.8 with some modifications<br>to make them build in userspace (remove RCU versions, adjust for<br>userspace include files and types, convert to doxygen).<br><br>Change-Id: I8ef73a62fe9846ce45058eb21cf999dd3eed5741<br>---<br>M include/Makefile.am<br>A include/osmocom/core/hash.h<br>A include/osmocom/core/hashtable.h<br>M include/osmocom/core/linuxlist.h<br>A include/osmocom/core/log2.h<br>5 files changed, 617 insertions(+), 0 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;"><span>diff --git a/include/Makefile.am b/include/Makefile.am</span><br><span>index 71171a4..f13ae76 100644</span><br><span>--- a/include/Makefile.am</span><br><span>+++ b/include/Makefile.am</span><br><span>@@ -27,9 +27,12 @@</span><br><span> osmocom/core/fsm.h \</span><br><span> osmocom/core/gsmtap.h \</span><br><span> osmocom/core/gsmtap_util.h \</span><br><span style="color: hsl(120, 100%, 40%);">+ osmocom/core/hash.h \</span><br><span style="color: hsl(120, 100%, 40%);">+ osmocom/core/hashtable.h \</span><br><span> osmocom/core/isdnhdlc.h \</span><br><span> osmocom/core/linuxlist.h \</span><br><span> osmocom/core/linuxrbtree.h \</span><br><span style="color: hsl(120, 100%, 40%);">+ osmocom/core/log2.h \</span><br><span> osmocom/core/logging.h \</span><br><span> osmocom/core/loggingrb.h \</span><br><span> osmocom/core/mnl.h \</span><br><span>diff --git a/include/osmocom/core/hash.h b/include/osmocom/core/hash.h</span><br><span>new file mode 100644</span><br><span>index 0000000..b45c036</span><br><span>--- /dev/null</span><br><span>+++ b/include/osmocom/core/hash.h</span><br><span>@@ -0,0 +1,101 @@</span><br><span style="color: hsl(120, 100%, 40%);">+#pragma once</span><br><span style="color: hsl(120, 100%, 40%);">+#include <osmocom/core/log2.h></span><br><span style="color: hsl(120, 100%, 40%);">+/* Fast hashing routine for ints, longs and pointers.</span><br><span style="color: hsl(120, 100%, 40%);">+ (C) 2002 Nadia Yvette Chambers, IBM */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#include <limits.h></span><br><span style="color: hsl(120, 100%, 40%);">+#if ULONG_MAX == 4294967295</span><br><span style="color: hsl(120, 100%, 40%);">+#define BITS_PER_LONG 32</span><br><span style="color: hsl(120, 100%, 40%);">+#else</span><br><span style="color: hsl(120, 100%, 40%);">+#define BITS_PER_LONG 64</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and</span><br><span style="color: hsl(120, 100%, 40%);">+ * fs/inode.c. It's not actually prime any more (the previous primes</span><br><span style="color: hsl(120, 100%, 40%);">+ * were actively bad for hashing), but the name remains.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#if BITS_PER_LONG == 32</span><br><span style="color: hsl(120, 100%, 40%);">+#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_long(val, bits) hash_32(val, bits)</span><br><span style="color: hsl(120, 100%, 40%);">+#elif BITS_PER_LONG == 64</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_long(val, bits) hash_64(val, bits)</span><br><span style="color: hsl(120, 100%, 40%);">+#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64</span><br><span style="color: hsl(120, 100%, 40%);">+#else</span><br><span style="color: hsl(120, 100%, 40%);">+#error Wordsize not 32 or 64</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * This hash multiplies the input by a large odd number and takes the</span><br><span style="color: hsl(120, 100%, 40%);">+ * high bits. Since multiplication propagates changes to the most</span><br><span style="color: hsl(120, 100%, 40%);">+ * significant end only, it is essential that the high bits of the</span><br><span style="color: hsl(120, 100%, 40%);">+ * product be used for the hash value.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Chuck Lever verified the effectiveness of this technique:</span><br><span style="color: hsl(120, 100%, 40%);">+ * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Although a random odd number will do, it turns out that the golden</span><br><span style="color: hsl(120, 100%, 40%);">+ * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice</span><br><span style="color: hsl(120, 100%, 40%);">+ * properties. (See Knuth vol 3, section 6.4, exercise 9.)</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,</span><br><span style="color: hsl(120, 100%, 40%);">+ * which is very slightly easier to multiply by and makes no</span><br><span style="color: hsl(120, 100%, 40%);">+ * difference to the hash distribution.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define GOLDEN_RATIO_32 0x61C88647</span><br><span style="color: hsl(120, 100%, 40%);">+#define GOLDEN_RATIO_64 0x61C8864680B583EBull</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * The _generic versions exist only so lib/test_hash.c can compare</span><br><span style="color: hsl(120, 100%, 40%);">+ * the arch-optimized versions with the generic.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Note that if you change these, any <asm/hash.h> that aren't updated</span><br><span style="color: hsl(120, 100%, 40%);">+ * to match need to have their HAVE_ARCH_* define values updated so the</span><br><span style="color: hsl(120, 100%, 40%);">+ * self-test will not false-positive.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#ifndef HAVE_ARCH__HASH_32</span><br><span style="color: hsl(120, 100%, 40%);">+#define __hash_32 __hash_32_generic</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+static inline uint32_t __hash_32_generic(uint32_t val)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return val * GOLDEN_RATIO_32;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#ifndef HAVE_ARCH_HASH_32</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_32 hash_32_generic</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+static inline uint32_t hash_32_generic(uint32_t val, unsigned int bits)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ /* High bits are more random, so use them. */</span><br><span style="color: hsl(120, 100%, 40%);">+ return __hash_32(val) >> (32 - bits);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#ifndef HAVE_ARCH_HASH_64</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_64 hash_64_generic</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+static __always_inline uint32_t hash_64_generic(uint64_t val, unsigned int bits)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+#if BITS_PER_LONG == 64</span><br><span style="color: hsl(120, 100%, 40%);">+ /* 64x64-bit multiply is efficient on all 64-bit processors */</span><br><span style="color: hsl(120, 100%, 40%);">+ return val * GOLDEN_RATIO_64 >> (64 - bits);</span><br><span style="color: hsl(120, 100%, 40%);">+#else</span><br><span style="color: hsl(120, 100%, 40%);">+ /* Hash 64 bits using only 32x32-bit multiply. */</span><br><span style="color: hsl(120, 100%, 40%);">+ return hash_32((uint32_t)val ^ __hash_32(val >> 32), bits);</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static inline uint32_t hash_ptr(const void *ptr, unsigned int bits)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return hash_long((unsigned long)ptr, bits);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/* This really should be called fold32_ptr; it does no hashing to speak of. */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline uint32_t hash32_ptr(const void *ptr)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ unsigned long val = (unsigned long)ptr;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#if BITS_PER_LONG == 64</span><br><span style="color: hsl(120, 100%, 40%);">+ val ^= (val >> 32);</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+ return (uint32_t)val;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span>diff --git a/include/osmocom/core/hashtable.h b/include/osmocom/core/hashtable.h</span><br><span>new file mode 100644</span><br><span>index 0000000..acaf6b9</span><br><span>--- /dev/null</span><br><span>+++ b/include/osmocom/core/hashtable.h</span><br><span>@@ -0,0 +1,141 @@</span><br><span style="color: hsl(120, 100%, 40%);">+/* SPDX-License-Identifier: GPL-2.0 */</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * Statically sized hash table implementation</span><br><span style="color: hsl(120, 100%, 40%);">+ * (C) 2012 Sasha Levin <levinsasha928@gmail.com></span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#pragma once</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#include <osmocom/core/linuxlist.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <osmocom/core/hash.h></span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define DEFINE_HASHTABLE(name, bits) \</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_head name[1 << (bits)] = \</span><br><span style="color: hsl(120, 100%, 40%);">+ { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define DECLARE_HASHTABLE(name, bits) \</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_head name[1 << (bits)]</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define HASH_SIZE(name) (ARRAY_SIZE(name))</span><br><span style="color: hsl(120, 100%, 40%);">+#define HASH_BITS(name) ilog2(HASH_SIZE(name))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_min(val, bits) \</span><br><span style="color: hsl(120, 100%, 40%);">+ (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void __hash_init(struct hlist_head *ht, unsigned int sz)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ unsigned int i;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ for (i = 0; i < sz; i++)</span><br><span style="color: hsl(120, 100%, 40%);">+ INIT_HLIST_HEAD(&ht[i]);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_init - initialize a hash table</span><br><span style="color: hsl(120, 100%, 40%);">+ * @hashtable: hashtable to be initialized</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Calculates the size of the hashtable from the given parameter, otherwise</span><br><span style="color: hsl(120, 100%, 40%);">+ * same as hash_init_size.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This has to be a macro since HASH_BITS() will not work on pointers since</span><br><span style="color: hsl(120, 100%, 40%);">+ * it calculates the size during preprocessing.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_add - add an object to a hashtable</span><br><span style="color: hsl(120, 100%, 40%);">+ * @hashtable: hashtable to add to</span><br><span style="color: hsl(120, 100%, 40%);">+ * @node: the &struct hlist_node of the object to be added</span><br><span style="color: hsl(120, 100%, 40%);">+ * @key: the key of the object to be added</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_add(hashtable, node, key) \</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_hashed - check whether an object is in any hashtable</span><br><span style="color: hsl(120, 100%, 40%);">+ * @node: the &struct hlist_node of the object to be checked</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline bool hash_hashed(struct hlist_node *node)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return !hlist_unhashed(node);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ unsigned int i;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ for (i = 0; i < sz; i++)</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!hlist_empty(&ht[i]))</span><br><span style="color: hsl(120, 100%, 40%);">+ return false;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ return true;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_empty - check whether a hashtable is empty</span><br><span style="color: hsl(120, 100%, 40%);">+ * @hashtable: hashtable to check</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This has to be a macro since HASH_BITS() will not work on pointers since</span><br><span style="color: hsl(120, 100%, 40%);">+ * it calculates the size during preprocessing.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_del - remove an object from a hashtable</span><br><span style="color: hsl(120, 100%, 40%);">+ * @node: &struct hlist_node of the object to remove</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hash_del(struct hlist_node *node)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_del_init(node);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_for_each - iterate over a hashtable</span><br><span style="color: hsl(120, 100%, 40%);">+ * @name: hashtable to iterate</span><br><span style="color: hsl(120, 100%, 40%);">+ * @bkt: integer to use as bucket loop cursor</span><br><span style="color: hsl(120, 100%, 40%);">+ * @obj: the type * to use as a loop cursor for each entry</span><br><span style="color: hsl(120, 100%, 40%);">+ * @member: the name of the hlist_node within the struct</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_for_each(name, bkt, obj, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\</span><br><span style="color: hsl(120, 100%, 40%);">+ (bkt)++)\</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_for_each_entry(obj, &name[bkt], member)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_for_each_safe - iterate over a hashtable safe against removal of</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash entry</span><br><span style="color: hsl(120, 100%, 40%);">+ * @name: hashtable to iterate</span><br><span style="color: hsl(120, 100%, 40%);">+ * @bkt: integer to use as bucket loop cursor</span><br><span style="color: hsl(120, 100%, 40%);">+ * @tmp: a &struct hlist_node used for temporary storage</span><br><span style="color: hsl(120, 100%, 40%);">+ * @obj: the type * to use as a loop cursor for each entry</span><br><span style="color: hsl(120, 100%, 40%);">+ * @member: the name of the hlist_node within the struct</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_for_each_safe(name, bkt, tmp, obj, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\</span><br><span style="color: hsl(120, 100%, 40%);">+ (bkt)++)\</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_for_each_possible - iterate over all possible objects hashing to the</span><br><span style="color: hsl(120, 100%, 40%);">+ * same bucket</span><br><span style="color: hsl(120, 100%, 40%);">+ * @name: hashtable to iterate</span><br><span style="color: hsl(120, 100%, 40%);">+ * @obj: the type * to use as a loop cursor for each entry</span><br><span style="color: hsl(120, 100%, 40%);">+ * @member: the name of the hlist_node within the struct</span><br><span style="color: hsl(120, 100%, 40%);">+ * @key: the key of the objects to iterate over</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_for_each_possible(name, obj, member, key) \</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * hash_for_each_possible_safe - iterate over all possible objects hashing to the</span><br><span style="color: hsl(120, 100%, 40%);">+ * same bucket safe against removals</span><br><span style="color: hsl(120, 100%, 40%);">+ * @name: hashtable to iterate</span><br><span style="color: hsl(120, 100%, 40%);">+ * @obj: the type * to use as a loop cursor for each entry</span><br><span style="color: hsl(120, 100%, 40%);">+ * @tmp: a &struct hlist_node used for temporary storage</span><br><span style="color: hsl(120, 100%, 40%);">+ * @member: the name of the hlist_node within the struct</span><br><span style="color: hsl(120, 100%, 40%);">+ * @key: the key of the objects to iterate over</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hash_for_each_possible_safe(name, obj, tmp, member, key) \</span><br><span style="color: hsl(120, 100%, 40%);">+ hlist_for_each_entry_safe(obj, tmp,\</span><br><span style="color: hsl(120, 100%, 40%);">+ &name[hash_min(key, HASH_BITS(name))], member)</span><br><span>diff --git a/include/osmocom/core/linuxlist.h b/include/osmocom/core/linuxlist.h</span><br><span>index 867605e..2c3a0a4 100644</span><br><span>--- a/include/osmocom/core/linuxlist.h</span><br><span>+++ b/include/osmocom/core/linuxlist.h</span><br><span>@@ -16,6 +16,7 @@</span><br><span> * \file linuxlist.h */</span><br><span> </span><br><span> #include <stddef.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <stdbool.h></span><br><span> </span><br><span> #ifndef inline</span><br><span> #define inline __inline__</span><br><span>@@ -393,6 +394,252 @@</span><br><span> return i;</span><br><span> }</span><br><span> </span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Double linked lists with a single pointer list head.</span><br><span style="color: hsl(120, 100%, 40%);">+ * Mostly useful for hash tables where the two pointer list head is</span><br><span style="color: hsl(120, 100%, 40%);">+ * too wasteful.</span><br><span style="color: hsl(120, 100%, 40%);">+ * You lose the ability to access the tail in O(1).</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct hlist_head {</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *first;</span><br><span style="color: hsl(120, 100%, 40%);">+};</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+struct hlist_node {</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *next, **pprev;</span><br><span style="color: hsl(120, 100%, 40%);">+};</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define HLIST_HEAD_INIT { .first = NULL }</span><br><span style="color: hsl(120, 100%, 40%);">+#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }</span><br><span style="color: hsl(120, 100%, 40%);">+#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void INIT_HLIST_NODE(struct hlist_node *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ h->next = NULL;</span><br><span style="color: hsl(120, 100%, 40%);">+ h->pprev = NULL;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define READ_ONCE(x) x</span><br><span style="color: hsl(120, 100%, 40%);">+#define WRITE_ONCE(a, b) a = b</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Has node been removed from list and reinitialized?.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] h: Node to be checked</span><br><span style="color: hsl(120, 100%, 40%);">+ * \return 1 if node is unhashed; 0 if not</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Not that not all removal functions will leave a node in unhashed</span><br><span style="color: hsl(120, 100%, 40%);">+ * state. For example, hlist_nulls_del_init_rcu() does leave the</span><br><span style="color: hsl(120, 100%, 40%);">+ * node in unhashed state, but hlist_nulls_del() does not.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline int hlist_unhashed(const struct hlist_node *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return !h->pprev;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Version of hlist_unhashed for lockless use.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n Node to be checked</span><br><span style="color: hsl(120, 100%, 40%);">+ * \return 1 if node is unhashed; 0 if not</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This variant of hlist_unhashed() must be used in lockless contexts</span><br><span style="color: hsl(120, 100%, 40%);">+ * to avoid potential load-tearing. The READ_ONCE() is paired with the</span><br><span style="color: hsl(120, 100%, 40%);">+ * various WRITE_ONCE() in hlist helpers that are defined below.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline int hlist_unhashed_lockless(const struct hlist_node *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return !READ_ONCE(h->pprev);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*!Is the specified hlist_head structure an empty hlist?.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] h Structure to check.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \return 1 if hlist is empty; 0 if not</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline int hlist_empty(const struct hlist_head *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return !READ_ONCE(h->first);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void __hlist_del(struct hlist_node *n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *next = n->next;</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node **pprev = n->pprev;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(*pprev, next);</span><br><span style="color: hsl(120, 100%, 40%);">+ if (next)</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(next->pprev, pprev);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Delete the specified hlist_node from its list.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n: Node to delete.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Note that this function leaves the node in hashed state. Use</span><br><span style="color: hsl(120, 100%, 40%);">+ * hlist_del_init() or similar instead to unhash @n.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_del(struct hlist_node *n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ __hlist_del(n);</span><br><span style="color: hsl(120, 100%, 40%);">+ n->next = LLIST_POISON1;</span><br><span style="color: hsl(120, 100%, 40%);">+ n->pprev = LLIST_POISON2;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Delete the specified hlist_node from its list and initialize.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n Node to delete.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Note that this function leaves the node in unhashed state.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_del_init(struct hlist_node *n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!hlist_unhashed(n)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ __hlist_del(n);</span><br><span style="color: hsl(120, 100%, 40%);">+ INIT_HLIST_NODE(n);</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! add a new entry at the beginning of the hlist.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n new entry to be added</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] h hlist head to add it after</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Insert a new entry after the specified head.</span><br><span style="color: hsl(120, 100%, 40%);">+ * This is good for implementing stacks.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *first = h->first;</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->next, first);</span><br><span style="color: hsl(120, 100%, 40%);">+ if (first)</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(first->pprev, &n->next);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(h->first, n);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->pprev, &h->first);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! add a new entry before the one specified.</span><br><span style="color: hsl(120, 100%, 40%);">+ * @n: new entry to be added</span><br><span style="color: hsl(120, 100%, 40%);">+ * @next: hlist node to add it before, which must be non-NULL</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_add_before(struct hlist_node *n,</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *next)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->pprev, next->pprev);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->next, next);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(next->pprev, &n->next);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(*(n->pprev), n);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! add a new entry after the one specified</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n new entry to be added</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] prev hlist node to add it after, which must be non-NULL</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_add_behind(struct hlist_node *n,</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_node *prev)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->next, prev->next);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(prev->next, n);</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->pprev, &prev->next);</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (n->next)</span><br><span style="color: hsl(120, 100%, 40%);">+ WRITE_ONCE(n->next->pprev, &n->next);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! create a fake hlist consisting of a single headless node.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n Node to make a fake list out of</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This makes @n appear to be its own predecessor on a headless hlist.</span><br><span style="color: hsl(120, 100%, 40%);">+ * The point of this is to allow things like hlist_del() to work correctly</span><br><span style="color: hsl(120, 100%, 40%);">+ * in cases where there is no list.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_add_fake(struct hlist_node *n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ n->pprev = &n->next;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Is this node a fake hlist?.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] h Node to check for being a self-referential fake hlist.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline bool hlist_fake(struct hlist_node *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return h->pprev == &h->next;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*!is node the only element of the specified hlist?.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] n Node to check for singularity.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] h Header for potentially singular list.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Check whether the node is the only node of the head without</span><br><span style="color: hsl(120, 100%, 40%);">+ * accessing head, thus avoiding unnecessary cache misses.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline bool</span><br><span style="color: hsl(120, 100%, 40%);">+hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return !n->next && n->pprev == &h->first;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! Move an hlist.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] old hlist_head for old list.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] new hlist_head for new list.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Move a list from one list head to another. Fixup the pprev</span><br><span style="color: hsl(120, 100%, 40%);">+ * reference of the first entry if it exists.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static inline void hlist_move_list(struct hlist_head *old,</span><br><span style="color: hsl(120, 100%, 40%);">+ struct hlist_head *new)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ new->first = old->first;</span><br><span style="color: hsl(120, 100%, 40%);">+ if (new->first)</span><br><span style="color: hsl(120, 100%, 40%);">+ new->first->pprev = &new->first;</span><br><span style="color: hsl(120, 100%, 40%);">+ old->first = NULL;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_entry(ptr, type, member) container_of(ptr,type,member)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each(pos, head) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (pos = (head)->first; pos ; pos = pos->next)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each_safe(pos, n, head) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \</span><br><span style="color: hsl(120, 100%, 40%);">+ pos = n)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_entry_safe(ptr, type, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ ({ typeof(ptr) ____ptr = (ptr); \</span><br><span style="color: hsl(120, 100%, 40%);">+ ____ptr ? hlist_entry(____ptr, type, member) : NULL; \</span><br><span style="color: hsl(120, 100%, 40%);">+ })</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! iterate over list of given type.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[out] pos the type * to use as a loop cursor.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] head the head for your list.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] member the name of the hlist_node within the struct.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each_entry(pos, head, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\</span><br><span style="color: hsl(120, 100%, 40%);">+ pos; \</span><br><span style="color: hsl(120, 100%, 40%);">+ pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! iterate over a hlist continuing after current point.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[out] pos the type * to use as a loop cursor.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] member the name of the hlist_node within the struct.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each_entry_continue(pos, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\</span><br><span style="color: hsl(120, 100%, 40%);">+ pos; \</span><br><span style="color: hsl(120, 100%, 40%);">+ pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! iterate over a hlist continuing from current point.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[out] pos the type * to use as a loop cursor.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] member the name of the hlist_node within the struct.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each_entry_from(pos, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (; pos; \</span><br><span style="color: hsl(120, 100%, 40%);">+ pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*! hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[out] pos the type * to use as a loop cursor.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[out] n a &struct hlist_node to use as temporary storage</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] head the head for your list.</span><br><span style="color: hsl(120, 100%, 40%);">+ * \param[in] member the name of the hlist_node within the struct</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define hlist_for_each_entry_safe(pos, n, head, member) \</span><br><span style="color: hsl(120, 100%, 40%);">+ for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\</span><br><span style="color: hsl(120, 100%, 40%);">+ pos && ({ n = pos->member.next; 1; }); \</span><br><span style="color: hsl(120, 100%, 40%);">+ pos = hlist_entry_safe(n, typeof(*pos), member))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span> /*!</span><br><span> * @}</span><br><span> */</span><br><span>diff --git a/include/osmocom/core/log2.h b/include/osmocom/core/log2.h</span><br><span>new file mode 100644</span><br><span>index 0000000..06b20f8</span><br><span>--- /dev/null</span><br><span>+++ b/include/osmocom/core/log2.h</span><br><span>@@ -0,0 +1,125 @@</span><br><span style="color: hsl(120, 100%, 40%);">+/* SPDX-License-Identifier: GPL-2.0-or-later */</span><br><span style="color: hsl(120, 100%, 40%);">+/* Integer base 2 logarithm calculation</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.</span><br><span style="color: hsl(120, 100%, 40%);">+ * Written by David Howells (dhowells@redhat.com)</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#pragma once</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/*</span><br><span style="color: hsl(120, 100%, 40%);">+ * non-constant log of base 2 calculators</span><br><span style="color: hsl(120, 100%, 40%);">+ * - the arch may override these in asm/bitops.h if they can be implemented</span><br><span style="color: hsl(120, 100%, 40%);">+ * more efficiently than using fls() and fls64()</span><br><span style="color: hsl(120, 100%, 40%);">+ * - the arch is not required to handle n==0 if implementing the fallback</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#ifndef CONFIG_ARCH_HAS_ILOG2_U32</span><br><span style="color: hsl(120, 100%, 40%);">+static inline __attribute__((const))</span><br><span style="color: hsl(120, 100%, 40%);">+int __ilog2_u32(uint32_t n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return fls(n) - 1;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+#ifndef CONFIG_ARCH_HAS_ILOG2_U64</span><br><span style="color: hsl(120, 100%, 40%);">+static inline __attribute__((const))</span><br><span style="color: hsl(120, 100%, 40%);">+int __ilog2_u64(uint64_t n)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ return fls64(n) - 1;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+#endif</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * const_ilog2 - log base 2 of 32-bit or a 64-bit constant unsigned value</span><br><span style="color: hsl(120, 100%, 40%);">+ * @n: parameter</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * Use this where sparse expects a true constant expression, e.g. for array</span><br><span style="color: hsl(120, 100%, 40%);">+ * indices.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define const_ilog2(n) \</span><br><span style="color: hsl(120, 100%, 40%);">+( \</span><br><span style="color: hsl(120, 100%, 40%);">+ __builtin_constant_p(n) ? ( \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) < 2 ? 0 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 63) ? 63 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 62) ? 62 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 61) ? 61 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 60) ? 60 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 59) ? 59 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 58) ? 58 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 57) ? 57 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 56) ? 56 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 55) ? 55 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 54) ? 54 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 53) ? 53 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 52) ? 52 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 51) ? 51 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 50) ? 50 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 49) ? 49 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 48) ? 48 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 47) ? 47 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 46) ? 46 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 45) ? 45 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 44) ? 44 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 43) ? 43 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 42) ? 42 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 41) ? 41 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 40) ? 40 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 39) ? 39 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 38) ? 38 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 37) ? 37 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 36) ? 36 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 35) ? 35 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 34) ? 34 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 33) ? 33 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 32) ? 32 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 31) ? 31 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 30) ? 30 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 29) ? 29 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 28) ? 28 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 27) ? 27 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 26) ? 26 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 25) ? 25 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 24) ? 24 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 23) ? 23 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 22) ? 22 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 21) ? 21 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 20) ? 20 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 19) ? 19 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 18) ? 18 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 17) ? 17 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 16) ? 16 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 15) ? 15 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 14) ? 14 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 13) ? 13 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 12) ? 12 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 11) ? 11 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 10) ? 10 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 9) ? 9 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 8) ? 8 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 7) ? 7 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 6) ? 6 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 5) ? 5 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 4) ? 4 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 3) ? 3 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (n) & (1ULL << 2) ? 2 : \</span><br><span style="color: hsl(120, 100%, 40%);">+ 1) : \</span><br><span style="color: hsl(120, 100%, 40%);">+ -1)</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value</span><br><span style="color: hsl(120, 100%, 40%);">+ * @n: parameter</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * constant-capable log of base 2 calculation</span><br><span style="color: hsl(120, 100%, 40%);">+ * - this can be used to initialise global variables from constant data, hence</span><br><span style="color: hsl(120, 100%, 40%);">+ * the massive ternary operator construction</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * selects the appropriately-sized optimised version depending on sizeof(n)</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+#define ilog2(n) \</span><br><span style="color: hsl(120, 100%, 40%);">+( \</span><br><span style="color: hsl(120, 100%, 40%);">+ __builtin_constant_p(n) ? \</span><br><span style="color: hsl(120, 100%, 40%);">+ const_ilog2(n) : \</span><br><span style="color: hsl(120, 100%, 40%);">+ (sizeof(n) <= 4) ? \</span><br><span style="color: hsl(120, 100%, 40%);">+ __ilog2_u32(n) : \</span><br><span style="color: hsl(120, 100%, 40%);">+ __ilog2_u64(n) \</span><br><span style="color: hsl(120, 100%, 40%);">+ )</span><br><span></span><br></pre><p>To view, visit <a href="https://gerrit.osmocom.org/c/libosmocore/+/21547">change 21547</a>. To unsubscribe, or for help writing mail filters, visit <a href="https://gerrit.osmocom.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://gerrit.osmocom.org/c/libosmocore/+/21547"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: libosmocore </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-Change-Id: I8ef73a62fe9846ce45058eb21cf999dd3eed5741 </div>
<div style="display:none"> Gerrit-Change-Number: 21547 </div>
<div style="display:none"> Gerrit-PatchSet: 3 </div>
<div style="display:none"> Gerrit-Owner: laforge <laforge@osmocom.org> </div>
<div style="display:none"> Gerrit-Reviewer: Jenkins Builder </div>
<div style="display:none"> Gerrit-Reviewer: laforge <laforge@osmocom.org> </div>
<div style="display:none"> Gerrit-MessageType: merged </div>