[8/8] git commit: Add support for iteration

[rn...@apache.org]

Add support for iteration

A basic iterator with accompanying fold/3 support.


Project: http://git-wip-us.apache.org/repos/asf/couchdb-khash/repo
Commit: http://git-wip-us.apache.org/repos/asf/couchdb-khash/commit/dd6a9035
Tree: http://git-wip-us.apache.org/repos/asf/couchdb-khash/tree/dd6a9035
Diff: http://git-wip-us.apache.org/repos/asf/couchdb-khash/diff/dd6a9035

Branch: refs/heads/windsor-merge
Commit: dd6a9035de3a0c298d8b4945401e42c32c9360ab
Parents: 4c04622
Author: Paul J. Davis <pa...@gmail.com>
Authored: Sat May 11 14:50:05 2013 -0500
Committer: Robert Newson <rn...@apache.org>
Committed: Wed Jul 30 17:16:33 2014 +0100

----------------------------------------------------------------------
 c_src/khash.c        | 118 +++++++++++++++++++++++++++++++++++++++++++++-
 src/khash.erl        |  59 +++++++++++++++++------
 test/006-iterators.t | 115 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 276 insertions(+), 16 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/couchdb-khash/blob/dd6a9035/c_src/khash.c
----------------------------------------------------------------------
diff --git a/c_src/khash.c b/c_src/khash.c
index de70490..038c81c 100644
--- a/c_src/khash.c
+++ b/c_src/khash.c
@@ -18,7 +18,10 @@ typedef struct
     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;
 
 
@@ -33,11 +36,21 @@ typedef struct
 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;
+
+
 // This is actually an internal Erlang VM function that
 // we're being a bit hacky to get access to. There's a
 // pending patch to expose this in the NIF API in newer
@@ -146,6 +159,7 @@ khash_create_int(ErlNifEnv* env, khash_priv* priv, ERL_NIF_TERM opts)
     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);
 
@@ -257,6 +271,8 @@ khash_clear(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
 
     kl_hash_free_nodes(khash->h);
 
+    khash->gen += 1;
+
     return priv->atom_ok;
 }
 
@@ -372,6 +388,8 @@ khash_put(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
         node->val = enif_make_copy(node->env, argv[2]);
     }
 
+    khash->gen += 1;
+
     return priv->atom_ok;
 }
 
@@ -404,6 +422,8 @@ khash_del(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
         ret = priv->atom_ok;
     }
 
+    khash->gen += 1;
+
     return ret;
 }
 
@@ -430,6 +450,91 @@ khash_size(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
 }
 
 
+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;
+    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, (void**) &khash)) {
+        return enif_make_badarg(env);
+    }
+
+    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);
+}
+
+
+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;
+    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, (void**) &iter)) {
+        return enif_make_badarg(env);
+    }
+
+    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)
 {
@@ -442,17 +547,24 @@ load(ErlNifEnv* env, void** priv, ERL_NIF_TERM info)
         return 1;
     }
 
-    res = enif_open_resource_type(env, mod, mod, khash_free, flags, NULL);
+    res = enif_open_resource_type(env, mod, "", khash_free, flags, NULL);
     if(res == NULL) {
         return 1;
     }
-
     new_priv->res_hash = res;
 
+    res = enif_open_resource_type(env, mod, "", 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;
 
@@ -491,6 +603,8 @@ static ErlNifFunc funcs[] = {
     {"put", 3, khash_put},
     {"del", 2, khash_del},
     {"size", 1, khash_size},
+    {"iter", 1, khash_iter},
+    {"iter_next", 1, khash_iter_next}
 };
 
 

http://git-wip-us.apache.org/repos/asf/couchdb-khash/blob/dd6a9035/src/khash.erl
----------------------------------------------------------------------
diff --git a/src/khash.erl b/src/khash.erl
index 5156d39..7b474bd 100644
--- a/src/khash.erl
+++ b/src/khash.erl
@@ -18,7 +18,10 @@
     get/3,
     put/3,
     del/2,
-    size/1
+    size/1,
+    iter/1,
+    iter_next/1,
+    fold/3
 ]).
 
 
@@ -26,26 +29,27 @@
 
 
 -type kv() :: {any(), any()}.
--type hash() :: term().
+-type khash() :: term().
+-type khash_iter() :: term().
 -type option() :: [].
 
 
--spec new() -> {ok, hash()}.
+-spec new() -> {ok, khash()}.
 new() ->
     new([]).
 
 
--spec new([option()]) -> {ok, hash()}.
+-spec new([option()]) -> {ok, khash()}.
 new(_Options) ->
     ?NOT_LOADED.
 
 
--spec from_list([kv()]) -> {ok, hash()}.
+-spec from_list([kv()]) -> {ok, khash()}.
 from_list(KVList) ->
     from_list(KVList, []).
 
 
--spec from_list([kv()], [option()]) -> {ok, hash()}.
+-spec from_list([kv()], [option()]) -> {ok, khash()}.
 from_list(KVList, Options) ->
     {ok, Hash} = ?MODULE:new(Options),
     lists:foreach(fun({Key, Val}) ->
@@ -54,46 +58,73 @@ from_list(KVList, Options) ->
     {ok, Hash}.
 
 
--spec to_list(hash()) -> [kv()].
+-spec to_list(khash()) -> [kv()].
 to_list(_Hash) ->
     ?NOT_LOADED.
 
 
--spec clear(hash()) -> ok.
+-spec clear(khash()) -> ok.
 clear(_Hash) ->
     ?NOT_LOADED.
 
 
--spec lookup(hash(), any()) -> {value, any()} | not_found.
+-spec lookup(khash(), any()) -> {value, any()} | not_found.
 lookup(_Hash, _Key) ->
     ?NOT_LOADED.
 
 
--spec get(hash(), any()) -> any().
+-spec get(khash(), any()) -> any().
 get(Hash, Key) ->
     get(Hash, Key, undefined).
 
 
--spec get(hash(), any(), any()) -> any().
+-spec get(khash(), any(), any()) -> any().
 get(_Hash, _Key, _Default) ->
     ?NOT_LOADED.
 
 
--spec put(hash(), any(), any()) -> ok.
+-spec put(khash(), any(), any()) -> ok.
 put(_Hash, _Key, _Value) ->
     ?NOT_LOADED.
 
 
--spec del(hash(), any()) -> ok.
+-spec del(khash(), any()) -> ok.
 del(_Hash, _Key) ->
     ?NOT_LOADED.
 
 
--spec size(hash()) -> non_neg_integer().
+-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, _} ->

http://git-wip-us.apache.org/repos/asf/couchdb-khash/blob/dd6a9035/test/006-iterators.t
----------------------------------------------------------------------
diff --git a/test/006-iterators.t b/test/006-iterators.t
new file mode 100755
index 0000000..02a7478
--- /dev/null
+++ b/test/006-iterators.t
@@ -0,0 +1,115 @@
+#! /usr/bin/env escript
+%% 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>
+
+-mode(compile).
+
+main([]) ->
+    code:add_pathz("test"),
+    util:run(12, fun() ->
+        test(),
+        ok
+    end).
+
+
+test() ->
+    test_basic(),
+    test_multi(),
+    test_expiration(),
+    test_no_expiration(),
+    ok.
+
+
+test_basic() ->
+    {ok, H} = khash:new(),
+    khash:put(H, foo, bar),
+    {ok, I} = khash:iter(H),
+    etap:is(khash:iter_next(I), {foo,bar}, "Got only kv pair as first element"),
+    etap:is(khash:iter_next(I), end_of_table, "Only the one kv pair exists"),
+    FoldFun = fun(K, V, Acc) -> [{K,V} | Acc] end,
+    etap:is(khash:fold(H, FoldFun, []), [{foo,bar}], "fold works").
+
+
+test_multi() ->
+    {ok, H} = khash:new(),
+    KVs = [{I, I} || I <- lists:seq(1, 10)],
+    lists:foreach(fun({K,V}) -> khash:put(H, K, V) end, KVs),
+    {ok, I} = khash:iter(H),
+    ReadKVs = test_multi_read(I, []),
+    etap:is(ReadKVs, KVs, "Read the same exact key/val pairs").
+
+
+test_multi_read(Iter, KVs) ->
+    case khash:iter_next(Iter) of
+        {K, V} ->
+            test_multi_read(Iter, [{K,V} | KVs]);
+        end_of_table ->
+            lists:sort(KVs)
+    end.
+
+
+test_expiration() ->
+    test_expiration("put", fun(H) ->
+        khash:put(H, foo, bar2),
+        ok
+    end),
+
+    test_expiration("del", fun(H) ->
+        khash:del(H, foo),
+        ok
+    end),
+
+    test_expiration("clear", fun(H) ->
+        khash:clear(H),
+        ok
+    end).
+
+
+test_expiration(FunName, Fun) ->
+    Error = {error, expired_iterator},
+    {ok, H} = khash:new(),
+    khash:put(H, foo, bar),
+    {ok, I} = khash:iter(H),
+    ok = Fun(H),
+    Msg = FunName ++ " expires iterators",
+    etap:is(khash:iter_next(I), Error, Msg).
+
+
+test_no_expiration() ->
+    test_no_expiration("to_list", fun(H) ->
+        [{foo,bar}] = khash:to_list(H),
+        ok
+    end),
+
+    test_no_expiration("lookup", fun(H) ->
+        {value,bar} = khash:lookup(H,foo),
+        ok
+    end),
+
+    test_no_expiration("get", fun(H) ->
+        bar = khash:get(H, foo),
+        ok
+    end),
+
+    test_no_expiration("size", fun(H) ->
+        1 = khash:size(H),
+        ok
+    end),
+
+    test_no_expiration("iteration", fun(H) ->
+        {ok, I} = khash:iter(H),
+        {foo, bar} = khash:iter_next(I),
+        end_of_table = khash:iter_next(I),
+        ok
+    end).
+
+
+test_no_expiration(FunName, Fun) ->
+    Error = {error, expired_iterator},
+    {ok, H} = khash:new(),
+    khash:put(H, foo, bar),
+    {ok, I} = khash:iter(H),
+    ok = Fun(H),
+    Msg = FunName ++ " doesn't expire iterators",
+    etap:isnt(khash:iter_next(I), Error, Msg).