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 14:57:51 UTC
[couchdb] branch main updated: Integrate b64url, ets_lru and khash into 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.git
The following commit(s) were added to refs/heads/main by this push:
new 8c6ac52cc Integrate b64url, ets_lru and khash into the main repo
8c6ac52cc is described below
commit 8c6ac52cc5dd591fd4b47f1f4619c3ce225dbc1f
Author: Nick Vatamaniuc <va...@gmail.com>
AuthorDate: Fri Oct 28 10:10:01 2022 -0400
Integrate b64url, ets_lru and khash into the main repo
As discussed on the mailing list https://lists.apache.org/thread/opvsmz1pwlnv96wozy5kp7ss896l9lfp
---
.gitignore | 3 -
rebar.config.script | 6 +-
src/b64url/.gitignore | 10 +
src/b64url/LICENSE | 203 +++++++++
src/b64url/Makefile | 46 +++
src/b64url/README.md | 46 +++
src/b64url/c_src/b64url.c | 665 ++++++++++++++++++++++++++++++
src/b64url/rebar.config | 32 ++
src/b64url/src/b64url.app.src | 18 +
src/b64url/src/b64url.erl | 88 ++++
src/b64url/test/b64url_tests.erl | 144 +++++++
src/b64url/test/benchmark.escript | 165 ++++++++
src/ets_lru/.gitignore | 3 +
src/ets_lru/LICENSE | 202 +++++++++
src/ets_lru/Makefile | 41 ++
src/ets_lru/src/ets_lru.app.src | 21 +
src/ets_lru/src/ets_lru.erl | 335 +++++++++++++++
src/ets_lru/test/ets_lru_test.erl | 339 +++++++++++++++
src/khash/.gitignore | 10 +
src/khash/LICENSE | 76 ++++
src/khash/Makefile | 44 ++
src/khash/README.md | 4 +
src/khash/c_src/hash.c | 843 ++++++++++++++++++++++++++++++++++++++
src/khash/c_src/hash.h | 240 +++++++++++
src/khash/c_src/khash.c | 658 +++++++++++++++++++++++++++++
src/khash/rebar.config | 14 +
src/khash/src/khash.app.src | 10 +
src/khash/src/khash.erl | 136 ++++++
src/khash/test/gen_term.erl | 113 +++++
src/khash/test/khash_test.erl | 374 +++++++++++++++++
30 files changed, 4883 insertions(+), 6 deletions(-)
diff --git a/.gitignore b/.gitignore
index acf98e5c0..816ece6d4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -39,7 +39,6 @@ rel/tmpdata
share/server/main-coffee.js
share/server/main.js
share/www
-src/b64url/
src/bear/
src/certifi/
src/couch/priv/couch_js/**/config.h
@@ -49,7 +48,6 @@ src/couch/priv/couch_ejson_compare/couch_ejson_compare.d
src/couch/priv/couch_js/**/*.d
src/couch/priv/icu_driver/couch_icu_driver.d
src/mango/src/mango_cursor_text.nocompile
-src/ets_lru/
src/excoveralls/
src/fauxton/
src/folsom/
@@ -59,7 +57,6 @@ src/hyper/
src/ibrowse/
src/idna/
src/jiffy/
-src/khash/
src/meck/
src/metrics/
src/mimerl/
diff --git a/rebar.config.script b/rebar.config.script
index 38a57c966..3952ad857 100644
--- a/rebar.config.script
+++ b/rebar.config.script
@@ -110,6 +110,9 @@ SubDirs = [
"src/couch_epi",
"src/config",
"src/couch_log",
+ "src/khash",
+ "src/b64url",
+ "src/ets_lru",
"src/chttpd",
"src/couch",
"src/couch_event",
@@ -142,9 +145,6 @@ SubDirs = [
DepDescs = [
%% Independent Apps
-{b64url, "b64url", {tag, "1.0.3"}},
-{ets_lru, "ets-lru", {tag, "1.1.0"}},
-{khash, "khash", {tag, "1.1.0"}},
{snappy, "snappy", {tag, "CouchDB-1.0.8"}},
%% %% Non-Erlang deps
diff --git a/src/b64url/.gitignore b/src/b64url/.gitignore
new file mode 100644
index 000000000..a3fd77fce
--- /dev/null
+++ b/src/b64url/.gitignore
@@ -0,0 +1,10 @@
+.eunit/
+c_src/*.o
+ebin/
+priv/
+.rebar/
+vc110.pdb
+compile_commands.json
+
+_build/
+c_src/*.d
\ No newline at end of file
diff --git a/src/b64url/LICENSE b/src/b64url/LICENSE
new file mode 100644
index 000000000..94ad231b8
--- /dev/null
+++ b/src/b64url/LICENSE
@@ -0,0 +1,203 @@
+
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "{}"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright {yyyy} {name of copyright owner}
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+
diff --git a/src/b64url/Makefile b/src/b64url/Makefile
new file mode 100644
index 000000000..754165e5c
--- /dev/null
+++ b/src/b64url/Makefile
@@ -0,0 +1,46 @@
+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
+
+
+%.beam: %.erl
+ erlc -o test/ $<
diff --git a/src/b64url/README.md b/src/b64url/README.md
new file mode 100644
index 000000000..c3a3497f2
--- /dev/null
+++ b/src/b64url/README.md
@@ -0,0 +1,46 @@
+# Base64 encoder with URL-safe scheme
+
+[](https://github.com/apache/couchdb-b64url/actions/workflows/ci.yml)
+
+This is a simple NIF that is responsible for quickly encoding and
+decoding Base64 URL values:
+
+```erlang
+1> Thing = b64url:encode("Hello, CouchDB!").
+<<"SGVsbG8sIENvdWNoREIh">>
+2> b64url:decode(Thing).
+<<"Hello, CouchDB!">>
+```
+
+## Performance
+
+This implementation is significantly faster than the Erlang version it replaced
+in CouchDB. The `benchmark.escript` file contains the original implementation
+(using regular expressions to replace unsafe characters in the output of the
+`base64` module) and can be used to compare the two for strings of various
+lengths. For example:
+
+```
+ERL_LIBS=_build/default/lib/b64url/ ./test/benchmark.escript 4 10 100 30
+erl : 75491270 bytes / 30 seconds = 2516375.67 bps
+nif : 672299342 bytes / 30 seconds = 22409978.07 bps
+```
+
+This test invocation spawns four workers that generate random strings between 10
+and 100 bytes in length and then perform an encode/decode on them in a tight
+loop for 30 seconds, and then reports the aggregate encoded data volume. Note
+that the generator overhead (`crypto:strong_rand_bytes/1`) is included in these
+results, so the relative difference in encoder throughput is rather larger than
+what's reported here.
+
+## Timeslice Consumption
+
+NIF implementations must take care to avoid doing [lengthy
+work](https://www.erlang.org/doc/man/erl_nif.html#lengthy_work) in a single
+invocation. This library will yield back to the Erlang VM as needed when
+operating on a large string, maintaining a partial result until it can resume
+operation. The current implementation uses a conservative heuristic that
+estimates 64 bytes of encoding / decoding to consume 1% of a timeslice, so input
+strings shorter than ~6k should be encoded / decoded within a single invocation,
+and the library should not adversely affect the responsiveness of the VM in any
+way.
diff --git a/src/b64url/c_src/b64url.c b/src/b64url/c_src/b64url.c
new file mode 100644
index 000000000..d9e2e0448
--- /dev/null
+++ b/src/b64url/c_src/b64url.c
@@ -0,0 +1,665 @@
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+#include <assert.h>
+#include <string.h>
+
+#include "erl_nif.h"
+
+#ifdef _WIN32
+#define INLINE __inline
+#else
+#define INLINE inline
+#endif
+
+
+typedef ERL_NIF_TERM ENTERM;
+
+
+typedef struct
+{
+ ENTERM atom_ok;
+ ENTERM atom_error;
+ ENTERM atom_partial;
+
+ ENTERM atom_nomem;
+ ENTERM atom_bad_block;
+
+ ErlNifResourceType* res_st;
+} b64url_priv;
+
+
+typedef struct
+{
+ ErlNifPid pid;
+ ErlNifBinary tgt;
+ size_t len;
+ size_t si;
+ size_t ti;
+ char res_released;
+ char bin_released;
+} b64url_st;
+
+
+typedef enum
+{
+ ST_OK,
+ ST_ERROR,
+ ST_PARTIAL
+} b64url_status;
+
+
+const unsigned char B64URL_B2A[256] = {
+ 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, // 0 - 15
+ 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 97, 98, 99,100,101,102, // 16 - 31
+ 103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118, // 32 - 47
+ 119,120,121,122, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 45, 95, // 48 - 63
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 64 - 79
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 80 - 95
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 96 - 111
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 112 - 127
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 128 - 143
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 144 - 159
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 160 - 175
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 176 - 191
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 192 - 207
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 208 - 223
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 224 - 239
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255 // 240 - 255
+};
+
+const unsigned char B64URL_A2B[256] = {
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 0 - 15
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 16 - 31
+ 255,255,255,255,255,255,255,255,255,255,255,255,255, 62,255,255, // 32 - 47
+ 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,255,255,255,255,255,255, // 48 - 63
+ 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, // 64 - 79
+ 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,255,255,255,255, 63, // 80 - 95
+ 255, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, // 96 - 111
+ 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,255,255,255,255,255, // 112 - 127
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 128 - 143
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 144 - 159
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 160 - 175
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 176 - 191
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 192 - 207
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 208 - 223
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, // 224 - 239
+ 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255 // 240 - 255
+};
+
+
+#define BYTES_PER_PERCENT 64
+
+static INLINE int
+do_consume_timeslice(ErlNifEnv* env) {
+#if(ERL_NIF_MAJOR_VERSION >= 2 && ERL_NIF_MINOR_VERSION >= 4)
+ return enif_consume_timeslice(env, 1);
+#else
+ return 0;
+#endif
+}
+
+
+static INLINE ENTERM
+make_atom(ErlNifEnv* env, const char* name)
+{
+ ENTERM ret;
+ if(enif_make_existing_atom(env, name, &ret, ERL_NIF_LATIN1)) {
+ return ret;
+ }
+ return enif_make_atom(env, name);
+}
+
+
+static INLINE ENTERM
+make_ok(ErlNifEnv* env, b64url_priv* priv, ENTERM value)
+{
+ return enif_make_tuple2(env, priv->atom_ok, value);
+}
+
+
+static INLINE ENTERM
+make_error(ErlNifEnv* env, b64url_priv* priv, ENTERM value)
+{
+ return enif_make_tuple2(env, priv->atom_error, value);
+}
+
+
+static INLINE ENTERM
+make_bad_block(ErlNifEnv* env, b64url_priv* priv, size_t pos)
+{
+ ENTERM pterm = enif_make_uint64(env, pos);
+ return enif_make_tuple2(env, priv->atom_bad_block, pterm);
+}
+
+
+static INLINE ENTERM
+make_partial(ErlNifEnv* env, b64url_priv* priv, ENTERM value)
+{
+ return enif_make_tuple2(env, priv->atom_partial, value);
+}
+
+
+static INLINE int
+check_pid(ErlNifEnv* env, b64url_st* st)
+{
+ ErlNifPid self_pid;
+ ENTERM self;
+ ENTERM orig;
+
+ enif_self(env, &self_pid);
+ self = enif_make_pid(env, &self_pid);
+ orig = enif_make_pid(env, &(st->pid));
+
+ if(enif_compare(self, orig) == 0) {
+ return 1;
+ }
+
+ return 0;
+}
+
+
+static b64url_st*
+b64url_st_alloc(ErlNifEnv* env, b64url_priv* priv, ErlNifBinary* src, size_t tlen)
+{
+ b64url_st* st = enif_alloc_resource(priv->res_st, sizeof(b64url_st));
+ if(st == NULL) {
+ goto error;
+ }
+
+ memset(st, '\0', sizeof(b64url_st));
+ enif_self(env, &(st->pid));
+ st->len = src->size;
+ st->si = 0;
+ st->ti = 0;
+ st->res_released = 0;
+ st->bin_released = 0;
+
+ if(!enif_alloc_binary(tlen, &(st->tgt))) {
+ goto error;
+ }
+
+ return st;
+
+error:
+ if(st != NULL) {
+ st->res_released = 1;
+ enif_release_resource(st);
+ }
+ return NULL;
+}
+
+
+static void
+b64url_st_free(ErlNifEnv* env, void* obj)
+{
+ b64url_st* st = (b64url_st*) obj;
+
+ if(!st->bin_released) {
+ enif_release_binary(&(st->tgt));
+ }
+}
+
+static ENTERM
+b64url_st_enc_ret(ErlNifEnv* env, b64url_st* st, int status)
+{
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ ENTERM ret;
+
+ if(status == ST_OK) {
+ ret = make_ok(env, priv, enif_make_binary(env, &(st->tgt)));
+ st->bin_released = 1;
+ } else if(status == ST_PARTIAL) {
+ ret = make_partial(env, priv, enif_make_resource(env, st));
+ } else {
+ assert(0 == 1 && "invalid status encoder status");
+ ret = enif_make_badarg(env);
+ }
+
+ if(!st->res_released) {
+ st->res_released = 1;
+ enif_release_resource(st);
+ }
+
+ return ret;
+}
+
+static ENTERM
+b64url_st_dec_ret(ErlNifEnv* env, b64url_st* st, int status, ENTERM ret)
+{
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+
+ if(status == ST_OK) {
+ ret = make_ok(env, priv, enif_make_binary(env, &(st->tgt)));
+ st->bin_released = 1;
+ } else if(status == ST_ERROR) {
+ ret = make_error(env, priv, ret);
+ } else if(status == ST_PARTIAL) {
+ ret = make_partial(env, priv, enif_make_resource(env, st));
+ } else {
+ assert(0 == 1 && "invalid status decoder status");
+ ret = enif_make_badarg(env);
+ }
+
+ if(!st->res_released) {
+ st->res_released = 1;
+ enif_release_resource(st);
+ }
+
+ return ret;
+}
+
+static int
+load(ErlNifEnv* env, void** priv, ENTERM info)
+{
+ int flags = ERL_NIF_RT_CREATE | ERL_NIF_RT_TAKEOVER;
+ ErlNifResourceType* res;
+
+ b64url_priv* new_priv = (b64url_priv*) enif_alloc(sizeof(b64url_priv));
+ if(new_priv == NULL) {
+ return 1;
+ }
+
+ res = enif_open_resource_type(
+ env, NULL, "b64url_st", b64url_st_free, flags, NULL);
+ if(res == NULL) {
+ return 1;
+ }
+ new_priv->res_st = res;
+
+ new_priv->atom_ok = make_atom(env, "ok");
+ new_priv->atom_error = make_atom(env, "error");
+ new_priv->atom_partial = make_atom(env, "partial");
+
+ new_priv->atom_nomem = make_atom(env, "enomem");
+ new_priv->atom_bad_block = make_atom(env, "bad_block");
+
+ *priv = (void*) new_priv;
+
+ return 0;
+}
+
+
+static int
+reload(ErlNifEnv* env, void** priv, ENTERM info)
+{
+ return 0;
+}
+
+
+static int
+upgrade(ErlNifEnv* env, void** priv, void** old_priv, ENTERM info)
+{
+ return 0;
+}
+
+
+static void
+unload(ErlNifEnv* env, void* priv)
+{
+ return;
+}
+
+
+static INLINE b64url_status
+b64url_encode(ErlNifEnv* env, ErlNifBinary* src, b64url_st* st)
+{
+ size_t chunk_start = st->si;
+ size_t rem;
+ unsigned char c1;
+ unsigned char c2;
+ unsigned char c3;
+
+ assert(st->si % 3 == 0 && "invalid source index");
+ assert(st->ti % 4 == 0 && "invalid target index");
+
+ while(st->si + 3 <= src->size) {
+ c1 = src->data[st->si++];
+ c2 = src->data[st->si++];
+ c3 = src->data[st->si++];
+
+ st->tgt.data[st->ti++] = B64URL_B2A[(c1 >> 2) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[((c1 << 4) | (c2 >> 4)) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[((c2 << 2) | (c3 >> 6)) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[c3 & 0x3F];
+
+ if(st->si - chunk_start > BYTES_PER_PERCENT) {
+ if(do_consume_timeslice(env)) {
+ return ST_PARTIAL;
+ } else {
+ chunk_start = st->si;
+ }
+ }
+ }
+
+ rem = src->size % 3;
+ if(rem == 1) {
+ c1 = src->data[st->si];
+ st->tgt.data[st->ti++] = B64URL_B2A[(c1 >> 2) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[(c1 << 4) & 0x3F];
+ } else if(rem == 2) {
+ c1 = src->data[st->si];
+ c2 = src->data[st->si+1];
+ st->tgt.data[st->ti++] = B64URL_B2A[(c1 >> 2) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[((c1 << 4) | (c2 >> 4)) & 0x3F];
+ st->tgt.data[st->ti++] = B64URL_B2A[(c2 << 2) & 0x3F];
+ } else if(rem != 0) {
+ assert(0 == 1 && "Inavlid length calculation");
+ }
+
+ return ST_OK;
+}
+
+
+static ENTERM
+b64url_encode_init(ErlNifEnv* env, int argc, const ENTERM argv[])
+{
+ ErlNifBinary src;
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ b64url_st* st = NULL;
+ size_t tlen;
+ size_t rem;
+ int status;
+ ENTERM ret;
+
+ if(argc != 1) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_inspect_iolist_as_binary(env, argv[0], &src)) {
+ ret = enif_make_badarg(env);
+ goto error;
+ }
+
+ // The target length is defined as 4 * ceil(src_len/3) but we
+ // don't use '=' padding for URLs so we only add exactly the
+ // extra bytes we need.
+ tlen = (src.size / 3) * 4;
+ rem = src.size % 3;
+ if(rem == 1) {
+ tlen += 2;
+ } else if(rem == 2) {
+ tlen += 3;
+ }
+
+ st = b64url_st_alloc(env, priv, &src, tlen);
+ if(st == NULL) {
+ ret = make_error(env, priv, priv->atom_nomem);
+ goto error;
+ }
+
+ status = b64url_encode(env, &src, st);
+
+ return b64url_st_enc_ret(env, st, status);
+
+error:
+ if(st != NULL) {
+ st->res_released = 1;
+ enif_release_resource(st);
+ }
+
+ return ret;
+}
+
+
+static ENTERM
+b64url_encode_cont(ErlNifEnv* env, int argc, const ENTERM argv[])
+{
+ ErlNifBinary src;
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ b64url_st* st = NULL;
+ void* res = NULL;
+ int status;
+
+ if(argc != 2) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_inspect_iolist_as_binary(env, argv[0], &src)) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_get_resource(env, argv[1], priv->res_st, &res)) {
+ return enif_make_badarg(env);
+ }
+
+ st = (b64url_st*) res;
+
+ if(!check_pid(env, st)) {
+ return enif_make_badarg(env);
+ }
+
+ if(src.size != st->len) {
+ return enif_make_badarg(env);
+ }
+
+ status = b64url_encode(env, &src, st);
+
+ return b64url_st_enc_ret(env, st, status);
+}
+
+
+static INLINE b64url_status
+b64url_decode(ErlNifEnv* env, ErlNifBinary* src, b64url_st* st, ENTERM* ret)
+{
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ size_t chunk_start = st->si;
+ size_t rem;
+ unsigned char c1;
+ unsigned char c2;
+ unsigned char c3;
+ unsigned char c4;
+
+ assert(st->si % 4 == 0 && "invalid source index");
+ assert(st->ti % 3 == 0 && "invalid target index");
+
+ while(st->si + 4 <= src->size) {
+ c1 = B64URL_A2B[src->data[st->si++]];
+ c2 = B64URL_A2B[src->data[st->si++]];
+ c3 = B64URL_A2B[src->data[st->si++]];
+ c4 = B64URL_A2B[src->data[st->si++]];
+
+ if(c1 == 255 || c2 == 255 || c3 == 255 || c4 == 255) {
+ *ret = make_bad_block(env, priv, st->si-4);
+ return ST_ERROR;
+ }
+
+ st->tgt.data[st->ti++] = (c1 << 2) | (c2 >> 4);
+ st->tgt.data[st->ti++] = (c2 << 4) | (c3 >> 2);
+ st->tgt.data[st->ti++] = (c3 << 6) | c4;
+
+ if(st->si - chunk_start > BYTES_PER_PERCENT) {
+ if(do_consume_timeslice(env)) {
+ return ST_PARTIAL;
+ } else {
+ chunk_start = st->si;
+ }
+ }
+ }
+
+ rem = src->size % 4;
+ if(rem == 2) {
+ c1 = B64URL_A2B[src->data[st->si]];
+ c2 = B64URL_A2B[src->data[st->si+1]];
+
+ if(c1 == 255 || c2 == 255) {
+ *ret = make_bad_block(env, priv, st->si);
+ return ST_ERROR;
+ }
+
+ st->tgt.data[st->ti++] = (c1 << 2) | (c2 >> 4);
+ } else if(rem == 3) {
+ c1 = B64URL_A2B[src->data[st->si]];
+ c2 = B64URL_A2B[src->data[st->si+1]];
+ c3 = B64URL_A2B[src->data[st->si+2]];
+
+ if(c1 == 255 || c2 == 255 || c3 == 255) {
+ *ret = make_bad_block(env, priv, st->si);
+ return ST_ERROR;
+ }
+
+ st->tgt.data[st->ti++] = (c1 << 2) | (c2 >> 4);
+ st->tgt.data[st->ti++] = (c2 << 4) | (c3 >> 2);
+ } else if(rem != 0) {
+ assert(0 == 1 && "invalid source length");
+ }
+
+ return ST_OK;
+}
+
+
+static ENTERM
+b64url_decode_init(ErlNifEnv* env, int argc, const ENTERM argv[])
+{
+ ErlNifBinary src;
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ b64url_st* st = NULL;
+ size_t tlen;
+ int status;
+ ENTERM ret = priv->atom_error;
+
+ if(argc != 1) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_inspect_iolist_as_binary(env, argv[0], &src)) {
+ return enif_make_badarg(env);
+ }
+
+ // We don't do use '=' padding for URLs so our target length
+ // will be the number of blocks of 4 bytes times 3, plus 1 or 2
+ // depending on the number of bytes in the last block.
+ tlen = (src.size / 4) * 3;
+ if(src.size % 4 == 1) {
+ ret = enif_make_badarg(env);
+ goto error;
+ } else if(src.size % 4 == 2) {
+ tlen += 1;
+ } else if(src.size % 4 == 3) {
+ tlen += 2;
+ }
+
+ st = b64url_st_alloc(env, priv, &src, tlen);
+ if(st == NULL) {
+ ret = make_error(env, priv, priv->atom_nomem);
+ goto error;
+ }
+
+ status = b64url_decode(env, &src, st, &ret);
+
+ return b64url_st_dec_ret(env, st, status, ret);
+
+error:
+ if(st != NULL) {
+ st->res_released = 1;
+ enif_release_resource(st);
+ }
+
+ return ret;
+}
+
+
+static ENTERM
+b64url_decode_cont(ErlNifEnv* env, int argc, const ENTERM argv[])
+{
+ ErlNifBinary src;
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ b64url_st* st = NULL;
+ void* res = NULL;
+ ENTERM ret = priv->atom_error;
+ int status;
+
+ if(argc != 2) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_inspect_iolist_as_binary(env, argv[0], &src)) {
+ return enif_make_badarg(env);
+ }
+
+ if(!enif_get_resource(env, argv[1], priv->res_st, &res)) {
+ return enif_make_badarg(env);
+ }
+
+ st = (b64url_st*) res;
+
+ if(!check_pid(env, st)) {
+ return enif_make_badarg(env);
+ }
+
+ if(src.size != st->len) {
+ return enif_make_badarg(env);
+ }
+
+ status = b64url_decode(env, &src, st, &ret);
+
+ return b64url_st_dec_ret(env, st, status, ret);
+}
+
+
+static unsigned char CHECK_A2B[64] =
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
+
+
+static ENTERM
+b64url_check_tables(ErlNifEnv* env, int argc, const ENTERM argv[])
+{
+ b64url_priv* priv = (b64url_priv*) enif_priv_data(env);
+ ENTERM pos;
+ int i;
+
+ for(i = 0; i < 64; i++) {
+ if(B64URL_B2A[i] != CHECK_A2B[i]) {
+ pos = enif_make_int(env, i);
+ return enif_make_tuple2(env, priv->atom_error, pos);
+ }
+ }
+
+ for(i = 64; i < 256; i++) {
+ if(B64URL_B2A[i] != 255) {
+ pos = enif_make_int(env, i);
+ return enif_make_tuple2(env, priv->atom_error, pos);
+ }
+ }
+
+ for(i = 0; i < 64; i++) {
+ if(B64URL_A2B[CHECK_A2B[i]] != i) {
+ pos = enif_make_int(env, i);
+ return enif_make_tuple2(env, priv->atom_error, pos);
+ }
+ }
+
+ for(i = 0; i < 256; i++) {
+ if(B64URL_A2B[i] == 255) {
+ continue;
+ }
+ if(CHECK_A2B[B64URL_A2B[i]] != i) {
+ pos = enif_make_int(env, i);
+ return enif_make_tuple2(env, priv->atom_error, pos);
+ }
+ }
+
+ return priv->atom_ok;
+}
+
+static ErlNifFunc funcs[] = {
+ {"encode_init", 1, b64url_encode_init},
+ {"encode_cont", 2, b64url_encode_cont},
+ {"decode_init", 1, b64url_decode_init},
+ {"decode_cont", 2, b64url_decode_cont},
+ {"check_tables", 0, b64url_check_tables}
+};
+
+
+ERL_NIF_INIT(b64url, funcs, &load, &reload, &upgrade, &unload);
+
+
diff --git a/src/b64url/rebar.config b/src/b64url/rebar.config
new file mode 100644
index 000000000..d9512aed3
--- /dev/null
+++ b/src/b64url/rebar.config
@@ -0,0 +1,32 @@
+{plugins, [
+ pc
+]}.
+
+{project_plugins, [
+ erlfmt
+]}.
+
+{provider_hooks, [
+ {pre, [
+ {compile, {pc, compile}},
+ {clean, {pc, clean}}
+ ]}
+]}.
+
+{port_specs, [
+ {"priv/b64url.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"}
+]}.
+
+{eunit_opts, [
+ debug_info,
+ verbose
+]}.
diff --git a/src/b64url/src/b64url.app.src b/src/b64url/src/b64url.app.src
new file mode 100644
index 000000000..aaf8e9fc4
--- /dev/null
+++ b/src/b64url/src/b64url.app.src
@@ -0,0 +1,18 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+{application, b64url, [
+ {description, "A small NIF for encoding Base64 URL encoding/decoding."},
+ {vsn, git},
+ {registered, []},
+ {applications, [kernel, stdlib]}
+]}.
diff --git a/src/b64url/src/b64url.erl b/src/b64url/src/b64url.erl
new file mode 100644
index 000000000..6e6ddaccd
--- /dev/null
+++ b/src/b64url/src/b64url.erl
@@ -0,0 +1,88 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(b64url).
+-on_load(init/0).
+
+-export([
+ encode/1,
+ decode/1
+]).
+
+% Internal sanity checks
+-export([
+ check_tables/0
+]).
+
+-define(NOT_LOADED, not_loaded(?LINE)).
+
+-spec encode(iodata()) -> binary().
+encode(IoData) ->
+ case encode_init(IoData) of
+ {ok, Bin} ->
+ Bin;
+ {partial, St} ->
+ encode_loop(IoData, St)
+ end.
+
+-spec decode(iodata()) -> binary() | {error, any()}.
+decode(IoData) ->
+ case decode_init(IoData) of
+ {ok, Bin} ->
+ Bin;
+ {error, _} = Ret ->
+ Ret;
+ {partial, St} ->
+ decode_loop(IoData, St)
+ end.
+
+-spec check_tables() -> ok | {error, non_neg_integer()}.
+check_tables() ->
+ ?NOT_LOADED.
+
+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, "b64url"), 0).
+
+encode_loop(IoData, St) ->
+ case encode_cont(IoData, St) of
+ {ok, Bin} ->
+ Bin;
+ {partial, St} ->
+ encode_loop(IoData, St)
+ end.
+
+decode_loop(IoData, St) ->
+ case decode_cont(IoData, St) of
+ {ok, Bin} ->
+ Bin;
+ {error, _} = Ret ->
+ Ret;
+ {partial, St} ->
+ decode_loop(IoData, St)
+ end.
+
+encode_init(_) -> ?NOT_LOADED.
+encode_cont(_, _) -> ?NOT_LOADED.
+decode_init(_) -> ?NOT_LOADED.
+decode_cont(_, _) -> ?NOT_LOADED.
+
+not_loaded(Line) ->
+ erlang:nif_error({not_loaded, [{module, ?MODULE}, {line, Line}]}).
diff --git a/src/b64url/test/b64url_tests.erl b/src/b64url/test/b64url_tests.erl
new file mode 100644
index 000000000..5e8e57502
--- /dev/null
+++ b/src/b64url/test/b64url_tests.erl
@@ -0,0 +1,144 @@
+-module(b64url_tests).
+
+-include_lib("eunit/include/eunit.hrl").
+
+-define(MAX_SIZE, 6401).
+-define(NUM_TESTS, 500).
+
+table_test() ->
+ ?assertEqual(ok, b64url:check_tables()).
+
+encode_binary_test() ->
+ lists:foreach(
+ fun(_) ->
+ Bin = gen_binary(),
+ A = couch_encode_base64url(Bin),
+ B = b64url:encode(Bin),
+ ?assertEqual(A, B)
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+encode_iolist_test() ->
+ lists:foreach(
+ fun(_) ->
+ IoList = shallow_iolist(),
+ A = couch_encode_base64url(iolist_to_binary(IoList)),
+ B = b64url:encode(IoList),
+ ?assertEqual(A, B)
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+decode_binary_test() ->
+ lists:foreach(
+ fun(_) ->
+ Bin = gen_binary(),
+ B64UrlBin = couch_encode_base64url(Bin),
+ Dec = b64url:decode(B64UrlBin),
+ ?assertEqual(Bin, Dec)
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+decode_iolist_test() ->
+ lists:foreach(
+ fun(_) ->
+ IoList = shallow_b64_iolist(),
+ A = couch_decode_base64url(iolist_to_binary(IoList)),
+ B = b64url:decode(IoList),
+ ?assertEqual(A, B)
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+decode_binary_error_test() ->
+ lists:foreach(
+ fun(_) ->
+ {ErrBin, BlockPos} = bad_binary(),
+ Dec = b64url:decode(ErrBin),
+ ?assertEqual({error, {bad_block, BlockPos}}, Dec)
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+decode_bad_length_test() ->
+ lists:foreach(
+ fun(_) ->
+ Bin = bad_len_binary(),
+ ?assertError(badarg, b64url:decode(Bin))
+ end,
+ lists:seq(1, ?NUM_TESTS)
+ ).
+
+gen_binary() ->
+ % -1 to allow for 0 length
+ Length = rand:uniform(?MAX_SIZE) - 1,
+ crypto:strong_rand_bytes(Length).
+
+shallow_iolist() ->
+ to_iolist(gen_binary()).
+
+shallow_b64_iolist() ->
+ to_iolist(couch_encode_base64url(gen_binary())).
+
+bad_binary() ->
+ insert_error(gen_binary()).
+
+bad_len_binary() ->
+ make_bad_len(gen_binary()).
+
+to_iolist(<<>>) ->
+ case rand:uniform(2) of
+ 1 -> <<>>;
+ 2 -> [<<>>]
+ end;
+to_iolist(B) when is_binary(B), size(B) > 0 ->
+ S = rand:uniform(size(B)),
+ <<First:S/binary, Second/binary>> = B,
+ case rand:uniform(3) of
+ 1 ->
+ [to_iolist(First), Second];
+ 2 ->
+ [First, to_iolist(Second)];
+ 3 ->
+ [First, Second]
+ end.
+
+insert_error(B) when is_binary(B), size(B) < 2 ->
+ case rand:uniform(2) of
+ 1 -> {<<122, 255>>, 0};
+ 2 -> {<<122, 122, 255>>, 0}
+ end;
+insert_error(B) when is_binary(B) ->
+ B64 = couch_encode_base64url(B),
+ S = rand:uniform(size(B64) - 1),
+ <<First:S/binary, _:1/binary, Second/binary>> = B64,
+ {<<First:S/binary, 255, Second/binary>>, 4 * (S div 4)}.
+
+make_bad_len(Bin) when size(Bin) rem 4 == 1 ->
+ Bin;
+make_bad_len(Bin) when size(Bin) rem 4 == 2 ->
+ <<"AAA", Bin/binary>>;
+make_bad_len(Bin) when size(Bin) rem 4 == 3 ->
+ <<"AA", Bin/binary>>;
+make_bad_len(Bin) when size(Bin) rem 4 == 0 ->
+ <<"A", Bin/binary>>.
+
+% These functions are copy/pasted from couch_util to avoid
+% the direct dependency. The goal of this project is to replace
+% these in couch_util anyway so when that happens they'll only
+% exist here for these tests.
+
+couch_encode_base64url(Url) ->
+ Url1 = iolist_to_binary(re:replace(base64:encode(Url), "=+$", "")),
+ Url2 = iolist_to_binary(re:replace(Url1, "/", "_", [global])),
+ iolist_to_binary(re:replace(Url2, "\\+", "-", [global])).
+
+couch_decode_base64url(Url64) ->
+ Url1 = re:replace(iolist_to_binary(Url64), "-", "+", [global]),
+ Url2 = iolist_to_binary(
+ re:replace(iolist_to_binary(Url1), "_", "/", [global])
+ ),
+ Padding = list_to_binary(lists:duplicate((4 - size(Url2) rem 4) rem 4, $=)),
+ base64:decode(<<Url2/binary, Padding/binary>>).
diff --git a/src/b64url/test/benchmark.escript b/src/b64url/test/benchmark.escript
new file mode 100755
index 000000000..00a6f0dda
--- /dev/null
+++ b/src/b64url/test/benchmark.escript
@@ -0,0 +1,165 @@
+#!/usr/bin/env escript
+
+-mode(compile).
+
+
+-export([
+ encode/1,
+ decode/1,
+ run_worker/1
+]).
+
+
+-record(st, {
+ parent,
+ module,
+ workers,
+ minsize,
+ maxsize,
+ duration,
+ total_bytes
+}).
+
+
+main([Workers0, MinSize0, MaxSize0, Duration0]) ->
+ code:add_path("./ebin"),
+ code:add_path("../ebin"),
+ Workers = to_int(Workers0),
+ MinSize = to_int(MinSize0),
+ MaxSize = to_int(MaxSize0),
+ Duration = to_int(Duration0),
+ if Workers > 0 -> ok; true ->
+ die("Worker count must be positive~n")
+ end,
+ if MinSize > 0 -> ok; true ->
+ die("Minimum size must be positive.~n")
+ end,
+ if MaxSize > 0 -> ok; true ->
+ die("Maximum size must be positive.~n")
+ end,
+ if MinSize < MaxSize -> ok; true ->
+ die("Minimum size must be less than maximum size.~n")
+ end,
+ if Duration > 0 -> ok; true ->
+ die("Duration must be positive.~n")
+ end,
+ St = #st{
+ parent = self(),
+ workers = Workers,
+ minsize = MinSize,
+ maxsize = MaxSize,
+ duration = Duration
+ },
+ lists:foreach(fun(M) ->
+ run_test(St#st{module=M})
+ end, randomize([b64url, ?MODULE]));
+
+main(_) ->
+ Args = [escript:script_name()],
+ die("usage: ~s num_workers min_size max_size time_per_test~n", Args).
+
+
+run_test(St) ->
+ Workers = spawn_workers(St#st.workers, St),
+ start_workers(Workers),
+ Results = wait_for_workers(Workers),
+ report(St#st.module, St#st.duration, Results).
+
+
+start_workers(Pids) ->
+ lists:foreach(fun(P) ->
+ P ! start
+ end, Pids).
+
+
+wait_for_workers(Pids) ->
+ lists:map(fun(P) ->
+ receive
+ {P, TotalBytes} -> TotalBytes
+ end
+ end, Pids).
+
+
+report(Module, Duration, TotalByteList) ->
+ ModDesc = case Module of
+ ?MODULE -> "erl";
+ b64url -> "nif"
+ end,
+ TotalBytes = lists:sum(TotalByteList),
+ io:format("~s : ~14b bytes / ~3b seconds = ~14.2f bps~n", [
+ ModDesc, TotalBytes, Duration, TotalBytes / Duration]).
+
+
+spawn_workers(NumWorkers, St) ->
+ lists:map(fun(_) ->
+ spawn_link(?MODULE, run_worker, [St])
+ end, lists:seq(1, NumWorkers)).
+
+
+run_worker(St) ->
+ receive
+ start -> ok
+ end,
+ run_worker(St#st{total_bytes=0}, os:timestamp()).
+
+
+run_worker(St, Started) ->
+ HasRun = timer:now_diff(os:timestamp(), Started),
+ case HasRun div 1000000 > St#st.duration of
+ true ->
+ St#st.parent ! {self(), St#st.total_bytes};
+ false ->
+ NewSt = do_round_trip(St),
+ run_worker(NewSt, Started)
+ end.
+
+
+do_round_trip(St) ->
+ Size = St#st.minsize + rand:uniform(St#st.maxsize - St#st.minsize),
+ Data = crypto:strong_rand_bytes(Size),
+ Encoded = (St#st.module):encode(Data),
+ Data = (St#st.module):decode(Encoded),
+ St#st{total_bytes=St#st.total_bytes+Size}.
+
+
+encode(Url) ->
+ Url1 = iolist_to_binary(re:replace(base64:encode(Url), "=+$", "")),
+ Url2 = iolist_to_binary(re:replace(Url1, "/", "_", [global])),
+ iolist_to_binary(re:replace(Url2, "\\+", "-", [global])).
+
+
+decode(Url64) ->
+ Url1 = re:replace(iolist_to_binary(Url64), "-", "+", [global]),
+ Url2 = iolist_to_binary(
+ re:replace(iolist_to_binary(Url1), "_", "/", [global])
+ ),
+ Padding = list_to_binary(lists:duplicate((4 - size(Url2) rem 4) rem 4, $=)),
+ base64:decode(<<Url2/binary, Padding/binary>>).
+
+randomize(List) ->
+ List0 = [{rand:uniform(), L} || L <- List],
+ List1 = lists:sort(List0),
+ [L || {_, L} <- List1].
+
+
+to_int(Val) when is_integer(Val) ->
+ Val;
+to_int(Val) when is_binary(Val) ->
+ to_int(binary_to_list(Val));
+to_int(Val) when is_list(Val) ->
+ try
+ list_to_integer(Val)
+ catch _:_ ->
+ die("Invalid integer: ~w~n", [Val])
+ end;
+to_int(Val) ->
+ die("Invalid integer: ~w~n", [Val]).
+
+
+die(Message) ->
+ die(Message, []).
+
+die(Format, Args) ->
+ io:format(Format, Args),
+ init:stop().
+
diff --git a/src/ets_lru/.gitignore b/src/ets_lru/.gitignore
new file mode 100644
index 000000000..3164eee31
--- /dev/null
+++ b/src/ets_lru/.gitignore
@@ -0,0 +1,3 @@
+.rebar
+ebin/
+*~
diff --git a/src/ets_lru/LICENSE b/src/ets_lru/LICENSE
new file mode 100644
index 000000000..f6cd2bc80
--- /dev/null
+++ b/src/ets_lru/LICENSE
@@ -0,0 +1,202 @@
+
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
diff --git a/src/ets_lru/Makefile b/src/ets_lru/Makefile
new file mode 100644
index 000000000..058a7ecfc
--- /dev/null
+++ b/src/ets_lru/Makefile
@@ -0,0 +1,41 @@
+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
+
+
+.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/src/ets_lru/src/ets_lru.app.src b/src/ets_lru/src/ets_lru.app.src
new file mode 100644
index 000000000..c81ce11bd
--- /dev/null
+++ b/src/ets_lru/src/ets_lru.app.src
@@ -0,0 +1,21 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+{application, ets_lru, [
+ {description, "ETS Base LRU Cache"},
+ {vsn, git},
+ {registered, []},
+ {applications, [
+ kernel,
+ stdlib
+ ]}
+]}.
diff --git a/src/ets_lru/src/ets_lru.erl b/src/ets_lru/src/ets_lru.erl
new file mode 100644
index 000000000..891aeeb57
--- /dev/null
+++ b/src/ets_lru/src/ets_lru.erl
@@ -0,0 +1,335 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(ets_lru).
+-behaviour(gen_server).
+-vsn(2).
+
+-export([
+ start_link/2,
+ stop/1,
+
+ insert/3,
+ lookup/2,
+ match/3,
+ match_object/3,
+ remove/2,
+ clear/1,
+
+ % Dirty functions read straight from
+ % the ETS tables which means there are
+ % race conditions with concurrent access.
+ lookup_d/2
+]).
+
+-export([
+ init/1,
+ terminate/2,
+
+ handle_call/3,
+ handle_cast/2,
+ handle_info/2,
+
+ code_change/3
+]).
+
+-define(DEFAULT_TIME_UNIT, millisecond).
+
+-type time_value() :: integer().
+-type strict_monotonic_time() :: {time_value(), integer()}.
+
+-record(entry, {
+ key :: term(),
+ val :: term(),
+ atime :: strict_monotonic_time(),
+ ctime :: strict_monotonic_time()
+}).
+
+-record(st, {
+ objects,
+ atimes,
+ ctimes,
+
+ max_objs :: non_neg_integer() | undefined,
+ max_size :: non_neg_integer() | undefined,
+ max_lifetime :: non_neg_integer() | undefined,
+ time_unit = ?DEFAULT_TIME_UNIT :: atom()
+}).
+
+start_link(Name, Options) when is_atom(Name) ->
+ gen_server:start_link({local, Name}, ?MODULE, {Name, Options}, []).
+
+stop(LRU) ->
+ gen_server:cast(LRU, stop).
+
+lookup(LRU, Key) ->
+ gen_server:call(LRU, {lookup, Key}).
+
+insert(LRU, Key, Val) ->
+ gen_server:call(LRU, {insert, Key, Val}).
+
+remove(LRU, Key) ->
+ gen_server:call(LRU, {remove, Key}).
+
+%% @doc match/3 provides an efficient way to retrieve parts of the
+%% keys and values without copying or requiring circumvention of the
+%% ets_lru API. The KeySpec and ValueSpec parameters are used as part
+%% of one larger match spec so keep in mind that all capturing
+%% placeholders will be aliased between the key and value parts.
+-spec match(atom() | pid(), term(), term()) -> [[any()]].
+match(LRU, KeySpec, ValueSpec) ->
+ gen_server:call(LRU, {match, KeySpec, ValueSpec}).
+
+%% @doc match_object/3 provides an efficient way to retrieve multiple
+%% values using match conditions. The KeySpec and ValueSpec parameters
+%% are used as part of one larger match spec so keep in mind that all
+%% capturing placeholders will be aliased between the key and value
+%% parts.
+-spec match_object(atom() | pid(), term(), term()) -> [any()].
+match_object(Name, KeySpec, ValueSpec) when is_atom(Name) ->
+ Pattern = #entry{key = KeySpec, val = ValueSpec, _ = '_'},
+ Entries = ets:match_object(obj_table(Name), Pattern),
+ lists:map(
+ fun(#entry{key = Key, val = Val}) ->
+ gen_server:cast(Name, {accessed, Key}),
+ Val
+ end,
+ Entries
+ );
+match_object(LRU, KeySpec, ValueSpec) ->
+ gen_server:call(LRU, {match_object, KeySpec, ValueSpec}).
+
+clear(LRU) ->
+ gen_server:call(LRU, clear).
+
+lookup_d(Name, Key) when is_atom(Name) ->
+ case ets:lookup(obj_table(Name), Key) of
+ [#entry{val = Val}] ->
+ gen_server:cast(Name, {accessed, Key}),
+ {ok, Val};
+ [] ->
+ not_found
+ end.
+
+init({Name, Options}) ->
+ St = set_options(#st{}, Options),
+ ObjOpts = [set, named_table, protected, {keypos, #entry.key}],
+ TimeOpts = [ordered_set, named_table, protected],
+
+ {ok, St#st{
+ objects = ets:new(obj_table(Name), ObjOpts),
+ atimes = ets:new(at_table(Name), TimeOpts),
+ ctimes = ets:new(ct_table(Name), TimeOpts)
+ }}.
+
+terminate(_Reason, St) ->
+ true = ets:delete(St#st.objects),
+ true = ets:delete(St#st.atimes),
+ true = ets:delete(St#st.ctimes),
+ ok.
+
+handle_call({lookup, Key}, _From, St) ->
+ Reply =
+ case ets:lookup(St#st.objects, Key) of
+ [#entry{val = Val} | _] ->
+ accessed(Key, St),
+ {ok, Val};
+ [] ->
+ not_found
+ end,
+ {reply, Reply, St, 0};
+handle_call({match_object, KeySpec, ValueSpec}, _From, St) ->
+ Pattern = #entry{key = KeySpec, val = ValueSpec, _ = '_'},
+ Entries = ets:match_object(St#st.objects, Pattern),
+ Values = lists:map(
+ fun(#entry{key = Key, val = Val}) ->
+ accessed(Key, St),
+ Val
+ end,
+ Entries
+ ),
+ {reply, Values, St, 0};
+handle_call({match, KeySpec, ValueSpec}, _From, St) ->
+ Pattern = #entry{key = KeySpec, val = ValueSpec, _ = '_'},
+ Values = ets:match(St#st.objects, Pattern),
+ {reply, Values, St, 0};
+handle_call({insert, Key, Val}, _From, St) ->
+ NewATime = strict_monotonic_time(St#st.time_unit),
+ Pattern = #entry{key = Key, atime = '$1', _ = '_'},
+ case ets:match(St#st.objects, Pattern) of
+ [[ATime]] ->
+ Update = {#entry.val, Val},
+ true = ets:update_element(St#st.objects, Key, Update),
+ true = ets:delete(St#st.atimes, ATime),
+ true = ets:insert(St#st.atimes, {NewATime, Key});
+ [] ->
+ Entry = #entry{key = Key, val = Val, atime = NewATime, ctime = NewATime},
+ true = ets:insert(St#st.objects, Entry),
+ true = ets:insert(St#st.atimes, {NewATime, Key}),
+ true = ets:insert(St#st.ctimes, {NewATime, Key})
+ end,
+ {reply, ok, St, 0};
+handle_call({remove, Key}, _From, St) ->
+ Pattern = #entry{key = Key, atime = '$1', ctime = '$2', _ = '_'},
+ Reply =
+ case ets:match(St#st.objects, Pattern) of
+ [[ATime, CTime]] ->
+ true = ets:delete(St#st.objects, Key),
+ true = ets:delete(St#st.atimes, ATime),
+ true = ets:delete(St#st.ctimes, CTime),
+ ok;
+ [] ->
+ not_found
+ end,
+ {reply, Reply, St, 0};
+handle_call(clear, _From, St) ->
+ true = ets:delete_all_objects(St#st.objects),
+ true = ets:delete_all_objects(St#st.atimes),
+ true = ets:delete_all_objects(St#st.ctimes),
+ % No need to timeout here and evict cache
+ % entries because its now empty.
+ {reply, ok, St};
+handle_call(Msg, _From, St) ->
+ {stop, {invalid_call, Msg}, {invalid_call, Msg}, St}.
+
+handle_cast({accessed, Key}, St) ->
+ accessed(Key, St),
+ {noreply, St, 0};
+handle_cast(stop, St) ->
+ {stop, normal, St};
+handle_cast(Msg, St) ->
+ {stop, {invalid_cast, Msg}, St}.
+
+handle_info(timeout, St) ->
+ trim(St),
+ {noreply, St, next_timeout(St)};
+handle_info(Msg, St) ->
+ {stop, {invalid_info, Msg}, St}.
+
+code_change(_OldVsn, St, _Extra) ->
+ {ok, St}.
+
+accessed(Key, St) ->
+ Pattern = #entry{key = Key, atime = '$1', _ = '_'},
+ case ets:match(St#st.objects, Pattern) of
+ [[ATime]] ->
+ NewATime = strict_monotonic_time(St#st.time_unit),
+ Update = {#entry.atime, NewATime},
+ true = ets:update_element(St#st.objects, Key, Update),
+ true = ets:delete(St#st.atimes, ATime),
+ true = ets:insert(St#st.atimes, {NewATime, Key}),
+ ok;
+ [] ->
+ ok
+ end.
+
+trim(St) ->
+ trim_count(St),
+ trim_size(St),
+ trim_lifetime(St).
+
+trim_count(#st{max_objs = undefined}) ->
+ ok;
+trim_count(#st{max_objs = Max} = St) ->
+ case ets:info(St#st.objects, size) > Max of
+ true ->
+ drop_lru(St, fun trim_count/1);
+ false ->
+ ok
+ end.
+
+trim_size(#st{max_size = undefined}) ->
+ ok;
+trim_size(#st{max_size = Max} = St) ->
+ case ets:info(St#st.objects, memory) > Max of
+ true ->
+ drop_lru(St, fun trim_size/1);
+ false ->
+ ok
+ end.
+
+trim_lifetime(#st{max_lifetime = undefined}) ->
+ ok;
+trim_lifetime(#st{max_lifetime = Max} = St) ->
+ Now = erlang:monotonic_time(St#st.time_unit),
+ case ets:first(St#st.ctimes) of
+ '$end_of_table' ->
+ ok;
+ CTime = {Time, _} ->
+ case Now - Time > Max of
+ true ->
+ [{CTime, Key}] = ets:lookup(St#st.ctimes, CTime),
+ Pattern = #entry{key = Key, atime = '$1', _ = '_'},
+ [[ATime]] = ets:match(St#st.objects, Pattern),
+ true = ets:delete(St#st.objects, Key),
+ true = ets:delete(St#st.atimes, ATime),
+ true = ets:delete(St#st.ctimes, CTime),
+ trim_lifetime(St);
+ false ->
+ ok
+ end
+ end.
+
+drop_lru(St, Continue) ->
+ case ets:first(St#st.atimes) of
+ '$end_of_table' ->
+ empty;
+ ATime ->
+ [{ATime, Key}] = ets:lookup(St#st.atimes, ATime),
+ Pattern = #entry{key = Key, ctime = '$1', _ = '_'},
+ [[CTime]] = ets:match(St#st.objects, Pattern),
+ true = ets:delete(St#st.objects, Key),
+ true = ets:delete(St#st.atimes, ATime),
+ true = ets:delete(St#st.ctimes, CTime),
+ Continue(St)
+ end.
+
+next_timeout(#st{max_lifetime = undefined}) ->
+ infinity;
+next_timeout(St) ->
+ case ets:first(St#st.ctimes) of
+ '$end_of_table' ->
+ infinity;
+ {Time, _} ->
+ Now = erlang:monotonic_time(St#st.time_unit),
+ TimeDiff = Now - Time,
+ erlang:max(St#st.max_lifetime - TimeDiff, 0)
+ end.
+
+set_options(St, []) ->
+ St;
+set_options(St, [{max_objects, N} | Rest]) when is_integer(N), N >= 0 ->
+ set_options(St#st{max_objs = N}, Rest);
+set_options(St, [{max_size, N} | Rest]) when is_integer(N), N >= 0 ->
+ set_options(St#st{max_size = N}, Rest);
+set_options(St, [{max_lifetime, N} | Rest]) when is_integer(N), N >= 0 ->
+ set_options(St#st{max_lifetime = N}, Rest);
+set_options(St, [{time_unit, T} | Rest]) when is_atom(T) ->
+ set_options(St#st{time_unit = T}, Rest);
+set_options(_, [Opt | _]) ->
+ throw({invalid_option, Opt}).
+
+obj_table(Name) ->
+ table_name(Name, "_objects").
+
+at_table(Name) ->
+ table_name(Name, "_atimes").
+
+ct_table(Name) ->
+ table_name(Name, "_ctimes").
+
+table_name(Name, Ext) ->
+ list_to_atom(atom_to_list(Name) ++ Ext).
+
+-spec strict_monotonic_time(atom()) -> strict_monotonic_time().
+strict_monotonic_time(TimeUnit) ->
+ {erlang:monotonic_time(TimeUnit), erlang:unique_integer([monotonic])}.
diff --git a/src/ets_lru/test/ets_lru_test.erl b/src/ets_lru/test/ets_lru_test.erl
new file mode 100644
index 000000000..5dd193f8d
--- /dev/null
+++ b/src/ets_lru/test/ets_lru_test.erl
@@ -0,0 +1,339 @@
+-module(ets_lru_test).
+
+-include_lib("eunit/include/eunit.hrl").
+
+lifecyle_test_() ->
+ {
+ "Test LRU lifecycle",
+ {setup, fun() -> ets_lru:start_link(?MODULE, []) end,
+ fun({ok, LRU}) -> is_process_alive(LRU) == false end, fun({ok, LRU}) ->
+ [
+ {
+ "ets_lru:start_link/2 returned an LRU",
+ ?_assert(is_pid(LRU))
+ },
+ {
+ "Destroyed the LRU ok",
+ ?_assertEqual(ok, ets_lru:stop(LRU))
+ }
+ ]
+ end}
+ }.
+
+table_names_test_() ->
+ {
+ "Test tables names",
+ {setup, fun() -> ets_lru:start_link(foo, []) end, fun({ok, LRU}) ->
+ [
+ {
+ "foo_objects exists",
+ ?_assertEqual(0, ets:info(foo_objects, size))
+ },
+ {
+ "foo_atimes exists",
+ ?_assertEqual(0, ets:info(foo_atimes, size))
+ },
+ {
+ "foo_ctimes exists",
+ ?_assertEqual(0, ets:info(foo_ctimes, size))
+ },
+ {
+ "LRU stopped normally",
+ ?_test(begin
+ Reason = stop_lru({ok, LRU}),
+ ?assertEqual(normal, Reason)
+ end)
+ },
+ {
+ "foo_objects doesn't exists",
+ ?_assertEqual(undefined, ets:info(foo_objects, size))
+ },
+ {
+ "foo_atimes doesn't exists",
+ ?_assertEqual(undefined, ets:info(foo_atimes, size))
+ },
+ {
+ "foo_ctimes doesn't exists",
+ ?_assertEqual(undefined, ets:info(foo_ctimes, size))
+ }
+ ]
+ end}
+ }.
+
+basic_behavior_test_() ->
+ {
+ "Test basic behavior",
+ {foreach,
+ fun() ->
+ {ok, LRU} = ets_lru:start_link(test_lru, []),
+ ok = ets_lru:insert(LRU, foo, bar),
+ {ok, LRU}
+ end,
+ fun stop_lru/1, [
+ fun({ok, LRU}) ->
+ {
+ "Lookup returned the inserted value",
+ ?_assertEqual({ok, bar}, ets_lru:lookup(LRU, foo))
+ }
+ end,
+ fun({ok, _LRU}) ->
+ {
+ "Dirty lookup returned the inserted value",
+ ?_assertEqual(
+ {ok, bar},
+ ets_lru:lookup_d(test_lru, foo)
+ )
+ }
+ end,
+ fun({ok, LRU}) ->
+ [
+ {
+ "Lookup returned the inserted value",
+ ?_assertEqual({ok, bar}, ets_lru:lookup(LRU, foo))
+ },
+ {
+ "Insert new value",
+ ?_assertEqual(ok, ets_lru:insert(LRU, foo, bam))
+ },
+ {
+ "Lookup returned the newly inserted value",
+ ?_assertEqual({ok, bam}, ets_lru:lookup(LRU, foo))
+ }
+ ]
+ end,
+ fun({ok, LRU}) ->
+ [
+ {
+ "Lookup returned the inserted value",
+ ?_assertEqual({ok, bar}, ets_lru:lookup(LRU, foo))
+ },
+ {
+ "Remove value",
+ ?_assertEqual(ok, ets_lru:remove(LRU, foo))
+ },
+ {
+ "Lookup returned not_found for removed value",
+ ?_assertEqual(not_found, ets_lru:lookup(LRU, foo))
+ }
+ ]
+ end,
+ fun({ok, LRU}) ->
+ [
+ {
+ "Lookup returned the inserted value",
+ ?_assertEqual({ok, bar}, ets_lru:lookup(LRU, foo))
+ },
+ {
+ "Clear LRU",
+ ?_assertEqual(ok, ets_lru:clear(LRU))
+ },
+ {
+ "Lookup returned not_found after a clear",
+ ?_assertEqual(not_found, ets_lru:lookup(LRU, foo))
+ }
+ ]
+ end
+ ]}
+ }.
+
+lru_good_options_test_() ->
+ {
+ "Test good LRU options",
+ {foreachx,
+ fun(Opts) ->
+ process_flag(trap_exit, true),
+ ets_lru:start_link(?MODULE, Opts)
+ end,
+ fun(_, Cfg) -> stop_lru(Cfg) end, [
+ {[{max_objects, 1}], fun test_good_opts/2},
+ {[{max_objects, 5}], fun test_good_opts/2},
+ {[{max_objects, 923928342098203942}], fun test_good_opts/2},
+ {[{max_size, 1}], fun test_good_opts/2},
+ {[{max_size, 5}], fun test_good_opts/2},
+ {[{max_size, 2342923423942309423094}], fun test_good_opts/2},
+ {[{max_lifetime, 1}], fun test_good_opts/2},
+ {[{max_lifetime, 5}], fun test_good_opts/2},
+ {[{max_lifetime, 1244209909180928348}], fun test_good_opts/2}
+ ]}
+ }.
+
+lru_bad_options_test_() ->
+ {
+ "Test bad LRU options",
+ {foreachx,
+ fun(Opts) ->
+ process_flag(trap_exit, true),
+ ets_lru:start_link(?MODULE, Opts)
+ end,
+ fun(_, _) ->
+ case whereis(?MODULE) of
+ Pid when is_pid(Pid) ->
+ stop_lru({ok, Pid});
+ undefined ->
+ ok
+ end
+ end,
+ [
+ {[{bingo, bango}], fun test_bad_opts/2},
+ {[12], fun test_bad_opts/2},
+ {[true], fun test_bad_opts/2}
+ ]}
+ }.
+
+lru_limits_test_() ->
+ {
+ "Test LRU limits",
+ {foreachx, fun(Opts) -> ets_lru:start_link(lru, Opts) end, fun(_, Cfg) -> stop_lru(Cfg) end,
+ [
+ {[{max_objects, 25}], fun test_limits/2},
+ {[{max_size, 1024}], fun test_limits/2},
+ {[{max_lifetime, 100}], fun test_limits/2}
+ ]}
+ }.
+
+lru_match_test_() ->
+ {
+ "Test match functions",
+ {foreach, fun() -> ets_lru:start_link(test_lru, []) end, fun stop_lru/1, [
+ fun({ok, LRU}) ->
+ {
+ "Empty match",
+ ?_assertEqual([], ets_lru:match(LRU, a, '$1'))
+ }
+ end,
+ fun({ok, LRU}) ->
+ ets_lru:insert(LRU, b, {x, y}),
+ {
+ "Single match",
+ ?_assertEqual(
+ [[x, y]],
+ ets_lru:match(LRU, b, {'$1', '$2'})
+ )
+ }
+ end,
+ fun({ok, LRU}) ->
+ ets_lru:insert(LRU, boston, {state, "MA"}),
+ ets_lru:insert(LRU, new_york, {state, "NY"}),
+ Values = ets_lru:match(LRU, '_', {state, '$1'}),
+ {
+ "Multiple match",
+ ?_assertEqual([["MA"], ["NY"]], lists:sort(Values))
+ }
+ end,
+ fun({ok, LRU}) ->
+ {
+ "Empty match_object",
+ ?_assertEqual([], ets_lru:match_object(LRU, a, '$1'))
+ }
+ end,
+ fun({ok, LRU}) ->
+ ets_lru:insert(LRU, ans, 42),
+ [
+ {
+ "Single match_object (registered)",
+ ?_assertEqual(
+ [42],
+ ets_lru:match_object(test_lru, ans, '$1')
+ )
+ },
+ {
+ "Single match_object (pid)",
+ ?_assertEqual(
+ [42],
+ ets_lru:match_object(LRU, ans, '$1')
+ )
+ }
+ ]
+ end,
+ fun({ok, LRU}) ->
+ ets_lru:insert(LRU, {color, blue}, a),
+ ets_lru:insert(LRU, {color, red}, b),
+ Values = ets_lru:match_object(LRU, {color, '_'}, '_'),
+ {
+ "Multiple match_object",
+ ?_assertEqual(lists:sort(Values), [a, b])
+ }
+ end
+ ]}
+ }.
+
+test_good_opts(Opts, {ok, LRU}) ->
+ Msg = io_lib:format("LRU created ok with options: ~w", [Opts]),
+ {lists:flatten(Msg), ?_assert(is_pid(LRU))};
+test_good_opts(Opts, ErrorMsg) ->
+ Msg = io_lib:format("LRU created ok with options: ~w", [Opts]),
+ {lists:flatten(Msg), ?_assertEqual(ok, ErrorMsg)}.
+
+test_bad_opts([Opts], {error, {bad_return_value, {invalid_option, Opts2}}}) ->
+ Msg = io_lib:format("LRU failed with bad options: ~w", [Opts]),
+ {lists:flatten(Msg), ?_assertEqual(Opts, Opts2)}.
+
+test_limits([{max_objects, N}], {ok, LRU}) ->
+ {
+ "Max object count ok",
+ ?_assert(insert_kvs(size, LRU, 100 * N, N))
+ };
+test_limits([{max_size, N}], {ok, LRU}) ->
+ {
+ "Max size ok",
+ ?_assert(insert_kvs(memory, LRU, 10 * N, N))
+ };
+test_limits([{max_lifetime, N}], {ok, LRU}) ->
+ [
+ {
+ "Expire leaves new entries",
+ ?_test(begin
+ ets_lru:insert(LRU, foo, bar),
+ ?assertEqual({ok, bar}, ets_lru:lookup(LRU, foo))
+ end)
+ },
+ {
+ "Entry was expired",
+ ?_test(begin
+ timer:sleep(round(N * 1.5)),
+ ?assertEqual(not_found, ets_lru:lookup(LRU, foo))
+ end)
+ }
+ ].
+
+insert_kvs(_, _, 0, _) ->
+ true;
+insert_kvs(Info, LRU, Count, Limit) ->
+ ets_lru:insert(LRU, Count, 1.5234),
+ case ets:info(lru_objects, Info) > Limit of
+ true ->
+ % Retry again as eviction statistics
+ % returned by ets:info() can be delayed.
+ timer:sleep(1),
+ case ets:info(lru_objects, Info) > Limit of
+ true ->
+ erlang:error(exceeded_limit);
+ false ->
+ true
+ end;
+ false ->
+ true
+ end,
+ insert_kvs(Info, LRU, Count - 1, Limit).
+
+stop_lru({ok, LRU}) ->
+ Ref = erlang:monitor(process, LRU),
+ ets_lru:stop(LRU),
+ receive
+ {'DOWN', Ref, process, LRU, Reason} -> Reason
+ end;
+stop_lru({error, _}) ->
+ ok.
+
+valid_parameterized_time_unit_test() ->
+ Opts = [{time_unit, microsecond}],
+ {ok, LRU} = ets_lru:start_link(lru_test, Opts),
+ ?assert(is_process_alive(LRU)),
+ ok = ets_lru:insert(LRU, foo, bar),
+ ?assertEqual({ok, bar}, ets_lru:lookup(LRU, foo)),
+ ?assertEqual(ok, ets_lru:stop(LRU)).
+
+invalid_parameterized_time_unit_test() ->
+ Opts = [{time_unit, invalid}],
+ {ok, LRU} = ets_lru:start_link(lru_test, Opts),
+ ?assertExit(_, ets_lru:insert(LRU, foo, bar)).
diff --git a/src/khash/.gitignore b/src/khash/.gitignore
new file mode 100644
index 000000000..a14ed6b30
--- /dev/null
+++ b/src/khash/.gitignore
@@ -0,0 +1,10 @@
+/c_src/hash.d
+/c_src/khash.d
+c_src/*.o
+ebin/
+test/*.beam
+.eunit
+.rebar
+priv/*.so
+vc*.pdb
+compile_commands.json
diff --git a/src/khash/LICENSE b/src/khash/LICENSE
new file mode 100644
index 000000000..873b78bd3
--- /dev/null
+++ b/src/khash/LICENSE
@@ -0,0 +1,76 @@
+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/src/khash/Makefile b/src/khash/Makefile
new file mode 100644
index 000000000..ccc4a8ab0
--- /dev/null
+++ b/src/khash/Makefile
@@ -0,0 +1,44 @@
+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/src/khash/README.md b/src/khash/README.md
new file mode 100644
index 000000000..c04d00829
--- /dev/null
+++ b/src/khash/README.md
@@ -0,0 +1,4 @@
+khash
+=====
+
+This is a basic NIF wrapper around Kazlib's hash data structure.
diff --git a/src/khash/c_src/hash.c b/src/khash/c_src/hash.c
new file mode 100644
index 000000000..e3da0da20
--- /dev/null
+++ b/src/khash/c_src/hash.c
@@ -0,0 +1,843 @@
+/*
+ * 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/src/khash/c_src/hash.h b/src/khash/c_src/hash.h
new file mode 100644
index 000000000..0c75ed00f
--- /dev/null
+++ b/src/khash/c_src/hash.h
@@ -0,0 +1,240 @@
+/*
+ * 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/src/khash/c_src/khash.c b/src/khash/c_src/khash.c
new file mode 100644
index 000000000..b15a18e64
--- /dev/null
+++ b/src/khash/c_src/khash.c
@@ -0,0 +1,658 @@
+// 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/src/khash/rebar.config b/src/khash/rebar.config
new file mode 100644
index 000000000..0bf93a8d1
--- /dev/null
+++ b/src/khash/rebar.config
@@ -0,0 +1,14 @@
+% 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/src/khash.app.src b/src/khash/src/khash.app.src
new file mode 100644
index 000000000..14a45c77d
--- /dev/null
+++ b/src/khash/src/khash.app.src
@@ -0,0 +1,10 @@
+%% 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/src/khash.erl b/src/khash/src/khash.erl
new file mode 100644
index 000000000..1db4c4cdb
--- /dev/null
+++ b/src/khash/src/khash.erl
@@ -0,0 +1,136 @@
+%% 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/src/khash/test/gen_term.erl b/src/khash/test/gen_term.erl
new file mode 100644
index 000000000..d4244f11f
--- /dev/null
+++ b/src/khash/test/gen_term.erl
@@ -0,0 +1,113 @@
+%% 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/src/khash/test/khash_test.erl b/src/khash/test/khash_test.erl
new file mode 100644
index 000000000..09e23a14e
--- /dev/null
+++ b/src/khash/test/khash_test.erl
@@ -0,0 +1,374 @@
+-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().