Repository: lucy-clownfish Updated Branches: refs/heads/master 06eebd371 -> 7161001d9
Add HashIterator. Current hash iteration behavior left intact for temporary back compat; it will be removed later. Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/509361cd Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/509361cd Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/509361cd Branch: refs/heads/master Commit: 509361cd20f72e4e37e14cc04a0fca3b042af107 Parents: a6568fe Author: Tim Wilkens <[email protected]> Authored: Wed Aug 13 16:28:57 2014 -0700 Committer: Tim Wilkens <[email protected]> Committed: Wed Sep 3 09:58:25 2014 -0700 ---------------------------------------------------------------------- runtime/core/Clownfish.c | 2 + runtime/core/Clownfish/Hash.c | 5 + runtime/core/Clownfish/Hash.cfh | 3 + runtime/core/Clownfish/HashIterator.c | 122 ++++++++++ runtime/core/Clownfish/HashIterator.cfh | 48 ++++ runtime/core/Clownfish/Test.c | 2 + runtime/core/Clownfish/Test/TestHashIterator.c | 240 +++++++++++++++++++ .../core/Clownfish/Test/TestHashIterator.cfh | 29 +++ 8 files changed, 451 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish.c b/runtime/core/Clownfish.c index 130b87a..d66a108 100644 --- a/runtime/core/Clownfish.c +++ b/runtime/core/Clownfish.c @@ -16,12 +16,14 @@ #include "Clownfish/Num.h" #include "Clownfish/Hash.h" +#include "Clownfish/HashIterator.h" #include "Clownfish/Err.h" void cfish_init_parcel() { cfish_Bool_init_class(); cfish_Hash_init_class(); + cfish_HashIter_init_class(); cfish_Err_init_class(); } http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/Hash.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Hash.c b/runtime/core/Clownfish/Hash.c index 987631c..403ee1e 100644 --- a/runtime/core/Clownfish/Hash.c +++ b/runtime/core/Clownfish/Hash.c @@ -343,6 +343,11 @@ SI_rebuild_hash(Hash *self) { return (HashEntry*)self->entries; } +HashTombStone* +Hash_get_tombstone() { + return TOMBSTONE; +} + /***************************************************************************/ uint32_t http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/Hash.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Hash.cfh b/runtime/core/Clownfish/Hash.cfh index afa1904..6cd5ff1 100644 --- a/runtime/core/Clownfish/Hash.cfh +++ b/runtime/core/Clownfish/Hash.cfh @@ -45,6 +45,9 @@ class Clownfish::Hash inherits Clownfish::Obj { inert Hash* init(Hash *self, uint32_t capacity = 0); + inert HashTombStone* + get_tombstone(); + /** Empty the hash of all key-value pairs. */ void http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/HashIterator.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/HashIterator.c b/runtime/core/Clownfish/HashIterator.c new file mode 100644 index 0000000..9f5b599 --- /dev/null +++ b/runtime/core/Clownfish/HashIterator.c @@ -0,0 +1,122 @@ +/* Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +#define C_CFISH_HASH +#define C_CFISH_HASHITERATOR +#define CFISH_USE_SHORT_NAMES + +#include "Clownfish/Class.h" +#include "Clownfish/Err.h" + +#include "Clownfish/Hash.h" +#include "Clownfish/HashIterator.h" + +static HashTombStone *TOMBSTONE; + +typedef struct HashEntry { + Obj *key; + Obj *value; + int32_t hash_sum; +} HashEntry; + +void +HashIter_init_class() { + TOMBSTONE = Hash_get_tombstone(); + if (!TOMBSTONE) { + THROW(ERR, "Singleton tombstone not set in Hash."); + } +} + +HashIterator* +HashIter_new(Hash *hash) { + HashIterator *self = (HashIterator*)Class_Make_Obj(HASHITERATOR); + return HashIter_init(self, hash); +} + +HashIterator* +HashIter_init(HashIterator *self, Hash *hash) { + self->hash = (Hash*)INCREF(hash); + self->tick = -1; + self->capacity = hash->capacity; + return self; +} + +bool +HashIter_Next_IMP(HashIterator *self) { + if (self->capacity != self->hash->capacity) { + THROW(ERR, "Hash modified during iteration."); + } + while (1) { + if (++self->tick >= (int32_t)self->capacity) { + // Iteration complete. Pin tick at capacity. + self->tick = self->capacity; + return false; + } + else { + HashEntry *const entry + = (HashEntry*)self->hash->entries + self->tick; + if (entry->key && entry->key != (Obj*)TOMBSTONE) { + // Success. + return true; + } + } + } +} + +Obj* +HashIter_Get_Key_IMP(HashIterator *self) { + if (self->capacity != self->hash->capacity) { + THROW(ERR, "Hash modified during iteration."); + } + if (self->tick >= (int32_t)self->capacity) { + THROW(ERR, "Invalid call to Get_Key after end of iteration."); + } + else if (self->tick == -1) { + THROW(ERR, "Invalid call to Get_Key before iteration."); + } + + HashEntry *const entry + = (HashEntry*)self->hash->entries + self->tick; + if (entry->key == (Obj*)TOMBSTONE) { + THROW(ERR, "Hash modified during iteration."); + } + return entry->key; +} + +Obj* +HashIter_Get_Value_IMP(HashIterator *self) { + if (self->capacity != self->hash->capacity) { + THROW(ERR, "Hash modified during iteration."); + } + if (self->tick >= (int32_t)self->capacity) { + THROW(ERR, "Invalid call to Get_Value after end of iteration."); + } + else if (self->tick == -1) { + THROW(ERR, "Invalid call to Get_Value before iteration."); + } + + HashEntry *const entry + = (HashEntry*)self->hash->entries + self->tick; + return entry->value; +} + +void +HashIter_Destroy_IMP(HashIterator *self) { + DECREF(self->hash); + + SUPER_DESTROY(self, HASHITERATOR); +} + http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/HashIterator.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/HashIterator.cfh b/runtime/core/Clownfish/HashIterator.cfh new file mode 100644 index 0000000..a636504 --- /dev/null +++ b/runtime/core/Clownfish/HashIterator.cfh @@ -0,0 +1,48 @@ +/* Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +parcel Clownfish; + +/** + * Hashtable Iterator. + */ + +class Clownfish::HashIterator nickname HashIter inherits Clownfish::Obj { + Hash *hash; + size_t tick; + uint32_t capacity; + + inert void + init_class(); + + inert incremented HashIterator* + new(Hash *hash); + + inert HashIterator* + init(HashIterator *self, Hash *hash); + + public bool + Next(HashIterator *self); + + public Obj* + Get_Key(HashIterator *self); + + public nullable Obj* + Get_Value(HashIterator *self); + + public void + Destroy(HashIterator *self); +} http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/Test.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test.c b/runtime/core/Clownfish/Test.c index b891331..2a1e445 100644 --- a/runtime/core/Clownfish/Test.c +++ b/runtime/core/Clownfish/Test.c @@ -27,6 +27,7 @@ #include "Clownfish/Test/TestCharBuf.h" #include "Clownfish/Test/TestErr.h" #include "Clownfish/Test/TestHash.h" +#include "Clownfish/Test/TestHashIterator.h" #include "Clownfish/Test/TestLockFreeRegistry.h" #include "Clownfish/Test/TestNum.h" #include "Clownfish/Test/TestObj.h" @@ -42,6 +43,7 @@ Test_create_test_suite() { TestSuite_Add_Batch(suite, (TestBatch*)TestVArray_new()); TestSuite_Add_Batch(suite, (TestBatch*)TestHash_new()); + TestSuite_Add_Batch(suite, (TestBatch*)TestHashIterator_new()); TestSuite_Add_Batch(suite, (TestBatch*)TestObj_new()); TestSuite_Add_Batch(suite, (TestBatch*)TestErr_new()); TestSuite_Add_Batch(suite, (TestBatch*)TestBB_new()); http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/Test/TestHashIterator.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestHashIterator.c b/runtime/core/Clownfish/Test/TestHashIterator.c new file mode 100644 index 0000000..0f37be9 --- /dev/null +++ b/runtime/core/Clownfish/Test/TestHashIterator.c @@ -0,0 +1,240 @@ +/* Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 <stdlib.h> +#include <time.h> + +#define CFISH_USE_SHORT_NAMES +#define TESTCFISH_USE_SHORT_NAMES + +#include "Clownfish/Test/TestHashIterator.h" + +#include "Clownfish/Err.h" +#include "Clownfish/String.h" +#include "Clownfish/Hash.h" +#include "Clownfish/HashIterator.h" +#include "Clownfish/Test.h" +#include "Clownfish/VArray.h" +#include "Clownfish/TestHarness/TestBatchRunner.h" +#include "Clownfish/TestHarness/TestUtils.h" +#include "Clownfish/Class.h" + +TestHashIterator* +TestHashIterator_new() { + return (TestHashIterator*)Class_Make_Obj(TESTHASHITERATOR); +} + +static void +test_Next(TestBatchRunner *runner) { + Hash *hash = Hash_new(0); // trigger multiple rebuilds. + VArray *expected = VA_new(100); + VArray *keys = VA_new(500); + VArray *values = VA_new(500); + + for (uint32_t i = 0; i < 500; i++) { + String *str = Str_newf("%u32", i); + Hash_Store(hash, (Obj*)str, (Obj*)str); + VA_Push(expected, INCREF(str)); + } + + VA_Sort(expected, NULL, NULL); + + { + Obj *key; + Obj *value; + HashIterator *iter = HashIter_new(hash); + while (HashIter_Next(iter)) { + Obj *key = HashIter_Get_Key(iter); + Obj *value = HashIter_Get_Value(iter); + VA_Push(keys, INCREF(key)); + VA_Push(values, INCREF(value)); + } + TEST_TRUE(runner, !HashIter_Next(iter), + "Next continues to return false after iteration finishes."); + + DECREF(iter); + } + + VA_Sort(keys, NULL, NULL); + VA_Sort(values, NULL, NULL); + TEST_TRUE(runner, VA_Equals(keys, (Obj*)expected), "Keys from Iter"); + TEST_TRUE(runner, VA_Equals(values, (Obj*)expected), "Values from Iter"); + + DECREF(hash); + DECREF(expected); + DECREF(keys); + DECREF(values); +} + +static void +S_invoke_Next(void *context) { + HashIterator *iter = (HashIterator*)context; + HashIter_Next(iter); +} + +static void +S_invoke_Get_Key(void *context) { + HashIterator *iter = (HashIterator*)context; + HashIter_Get_Key(iter); +} + +static void +S_invoke_Get_Value(void *context) { + HashIterator *iter = (HashIterator*)context; + HashIter_Get_Value(iter); +} + +static void +test_empty(TestBatchRunner *runner) { + Hash *hash = Hash_new(0); + HashIterator *iter = HashIter_new(hash); + + TEST_TRUE(runner, !HashIter_Next(iter), + "First call to next false on empty hash iteration"); + + Err *get_key_error = Err_trap(S_invoke_Get_Key, iter); + TEST_TRUE(runner, get_key_error != NULL, + "Get_Key throws exception on empty hash."); + DECREF(get_key_error); + + Err *get_value_error = Err_trap(S_invoke_Get_Value, iter); + TEST_TRUE(runner, get_value_error != NULL, + "Get_Value throws exception on empty hash."); + DECREF(get_value_error); + + DECREF(hash); + DECREF(iter); +} + +static void +test_Get_Key_and_Get_Value(TestBatchRunner *runner) { + Hash *hash = Hash_new(0); + String *str = Str_newf("foo"); + Hash_Store(hash, (Obj*)str, (Obj*)str); + + HashIterator *iter = HashIter_new(hash); + DECREF(hash); + + Err *get_key_error = Err_trap(S_invoke_Get_Key, iter); + TEST_TRUE(runner, get_key_error != NULL, + "Get_Key throws exception before first call to Next."); + + Err *get_value_error = Err_trap(S_invoke_Get_Value, iter); + TEST_TRUE(runner, get_value_error != NULL, + "Get_Value throws exception before first call to Next."); + + HashIter_Next(iter); + TEST_TRUE(runner, HashIter_Get_Key(iter), "Get_Key during iteration."); + TEST_TRUE(runner, HashIter_Get_Value(iter), "Get_Value during iteration."); + + HashIter_Next(iter); + get_key_error = Err_trap(S_invoke_Get_Key, iter); + TEST_TRUE(runner, get_key_error != NULL, + "Get_Key throws exception after end of iteration."); + DECREF(get_key_error); + + get_value_error = Err_trap(S_invoke_Get_Value, iter); + TEST_TRUE(runner, get_value_error != NULL, + "Get_Value throws exception after end of iteration."); + DECREF(get_value_error); + + + DECREF(iter); +} + +static void +test_illegal_modification(TestBatchRunner *runner) { + Hash *hash = Hash_new(0); + + for (uint32_t i = 0; i < 3; i++) { + String *str = Str_newf("%u32", i); + Hash_Store(hash, (Obj*)str, (Obj*)str); + } + + HashIterator *iter = HashIter_new(hash); + HashIter_Next(iter); + + for (uint32_t i = 0; i < 100; i++) { + String *str = Str_newf("foo %u32", i); + Hash_Store(hash, (Obj*)str, (Obj*)str); + } + + Err *next_error = Err_trap(S_invoke_Next, iter); + TEST_TRUE(runner, next_error != NULL, + "Next on resized hash throws exception."); + DECREF(next_error); + + Err *get_key_error = Err_trap(S_invoke_Get_Key, iter); + TEST_TRUE(runner, get_key_error != NULL, + "Get_Key on resized hash throws exception."); + DECREF(get_key_error); + + Err *get_value_error = Err_trap(S_invoke_Get_Value, iter); + TEST_TRUE(runner, get_value_error != NULL, + "Get_Value on resized hash throws exception."); + DECREF(get_value_error); + + DECREF(hash); + DECREF(iter); +} + +static void +test_tombstone(TestBatchRunner *runner) { + { + Hash *hash = Hash_new(0); + String *str = Str_newf("foo"); + Hash_Store(hash, (Obj*)str, INCREF(str)); + DECREF(Hash_Delete(hash, (Obj*)str)); + DECREF(str); + + HashIterator *iter = HashIter_new(hash); + TEST_TRUE(runner, !HashIter_Next(iter), "Next advances past tombstones."); + + DECREF(iter); + } + + { + Hash *hash = Hash_new(0); + String *str = Str_newf("foo"); + Hash_Store(hash, (Obj*)str, INCREF(str)); + + HashIterator *iter = HashIter_new(hash); + HashIter_Next(iter); + DECREF(Hash_Delete(hash, (Obj*)str)); + + + Err *get_key_error = Err_trap(S_invoke_Get_Key, iter); + TEST_TRUE(runner, get_key_error != NULL, + "Get_Key doesn't return tombstone and throws error."); + DECREF(get_key_error); + + DECREF(str); + DECREF(iter); + } +} + +void +TestHashIterator_Run_IMP(TestHashIterator *self, TestBatchRunner *runner) { + TestBatchRunner_Plan(runner, (TestBatch*)self, 17); + srand((unsigned int)time((time_t*)NULL)); + test_Next(runner); + test_empty(runner); + test_Get_Key_and_Get_Value(runner); + test_illegal_modification(runner); + test_tombstone(runner); +} + + http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/509361cd/runtime/core/Clownfish/Test/TestHashIterator.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestHashIterator.cfh b/runtime/core/Clownfish/Test/TestHashIterator.cfh new file mode 100644 index 0000000..4765f76 --- /dev/null +++ b/runtime/core/Clownfish/Test/TestHashIterator.cfh @@ -0,0 +1,29 @@ +/* Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +parcel TestClownfish; + +class Clownfish::Test::TestHashIterator + inherits Clownfish::TestHarness::TestBatch { + + inert incremented TestHashIterator* + new(); + + void + Run(TestHashIterator *self, TestBatchRunner *runner); +} + +
