claude is gud

1 files changed, 287 insertions, 0 deletions

diff --git a/vere/ext/nasm/nasmlib/hashtbl.c b/vere/ext/nasm/nasmlib/hashtbl.c
new file mode 100644
index 0000000..9a4c0b5
--- /dev/null
+++ b/vere/ext/nasm/nasmlib/hashtbl.c
@@ -0,0 +1,287 @@
+/* ----------------------------------------------------------------------- *
+ *
+ *   Copyright 1996-2018 The NASM Authors - All Rights Reserved
+ *   See the file AUTHORS included with the NASM distribution for
+ *   the specific copyright holders.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following
+ *   conditions are met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ *     copyright notice, this list of conditions and the following
+ *     disclaimer in the documentation and/or other materials provided
+ *     with the distribution.
+ *
+ *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+ *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * hashtbl.c
+ *
+ * Efficient dictionary hash table class.
+ */
+
+#include "compiler.h"
+
+#include "nasm.h"
+#include "hashtbl.h"
+
+#define HASH_MAX_LOAD   2	/* Higher = more memory-efficient, slower */
+#define HASH_INIT_SIZE  16      /* Initial size (power of 2, min 4) */
+
+#define hash_calc(key,keylen)   crc64b(CRC64_INIT, (key), (keylen))
+#define hash_calci(key,keylen)  crc64ib(CRC64_INIT, (key), (keylen))
+#define hash_max_load(size)     ((size) * (HASH_MAX_LOAD - 1) / HASH_MAX_LOAD)
+#define hash_expand(size)       ((size) << 1)
+#define hash_mask(size)         ((size) - 1)
+#define hash_pos(hash, mask)    ((hash) & (mask))
+#define hash_inc(hash, mask)    ((((hash) >> 32) & (mask)) | 1) /* always odd */
+#define hash_pos_next(pos, inc, mask) (((pos) + (inc)) & (mask))
+
+static void hash_init(struct hash_table *head)
+{
+    head->size     = HASH_INIT_SIZE;
+    head->load     = 0;
+    head->max_load = hash_max_load(head->size);
+    nasm_newn(head->table, head->size);
+}
+
+/*
+ * Find an entry in a hash table.  The key can be any binary object.
+ *
+ * On failure, if "insert" is non-NULL, store data in that structure
+ * which can be used to insert that node using hash_add().
+ * See hash_add() for constraints on the uses of the insert object.
+ *
+ * On success, return a pointer to the "data" element of the hash
+ * structure.
+ */
+void **hash_findb(struct hash_table *head, const void *key,
+                  size_t keylen, struct hash_insert *insert)
+{
+    struct hash_node *np = NULL;
+    struct hash_node *tbl = head->table;
+    uint64_t hash = hash_calc(key, keylen);
+    size_t mask = hash_mask(head->size);
+    size_t pos = hash_pos(hash, mask);
+    size_t inc = hash_inc(hash, mask);
+
+    if (likely(tbl)) {
+        while ((np = &tbl[pos])->key) {
+            if (hash == np->hash &&
+                keylen == np->keylen &&
+                !memcmp(key, np->key, keylen))
+                return &np->data;
+            pos = hash_pos_next(pos, inc, mask);
+        }
+    }
+
+    /* Not found.  Store info for insert if requested. */
+    if (insert) {
+        insert->node.hash = hash;
+        insert->node.key = key;
+        insert->node.keylen = keylen;
+        insert->node.data = NULL;
+        insert->head  = head;
+        insert->where = np;
+    }
+    return NULL;
+}
+
+/*
+ * Same as hash_findb(), but for a C string.
+ */
+void **hash_find(struct hash_table *head, const char *key,
+                 struct hash_insert *insert)
+{
+    return hash_findb(head, key, strlen(key)+1, insert);
+}
+
+/*
+ * Same as hash_findb(), but for case-insensitive hashing.
+ */
+void **hash_findib(struct hash_table *head, const void *key, size_t keylen,
+                   struct hash_insert *insert)
+{
+    struct hash_node *np = NULL;
+    struct hash_node *tbl = head->table;
+    uint64_t hash = hash_calci(key, keylen);
+    size_t mask = hash_mask(head->size);
+    size_t pos = hash_pos(hash, mask);
+    size_t inc = hash_inc(hash, mask);
+
+    if (likely(tbl)) {
+        while ((np = &tbl[pos])->key) {
+            if (hash == np->hash &&
+                keylen == np->keylen &&
+                !nasm_memicmp(key, np->key, keylen))
+                return &np->data;
+            pos = hash_pos_next(pos, inc, mask);
+        }
+    }
+
+    /* Not found.  Store info for insert if requested. */
+    if (insert) {
+        insert->node.hash = hash;
+        insert->node.key = key;
+        insert->node.keylen = keylen;
+        insert->node.data = NULL;
+        insert->head  = head;
+        insert->where = np;
+    }
+    return NULL;
+}
+
+/*
+ * Same as hash_find(), but for case-insensitive hashing.
+ */
+void **hash_findi(struct hash_table *head, const char *key,
+                  struct hash_insert *insert)
+{
+    return hash_findib(head, key, strlen(key)+1, insert);
+}
+
+/*
+ * Insert node.  Return a pointer to the "data" element of the newly
+ * created hash node.
+ *
+ * The following constraints apply:
+ * 1. A call to hash_add() invalidates all other outstanding hash_insert
+ *    objects; attempting to use them causes a wild pointer reference.
+ * 2. The key provided must exactly match the key passed to hash_find*(),
+ *    but it does not have to point to the same storage address. The key
+ *    buffer provided to this function must not be freed for the lifespan
+ *    of the hash. NULL will use the same pointer that was passed to
+ *    hash_find*().
+ */
+void **hash_add(struct hash_insert *insert, const void *key, void *data)
+{
+    struct hash_table *head  = insert->head;
+    struct hash_node *np = insert->where;
+
+    if (unlikely(!np)) {
+        hash_init(head);
+        /* The hash table is empty, so we don't need to iterate here */
+        np = &head->table[hash_pos(insert->node.hash, hash_mask(head->size))];
+    }
+
+    /*
+     * Insert node.  We can always do this, even if we need to
+     * rebalance immediately after.
+     */
+    *np = insert->node;
+    np->data = data;
+    if (key)
+        np->key = key;
+
+    if (unlikely(++head->load > head->max_load)) {
+        /* Need to expand the table */
+        size_t newsize           = hash_expand(head->size);
+        struct hash_node *newtbl;
+        size_t mask              = hash_mask(newsize);
+        struct hash_node *op, *xp;
+        size_t i;
+
+        nasm_newn(newtbl, newsize);
+
+        /* Rebalance all the entries */
+        for (i = 0, op = head->table; i < head->size; i++, op++) {
+            if (op->key) {
+                size_t pos = hash_pos(op->hash, mask);
+                size_t inc = hash_inc(op->hash, mask);
+
+                while ((xp = &newtbl[pos])->key)
+                    pos = hash_pos_next(pos, inc, mask);
+
+                *xp = *op;
+                if (op == np)
+                    np = xp;
+            }
+        }
+        nasm_free(head->table);
+
+        head->table    = newtbl;
+        head->size     = newsize;
+        head->max_load = hash_max_load(newsize);
+    }
+
+    return &np->data;
+}
+
+/*
+ * Iterate over all members of a hash set. For the first call, iter
+ * should be as initialized by hash_iterator_init(). Returns a struct
+ * hash_node representing the current object, or NULL if we have
+ * reached the end of the hash table.
+ *
+ * Calling hash_add() will invalidate the iterator.
+ */
+const struct hash_node *hash_iterate(struct hash_iterator *iter)
+{
+    const struct hash_table *head = iter->head;
+    const struct hash_node *cp = iter->next;
+    const struct hash_node *ep = head->table + head->size;
+
+    /* For an empty table, cp == ep == NULL */
+    while (cp < ep) {
+        if (cp->key) {
+            iter->next = cp+1;
+            return cp;
+        }
+        cp++;
+    }
+
+    iter->next = head->table;
+    return NULL;
+}
+
+/*
+ * Free the hash itself.  Doesn't free the data elements; use
+ * hash_iterate() to do that first, if needed.  This function is normally
+ * used when the hash data entries are either freed separately, or
+ * compound objects which can't be freed in a single operation.
+ */
+void hash_free(struct hash_table *head)
+{
+    void *p = head->table;
+    memset(head, 0, sizeof *head);
+    nasm_free(p);
+}
+
+/*
+ * Frees the hash *and* all data elements.  This is applicable only in
+ * the case where the data element is a single allocation.  If the
+ * second argument is false, the key string is part of the data
+ * allocation or belongs to an allocation which will be freed
+ * separately, if it is true the keys are also freed.
+ */
+void hash_free_all(struct hash_table *head, bool free_keys)
+{
+    struct hash_iterator it;
+    const struct hash_node *np;
+
+    hash_for_each(head, it, np) {
+        if (np->data)
+            nasm_free(np->data);
+        if (free_keys && np->key)
+            nasm_free((void *)np->key);
+    }
+
+    hash_free(head);
+}