You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by ma...@apache.org on 2009/09/15 03:05:38 UTC
svn commit: r814950 - in /lucene/lucy/trunk: core/Lucy/Object/Hash.bp
core/Lucy/Object/Hash.c core/Lucy/Test/Object/TestHash.bp
core/Lucy/Test/Object/TestHash.c perl/lib/Lucy/Object/Hash.pm
perl/t/core/017-hash.t
Author: marvin
Date: Tue Sep 15 01:05:38 2009
New Revision: 814950
URL: http://svn.apache.org/viewvc?rev=814950&view=rev
Log:
Commit LUCY-42, adding Lucy::Object::Hash.
Added:
lucene/lucy/trunk/core/Lucy/Object/Hash.bp (with props)
lucene/lucy/trunk/core/Lucy/Object/Hash.c (with props)
lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp (with props)
lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c (with props)
lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm (with props)
lucene/lucy/trunk/perl/t/core/017-hash.t (with props)
Added: lucene/lucy/trunk/core/Lucy/Object/Hash.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/Hash.bp?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/Hash.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Object/Hash.bp Tue Sep 15 01:05:38 2009
@@ -0,0 +1,141 @@
+parcel Lucy;
+
+/**
+ * Hashtable.
+ *
+ * Values are stored by reference and may be any kind of Obj. By default, keys
+ * are cloned and so must belong to a class that implements Clone(); however,
+ * this behavior can be changed by overridding Make_Key(), e.g. to implement
+ * efficient hash sets.
+ */
+class Lucy::Object::Hash extends Lucy::Object::Obj {
+
+ void *entries;
+ u32_t capacity;
+ u32_t size;
+ u32_t threshold; /* rehashing trigger point */
+ i32_t iter_tick; /* used when iterating */
+
+ inert incremented Hash*
+ new(u32_t capacity = 0);
+
+ /**
+ * @param capacity The number of elements that the hash will be asked to
+ * hold initially.
+ */
+ inert Hash*
+ init(Hash *self, u32_t capacity = 0);
+
+ /** Empty the hash of all key-value pairs.
+ */
+ void
+ Clear(Hash *self);
+
+ /** Store a key-value pair. If <code>key</code> is not already present,
+ * Make_Key() will be called to manufacture the internally used key.
+ */
+ void
+ Store(Hash *self, Obj *key, decremented Obj *value);
+
+ void
+ Store_Str(Hash *self, const char *str, size_t len,
+ decremented Obj *value);
+
+ /** Fetch the value associated with <code>key</code>.
+ *
+ * @return the value, or NULL if <code>key</code> is not present.
+ */
+ Obj*
+ Fetch(Hash *self, const Obj *key);
+
+ Obj*
+ Fetch_Str(Hash *self, const char *key, size_t key_len);
+
+ /** Attempt to delete a key-value pair from the hash.
+ *
+ * @return the value if <code>key</code> exists and thus deletion
+ * succeeds; otherwise NULL.
+ */
+ incremented Obj*
+ Delete(Hash *self, const Obj *key);
+
+ incremented Obj*
+ Delete_Str(Hash *self, const char *key, size_t key_ley);
+
+ /** Prepare to iterate over all the key-value pairs in the hash.
+ *
+ * @return the number of pairs which will be iterated over.
+ */
+ u32_t
+ Iter_Init(Hash *self);
+
+ /** Retrieve the next key-value pair from the hash, setting the supplied
+ * pointers to point at them.
+ *
+ * @return true while iterating, false when the iterator has been
+ * exhausted.
+ */
+ bool_t
+ Iter_Next(Hash *self, Obj **key, Obj **value);
+
+ /** Search for a key which Equals the key supplied, and return the key
+ * rather than its value.
+ */
+ Obj*
+ Find_Key(Hash *self, const Obj *key, i32_t hash_code);
+
+ /** Return an VArray of pointers to the hash's keys.
+ */
+ incremented VArray*
+ Keys(Hash *self);
+
+ /** Return an VArray of pointers to the hash's values.
+ */
+ incremented VArray*
+ Values(Hash *self);
+
+ /** Create a key to be stored within the hash entry. Implementations must
+ * supply an object which produces the same Hash_Code() value and tests
+ * true for Equals(). By default, calls Clone().
+ */
+ public incremented Obj*
+ Make_Key(Hash *self, Obj *key, i32_t hash_code);
+
+ u32_t
+ Get_Capacity(Hash *self);
+
+ /** Accessor for Hash's "size" member.
+ *
+ * @return the number of key-value pairs.
+ */
+ public u32_t
+ Get_Size(Hash *self);
+
+ public bool_t
+ Equals(Hash *self, Obj *other);
+
+ public incremented Hash*
+ Dump(Hash *self);
+
+ public incremented Obj*
+ Load(Hash *self, Obj *dump);
+
+ public void
+ Destroy(Hash *self);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * 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.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Object/Hash.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Object/Hash.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/Hash.c?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/Hash.c (added)
+++ lucene/lucy/trunk/core/Lucy/Object/Hash.c Tue Sep 15 01:05:38 2009
@@ -0,0 +1,435 @@
+#define C_LUCY_HASH
+#define C_LUCY_ZOMBIECHARBUF
+#define LUCY_USE_SHORT_NAMES
+#define CHY_USE_SHORT_NAMES
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "Lucy/Object/VTable.h"
+
+#include "Lucy/Object/Hash.h"
+#include "Lucy/Object/CharBuf.h"
+#include "Lucy/Object/Err.h"
+#include "Lucy/Object/Undefined.h"
+#include "Lucy/Object/VArray.h"
+#include "Lucy/Util/Memory.h"
+
+#define HashEntry lucy_HashEntry
+
+typedef struct lucy_HashEntry {
+ Obj *key;
+ Obj *value;
+ i32_t hash_code;
+} lucy_HashEntry;
+
+/* Reset the iterator. Hash_iter_init must be called to restart iteration.
+ */
+static INLINE void
+SI_kill_iter(Hash *self);
+
+/* Return the entry associated with the key, if any.
+ */
+static INLINE HashEntry*
+SI_fetch_entry(Hash *self, const Obj *key, i32_t hash_code);
+
+/* Double the number of buckets and redistribute all entries.
+ *
+ * This should be a static inline function, but right now we need to suppress
+ * memory leaks from it because the VTable_registry never gets completely
+ * cleaned up.
+ */
+HashEntry*
+lucy_Hash_rebuild_hash(Hash *self);
+
+Hash*
+Hash_new(u32_t capacity)
+{
+ Hash *self = (Hash*)VTable_Make_Obj(HASH);
+ return Hash_init(self, capacity);
+}
+
+Hash*
+Hash_init(Hash *self, u32_t capacity)
+{
+ /* Allocate enough space to hold the requested number of elements without
+ * triggering a rebuild. */
+ u32_t requested_capacity = capacity < I32_MAX ? capacity : I32_MAX;
+ u32_t threshold;
+ capacity = 16;
+ while (1) {
+ threshold = (capacity / 3) * 2;
+ if (threshold > requested_capacity) { break; }
+ capacity *= 2;
+ }
+
+ /* Init. */
+ self->size = 0;
+ self->iter_tick = -1;
+
+ /* Derive. */
+ self->capacity = capacity;
+ self->entries = (HashEntry*)CALLOCATE(capacity, sizeof(HashEntry));
+ self->threshold = threshold;
+
+ return self;
+}
+
+void
+Hash_destroy(Hash *self)
+{
+ if (self->entries) {
+ Hash_Clear(self);
+ FREEMEM(self->entries);
+ }
+ SUPER_DESTROY(self, HASH);
+}
+
+Hash*
+Hash_dump(Hash *self)
+{
+ Hash *dump = Hash_new(self->size);
+ Obj *key;
+ Obj *value;
+
+ Hash_Iter_Init(self);
+ while (Hash_Iter_Next(self, &key, &value)) {
+ /* Since JSON only supports text hash keys, Dump() can only support
+ * text hash keys. */
+ ASSERT_IS_A(key, CHARBUF);
+ Hash_Store(dump, key, Obj_Dump(value));
+ }
+
+ return dump;
+}
+
+Obj*
+Hash_load(Hash *self, Obj *dump)
+{
+ Hash *source = (Hash*)ASSERT_IS_A(dump, HASH);
+ CharBuf *class_name = (CharBuf*)Hash_Fetch_Str(source, "_class", 6);
+ UNUSED_VAR(self);
+
+ /* Assume that the presence of the "_class" key paired with a valid class
+ * name indicates the output of a Dump rather than an ordinary Hash. */
+ if (class_name && Obj_Is_A(class_name, CHARBUF)) {
+ VTable *vtable = VTable_fetch_vtable(class_name);
+
+ if (!vtable) {
+ CharBuf *parent_class = VTable_find_parent_class(class_name);
+ if (parent_class) {
+ VTable *parent = VTable_singleton(parent_class, NULL);
+ vtable = VTable_singleton(class_name, parent);
+ DECREF(parent_class);
+ }
+ else {
+ /* TODO: Fix Hash_Load() so that it works with ordinary hash
+ * keys named "_class". */
+ THROW(ERR, "Can't find class '%o'", class_name);
+ }
+ }
+
+ /* Dispatch to an alternate Load() method. */
+ if (vtable) {
+ Obj_load_t load = (Obj_load_t)METHOD(vtable, Obj, Load);
+ if (load == Obj_load) {
+ THROW(ERR, "Abstract method Load() not defined for %o",
+ VTable_Get_Name(vtable));
+ }
+ else if (load != (Obj_load_t)Hash_load) { /* stop inf loop */
+ return load(NULL, dump);
+ }
+ }
+ }
+
+ /* It's an ordinary Hash. */
+ {
+ Hash *loaded = Hash_new(source->size);
+ Obj *key;
+ Obj *value;
+
+ Hash_Iter_Init(source);
+ while (Hash_Iter_Next(source, &key, &value)) {
+ Hash_Store(loaded, key, Obj_Load(value, value));
+ }
+
+ return (Obj*)loaded;
+ }
+}
+
+void
+Hash_clear(Hash *self)
+{
+ HashEntry *entry = (HashEntry*)self->entries;
+ HashEntry *const limit = entry + self->capacity;
+
+ /* Iterate through all entries. */
+ for ( ; entry < limit; entry++) {
+ if (!entry->key) { continue; }
+ DECREF(entry->key);
+ DECREF(entry->value);
+ entry->key = NULL;
+ entry->value = NULL;
+ entry->hash_code = 0;
+ }
+
+ self->size = 0;
+}
+
+void
+lucy_Hash_do_store(Hash *self, Obj *key, Obj *value,
+ i32_t hash_code, bool_t use_this_key)
+{
+ HashEntry *entries = self->size >= self->threshold
+ ? lucy_Hash_rebuild_hash(self)
+ : (HashEntry*)self->entries;
+ HashEntry *entry;
+ u32_t tick = hash_code;
+ const u32_t mask = self->capacity - 1;
+
+ while (1) {
+ tick &= mask;
+ entry = entries + tick;
+ if (entry->key == (Obj*)UNDEF || !entry->key) {
+ if (entry->key == (Obj*)UNDEF) {
+ /* Take note of diminished tombstone clutter. */
+ self->threshold++;
+ }
+ entry->key = use_this_key
+ ? key
+ : Hash_Make_Key(self, key, hash_code);
+ entry->value = value;
+ entry->hash_code = hash_code;
+ self->size++;
+ break;
+ }
+ else if ( entry->hash_code == hash_code
+ && Obj_Equals(key, entry->key)
+ ) {
+ DECREF(entry->value);
+ entry->value = value;
+ break;
+ }
+ tick++; /* linear scan */
+ }
+}
+
+void
+Hash_store(Hash *self, Obj *key, Obj *value)
+{
+ lucy_Hash_do_store(self, key, value, Obj_Hash_Code(key), false);
+}
+
+void
+Hash_store_str(Hash *self, const char *key, size_t key_len, Obj *value)
+{
+ ZombieCharBuf key_buf = ZCB_make_str((char*)key, key_len);
+ lucy_Hash_do_store(self, (Obj*)&key_buf, value,
+ ZCB_Hash_Code(&key_buf), false);
+}
+
+Obj*
+Hash_make_key(Hash *self, Obj *key, i32_t hash_code)
+{
+ UNUSED_VAR(self);
+ UNUSED_VAR(hash_code);
+ return Obj_Clone(key);
+}
+
+Obj*
+Hash_fetch_str(Hash *self, const char *key, size_t key_len)
+{
+ ZombieCharBuf key_buf = ZCB_make_str(key, key_len);
+ return Hash_fetch(self, (Obj*)&key_buf);
+}
+
+static INLINE HashEntry*
+SI_fetch_entry(Hash *self, const Obj *key, i32_t hash_code)
+{
+ u32_t tick = hash_code;
+ HashEntry *const entries = (HashEntry*)self->entries;
+ HashEntry *entry;
+
+ while (1) {
+ tick &= self->capacity - 1;
+ entry = entries + tick;
+ if (!entry->key) {
+ /* Failed to find the key, so return NULL. */
+ return NULL;
+ }
+ else if ( entry->hash_code == hash_code
+ && Obj_Equals(key, entry->key)
+ ) {
+ return entry;
+ }
+ tick++;
+ }
+}
+
+Obj*
+Hash_fetch(Hash *self, const Obj *key)
+{
+ HashEntry *entry = SI_fetch_entry(self, key, Obj_Hash_Code(key));
+ return entry ? entry->value : NULL;
+}
+
+Obj*
+Hash_delete(Hash *self, const Obj *key)
+{
+ HashEntry *entry = SI_fetch_entry(self, key, Obj_Hash_Code(key));
+ if (entry) {
+ Obj *value = entry->value;
+ DECREF(entry->key);
+ entry->key = (Obj*)UNDEF;
+ entry->value = NULL;
+ entry->hash_code = 0;
+ self->size--;
+ self->threshold--; /* limit number of tombstones */
+ return value;
+ }
+ else {
+ return NULL;
+ }
+}
+
+Obj*
+Hash_delete_str(Hash *self, const char *key, size_t key_len)
+{
+ ZombieCharBuf key_buf = ZCB_make_str(key, key_len);
+ return Hash_delete(self, (Obj*)&key_buf);
+}
+
+u32_t
+Hash_iter_init(Hash *self)
+{
+ SI_kill_iter(self);
+ return self->size;
+}
+
+static INLINE void
+SI_kill_iter(Hash *self)
+{
+ self->iter_tick = -1;
+}
+
+bool_t
+Hash_iter_next(Hash *self, Obj **key, Obj **value)
+{
+ while (1) {
+ if (++self->iter_tick >= (i32_t)self->capacity) {
+ /* Bail since we've completed the iteration. */
+ --self->iter_tick;
+ *key = NULL;
+ *value = NULL;
+ return false;
+ }
+ else {
+ HashEntry *const entry
+ = (HashEntry*)self->entries + self->iter_tick;
+ if (entry->key && entry->key != (Obj*)UNDEF) {
+ /* Success! */
+ *key = entry->key;
+ *value = entry->value;
+ return true;
+ }
+ }
+ }
+}
+
+Obj*
+Hash_find_key(Hash *self, const Obj *key, i32_t hash_code)
+{
+ HashEntry *entry = SI_fetch_entry(self, key, hash_code);
+ return entry ? entry->key : NULL;
+}
+
+VArray*
+Hash_keys(Hash *self)
+{
+ Obj *key;
+ Obj *val;
+ VArray *keys = VA_new(self->size);
+ Hash_Iter_Init(self);
+ while (Hash_Iter_Next(self, &key, &val)) {
+ VA_push(keys, INCREF(key));
+ }
+ return keys;
+}
+
+VArray*
+Hash_values(Hash *self)
+{
+ Obj *key;
+ Obj *val;
+ VArray *values = VA_new(self->size);
+ Hash_Iter_Init(self);
+ while (Hash_Iter_Next(self, &key, &val)) VA_push(values, INCREF(val));
+ return values;
+}
+
+bool_t
+Hash_equals(Hash *self, Obj *other)
+{
+ Hash *evil_twin = (Hash*)other;
+ Obj *key;
+ Obj *val;
+
+ if (evil_twin == self) return true;
+ if (!Obj_Is_A(evil_twin, HASH)) return false;
+ if (self->size != evil_twin->size) return false;
+
+ Hash_Iter_Init(self);
+ while (Hash_Iter_Next(self, &key, &val)) {
+ Obj *other_val = Hash_Fetch(evil_twin, key);
+ if (!other_val || !Obj_Equals(other_val, val)) return false;
+ }
+
+ return true;
+}
+
+u32_t
+Hash_get_capacity(Hash *self) { return self->capacity; }
+u32_t
+Hash_get_size(Hash *self) { return self->size; }
+
+HashEntry*
+lucy_Hash_rebuild_hash(Hash *self)
+{
+ HashEntry *old_entries = (HashEntry*)self->entries;
+ HashEntry *entry = old_entries;
+ HashEntry *limit = old_entries + self->capacity;
+
+ SI_kill_iter(self);
+ self->capacity *= 2;
+ self->threshold = (self->capacity / 3) * 2;
+ self->entries = (HashEntry*)CALLOCATE(self->capacity, sizeof(HashEntry));
+ self->size = 0;
+
+ for ( ; entry < limit; entry++) {
+ if (!entry->key || entry->key == (Obj*)UNDEF) {
+ continue;
+ }
+ lucy_Hash_do_store(self, entry->key, entry->value,
+ entry->hash_code, true);
+ }
+
+ FREEMEM(old_entries);
+
+ return self->entries;
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * 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.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Object/Hash.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp Tue Sep 15 01:05:38 2009
@@ -0,0 +1,22 @@
+parcel Lucy;
+
+inert class Lucy::Test::Object::TestHash {
+ inert void
+ run_tests();
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * 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.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c Tue Sep 15 01:05:38 2009
@@ -0,0 +1,290 @@
+#include "Lucy/Util/ToolSet.h"
+#include <stdlib.h>
+#include <time.h>
+
+#include "Lucy/Test.h"
+#include "Lucy/Test/Object/TestHash.h"
+#include "Lucy/Object/Hash.h"
+#include "Lucy/Object/Undefined.h"
+
+static CharBuf*
+S_random_string()
+{
+ u32_t len = rand() % 1200;
+ CharBuf *string = CB_new(len * 3);
+
+ while (len--) {
+ u8_t bytes = (rand() % 3) + 1;
+ u32_t code_point = 0;
+ switch (bytes & 0x3) {
+ case 1:
+ code_point = rand() % 0x80;
+ break;
+ case 2:
+ code_point = (rand() % (0x0800 - 0x0080)) + 0x0080;
+ break;
+ case 3:
+ code_point = (rand() % (0x10000 - 0x0800)) + 0x0800;
+ break;
+ }
+ CB_Cat_Char(string, code_point);
+ }
+
+ return string;
+}
+
+static void
+test_Equals(TestBatch *batch)
+{
+ Hash *hash = Hash_new(0);
+ Hash *other = Hash_new(0);
+
+ ASSERT_TRUE(batch, Hash_Equals(hash, (Obj*)other),
+ "Empty hashes are equal");
+
+ Hash_Store_Str(hash, "foo", 3, INCREF(&EMPTY));
+ ASSERT_FALSE(batch, Hash_Equals(hash, (Obj*)other),
+ "Add one pair and Equals returns false");
+
+ Hash_Store_Str(other, "foo", 3, INCREF(&EMPTY));
+ ASSERT_TRUE(batch, Hash_Equals(hash, (Obj*)other),
+ "Add a matching pair and Equals returns true");
+
+ Hash_Store_Str(other, "foo", 3, INCREF(UNDEF));
+ ASSERT_FALSE(batch, Hash_Equals(hash, (Obj*)other),
+ "Non-matching value spoils Equals");
+
+ DECREF(hash);
+ DECREF(other);
+}
+
+static void
+test_Store_and_Fetch(TestBatch *batch)
+{
+ Hash *hash = Hash_new(100);
+ Hash *dupe = Hash_new(100);
+ const u32_t starting_cap = Hash_Get_Capacity(hash);
+ VArray *expected = VA_new(100);
+ VArray *got = VA_new(100);
+ ZombieCharBuf twenty = ZCB_make_str("20", 2);
+ ZombieCharBuf forty = ZCB_make_str("40", 2);
+ ZombieCharBuf foo = ZCB_make_str("foo", 3);
+ i32_t i;
+
+ for (i = 0; i < 100; i++) {
+ CharBuf *cb = CB_newf("%i32", i);
+ Hash_Store(hash, (Obj*)cb, (Obj*)cb);
+ Hash_Store(dupe, (Obj*)cb, INCREF(cb));
+ VA_Push(expected, INCREF(cb));
+ }
+ ASSERT_TRUE(batch, Hash_Equals(hash, (Obj*)dupe), "Equals");
+
+ ASSERT_INT_EQ(batch, Hash_Get_Capacity(hash), starting_cap,
+ "Initial capacity sufficient (no rebuilds)");
+
+ for (i = 0; i < 100; i++) {
+ Obj *key = VA_Fetch(expected, i);
+ Obj *elem = Hash_Fetch(hash, key);
+ VA_Push(got, (Obj*)INCREF(elem));
+ }
+
+ ASSERT_TRUE(batch, VA_Equals(got, (Obj*)expected),
+ "basic Store and Fetch");
+ ASSERT_INT_EQ(batch, Hash_Get_Size(hash), 100,
+ "size incremented properly by Hash_Store");
+
+ ASSERT_TRUE(batch, Hash_Fetch(hash, (Obj*)&foo) == NULL,
+ "Fetch against non-existent key returns NULL");
+
+ Hash_Store(hash, (Obj*)&forty, INCREF(&foo));
+ ASSERT_TRUE(batch, Hash_Equals(&foo, Hash_Fetch(hash, (Obj*)&forty)),
+ "Hash_Store replaces existing value");
+ ASSERT_FALSE(batch, Hash_Equals(hash, (Obj*)dupe),
+ "replacement value spoils equals");
+ ASSERT_INT_EQ(batch, Hash_Get_Size(hash), 100,
+ "size unaffected after value replaced");
+
+ ASSERT_TRUE(batch, Hash_Delete(hash, (Obj*)&forty) == (Obj*)&foo,
+ "Delete returns value");
+ DECREF(&foo);
+ ASSERT_INT_EQ(batch, Hash_Get_Size(hash), 99,
+ "size decremented by successful Delete");
+ ASSERT_TRUE(batch, Hash_Delete(hash, (Obj*)&forty) == NULL,
+ "Delete returns NULL when key not found");
+ ASSERT_INT_EQ(batch, Hash_Get_Size(hash), 99,
+ "size not decremented by unsuccessful Delete");
+ DECREF(Hash_Delete(dupe, (Obj*)&forty));
+ ASSERT_TRUE(batch, VA_Equals(got, (Obj*)expected), "Equals after Delete");
+
+ Hash_Clear(hash);
+ ASSERT_TRUE(batch, Hash_Fetch(hash, (Obj*)&twenty) == NULL, "Clear");
+ ASSERT_TRUE(batch, Hash_Get_Size(hash) == 0, "size is 0 after Clear");
+
+ DECREF(hash);
+ DECREF(dupe);
+ DECREF(got);
+ DECREF(expected);
+}
+
+static void
+test_Keys_Values_Iter(TestBatch *batch)
+{
+ u32_t i;
+ Hash *hash = Hash_new(0); /* trigger multiple rebuilds. */
+ VArray *expected = VA_new(100);
+ VArray *keys;
+ VArray *values;
+
+ for (i = 0; i < 500; i++) {
+ CharBuf *cb = CB_newf("%u32", i);
+ Hash_Store(hash, (Obj*)cb, (Obj*)cb);
+ VA_Push(expected, INCREF(cb));
+ }
+
+ VA_Sort(expected, NULL, NULL);
+
+ keys = Hash_Keys(hash);
+ values = Hash_Values(hash);
+ VA_Sort(keys, NULL, NULL);
+ VA_Sort(values, NULL, NULL);
+ ASSERT_TRUE(batch, VA_Equals(keys, (Obj*)expected), "Keys");
+ ASSERT_TRUE(batch, VA_Equals(values, (Obj*)expected), "Values");
+ VA_Clear(keys);
+ VA_Clear(values);
+
+ {
+ Obj *key;
+ Obj *value;
+ Hash_Iter_Init(hash);
+ while (Hash_Iter_Next(hash, &key, &value)) {
+ VA_Push(keys, INCREF(key));
+ VA_Push(values, INCREF(value));
+ }
+ }
+
+ VA_Sort(keys, NULL, NULL);
+ VA_Sort(values, NULL, NULL);
+ ASSERT_TRUE(batch, VA_Equals(keys, (Obj*)expected), "Keys from Iter");
+ ASSERT_TRUE(batch, VA_Equals(values, (Obj*)expected), "Values from Iter");
+
+ {
+ ZombieCharBuf forty = ZCB_make_str("40", 2);
+ ZombieCharBuf nope = ZCB_make_str("nope", 4);
+ Obj *key = Hash_Find_Key(hash, (Obj*)&forty, ZCB_Hash_Code(&forty));
+ ASSERT_TRUE(batch, Obj_Equals(key, (Obj*)&forty), "Find_Key");
+ key = Hash_Find_Key(hash, (Obj*)&nope, ZCB_Hash_Code(&nope)),
+ ASSERT_TRUE(batch, key == NULL,
+ "Find_Key returns NULL for non-existent key");
+ }
+
+ DECREF(hash);
+ DECREF(expected);
+ DECREF(keys);
+ DECREF(values);
+}
+
+static void
+test_Dump_and_Load(TestBatch *batch)
+{
+ Hash *hash = Hash_new(0);
+ Obj *dump;
+ Hash *loaded;
+
+ Hash_Store_Str(hash, "foo", 3,
+ (Obj*)CB_new_from_trusted_utf8("foo", 3));
+ dump = (Obj*)Hash_Dump(hash);
+ loaded = (Hash*)Obj_Load(dump, dump);
+ ASSERT_TRUE(batch, Hash_Equals(hash, (Obj*)loaded),
+ "Dump => Load round trip");
+ DECREF(dump);
+ DECREF(loaded);
+
+ /* TODO: Fix Hash_Load().
+
+ Hash_Store_Str(hash, "_class", 6,
+ (Obj*)CB_new_from_trusted_utf8("not_a_class", 11));
+ dump = (Obj*)Hash_Dump(hash);
+ loaded = (Hash*)Obj_Load(dump, dump);
+
+ ASSERT_TRUE(batch, Hash_Equals(hash, (Obj*)loaded),
+ "Load still works with _class if it's not a real class");
+ DECREF(dump);
+ DECREF(loaded);
+
+ */
+
+ DECREF(hash);
+}
+
+static void
+test_stress(TestBatch *batch)
+{
+ u32_t i;
+ Hash *hash = Hash_new(0); /* trigger multiple rebuilds. */
+ VArray *expected = VA_new(1000);
+ VArray *keys;
+ VArray *values;
+
+ for (i = 0; i < 1000; i++) {
+ CharBuf *cb = S_random_string();
+ while (Hash_Fetch(hash, (Obj*)cb)) {
+ DECREF(cb);
+ cb = S_random_string();
+ }
+ Hash_Store(hash, (Obj*)cb, (Obj*)cb);
+ VA_Push(expected, INCREF(cb));
+ }
+
+ VA_Sort(expected, NULL, NULL);
+
+ /* Overwrite for good measure. */
+ for (i = 0; i < 1000; i++) {
+ CharBuf *cb = (CharBuf*)VA_Fetch(expected, i);
+ Hash_Store(hash, (Obj*)cb, INCREF(cb));
+ }
+
+ keys = Hash_Keys(hash);
+ values = Hash_Values(hash);
+ VA_Sort(keys, NULL, NULL);
+ VA_Sort(values, NULL, NULL);
+ ASSERT_TRUE(batch, VA_Equals(keys, (Obj*)expected), "stress Keys");
+ ASSERT_TRUE(batch, VA_Equals(values, (Obj*)expected), "stress Values");
+
+ DECREF(keys);
+ DECREF(values);
+ DECREF(expected);
+ DECREF(hash);
+}
+
+void
+TestHash_run_tests()
+{
+ TestBatch *batch = Test_new_batch("TestHash", 28, NULL);
+
+ srand((unsigned int)time((time_t*)NULL));
+
+ PLAN(batch);
+ test_Equals(batch);
+ test_Store_and_Fetch(batch);
+ test_Keys_Values_Iter(batch);
+ test_Dump_and_Load(batch);
+ test_stress(batch);
+
+ batch->destroy(batch);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * 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.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestHash.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm (added)
+++ lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm Tue Sep 15 01:05:38 2009
@@ -0,0 +1,89 @@
+use Lucy;
+
+1;
+
+__END__
+
+__BINDING__
+
+my $xs_code = <<'END_XS_CODE';
+MODULE = Lucy PACKAGE = Lucy::Object::Hash
+
+SV*
+_fetch(self, key)
+ lucy_Hash *self;
+ lucy_ZombieCharBuf key;
+CODE:
+ RETVAL = LUCY_OBJ_TO_SV(lucy_Hash_fetch(self, (lucy_Obj*)&key));
+OUTPUT: RETVAL
+
+void
+store(self, key, value);
+ lucy_Hash *self;
+ lucy_ZombieCharBuf key;
+ lucy_Obj *value;
+PPCODE:
+{
+ if (value) { LUCY_INCREF(value); }
+ lucy_Hash_store(self, (lucy_Obj*)&key, value);
+}
+
+void
+iter_next(self)
+ lucy_Hash *self;
+PPCODE:
+{
+ lucy_Obj *key;
+ lucy_Obj *val;
+
+ if (Lucy_Hash_Iter_Next(self, &key, &val)) {
+ SV *key_sv = Lucy_Obj_To_Host(key);
+ SV *val_sv = Lucy_Obj_To_Host(val);
+
+ XPUSHs(sv_2mortal( key_sv ));
+ XPUSHs(sv_2mortal( val_sv ));
+ XSRETURN(2);
+ }
+ else {
+ XSRETURN_EMPTY;
+ }
+}
+END_XS_CODE
+
+Boilerplater::Binding::Perl::Class->register(
+ parcel => "Lucy",
+ class_name => "Lucy::Object::Hash",
+ xs_code => $xs_code,
+ bind_methods => [
+ qw(
+ Fetch
+ Delete
+ Keys
+ Values
+ Find_Key
+ Clear
+ Iter_Init
+ Get_Size
+ )
+ ],
+ bind_constructors => ["new"],
+);
+
+__COPYRIGHT__
+
+ /**
+ * Copyright 2009 The Apache Software Foundation
+ *
+ * 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.
+ */
+
Propchange: lucene/lucy/trunk/perl/lib/Lucy/Object/Hash.pm
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/perl/t/core/017-hash.t
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/t/core/017-hash.t?rev=814950&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/t/core/017-hash.t (added)
+++ lucene/lucy/trunk/perl/t/core/017-hash.t Tue Sep 15 01:05:38 2009
@@ -0,0 +1,6 @@
+use strict;
+use warnings;
+
+use Lucy::Test;
+Lucy::Test::run_tests("TestHash");
+
Propchange: lucene/lucy/trunk/perl/t/core/017-hash.t
------------------------------------------------------------------------------
svn:eol-style = native