You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by va...@apache.org on 2022/10/28 15:34:17 UTC
[couchdb-khash] branch main updated: Add notice about migrating to the main repo
This is an automated email from the ASF dual-hosted git repository.
vatamane pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/couchdb-khash.git
The following commit(s) were added to refs/heads/main by this push:
new 48c8e22 Add notice about migrating to the main repo
48c8e22 is described below
commit 48c8e22b2c0b90312949511913db6575c6a05b1a
Author: Nick Vatamaniuc <va...@gmail.com>
AuthorDate: Fri Oct 28 11:31:06 2022 -0400
Add notice about migrating to the main repo
---
.travis.yml | 9 -
LICENSE | 76 -----
Makefile | 44 ---
README.md | 5 +-
c_src/hash.c | 843 ----------------------------------------------------
c_src/hash.h | 240 ---------------
c_src/khash.c | 658 ----------------------------------------
rebar.config | 14 -
src/khash.app.src | 10 -
src/khash.erl | 157 ----------
test/gen_term.erl | 131 --------
test/khash_test.erl | 388 ------------------------
12 files changed, 2 insertions(+), 2573 deletions(-)
diff --git a/.travis.yml b/.travis.yml
deleted file mode 100644
index ad5b569..0000000
--- a/.travis.yml
+++ /dev/null
@@ -1,9 +0,0 @@
-language: erlang
-
-otp_release:
- - 21.2
- - 20.3
- - 19.3
-
-script:
- - make check
diff --git a/LICENSE b/LICENSE
deleted file mode 100644
index 873b78b..0000000
--- a/LICENSE
+++ /dev/null
@@ -1,76 +0,0 @@
-khash
-=====
-
-Files: c_src/khash.c src/* test/*.t test/util.erl test/gen_term.erl
-
-Copyright 2013 Cloudant, Inc <su...@cloudant.com>
-
-Permission is hereby granted, free of charge, to any person
-obtaining a copy of this software and associated documentation
-files (the "Software"), to deal in the Software without
-restriction, including without limitation the rights to use,
-copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the
-Software is furnished to do so, subject to the following
-conditions:
-
-The above copyright notice and this permission notice shall be
-included in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-OTHER DEALINGS IN THE SOFTWARE.
-
-
-Kazlib - Hash Table Data Type
-=============================
-
-Files: c_src/hash.*
-
-Copyright (C) 1997 Kaz Kylheku <ka...@ashi.footprints.net>
-
-Free Software License:
-
-All rights are reserved by the author, with the following exceptions:
-Permission is granted to freely reproduce and distribute this software,
-possibly in exchange for a fee, provided that this copyright notice appears
-intact. Permission is also granted to adapt this software to produce
-derivative works, as long as the modified versions carry this copyright
-notice and additional notices stating that the work has been modified.
-This source code may be translated into executable form and incorporated
-into proprietary software; there is no requirement for such software to
-contain a copyright notice related to this source.
-
-
-Etap
-====
-
-Files: test/etap.erl
-
-Copyright (c) 2008-2009 Nick Gerakines <ni...@gerakines.net>
-
-Permission is hereby granted, free of charge, to any person
-obtaining a copy of this software and associated documentation
-files (the "Software"), to deal in the Software without
-restriction, including without limitation the rights to use,
-copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the
-Software is furnished to do so, subject to the following
-conditions:
-
-The above copyright notice and this permission notice shall be
-included in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-OTHER DEALINGS IN THE SOFTWARE.
diff --git a/Makefile b/Makefile
deleted file mode 100644
index ccc4a8a..0000000
--- a/Makefile
+++ /dev/null
@@ -1,44 +0,0 @@
-REBAR?=rebar
-
-
-.PHONY: all
-# target: all - Makes everything
-all: build
-
-
-.PHONY: build
-# target: build - Builds the project
-build:
- $(REBAR) compile
-
-
-.PHONY: check
-# target: check - Checks if project builds and passes all the tests
-check: build eunit
-
-
-.PHONY: clean
-# target: clean - Removes build artifacts
-clean:
- $(REBAR) clean
- rm -f test/*.beam
-
-
-.PHONY: distclean
-# target: distclean - Removes all unversioned files
-distclean: clean
- git clean -fxd
-
-
-.PHONY: eunit
-# target: eunit - Runs eunit test suite
-eunit:
- $(REBAR) eunit
-
-
-.PHONY: help
-# target: help - Prints this help
-help:
- @egrep "^# target:" Makefile | sed -e 's/^# target: //g' | sort
-
-
diff --git a/README.md b/README.md
index c04d008..c75fbcd 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,3 @@
-khash
-=====
+## NOTE ##
-This is a basic NIF wrapper around Kazlib's hash data structure.
+Application was moved to the [main repository](https://github.com/apache/couchdb.git)
diff --git a/c_src/hash.c b/c_src/hash.c
deleted file mode 100644
index e3da0da..0000000
--- a/c_src/hash.c
+++ /dev/null
@@ -1,843 +0,0 @@
-/*
- * Hash Table Data Type
- * Copyright (C) 1997 Kaz Kylheku <ka...@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: hash.c,v 1.36.2.11 2000/11/13 01:36:45 kaz Exp $
- * $Name: kazlib_1_20 $
- */
-
-#include <stdlib.h>
-#include <stddef.h>
-#include <assert.h>
-#include <string.h>
-#define HASH_IMPLEMENTATION
-#include "hash.h"
-
-#ifdef KAZLIB_RCSID
-static const char rcsid[] = "$Id: hash.c,v 1.36.2.11 2000/11/13 01:36:45 kaz Exp $";
-#endif
-
-#define INIT_BITS 6
-#define INIT_SIZE (1UL << (INIT_BITS)) /* must be power of two */
-#define INIT_MASK ((INIT_SIZE) - 1)
-
-#define next hash_next
-#define key hash_key
-#define data hash_data
-#define hkey hash_hkey
-
-#define table hash_table
-#define nchains hash_nchains
-#define nodecount hash_nodecount
-#define maxcount hash_maxcount
-#define highmark hash_highmark
-#define lowmark hash_lowmark
-#define compare hash_compare
-#define function hash_function
-#define allocnode hash_allocnode
-#define freenode hash_freenode
-#define context hash_context
-#define mask hash_mask
-#define dynamic hash_dynamic
-
-#define table hash_table
-#define chain hash_chain
-
-static hnode_t *kl_hnode_alloc(void *context);
-static void kl_hnode_free(hnode_t *node, void *context);
-static hash_val_t hash_fun_default(const void *key);
-static int hash_comp_default(const void *key1, const void *key2);
-
-int hash_val_t_bit;
-
-/*
- * Compute the number of bits in the hash_val_t type. We know that hash_val_t
- * is an unsigned integral type. Thus the highest value it can hold is a
- * Mersenne number (power of two, less one). We initialize a hash_val_t
- * object with this value and then shift bits out one by one while counting.
- * Notes:
- * 1. HASH_VAL_T_MAX is a Mersenne number---one that is one less than a power
- * of two. This means that its binary representation consists of all one
- * bits, and hence ``val'' is initialized to all one bits.
- * 2. While bits remain in val, we increment the bit count and shift it to the
- * right, replacing the topmost bit by zero.
- */
-
-static void compute_bits(void)
-{
- hash_val_t val = HASH_VAL_T_MAX; /* 1 */
- int bits = 0;
-
- while (val) { /* 2 */
- bits++;
- val >>= 1;
- }
-
- hash_val_t_bit = bits;
-}
-
-/*
- * Verify whether the given argument is a power of two.
- */
-
-static int is_power_of_two(hash_val_t arg)
-{
- if (arg == 0)
- return 0;
- while ((arg & 1) == 0)
- arg >>= 1;
- return (arg == 1);
-}
-
-/*
- * Compute a shift amount from a given table size
- */
-
-static hash_val_t compute_mask(hashcount_t size)
-{
- assert (is_power_of_two(size));
- assert (size >= 2);
-
- return size - 1;
-}
-
-/*
- * Initialize the table of pointers to null.
- */
-
-static void clear_table(hash_t *hash)
-{
- hash_val_t i;
-
- for (i = 0; i < hash->nchains; i++)
- hash->table[i] = NULL;
-}
-
-/*
- * Double the size of a dynamic table. This works as follows. Each chain splits
- * into two adjacent chains. The shift amount increases by one, exposing an
- * additional bit of each hashed key. For each node in the original chain, the
- * value of this newly exposed bit will decide which of the two new chains will
- * receive the node: if the bit is 1, the chain with the higher index will have
- * the node, otherwise the lower chain will receive the node. In this manner,
- * the hash table will continue to function exactly as before without having to
- * rehash any of the keys.
- * Notes:
- * 1. Overflow check.
- * 2. The new number of chains is twice the old number of chains.
- * 3. The new mask is one bit wider than the previous, revealing a
- * new bit in all hashed keys.
- * 4. Allocate a new table of chain pointers that is twice as large as the
- * previous one.
- * 5. If the reallocation was successful, we perform the rest of the growth
- * algorithm, otherwise we do nothing.
- * 6. The exposed_bit variable holds a mask with which each hashed key can be
- * AND-ed to test the value of its newly exposed bit.
- * 7. Now loop over each chain in the table and sort its nodes into two
- * chains based on the value of each node's newly exposed hash bit.
- * 8. The low chain replaces the current chain. The high chain goes
- * into the corresponding sister chain in the upper half of the table.
- * 9. We have finished dealing with the chains and nodes. We now update
- * the various bookeeping fields of the hash structure.
- */
-
-static void grow_table(hash_t *hash)
-{
- hnode_t **newtable;
-
- assert (2 * hash->nchains > hash->nchains); /* 1 */
-
- newtable = realloc(hash->table,
- sizeof *newtable * hash->nchains * 2); /* 4 */
-
- if (newtable) { /* 5 */
- hash_val_t mask = (hash->mask << 1) | 1; /* 3 */
- hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */
- hash_val_t chain;
-
- assert (mask != hash->mask);
-
- for (chain = 0; chain < hash->nchains; chain++) { /* 7 */
- hnode_t *low_chain = 0, *high_chain = 0, *hptr, *next;
-
- for (hptr = newtable[chain]; hptr != 0; hptr = next) {
- next = hptr->next;
-
- if (hptr->hkey & exposed_bit) {
- hptr->next = high_chain;
- high_chain = hptr;
- } else {
- hptr->next = low_chain;
- low_chain = hptr;
- }
- }
-
- newtable[chain] = low_chain; /* 8 */
- newtable[chain + hash->nchains] = high_chain;
- }
-
- hash->table = newtable; /* 9 */
- hash->mask = mask;
- hash->nchains *= 2;
- hash->lowmark *= 2;
- hash->highmark *= 2;
- }
- assert (kl_hash_verify(hash));
-}
-
-/*
- * Cut a table size in half. This is done by folding together adjacent chains
- * and populating the lower half of the table with these chains. The chains are
- * simply spliced together. Once this is done, the whole table is reallocated
- * to a smaller object.
- * Notes:
- * 1. It is illegal to have a hash table with one slot. This would mean that
- * hash->shift is equal to hash_val_t_bit, an illegal shift value.
- * Also, other things could go wrong, such as hash->lowmark becoming zero.
- * 2. Looping over each pair of sister chains, the low_chain is set to
- * point to the head node of the chain in the lower half of the table,
- * and high_chain points to the head node of the sister in the upper half.
- * 3. The intent here is to compute a pointer to the last node of the
- * lower chain into the low_tail variable. If this chain is empty,
- * low_tail ends up with a null value.
- * 4. If the lower chain is not empty, we simply tack the upper chain onto it.
- * If the upper chain is a null pointer, nothing happens.
- * 5. Otherwise if the lower chain is empty but the upper one is not,
- * If the low chain is empty, but the high chain is not, then the
- * high chain is simply transferred to the lower half of the table.
- * 6. Otherwise if both chains are empty, there is nothing to do.
- * 7. All the chain pointers are in the lower half of the table now, so
- * we reallocate it to a smaller object. This, of course, invalidates
- * all pointer-to-pointers which reference into the table from the
- * first node of each chain.
- * 8. Though it's unlikely, the reallocation may fail. In this case we
- * pretend that the table _was_ reallocated to a smaller object.
- * 9. Finally, update the various table parameters to reflect the new size.
- */
-
-static void shrink_table(hash_t *hash)
-{
- hash_val_t chain, nchains;
- hnode_t **newtable, *low_tail, *low_chain, *high_chain;
-
- assert (hash->nchains >= 2); /* 1 */
- nchains = hash->nchains / 2;
-
- for (chain = 0; chain < nchains; chain++) {
- low_chain = hash->table[chain]; /* 2 */
- high_chain = hash->table[chain + nchains];
- for (low_tail = low_chain; low_tail && low_tail->next; low_tail = low_tail->next)
- ; /* 3 */
- if (low_chain != 0) /* 4 */
- low_tail->next = high_chain;
- else if (high_chain != 0) /* 5 */
- hash->table[chain] = high_chain;
- else
- assert (hash->table[chain] == NULL); /* 6 */
- }
- newtable = realloc(hash->table,
- sizeof *newtable * nchains); /* 7 */
- if (newtable) /* 8 */
- hash->table = newtable;
- hash->mask >>= 1; /* 9 */
- hash->nchains = nchains;
- hash->lowmark /= 2;
- hash->highmark /= 2;
- assert (kl_hash_verify(hash));
-}
-
-
-/*
- * Create a dynamic hash table. Both the hash table structure and the table
- * itself are dynamically allocated. Furthermore, the table is extendible in
- * that it will automatically grow as its load factor increases beyond a
- * certain threshold.
- * Notes:
- * 1. If the number of bits in the hash_val_t type has not been computed yet,
- * we do so here, because this is likely to be the first function that the
- * user calls.
- * 2. Allocate a hash table control structure.
- * 3. If a hash table control structure is successfully allocated, we
- * proceed to initialize it. Otherwise we return a null pointer.
- * 4. We try to allocate the table of hash chains.
- * 5. If we were able to allocate the hash chain table, we can finish
- * initializing the hash structure and the table. Otherwise, we must
- * backtrack by freeing the hash structure.
- * 6. INIT_SIZE should be a power of two. The high and low marks are always set
- * to be twice the table size and half the table size respectively. When the
- * number of nodes in the table grows beyond the high size (beyond load
- * factor 2), it will double in size to cut the load factor down to about
- * about 1. If the table shrinks down to or beneath load factor 0.5,
- * it will shrink, bringing the load up to about 1. However, the table
- * will never shrink beneath INIT_SIZE even if it's emptied.
- * 7. This indicates that the table is dynamically allocated and dynamically
- * resized on the fly. A table that has this value set to zero is
- * assumed to be statically allocated and will not be resized.
- * 8. The table of chains must be properly reset to all null pointers.
- */
-
-hash_t *kl_hash_create(hashcount_t maxcount, hash_comp_t compfun,
- hash_fun_t hashfun)
-{
- hash_t *hash;
-
- if (hash_val_t_bit == 0) /* 1 */
- compute_bits();
-
- hash = malloc(sizeof *hash); /* 2 */
-
- if (hash) { /* 3 */
- hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */
- if (hash->table) { /* 5 */
- hash->nchains = INIT_SIZE; /* 6 */
- hash->highmark = INIT_SIZE * 2;
- hash->lowmark = INIT_SIZE / 2;
- hash->nodecount = 0;
- hash->maxcount = maxcount;
- hash->compare = compfun ? compfun : hash_comp_default;
- hash->function = hashfun ? hashfun : hash_fun_default;
- hash->allocnode = kl_hnode_alloc;
- hash->freenode = kl_hnode_free;
- hash->context = NULL;
- hash->mask = INIT_MASK;
- hash->dynamic = 1; /* 7 */
- clear_table(hash); /* 8 */
- assert (kl_hash_verify(hash));
- return hash;
- }
- free(hash);
- }
-
- return NULL;
-}
-
-/*
- * Select a different set of node allocator routines.
- */
-
-void kl_hash_set_allocator(hash_t *hash, hnode_alloc_t al,
- hnode_free_t fr, void *context)
-{
- assert (kl_hash_count(hash) == 0);
- assert ((al == 0 && fr == 0) || (al != 0 && fr != 0));
-
- hash->allocnode = al ? al : kl_hnode_alloc;
- hash->freenode = fr ? fr : kl_hnode_free;
- hash->context = context;
-}
-
-/*
- * Free every node in the hash using the hash->freenode() function pointer, and
- * cause the hash to become empty.
- */
-
-void kl_hash_free_nodes(hash_t *hash)
-{
- hscan_t hs;
- hnode_t *node;
- kl_hash_scan_begin(&hs, hash);
- while ((node = kl_hash_scan_next(&hs))) {
- kl_hash_scan_delete(hash, node);
- hash->freenode(node, hash->context);
- }
- hash->nodecount = 0;
- clear_table(hash);
-}
-
-/*
- * Obsolescent function for removing all nodes from a table,
- * freeing them and then freeing the table all in one step.
- */
-
-void kl_hash_free(hash_t *hash)
-{
-#ifdef KAZLIB_OBSOLESCENT_DEBUG
- assert ("call to obsolescent function hash_free()" && 0);
-#endif
- kl_hash_free_nodes(hash);
- kl_hash_destroy(hash);
-}
-
-/*
- * Free a dynamic hash table structure.
- */
-
-void kl_hash_destroy(hash_t *hash)
-{
- assert (hash_val_t_bit != 0);
- assert (kl_hash_isempty(hash));
- free(hash->table);
- free(hash);
-}
-
-/*
- * Initialize a user supplied hash structure. The user also supplies a table of
- * chains which is assigned to the hash structure. The table is static---it
- * will not grow or shrink.
- * 1. See note 1. in hash_create().
- * 2. The user supplied array of pointers hopefully contains nchains nodes.
- * 3. See note 7. in hash_create().
- * 4. We must dynamically compute the mask from the given power of two table
- * size.
- * 5. The user supplied table can't be assumed to contain null pointers,
- * so we reset it here.
- */
-
-hash_t *kl_hash_init(hash_t *hash, hashcount_t maxcount,
- hash_comp_t compfun, hash_fun_t hashfun, hnode_t **table,
- hashcount_t nchains)
-{
- if (hash_val_t_bit == 0) /* 1 */
- compute_bits();
-
- assert (is_power_of_two(nchains));
-
- hash->table = table; /* 2 */
- hash->nchains = nchains;
- hash->nodecount = 0;
- hash->maxcount = maxcount;
- hash->compare = compfun ? compfun : hash_comp_default;
- hash->function = hashfun ? hashfun : hash_fun_default;
- hash->dynamic = 0; /* 3 */
- hash->mask = compute_mask(nchains); /* 4 */
- clear_table(hash); /* 5 */
-
- assert (kl_hash_verify(hash));
-
- return hash;
-}
-
-/*
- * Reset the hash scanner so that the next element retrieved by
- * hash_scan_next() shall be the first element on the first non-empty chain.
- * Notes:
- * 1. Locate the first non empty chain.
- * 2. If an empty chain is found, remember which one it is and set the next
- * pointer to refer to its first element.
- * 3. Otherwise if a chain is not found, set the next pointer to NULL
- * so that hash_scan_next() shall indicate failure.
- */
-
-void kl_hash_scan_begin(hscan_t *scan, hash_t *hash)
-{
- hash_val_t nchains = hash->nchains;
- hash_val_t chain;
-
- scan->table = hash;
-
- /* 1 */
-
- for (chain = 0; chain < nchains && hash->table[chain] == 0; chain++)
- ;
-
- if (chain < nchains) { /* 2 */
- scan->chain = chain;
- scan->next = hash->table[chain];
- } else { /* 3 */
- scan->next = NULL;
- }
-}
-
-/*
- * Retrieve the next node from the hash table, and update the pointer
- * for the next invocation of hash_scan_next().
- * Notes:
- * 1. Remember the next pointer in a temporary value so that it can be
- * returned.
- * 2. This assertion essentially checks whether the module has been properly
- * initialized. The first point of interaction with the module should be
- * either hash_create() or hash_init(), both of which set hash_val_t_bit to
- * a non zero value.
- * 3. If the next pointer we are returning is not NULL, then the user is
- * allowed to call hash_scan_next() again. We prepare the new next pointer
- * for that call right now. That way the user is allowed to delete the node
- * we are about to return, since we will no longer be needing it to locate
- * the next node.
- * 4. If there is a next node in the chain (next->next), then that becomes the
- * new next node, otherwise ...
- * 5. We have exhausted the current chain, and must locate the next subsequent
- * non-empty chain in the table.
- * 6. If a non-empty chain is found, the first element of that chain becomes
- * the new next node. Otherwise there is no new next node and we set the
- * pointer to NULL so that the next time hash_scan_next() is called, a null
- * pointer shall be immediately returned.
- */
-
-
-hnode_t *kl_hash_scan_next(hscan_t *scan)
-{
- hnode_t *next = scan->next; /* 1 */
- hash_t *hash = scan->table;
- hash_val_t chain = scan->chain + 1;
- hash_val_t nchains = hash->nchains;
-
- assert (hash_val_t_bit != 0); /* 2 */
-
- if (next) { /* 3 */
- if (next->next) { /* 4 */
- scan->next = next->next;
- } else {
- while (chain < nchains && hash->table[chain] == 0) /* 5 */
- chain++;
- if (chain < nchains) { /* 6 */
- scan->chain = chain;
- scan->next = hash->table[chain];
- } else {
- scan->next = NULL;
- }
- }
- }
- return next;
-}
-
-/*
- * Insert a node into the hash table.
- * Notes:
- * 1. It's illegal to insert more than the maximum number of nodes. The client
- * should verify that the hash table is not full before attempting an
- * insertion.
- * 2. The same key may not be inserted into a table twice.
- * 3. If the table is dynamic and the load factor is already at >= 2,
- * grow the table.
- * 4. We take the bottom N bits of the hash value to derive the chain index,
- * where N is the base 2 logarithm of the size of the hash table.
- */
-
-void kl_hash_insert(hash_t *hash, hnode_t *node, const void *key)
-{
- hash_val_t hkey, chain;
-
- assert (hash_val_t_bit != 0);
- assert (node->next == NULL);
- assert (hash->nodecount < hash->maxcount); /* 1 */
- assert (kl_hash_lookup(hash, key) == NULL); /* 2 */
-
- if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */
- grow_table(hash);
-
- hkey = hash->function(key);
- chain = hkey & hash->mask; /* 4 */
-
- node->key = key;
- node->hkey = hkey;
- node->next = hash->table[chain];
- hash->table[chain] = node;
- hash->nodecount++;
-
- assert (kl_hash_verify(hash));
-}
-
-/*
- * Find a node in the hash table and return a pointer to it.
- * Notes:
- * 1. We hash the key and keep the entire hash value. As an optimization, when
- * we descend down the chain, we can compare hash values first and only if
- * hash values match do we perform a full key comparison.
- * 2. To locate the chain from among 2^N chains, we look at the lower N bits of
- * the hash value by anding them with the current mask.
- * 3. Looping through the chain, we compare the stored hash value inside each
- * node against our computed hash. If they match, then we do a full
- * comparison between the unhashed keys. If these match, we have located the
- * entry.
- */
-
-hnode_t *kl_hash_lookup(hash_t *hash, const void *key)
-{
- hash_val_t hkey, chain;
- hnode_t *nptr;
-
- hkey = hash->function(key); /* 1 */
- chain = hkey & hash->mask; /* 2 */
-
- for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */
- if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
- return nptr;
- }
-
- return NULL;
-}
-
-/*
- * Delete the given node from the hash table. Since the chains
- * are singly linked, we must locate the start of the node's chain
- * and traverse.
- * Notes:
- * 1. The node must belong to this hash table, and its key must not have
- * been tampered with.
- * 2. If this deletion will take the node count below the low mark, we
- * shrink the table now.
- * 3. Determine which chain the node belongs to, and fetch the pointer
- * to the first node in this chain.
- * 4. If the node being deleted is the first node in the chain, then
- * simply update the chain head pointer.
- * 5. Otherwise advance to the node's predecessor, and splice out
- * by updating the predecessor's next pointer.
- * 6. Indicate that the node is no longer in a hash table.
- */
-
-hnode_t *kl_hash_delete(hash_t *hash, hnode_t *node)
-{
- hash_val_t chain;
- hnode_t *hptr;
-
- assert (kl_hash_lookup(hash, node->key) == node); /* 1 */
- assert (hash_val_t_bit != 0);
-
- if (hash->dynamic && hash->nodecount <= hash->lowmark
- && hash->nodecount > INIT_SIZE)
- shrink_table(hash); /* 2 */
-
- chain = node->hkey & hash->mask; /* 3 */
- hptr = hash->table[chain];
-
- if (hptr == node) { /* 4 */
- hash->table[chain] = node->next;
- } else {
- while (hptr->next != node) { /* 5 */
- assert (hptr != 0);
- hptr = hptr->next;
- }
- assert (hptr->next == node);
- hptr->next = node->next;
- }
-
- hash->nodecount--;
- assert (kl_hash_verify(hash));
-
- node->next = NULL; /* 6 */
- return node;
-}
-
-int kl_hash_alloc_insert(hash_t *hash, const void *key, void *data)
-{
- hnode_t *node = hash->allocnode(hash->context);
-
- if (node) {
- kl_hnode_init(node, data);
- kl_hash_insert(hash, node, key);
- return 1;
- }
- return 0;
-}
-
-void kl_hash_delete_free(hash_t *hash, hnode_t *node)
-{
- kl_hash_delete(hash, node);
- hash->freenode(node, hash->context);
-}
-
-/*
- * Exactly like hash_delete, except does not trigger table shrinkage. This is to be
- * used from within a hash table scan operation. See notes for hash_delete.
- */
-
-hnode_t *kl_hash_scan_delete(hash_t *hash, hnode_t *node)
-{
- hash_val_t chain;
- hnode_t *hptr;
-
- assert (kl_hash_lookup(hash, node->key) == node);
- assert (hash_val_t_bit != 0);
-
- chain = node->hkey & hash->mask;
- hptr = hash->table[chain];
-
- if (hptr == node) {
- hash->table[chain] = node->next;
- } else {
- while (hptr->next != node)
- hptr = hptr->next;
- hptr->next = node->next;
- }
-
- hash->nodecount--;
- assert (kl_hash_verify(hash));
- node->next = NULL;
-
- return node;
-}
-
-/*
- * Like hash_delete_free but based on hash_scan_delete.
- */
-
-void kl_hash_scan_delfree(hash_t *hash, hnode_t *node)
-{
- kl_hash_scan_delete(hash, node);
- hash->freenode(node, hash->context);
-}
-
-/*
- * Verify whether the given object is a valid hash table. This means
- * Notes:
- * 1. If the hash table is dynamic, verify whether the high and
- * low expansion/shrinkage thresholds are powers of two.
- * 2. Count all nodes in the table, and test each hash value
- * to see whether it is correct for the node's chain.
- */
-
-int kl_hash_verify(hash_t *hash)
-{
- hashcount_t count = 0;
- hash_val_t chain;
- hnode_t *hptr;
-
- if (hash->dynamic) { /* 1 */
- if (hash->lowmark >= hash->highmark)
- return 0;
- if (!is_power_of_two(hash->highmark))
- return 0;
- if (!is_power_of_two(hash->lowmark))
- return 0;
- }
-
- for (chain = 0; chain < hash->nchains; chain++) { /* 2 */
- for (hptr = hash->table[chain]; hptr != 0; hptr = hptr->next) {
- if ((hptr->hkey & hash->mask) != chain)
- return 0;
- count++;
- }
- }
-
- if (count != hash->nodecount)
- return 0;
-
- return 1;
-}
-
-/*
- * Test whether the hash table is full and return 1 if this is true,
- * 0 if it is false.
- */
-
-#undef kl_hash_isfull
-int kl_hash_isfull(hash_t *hash)
-{
- return hash->nodecount == hash->maxcount;
-}
-
-/*
- * Test whether the hash table is empty and return 1 if this is true,
- * 0 if it is false.
- */
-
-#undef kl_hash_isempty
-int kl_hash_isempty(hash_t *hash)
-{
- return hash->nodecount == 0;
-}
-
-static hnode_t *kl_hnode_alloc(void *context)
-{
- return malloc(sizeof *kl_hnode_alloc(NULL));
-}
-
-static void kl_hnode_free(hnode_t *node, void *context)
-{
- free(node);
-}
-
-
-/*
- * Create a hash table node dynamically and assign it the given data.
- */
-
-hnode_t *kl_hnode_create(void *data)
-{
- hnode_t *node = malloc(sizeof *node);
- if (node) {
- node->data = data;
- node->next = NULL;
- }
- return node;
-}
-
-/*
- * Initialize a client-supplied node
- */
-
-hnode_t *kl_hnode_init(hnode_t *hnode, void *data)
-{
- hnode->data = data;
- hnode->next = NULL;
- return hnode;
-}
-
-/*
- * Destroy a dynamically allocated node.
- */
-
-void kl_hnode_destroy(hnode_t *hnode)
-{
- free(hnode);
-}
-
-#undef kl_hnode_put
-void kl_hnode_put(hnode_t *node, void *data)
-{
- node->data = data;
-}
-
-#undef kl_hnode_get
-void *kl_hnode_get(hnode_t *node)
-{
- return node->data;
-}
-
-#undef kl_hnode_getkey
-const void *kl_hnode_getkey(hnode_t *node)
-{
- return node->key;
-}
-
-#undef kl_hash_count
-hashcount_t kl_hash_count(hash_t *hash)
-{
- return hash->nodecount;
-}
-
-#undef kl_hash_size
-hashcount_t kl_hash_size(hash_t *hash)
-{
- return hash->nchains;
-}
-
-static hash_val_t hash_fun_default(const void *key)
-{
- static unsigned long randbox[] = {
- 0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U,
- 0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU,
- 0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU,
- 0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU,
- };
-
- const unsigned char *str = key;
- hash_val_t acc = 0;
-
- while (*str) {
- acc ^= randbox[(*str + acc) & 0xf];
- acc = (acc << 1) | (acc >> 31);
- acc &= 0xffffffffU;
- acc ^= randbox[((*str++ >> 4) + acc) & 0xf];
- acc = (acc << 2) | (acc >> 30);
- acc &= 0xffffffffU;
- }
- return acc;
-}
-
-static int hash_comp_default(const void *key1, const void *key2)
-{
- return strcmp(key1, key2);
-}
diff --git a/c_src/hash.h b/c_src/hash.h
deleted file mode 100644
index 0c75ed0..0000000
--- a/c_src/hash.h
+++ /dev/null
@@ -1,240 +0,0 @@
-/*
- * Hash Table Data Type
- * Copyright (C) 1997 Kaz Kylheku <ka...@ashi.footprints.net>
- *
- * Free Software License:
- *
- * All rights are reserved by the author, with the following exceptions:
- * Permission is granted to freely reproduce and distribute this software,
- * possibly in exchange for a fee, provided that this copyright notice appears
- * intact. Permission is also granted to adapt this software to produce
- * derivative works, as long as the modified versions carry this copyright
- * notice and additional notices stating that the work has been modified.
- * This source code may be translated into executable form and incorporated
- * into proprietary software; there is no requirement for such software to
- * contain a copyright notice related to this source.
- *
- * $Id: hash.h,v 1.22.2.7 2000/11/13 01:36:45 kaz Exp $
- * $Name: kazlib_1_20 $
- */
-
-#ifndef HASH_H
-#define HASH_H
-
-#include <limits.h>
-#ifdef KAZLIB_SIDEEFFECT_DEBUG
-#include "sfx.h"
-#endif
-
-/*
- * Blurb for inclusion into C++ translation units
- */
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-typedef unsigned long hashcount_t;
-#define HASHCOUNT_T_MAX ULONG_MAX
-
-typedef unsigned long hash_val_t;
-#define HASH_VAL_T_MAX ULONG_MAX
-
-extern int hash_val_t_bit;
-
-#ifndef HASH_VAL_T_BIT
-#define HASH_VAL_T_BIT ((int) hash_val_t_bit)
-#endif
-
-/*
- * Hash chain node structure.
- * Notes:
- * 1. This preprocessing directive is for debugging purposes. The effect is
- * that if the preprocessor symbol KAZLIB_OPAQUE_DEBUG is defined prior to the
- * inclusion of this header, then the structure shall be declared as having
- * the single member int __OPAQUE__. This way, any attempts by the
- * client code to violate the principles of information hiding (by accessing
- * the structure directly) can be diagnosed at translation time. However,
- * note the resulting compiled unit is not suitable for linking.
- * 2. This is a pointer to the next node in the chain. In the last node of a
- * chain, this pointer is null.
- * 3. The key is a pointer to some user supplied data that contains a unique
- * identifier for each hash node in a given table. The interpretation of
- * the data is up to the user. When creating or initializing a hash table,
- * the user must supply a pointer to a function for comparing two keys,
- * and a pointer to a function for hashing a key into a numeric value.
- * 4. The value is a user-supplied pointer to void which may refer to
- * any data object. It is not interpreted in any way by the hashing
- * module.
- * 5. The hashed key is stored in each node so that we don't have to rehash
- * each key when the table must grow or shrink.
- */
-
-typedef struct hnode_t {
- #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG) /* 1 */
- struct hnode_t *hash_next; /* 2 */
- const void *hash_key; /* 3 */
- void *hash_data; /* 4 */
- hash_val_t hash_hkey; /* 5 */
- #else
- int hash_dummy;
- #endif
-} hnode_t;
-
-/*
- * The comparison function pointer type. A comparison function takes two keys
- * and produces a value of -1 if the left key is less than the right key, a
- * value of 0 if the keys are equal, and a value of 1 if the left key is
- * greater than the right key.
- */
-
-typedef int (*hash_comp_t)(const void *, const void *);
-
-/*
- * The hashing function performs some computation on a key and produces an
- * integral value of type hash_val_t based on that key. For best results, the
- * function should have a good randomness properties in *all* significant bits
- * over the set of keys that are being inserted into a given hash table. In
- * particular, the most significant bits of hash_val_t are most significant to
- * the hash module. Only as the hash table expands are less significant bits
- * examined. Thus a function that has good distribution in its upper bits but
- * not lower is preferrable to one that has poor distribution in the upper bits
- * but not the lower ones.
- */
-
-typedef hash_val_t (*hash_fun_t)(const void *);
-
-/*
- * allocator functions
- */
-
-typedef hnode_t *(*hnode_alloc_t)(void *);
-typedef void (*hnode_free_t)(hnode_t *, void *);
-
-/*
- * This is the hash table control structure. It keeps track of information
- * about a hash table, as well as the hash table itself.
- * Notes:
- * 1. Pointer to the hash table proper. The table is an array of pointers to
- * hash nodes (of type hnode_t). If the table is empty, every element of
- * this table is a null pointer. A non-null entry points to the first
- * element of a chain of nodes.
- * 2. This member keeps track of the size of the hash table---that is, the
- * number of chain pointers.
- * 3. The count member maintains the number of elements that are presently
- * in the hash table.
- * 4. The maximum count is the greatest number of nodes that can populate this
- * table. If the table contains this many nodes, no more can be inserted,
- * and the hash_isfull() function returns true.
- * 5. The high mark is a population threshold, measured as a number of nodes,
- * which, if exceeded, will trigger a table expansion. Only dynamic hash
- * tables are subject to this expansion.
- * 6. The low mark is a minimum population threshold, measured as a number of
- * nodes. If the table population drops below this value, a table shrinkage
- * will occur. Only dynamic tables are subject to this reduction. No table
- * will shrink beneath a certain absolute minimum number of nodes.
- * 7. This is the a pointer to the hash table's comparison function. The
- * function is set once at initialization or creation time.
- * 8. Pointer to the table's hashing function, set once at creation or
- * initialization time.
- * 9. The current hash table mask. If the size of the hash table is 2^N,
- * this value has its low N bits set to 1, and the others clear. It is used
- * to select bits from the result of the hashing function to compute an
- * index into the table.
- * 10. A flag which indicates whether the table is to be dynamically resized. It
- * is set to 1 in dynamically allocated tables, 0 in tables that are
- * statically allocated.
- */
-
-typedef struct hash_t {
- #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
- struct hnode_t **hash_table; /* 1 */
- hashcount_t hash_nchains; /* 2 */
- hashcount_t hash_nodecount; /* 3 */
- hashcount_t hash_maxcount; /* 4 */
- hashcount_t hash_highmark; /* 5 */
- hashcount_t hash_lowmark; /* 6 */
- hash_comp_t hash_compare; /* 7 */
- hash_fun_t hash_function; /* 8 */
- hnode_alloc_t hash_allocnode;
- hnode_free_t hash_freenode;
- void *hash_context;
- hash_val_t hash_mask; /* 9 */
- int hash_dynamic; /* 10 */
- #else
- int hash_dummy;
- #endif
-} hash_t;
-
-/*
- * Hash scanner structure, used for traversals of the data structure.
- * Notes:
- * 1. Pointer to the hash table that is being traversed.
- * 2. Reference to the current chain in the table being traversed (the chain
- * that contains the next node that shall be retrieved).
- * 3. Pointer to the node that will be retrieved by the subsequent call to
- * hash_scan_next().
- */
-
-typedef struct hscan_t {
- #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
- hash_t *hash_table; /* 1 */
- hash_val_t hash_chain; /* 2 */
- hnode_t *hash_next; /* 3 */
- #else
- int hash_dummy;
- #endif
-} hscan_t;
-
-extern hash_t *kl_hash_create(hashcount_t, hash_comp_t, hash_fun_t);
-extern void kl_hash_set_allocator(hash_t *, hnode_alloc_t, hnode_free_t, void *);
-extern void kl_hash_destroy(hash_t *);
-extern void kl_hash_free_nodes(hash_t *);
-extern void kl_hash_free(hash_t *);
-extern hash_t *kl_hash_init(hash_t *, hashcount_t, hash_comp_t,
- hash_fun_t, hnode_t **, hashcount_t);
-extern void kl_hash_insert(hash_t *, hnode_t *, const void *);
-extern hnode_t *kl_hash_lookup(hash_t *, const void *);
-extern hnode_t *kl_hash_delete(hash_t *, hnode_t *);
-extern int kl_hash_alloc_insert(hash_t *, const void *, void *);
-extern void kl_hash_delete_free(hash_t *, hnode_t *);
-
-extern void kl_hnode_put(hnode_t *, void *);
-extern void *kl_hnode_get(hnode_t *);
-extern const void *kl_hnode_getkey(hnode_t *);
-extern hashcount_t kl_hash_count(hash_t *);
-extern hashcount_t kl_hash_size(hash_t *);
-
-extern int kl_hash_isfull(hash_t *);
-extern int kl_hash_isempty(hash_t *);
-
-extern void kl_hash_scan_begin(hscan_t *, hash_t *);
-extern hnode_t *kl_hash_scan_next(hscan_t *);
-extern hnode_t *kl_hash_scan_delete(hash_t *, hnode_t *);
-extern void kl_hash_scan_delfree(hash_t *, hnode_t *);
-
-extern int kl_hash_verify(hash_t *);
-
-extern hnode_t *kl_hnode_create(void *);
-extern hnode_t *kl_hnode_init(hnode_t *, void *);
-extern void kl_hnode_destroy(hnode_t *);
-
-#if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
-#ifdef KAZLIB_SIDEEFFECT_DEBUG
-#define kl_hash_isfull(H) (SFX_CHECK(H)->hash_nodecount == (H)->hash_maxcount)
-#else
-#define kl_hash_isfull(H) ((H)->hash_nodecount == (H)->hash_maxcount)
-#endif
-#define kl_hash_isempty(H) ((H)->hash_nodecount == 0)
-#define kl_hash_count(H) ((H)->hash_nodecount)
-#define kl_hash_size(H) ((H)->hash_nchains)
-#define kl_hnode_get(N) ((N)->hash_data)
-#define kl_hnode_getkey(N) ((N)->hash_key)
-#define kl_hnode_put(N, V) ((N)->hash_data = (V))
-#endif
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif
diff --git a/c_src/khash.c b/c_src/khash.c
deleted file mode 100644
index b15a18e..0000000
--- a/c_src/khash.c
+++ /dev/null
@@ -1,658 +0,0 @@
-// This file is part of khash released under the MIT license.
-// See the LICENSE file for more information.
-// Copyright 2013 Cloudant, Inc <su...@cloudant.com>
-
-#include <assert.h>
-#include <string.h>
-#include <stdint.h>
-
-#include "erl_nif.h"
-#include "hash.h"
-
-#ifdef _WIN32
-#define INLINE __inline
-#else
-#define INLINE inline
-#endif
-
-#define KHASH_VERSION 0
-
-
-typedef struct
-{
- ERL_NIF_TERM atom_ok;
- ERL_NIF_TERM atom_error;
- ERL_NIF_TERM atom_value;
- ERL_NIF_TERM atom_not_found;
- ERL_NIF_TERM atom_end_of_table;
- ERL_NIF_TERM atom_expired_iterator;
- ErlNifResourceType* res_hash;
- ErlNifResourceType* res_iter;
-} khash_priv;
-
-
-typedef struct
-{
- unsigned int hval;
- ErlNifEnv* env;
- ERL_NIF_TERM key;
- ERL_NIF_TERM val;
-} khnode_t;
-
-
-typedef struct
-{
- int version;
- unsigned int gen;
- hash_t* h;
- ErlNifPid p;
-} khash_t;
-
-
-typedef struct
-{
- int version;
- unsigned int gen;
- khash_t* khash;
- hscan_t scan;
-} khash_iter_t;
-
-
-static INLINE ERL_NIF_TERM
-make_atom(ErlNifEnv* env, const char* name)
-{
- ERL_NIF_TERM ret;
- if(enif_make_existing_atom(env, name, &ret, ERL_NIF_LATIN1)) {
- return ret;
- }
- return enif_make_atom(env, name);
-}
-
-
-static INLINE ERL_NIF_TERM
-make_ok(ErlNifEnv* env, khash_priv* priv, ERL_NIF_TERM value)
-{
- return enif_make_tuple2(env, priv->atom_ok, value);
-}
-
-
-static INLINE ERL_NIF_TERM
-make_error(ErlNifEnv* env, khash_priv* priv, ERL_NIF_TERM reason)
-{
- return enif_make_tuple2(env, priv->atom_error, reason);
-}
-
-
-static INLINE int
-check_pid(ErlNifEnv* env, khash_t* khash)
-{
- ErlNifPid pid;
- enif_self(env, &pid);
-
- if(enif_compare(pid.pid, khash->p.pid) == 0) {
- return 1;
- }
-
- return 0;
-}
-
-
-hnode_t*
-khnode_alloc(void* ctx)
-{
- hnode_t* ret = (hnode_t*) enif_alloc(sizeof(hnode_t));
- khnode_t* node = (khnode_t*) enif_alloc(sizeof(khnode_t));
-
- memset(ret, '\0', sizeof(hnode_t));
- memset(node, '\0', sizeof(khnode_t));
-
- node->env = enif_alloc_env();
- ret->hash_key = node;
-
- return ret;
-}
-
-
-void
-khnode_free(hnode_t* obj, void* ctx)
-{
- khnode_t* node = (khnode_t*) kl_hnode_getkey(obj);
- enif_free_env(node->env);
- enif_free(node);
- enif_free(obj);
- return;
-}
-
-
-int
-khash_cmp_fun(const void* l, const void* r)
-{
- khnode_t* left = (khnode_t*) l;
- khnode_t* right = (khnode_t*) r;
- int cmp = enif_compare(left->key, right->key);
-
- if(cmp < 0) {
- return -1;
- } else if(cmp == 0) {
- return 0;
- } else {
- return 1;
- }
-}
-
-
-hash_val_t
-khash_hash_fun(const void* obj)
-{
- khnode_t* node = (khnode_t*) obj;
- return (hash_val_t) node->hval;
-}
-
-
-static INLINE khash_t*
-khash_create_int(ErlNifEnv* env, khash_priv* priv, ERL_NIF_TERM opts)
-{
- khash_t* khash = NULL;
-
- assert(priv != NULL && "missing private data member");
-
- khash = (khash_t*) enif_alloc_resource(priv->res_hash, sizeof(khash_t));
- memset(khash, '\0', sizeof(khash_t));
- khash->version = KHASH_VERSION;
- khash->gen = 0;
-
- khash->h = kl_hash_create(HASHCOUNT_T_MAX, khash_cmp_fun, khash_hash_fun);
-
- if(khash->h == NULL ) {
- enif_release_resource(khash);
- return NULL;
- }
-
- kl_hash_set_allocator(khash->h, khnode_alloc, khnode_free, NULL);
- enif_self(env, &(khash->p));
-
- return khash;
-}
-
-
-static ERL_NIF_TERM
-khash_new(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash;
- ERL_NIF_TERM ret;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- khash = khash_create_int(env, priv, argv[0]);
- if(khash == NULL) {
- return enif_make_badarg(env);
- }
-
- ret = enif_make_resource(env, khash);
- enif_release_resource(khash);
-
- return make_ok(env, priv, ret);
-}
-
-
-static void
-khash_free(ErlNifEnv* env, void* obj)
-{
- khash_t* khash = (khash_t*) obj;
-
- if(khash->h != NULL) {
- kl_hash_free_nodes(khash->h);
- kl_hash_destroy(khash->h);
- }
-
- return;
-}
-
-
-static ERL_NIF_TERM
-khash_to_list(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = (khash_priv*) enif_priv_data(env);
- ERL_NIF_TERM ret = enif_make_list(env, 0);
- khash_t* khash = NULL;
- void* res = NULL;
- hscan_t scan;
- hnode_t* entry;
- khnode_t* node;
- ERL_NIF_TERM key;
- ERL_NIF_TERM val;
- ERL_NIF_TERM tuple;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- kl_hash_scan_begin(&scan, khash->h);
-
- while((entry = kl_hash_scan_next(&scan)) != NULL) {
- node = (khnode_t*) kl_hnode_getkey(entry);
- key = enif_make_copy(env, node->key);
- val = enif_make_copy(env, node->val);
- tuple = enif_make_tuple2(env, key, val);
- ret = enif_make_list_cell(env, tuple, ret);
- }
-
- return ret;
-}
-
-
-static ERL_NIF_TERM
-khash_clear(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- kl_hash_free_nodes(khash->h);
-
- khash->gen += 1;
-
- return priv->atom_ok;
-}
-
-
-static INLINE hnode_t*
-khash_lookup_int(ErlNifEnv* env, uint32_t hv, ERL_NIF_TERM key, khash_t* khash)
-{
- khnode_t node;
- node.hval = hv;
- node.env = env;
- node.key = key;
- return kl_hash_lookup(khash->h, &node);
-}
-
-
-static ERL_NIF_TERM
-khash_lookup(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
- uint32_t hval;
- hnode_t* entry;
- khnode_t* node;
- ERL_NIF_TERM ret;
-
- if(argc != 3) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_uint(env, argv[1], &hval)) {
- return enif_make_badarg(env);
- }
-
- entry = khash_lookup_int(env, hval, argv[2], khash);
- if(entry == NULL) {
- ret = priv->atom_not_found;
- } else {
- node = (khnode_t*) kl_hnode_getkey(entry);
- ret = enif_make_copy(env, node->val);
- ret = enif_make_tuple2(env, priv->atom_value, ret);
- }
-
- return ret;
-}
-
-
-static ERL_NIF_TERM
-khash_get(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
- uint32_t hval;
- hnode_t* entry;
- khnode_t* node;
- ERL_NIF_TERM ret;
-
- if(argc != 4) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_uint(env, argv[1], &hval)) {
- return enif_make_badarg(env);
- }
-
- entry = khash_lookup_int(env, hval, argv[2], khash);
- if(entry == NULL) {
- ret = argv[3];
- } else {
- node = (khnode_t*) kl_hnode_getkey(entry);
- ret = enif_make_copy(env, node->val);
- }
-
- return ret;
-}
-
-
-static ERL_NIF_TERM
-khash_put(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
- uint32_t hval;
- hnode_t* entry;
- khnode_t* node;
-
- if(argc != 4) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_uint(env, argv[1], &hval)) {
- return enif_make_badarg(env);
- }
-
- entry = khash_lookup_int(env, hval, argv[2], khash);
- if(entry == NULL) {
- entry = khnode_alloc(NULL);
- node = (khnode_t*) kl_hnode_getkey(entry);
- node->hval = hval;
- node->key = enif_make_copy(node->env, argv[2]);
- node->val = enif_make_copy(node->env, argv[3]);
- kl_hash_insert(khash->h, entry, node);
- } else {
- node = (khnode_t*) kl_hnode_getkey(entry);
- enif_clear_env(node->env);
- node->key = enif_make_copy(node->env, argv[2]);
- node->val = enif_make_copy(node->env, argv[3]);
- }
-
- khash->gen += 1;
-
- return priv->atom_ok;
-}
-
-
-static ERL_NIF_TERM
-khash_del(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
- uint32_t hval;
- hnode_t* entry;
- ERL_NIF_TERM ret;
-
- if(argc != 3) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_uint(env, argv[1], &hval)) {
- return enif_make_badarg(env);
- }
-
- entry = khash_lookup_int(env, hval, argv[2], khash);
- if(entry == NULL) {
- ret = priv->atom_not_found;
- } else {
- kl_hash_delete_free(khash->h, entry);
- ret = priv->atom_ok;
- }
-
- khash->gen += 1;
-
- return ret;
-}
-
-
-static ERL_NIF_TERM
-khash_size(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, (void*) &khash)) {
- return enif_make_badarg(env);
- }
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- return enif_make_uint64(env, kl_hash_count(khash->h));
-}
-
-
-static ERL_NIF_TERM
-khash_iter(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_t* khash = NULL;
- void* res = NULL;
- khash_iter_t* iter;
- ERL_NIF_TERM ret;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_hash, &res)) {
- return enif_make_badarg(env);
- }
-
- khash = (khash_t*) res;
-
- if(!check_pid(env, khash)) {
- return enif_make_badarg(env);
- }
-
- iter = (khash_iter_t*) enif_alloc_resource(
- priv->res_iter, sizeof(khash_iter_t));
- memset(iter, '\0', sizeof(khash_iter_t));
- iter->version = KHASH_VERSION;
- iter->gen = khash->gen;
- iter->khash = khash;
- kl_hash_scan_begin(&(iter->scan), iter->khash->h);
-
- // The iterator needs to guarantee that the khash
- // remains alive for the life of the iterator.
- enif_keep_resource(khash);
-
- ret = enif_make_resource(env, iter);
- enif_release_resource(iter);
-
- return make_ok(env, priv, ret);
-}
-
-
-static void
-khash_iter_free(ErlNifEnv* env, void* obj)
-{
- khash_iter_t* iter = (khash_iter_t*) obj;
- enif_release_resource(iter->khash);
-}
-
-
-static ERL_NIF_TERM
-khash_iter_next(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
-{
- khash_priv* priv = enif_priv_data(env);
- khash_iter_t* iter = NULL;
- void* res = NULL;
- hnode_t* entry;
- khnode_t* node;
- ERL_NIF_TERM key;
- ERL_NIF_TERM val;
-
- if(argc != 1) {
- return enif_make_badarg(env);
- }
-
- if(!enif_get_resource(env, argv[0], priv->res_iter, &res)) {
- return enif_make_badarg(env);
- }
-
- iter = (khash_iter_t*) res;
-
- if(!check_pid(env, iter->khash)) {
- return enif_make_badarg(env);
- }
-
- if(iter->gen != iter->khash->gen) {
- return make_error(env, priv, priv->atom_expired_iterator);
- }
-
- entry = kl_hash_scan_next(&(iter->scan));
- if(entry == NULL) {
- return priv->atom_end_of_table;
- }
-
- node = (khnode_t*) kl_hnode_getkey(entry);
- key = enif_make_copy(env, node->key);
- val = enif_make_copy(env, node->val);
- return enif_make_tuple2(env, key, val);
-}
-
-
-static int
-load(ErlNifEnv* env, void** priv, ERL_NIF_TERM info)
-{
- int flags = ERL_NIF_RT_CREATE | ERL_NIF_RT_TAKEOVER;
- ErlNifResourceType* res;
-
- khash_priv* new_priv = (khash_priv*) enif_alloc(sizeof(khash_priv));
- if(new_priv == NULL) {
- return 1;
- }
-
- res = enif_open_resource_type(
- env, NULL, "khash", khash_free, flags, NULL);
- if(res == NULL) {
- return 1;
- }
- new_priv->res_hash = res;
-
- res = enif_open_resource_type(
- env, NULL, "khash_iter", khash_iter_free, flags, NULL);
- if(res == NULL) {
- return 1;
- }
- new_priv->res_iter = res;
-
- new_priv->atom_ok = make_atom(env, "ok");
- new_priv->atom_error = make_atom(env, "error");
- new_priv->atom_value = make_atom(env, "value");
- new_priv->atom_not_found = make_atom(env, "not_found");
- new_priv->atom_end_of_table = make_atom(env, "end_of_table");
- new_priv->atom_expired_iterator = make_atom(env, "expired_iterator");
-
- *priv = (void*) new_priv;
-
- return 0;
-}
-
-
-static int
-reload(ErlNifEnv* env, void** priv, ERL_NIF_TERM info)
-{
- return 0;
-}
-
-
-static int
-upgrade(ErlNifEnv* env, void** priv, void** old_priv, ERL_NIF_TERM info)
-{
- return load(env, priv, info);
-}
-
-
-static void
-unload(ErlNifEnv* env, void* priv)
-{
- enif_free(priv);
- return;
-}
-
-
-static ErlNifFunc funcs[] = {
- {"new", 1, khash_new},
- {"to_list", 1, khash_to_list},
- {"clear", 1, khash_clear},
- {"lookup_int", 3, khash_lookup},
- {"get_int", 4, khash_get},
- {"put_int", 4, khash_put},
- {"del_int", 3, khash_del},
- {"size", 1, khash_size},
- {"iter", 1, khash_iter},
- {"iter_next", 1, khash_iter_next}
-};
-
-
-ERL_NIF_INIT(khash, funcs, &load, &reload, &upgrade, &unload);
diff --git a/rebar.config b/rebar.config
deleted file mode 100644
index 0bf93a8..0000000
--- a/rebar.config
+++ /dev/null
@@ -1,14 +0,0 @@
-% vim: set ft=erlang : -*- erlang -*- % Magic lines for code editors
-
-{port_specs, [
- {"priv/khash.so", ["c_src/*.c"]}
-]}.
-
-{port_env, [
- % Development compilation
- % {".*", "CFLAGS", "$CFLAGS -g -Wall -Werror -fPIC"}
-
- % Production compilation
- {"(linux|solaris|darwin|freebsd)", "CFLAGS", "$CFLAGS -Wall -Werror -DNDEBUG -O3"},
- {"win32", "CFLAGS", "$CFLAGS /O2 /DNDEBUG /Wall"}
-]}.
diff --git a/src/khash.app.src b/src/khash.app.src
deleted file mode 100644
index 14a45c7..0000000
--- a/src/khash.app.src
+++ /dev/null
@@ -1,10 +0,0 @@
-%% This file is part of khash released under the MIT license.
-%% See the LICENSE file for more information.
-%% Copyright 2013 Cloudant, Inc <su...@cloudant.com>
-
-{application, khash, [
- {description, "A NIF wrapper for Kazlib's hash structure."},
- {vsn, git},
- {registered, []},
- {applications, [kernel]}
-]}.
diff --git a/src/khash.erl b/src/khash.erl
deleted file mode 100644
index daaf5ea..0000000
--- a/src/khash.erl
+++ /dev/null
@@ -1,157 +0,0 @@
-%% This file is part of khash released under the MIT license.
-%% See the LICENSE file for more information.
-%% Copyright 2013 Cloudant, Inc <su...@cloudant.com>
-
--module(khash).
--on_load(init/0).
-
-
--export([
- new/0,
- new/1,
- from_list/1,
- from_list/2,
- to_list/1,
- clear/1,
- lookup/2,
- get/2,
- get/3,
- put/3,
- del/2,
- size/1,
- iter/1,
- iter_next/1,
- fold/3
-]).
-
-
--define(NOT_LOADED, not_loaded(?LINE)).
-
-
--type kv() :: {any(), any()}.
--type khash() :: term().
--type khash_iter() :: term().
--type option() :: [].
-
-
--spec new() -> {ok, khash()}.
-new() ->
- new([]).
-
-
--spec new([option()]) -> {ok, khash()}.
-new(_Options) ->
- ?NOT_LOADED.
-
-
--spec from_list([kv()]) -> {ok, khash()}.
-from_list(KVList) ->
- from_list(KVList, []).
-
-
--spec from_list([kv()], [option()]) -> {ok, khash()}.
-from_list(KVList, Options) ->
- {ok, Hash} = ?MODULE:new(Options),
- lists:foreach(fun({Key, Val}) ->
- ?MODULE:put(Hash, Key, Val)
- end, KVList),
- {ok, Hash}.
-
-
--spec to_list(khash()) -> [kv()].
-to_list(_Hash) ->
- ?NOT_LOADED.
-
-
--spec clear(khash()) -> ok.
-clear(_Hash) ->
- ?NOT_LOADED.
-
-
--spec lookup(khash(), any()) -> {value, any()} | not_found.
-lookup(Hash, Key) ->
- lookup_int(Hash, erlang:phash2(Key), Key).
-
-
--spec get(khash(), any()) -> any().
-get(Hash, Key) ->
- get(Hash, Key, undefined).
-
-
--spec get(khash(), any(), any()) -> any().
-get(Hash, Key, Default) ->
- get_int(Hash, erlang:phash2(Key), Key, Default).
-
-
--spec put(khash(), any(), any()) -> ok.
-put(Hash, Key, Value) ->
- put_int(Hash, erlang:phash2(Key), Key, Value).
-
-
--spec del(khash(), any()) -> ok.
-del(Hash, Key) ->
- del_int(Hash, erlang:phash2(Key), Key).
-
-
--spec size(khash()) -> non_neg_integer().
-size(_Hash) ->
- ?NOT_LOADED.
-
-
--spec iter(khash()) -> {ok, khash_iter()}.
-iter(_Hash) ->
- ?NOT_LOADED.
-
-
--spec iter_next(khash_iter()) ->
- kv() | end_of_table | {error, expired_iterator}.
-iter_next(_Iter) ->
- ?NOT_LOADED.
-
-
--spec fold(khash(), fun(), any()) -> any().
-fold(Hash, FoldFun, Acc) ->
- {ok, Iter} = ?MODULE:iter(Hash),
- fold_int(Iter, FoldFun, Acc).
-
-
-fold_int(Iter, FoldFun, Acc) ->
- case ?MODULE:iter_next(Iter) of
- {Key, Value} ->
- NewAcc = FoldFun(Key, Value, Acc),
- fold_int(Iter, FoldFun, NewAcc);
- end_of_table ->
- Acc
- end.
-
-
-init() ->
- PrivDir = case code:priv_dir(?MODULE) of
- {error, _} ->
- EbinDir = filename:dirname(code:which(?MODULE)),
- AppPath = filename:dirname(EbinDir),
- filename:join(AppPath, "priv");
- Path ->
- Path
- end,
- erlang:load_nif(filename:join(PrivDir, "khash"), 0).
-
-
-lookup_int(_Hash, _HashValue, _Key) ->
- ?NOT_LOADED.
-
-
-get_int(_Hash, _HashValue, _Key, _Default) ->
- ?NOT_LOADED.
-
-
-put_int(_Hash, _HashValue, _Key, _Value) ->
- ?NOT_LOADED.
-
-
-del_int(_Hash, _HashValue, _Key) ->
- ?NOT_LOADED.
-
-
-not_loaded(Line) ->
- erlang:nif_error({not_loaded, [{module, ?MODULE}, {line, Line}]}).
diff --git a/test/gen_term.erl b/test/gen_term.erl
deleted file mode 100644
index 08d9f35..0000000
--- a/test/gen_term.erl
+++ /dev/null
@@ -1,131 +0,0 @@
-%% This file is part of khash released under the MIT license.
-%% See the LICENSE file for more information.
-%% Copyright 2013 Cloudant, Inc <su...@cloudant.com>
-
--module(gen_term).
-
--export([
- any/0,
- any/1,
-
- gen_atom/1,
- gen_integer/1,
- gen_float/1,
- gen_reference/1,
- gen_port/1,
- gen_pid/1,
- gen_tuple/1,
- gen_list/1,
- gen_short_string/1,
- gen_string/1,
- gen_binary/1,
- gen_bitstring/1,
- gen_bignum/1,
- gen_function/1
-]).
-
-
-any() ->
- any(16).
-
-
-any(MaxSize) when MaxSize =< 0 ->
- Fun = choice(value_types()),
- ?MODULE:Fun(MaxSize);
-any(MaxSize) ->
- Fun = choice(all_types()),
- ?MODULE:Fun(MaxSize).
-
-
-gen_atom(MaxSize) ->
- list_to_atom(gen_short_string(MaxSize)).
-
-
-gen_integer(_) ->
- Value = case rand:uniform() < 0.5 of
- true -> rand:uniform(127);
- false -> rand:uniform(16#FFFFFFFF)
- end,
- case rand:uniform() < 0.5 of
- true -> -1 * Value;
- false -> Value
- end.
-
-
-gen_float(_) ->
- rand:uniform() * float(16#FFFFFFFF).
-
-
-gen_reference(_) ->
- erlang:make_ref().
-
-
-gen_port(_) ->
- Ports = erlang:ports(),
- lists:nth(rand:uniform(length(Ports)), Ports).
-
-
-gen_pid(_) ->
- Pids = erlang:processes(),
- lists:nth(rand:uniform(length(Pids)), Pids).
-
-
-gen_tuple(MaxSize) ->
- list_to_tuple(gen_list(MaxSize)).
-
-
-gen_list(MaxSize) ->
- Width = rand:uniform(MaxSize),
- [any(MaxSize-Width) || _ <- lists:seq(1, Width)].
-
-
-gen_short_string(_) ->
- Size = rand:uniform(255),
- [rand:uniform(127) || _ <- lists:seq(1, Size)].
-
-
-gen_string(_) ->
- Size = rand:uniform(4096),
- [rand:uniform(127) || _ <- lists:seq(1, Size)].
-
-
-gen_binary(MaxSize) ->
- list_to_binary(gen_string(MaxSize)).
-
-
-gen_bitstring(MaxSize) ->
- B = gen_binary(MaxSize),
- <<2:4/integer, B/binary>>.
-
-
-gen_bignum(_) ->
- 16#FFFFFFFFFFFFFFFF + rand:uniform(16#FFFFFFFF).
-
-
-gen_function(_) ->
- choice(all_types()).
-
-
-choice(Options) ->
- lists:nth(rand:uniform(length(Options)), Options).
-
-
-value_types() ->
- [
- gen_atom,
- gen_integer,
- gen_float,
- gen_reference,
- gen_port,
- gen_pid,
- gen_short_string,
- gen_string,
- gen_binary,
- gen_bitstring,
- gen_bignum,
- gen_function
- ].
-
-
-all_types() ->
- value_types() ++ [gen_tuple, gen_list].
diff --git a/test/khash_test.erl b/test/khash_test.erl
deleted file mode 100644
index 6a23661..0000000
--- a/test/khash_test.erl
+++ /dev/null
@@ -1,388 +0,0 @@
--module(khash_test).
-
--export([
- khash_fetch/0,
- khash_store/0,
- run_keys/1
-]).
-
--include_lib("eunit/include/eunit.hrl").
-
--define(NUM_RAND_CYCLES, 10000).
--define(NUM_CYCLES, 1000000).
--define(NUM_KVS, 5000).
--define(TIMEOUT, 15).
-
-load_test_() ->
- {
- "Loaded khash",
- ?_assertEqual({module, khash}, code:load_file(khash))
- }.
-
-basic_test_() ->
- {
- "khash basic operations",
- {setup,
- local,
- fun() -> khash:new() end,
- fun({ok, _}) -> ok end,
- fun({ok, C}) ->
- [
- {
- "Lookup missing is ok",
- ?_assertEqual(not_found, khash:lookup(C, <<"foo">>))
- },
- {
- "Get missing is ok",
- ?_assertEqual(undefined, khash:get(C, <<"foo">>))
- },
- {
- "Del missing is ok",
- ?_assertEqual(not_found, khash:del(C, <<"foo">>))
- },
- {
- "Stored a key",
- ?_assertEqual(ok, khash:put(C, <<"foo">>, bar))
- },
- {
- "Lookuped a key",
- ?_assertEqual({value, bar}, khash:lookup(C, <<"foo">>))
- },
- {
- "Retrieved a key",
- ?_assertEqual(bar, khash:get(C, <<"foo">>))
- },
- {
- "Stored a key",
- ?_assertEqual(ok, khash:put(C, <<"bar">>, foo))
- },
- {
- "Correct size for hash",
- ?_assertEqual(2, khash:size(C))
- },
- {
- "Deleted a key",
- ?_assertEqual(ok, khash:del(C, <<"foo">>))
- },
- {
- "Correct size after delete",
- ?_assertEqual(1, khash:size(C))
- },
- {
- "Cleared the hash",
- ?_assertEqual(ok, khash:clear(C))
- },
- {
- "Correct size after clear",
- ?_assertEqual(0, khash:size(C))
- }
- ]
- end
- }
- }.
-
-randomized_test_() ->
- {
- "khash randomized test",
- {setup,
- local,
- fun() ->
- Dict = dict:new(),
- {ok, KHash} = khash:new(),
- Actions = [
- {0.1, fun run_clear/1},
- {1.0, fun run_get2/1},
- {1.0, fun run_get3/1},
- {1.0, fun run_put/1},
- {1.0, fun run_del/1},
- {0.5, fun run_size/1},
- % {0.3, fun run_keys/1},
- {0.3, fun run_to_list/1}
- ],
- {ok, Actions, ?NUM_RAND_CYCLES, {Dict, KHash}}
- end,
- fun(State) ->
- {timeout, ?TIMEOUT, {
- "State matches dict implementation",
- ?_assert(run_randomized(State, true))
- }}
- end
- }
- }.
-
-basic_iterators_test_() ->
- {
- "khash itrators basics operations",
- {setup,
- local,
- fun() ->
- {ok, H} = khash:new(),
- khash:put(H, foo, bar),
- {ok, I} = khash:iter(H),
- {ok, H, I}
- end,
- fun({ok, H, I}) ->
- [
- {
- "Got only kv pair as first element",
- ?_assertEqual(khash:iter_next(I), {foo,bar})
- },
- {
- "Only the one kv pair exists",
- ?_assertEqual(khash:iter_next(I), end_of_table)
- },
- {
- "Fold works",
- ?_test(begin
- Fold = fun(K, V, Acc) -> [{K,V} | Acc] end,
- ?assertEqual(khash:fold(H, Fold, []), [{foo,bar}])
- end)
- }
- ]
- end
- }
- }.
-
-multiread_iterators_test_() ->
- {
- "khash iterators multi-read test",
- {setup,
- local,
- fun() ->
- {ok, H} = khash:new(),
- KVs = kv_data(10),
- lists:foreach(fun({K,V}) -> khash:put(H, K, V) end, KVs),
- {ok, I} = khash:iter(H),
- {ok, I, KVs}
- end,
- fun({ok, I, KVs}) ->
- {
- "Read the same exact key/val pairs",
- ?_assertEqual(khash_iterate(I, []), KVs)
- }
- end
- }
- }.
-
-expiration_iterators_test_() ->
- {
- "khash iterators exipiration functions",
- {foreach,
- local,
- fun() ->
- Err = {error, expired_iterator},
- {ok, H} = khash:new(),
- khash:put(H, foo, bar),
- {ok, I} = khash:iter(H),
- {ok, H, I, Err}
- end,
- [
- fun({ok, H, I, Err}) ->
- khash:put(H, foo, bar2),
- {
- "put expires iterators",
- ?_assertEqual(khash:iter_next(I), Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- khash:del(H, foo),
- {
- "del expires iterators",
- ?_assertEqual(khash:iter_next(I), Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- khash:clear(H),
- {
- "clear expires iterators",
- ?_assertEqual(khash:iter_next(I), Err)
- }
- end
- ]
- }
- }.
-
-no_expiration_iterators_test_() ->
- {
- "khash iterators no exipiration functions",
- {foreach,
- local,
- fun() ->
- Err = {error, expired_iterator},
- {ok, H} = khash:new(),
- khash:put(H, foo, bar),
- {ok, I} = khash:iter(H),
- {ok, H, I, Err}
- end,
- [
- fun({ok, H, I, Err}) ->
- [{foo, bar}] = khash:to_list(H),
- {
- "to_list doesn't expire iterators",
- ?_assertNot(khash:iter_next(I) == Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- {value, bar} = khash:lookup(H,foo),
- {
- "lookup doesn't expire iterators",
- ?_assertNot(khash:iter_next(I) == Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- bar = khash:get(H, foo),
- {
- "get doesn't expire iterators",
- ?_assertNot(khash:iter_next(I) == Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- 1 = khash:size(H),
- {
- "size doesn't expire iterators",
- ?_assertNot(khash:iter_next(I) == Err)
- }
- end,
- fun({ok, H, I, Err}) ->
- {ok, _OtherI} = khash:iter(H),
- {foo, bar} = khash:iter_next(I),
- end_of_table = khash:iter_next(I),
- {
- "iteration doesn't expire iterators",
- ?_assertNot(khash:iter_next(I) == Err)
- }
- end
- ]
- }
- }.
-
-khash_fetch() ->
- erlang:garbage_collect(),
- List = kv_data(?NUM_KVS),
- {ok, KHash} = khash:from_list(List),
- khash_fetch(KHash, ?NUM_CYCLES * 10).
-
-khash_fetch(_, 0) ->
- ok;
-khash_fetch(KHash, NumCycles) ->
- ?assertMatch(1, khash:get(KHash, 1)),
- khash_fetch(KHash, NumCycles - 1).
-
-khash_store() ->
- List = kv_data(?NUM_KVS * 2),
- {ok, KHash} = khash:from_list(List),
- khash_store(KHash, ?NUM_CYCLES).
-
-khash_store(_, 0) ->
- ok;
-khash_store(KHash, NumCycles) ->
- khash:put(KHash, 1, 1),
- khash_store(KHash, NumCycles - 1).
-
-khash_iterate(I, Acc) ->
- case khash:iter_next(I) of
- {K, V} ->
- khash_iterate(I, [{K, V}|Acc]);
- end_of_table ->
- lists:sort(Acc)
- end.
-
-kv_data(NumKVs) ->
- [{I, I} || I <- lists:seq(1, NumKVs)].
-
-run_randomized({ok, _, N, _}, Valid) when N =< 0 ->
- Valid;
-run_randomized({ok, Actions, N, S0}, Valid) ->
- Action = weighted_choice(Actions),
- S1 = Action(S0),
- Assertion = Valid andalso validate_randomized_state(S1),
- run_randomized({ok, Actions, N - 1, S1}, Assertion).
-
-validate_randomized_state({D, H}) ->
- DKVs = lists:sort(dict:to_list(D)),
- HKVs = lists:sort(khash:to_list(H)),
- DKVs == HKVs.
-
-run_clear({_D0, H}) ->
- ?assertMatch(ok, khash:clear(H)),
- {dict:new(), H}.
-
-run_get2({D, H}) ->
- K = random_key(D),
- case dict:find(K, D) of
- {ok, Value} ->
- ?assertMatch({value, Value}, khash:lookup(H, K)),
- ?assertMatch(Value, khash:get(H, K));
- error ->
- ?assertMatch(not_found, khash:lookup(H, K)),
- ?assertMatch(undefined, khash:get(H, K))
- end,
- {D, H}.
-
-run_get3({D, H}) ->
- K = random_key(D),
- case dict:find(K, D) of
- {ok, Value} ->
- ?assertMatch({value, Value}, khash:lookup(H, K)),
- ?assertMatch(Value, khash:get(H, K));
- error ->
- Val = random_val(),
- ?assertMatch(Val, khash:get(H, K, Val))
- end,
- {D, H}.
-
-run_put({D0, H}) ->
- K = random_key(D0),
- V = random_val(),
- D1 = dict:store(K, V, D0),
- ?assertMatch(ok, khash:put(H, K, V)),
- {D1, H}.
-
-run_del({D0, H}) ->
- K = random_key(D0),
- D1 = case dict:is_key(K, D0) of
- true ->
- ?assertMatch(ok, khash:del(H, K)),
- dict:erase(K, D0);
- false ->
- ?assertMatch(not_found, khash:del(H, K)),
- D0
- end,
- {D1, H}.
-
-run_size({D, H}) ->
- ?assertEqual(dict:size(D), khash:size(H)),
- {D, H}.
-
-run_keys({D, H}) ->
- DKeys = dict:fetch_keys(D),
- {ok, HKeys0} = khash:keys(H),
- HKeys = lists:sort(HKeys0),
- ?assertEqual(lists:sort(DKeys), lists:sort(HKeys)),
- {D, H}.
-
-run_to_list({D, H}) ->
- DKVs = dict:to_list(D),
- HKVs = khash:to_list(H),
- ?assertEqual(lists:sort(DKVs), lists:sort(HKVs)),
- {D, H}.
-
-weighted_choice(Items0) ->
- Items = lists:sort(Items0),
- Sum = lists:sum([W || {W, _} <- Items]),
- Choice = rand:uniform() * Sum,
- weighted_choice(Items, 0.0, Choice).
-
-weighted_choice([], _, _) ->
- throw(bad_choice);
-weighted_choice([{W, _} | Rest], S, C) when W + S < C ->
- weighted_choice(Rest, W+S, C);
-weighted_choice([{_, I} | _], _, _) ->
- I.
-
-random_key(D) ->
- Keys = lists:usort(dict:fetch_keys(D) ++ [foo]),
- lists:nth(rand:uniform(length(Keys)), Keys).
-
-random_val() ->
- gen_term:any().