Update from trunk r1375509 through r1450773asyncstore

git-svn-id: https://svn.apache.org/repos/asf/qpid/branches/asyncstore@1451244 13f79535-47bb-0310-9956-ffa450edef68

1 files changed, 223 insertions, 0 deletions

diff --git a/extras/dispatch/src/hash.c b/extras/dispatch/src/hash.c
new file mode 100644
index 0000000000..c54d5d6fcf
--- /dev/null
+++ b/extras/dispatch/src/hash.c
@@ -0,0 +1,223 @@
+/*
+ * 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 <qpid/dispatch/hash.h>
+#include <qpid/dispatch/ctools.h>
+#include <qpid/dispatch/alloc.h>
+#include <stdio.h>
+#include <string.h>
+
+typedef struct hash_item_t {
+    DEQ_LINKS(struct hash_item_t);
+    unsigned char *key;
+    union {
+        void       *val;
+        const void *val_const;
+    } v;
+} hash_item_t;
+
+ALLOC_DECLARE(hash_item_t);
+ALLOC_DEFINE(hash_item_t);
+DEQ_DECLARE(hash_item_t, items_t);
+
+
+typedef struct bucket_t {
+    items_t items;    
+} bucket_t;
+
+
+struct hash_t {
+    bucket_t     *buckets;
+    unsigned int  bucket_count;
+    unsigned int  bucket_mask;
+    int           batch_size;
+    size_t        size;
+    int           is_const;
+};
+
+
+// djb2 hash algorithm
+static unsigned long hash_function(dx_field_iterator_t *iter)
+{
+    unsigned long hash = 5381;
+    int c;
+
+    while (!dx_field_iterator_end(iter)) {
+        c = (int) dx_field_iterator_octet(iter);
+        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+    }
+
+    return hash;
+}
+
+
+hash_t *hash(int bucket_exponent, int batch_size, int value_is_const)
+{
+    int i;
+    hash_t *h = NEW(hash_t);
+
+    if (!h)
+        return 0;
+
+    h->bucket_count = 1 << bucket_exponent;
+    h->bucket_mask  = h->bucket_count - 1;
+    h->batch_size   = batch_size;
+    h->size         = 0;
+    h->is_const     = value_is_const;
+    h->buckets = NEW_ARRAY(bucket_t, h->bucket_count);
+    for (i = 0; i < h->bucket_count; i++) {
+        DEQ_INIT(h->buckets[i].items);
+    }
+
+    return h;
+}
+
+
+void hash_free(hash_t *h)
+{
+    // TODO - Implement this
+}
+
+
+size_t hash_size(hash_t *h)
+{
+    return h ? h->size : 0;
+}
+
+
+static hash_item_t *hash_internal_insert(hash_t *h, dx_field_iterator_t *key, int *error)
+{
+    unsigned long  idx  = hash_function(key) & h->bucket_mask;
+    hash_item_t   *item = DEQ_HEAD(h->buckets[idx].items);
+
+    *error = 0;
+
+    while (item) {
+        if (dx_field_iterator_equal(key, item->key))
+            break;
+        item = item->next;
+    }
+
+    if (item) {
+        *error = -1;
+        return 0;
+    }
+
+    item = new_hash_item_t();
+    if (!item) {
+        *error = -2;
+        return 0;
+    }
+
+    DEQ_ITEM_INIT(item);
+    item->key = dx_field_iterator_copy(key);
+
+    DEQ_INSERT_TAIL(h->buckets[idx].items, item);
+    h->size++;
+    return item;
+}
+
+
+int hash_insert(hash_t *h, dx_field_iterator_t *key, void *val)
+{
+    int          error = 0;
+    hash_item_t *item  = hash_internal_insert(h, key, &error);
+
+    if (item)
+        item->v.val = val;
+    return error;
+}
+
+
+int hash_insert_const(hash_t *h, dx_field_iterator_t *key, const void *val)
+{
+    if (!h->is_const)
+        return -3;
+
+    int          error = 0;
+    hash_item_t *item  = hash_internal_insert(h, key, &error);
+
+    if (item)
+        item->v.val_const = val;
+    return error;
+}
+
+
+static hash_item_t *hash_internal_retrieve(hash_t *h, dx_field_iterator_t *key)
+{
+    unsigned long  idx  = hash_function(key) & h->bucket_mask;
+    hash_item_t   *item = DEQ_HEAD(h->buckets[idx].items);
+
+    while (item) {
+        if (dx_field_iterator_equal(key, item->key))
+            break;
+        item = item->next;
+    }
+
+    return item;
+}
+
+
+int hash_retrieve(hash_t *h, dx_field_iterator_t *key, void **val)
+{
+    hash_item_t *item = hash_internal_retrieve(h, key);
+    if (item) {
+        *val = item->v.val;
+        return 0;
+    }
+    return -1;
+}
+
+
+int hash_retrieve_const(hash_t *h, dx_field_iterator_t *key, const void **val)
+{
+    if (!h->is_const)
+        return -3;
+
+    hash_item_t *item = hash_internal_retrieve(h, key);
+    if (item) {
+        *val = item->v.val_const;
+        return 0;
+    }
+    return -1;
+}
+
+
+int hash_remove(hash_t *h, dx_field_iterator_t *key)
+{
+    unsigned long  idx  = hash_function(key) & h->bucket_mask;
+    hash_item_t   *item = DEQ_HEAD(h->buckets[idx].items);
+
+    while (item) {
+        if (dx_field_iterator_equal(key, item->key))
+            break;
+        item = item->next;
+    }
+
+    if (item) {
+        free(item->key);
+        DEQ_REMOVE(h->buckets[idx].items, item);
+        free_hash_item_t(item);
+        h->size--;
+        return 0;
+    }
+
+    return -1;
+}
+