hash.c

Go to the documentation of this file.

/* -*- C -*- */
/*
 * Copyright (c) 2013-2020 Seagate Technology LLC and/or its Affiliates
 *
 * 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.
 *
 * For any questions about this software or licensing,
 * please email opensource@seagate.com or cortx-questions@seagate.com.
 *
 */


#include "lib/bob.h"    /* m0_bob_type */
#include "lib/hash.h"   /* m0_htable */
#include "lib/errno.h"  /* Include appropriate errno.h header. */
#include "lib/arith.h"  /* min64u() */
#include "lib/memory.h" /* M0_ALLOC_ARR() */
#include "lib/misc.h"   /* m0_forall() */

#define M0_TRACE_SUBSYSTEM M0_TRACE_SUBSYS_LIB
#include "lib/trace.h"

static const struct m0_bob_type htable_bobtype;
M0_BOB_DEFINE(static, &htable_bobtype, m0_htable);

static const struct m0_bob_type htable_bobtype = {
        .bt_name         = "hashtable",
        .bt_magix_offset = offsetof(struct m0_htable, h_magic),
        .bt_magix        = M0_LIB_HASHLIST_MAGIC,
        .bt_check        = NULL,
};

static bool htable_invariant(const struct m0_htable *htable);

static void hbucket_init(const struct m0_ht_descr *d,
                         struct m0_hbucket        *bucket)
{
        M0_PRE(bucket != NULL);
        M0_PRE(d != NULL);

        m0_tlist_init(d->hd_tldescr, &bucket->hb_objects);
        m0_mutex_init(&bucket->hb_mutex);
}

static void hbucket_fini(const struct m0_ht_descr *d,
                         struct m0_hbucket        *bucket)
{
        M0_PRE(bucket != NULL);
        M0_PRE(d != NULL);

        m0_tlist_fini(d->hd_tldescr, &bucket->hb_objects);
        m0_mutex_fini(&bucket->hb_mutex);
}

static void *obj_key(const struct m0_ht_descr *hd, void *obj)
{
        return obj + hd->hd_key_offset;
}

static bool hbucket_invariant(const struct m0_ht_descr *desc,
                              const struct m0_hbucket  *bucket,
                              const struct m0_htable   *htable)
{
        uint64_t  index;
        void     *amb;

        index = bucket - htable->h_buckets;

        return
                bucket != NULL &&
                desc != NULL &&
                m0_hbucket_forall_ol(desc->hd_tldescr, amb, bucket,
                                     index == desc->hd_hash_func(htable,
                                     obj_key(desc, amb)));
}

static bool htable_invariant(const struct m0_htable *htable)
{
        return
                m0_htable_bob_check(htable) &&
                htable->h_bucket_nr >  0 &&
                htable->h_buckets   != NULL &&
                m0_forall(i, htable->h_bucket_nr,
                          hbucket_invariant(htable->h_descr,
                                            &htable->h_buckets[i], htable));
}

M0_INTERNAL int m0_htable_init(const struct m0_ht_descr *d,
                               struct m0_htable         *htable,
                               uint64_t                  bucket_nr)
{
        uint64_t nr;

        M0_PRE(htable != NULL);
        M0_PRE(d != NULL);
        M0_PRE(bucket_nr > 0);

        m0_htable_bob_init(htable);

        htable->h_descr     = d;
        htable->h_bucket_nr = bucket_nr;
        M0_ALLOC_ARR(htable->h_buckets, htable->h_bucket_nr);
        if (htable->h_buckets == NULL)
                return M0_ERR(-ENOMEM);

        for (nr = 0; nr < htable->h_bucket_nr; ++nr)
                hbucket_init(d, &htable->h_buckets[nr]);
        M0_POST_EX(htable_invariant(htable));
        return 0;
}

M0_INTERNAL bool m0_htable_is_init(const struct m0_htable *htable)
{
        return htable_invariant(htable);
}

M0_INTERNAL void m0_htable_add(struct m0_htable *htable,
                               void             *amb)
{
        uint64_t bucket_id;

        M0_PRE_EX(htable_invariant(htable));
        M0_PRE(amb != NULL);
        M0_PRE(!m0_tlink_is_in(htable->h_descr->hd_tldescr, amb));

        bucket_id = htable->h_descr->hd_hash_func(htable,
                        obj_key(htable->h_descr, amb));

        m0_tlist_add(htable->h_descr->hd_tldescr,
                     &htable->h_buckets[bucket_id].hb_objects, amb);
        M0_POST_EX(htable_invariant(htable));
        M0_POST(m0_tlink_is_in(htable->h_descr->hd_tldescr, amb));
}

M0_INTERNAL void m0_htable_del(struct m0_htable *htable,
                               void             *amb)
{
        M0_PRE_EX(htable_invariant(htable));
        M0_PRE(amb != NULL);

        m0_tlist_del(htable->h_descr->hd_tldescr, amb);

        M0_POST_EX(htable_invariant(htable));
        M0_POST(!m0_tlink_is_in(htable->h_descr->hd_tldescr, amb));
}

M0_INTERNAL void *m0_htable_lookup(const struct m0_htable *htable,
                                   const void             *key)
{
        void     *scan;
        uint64_t  bucket_id;

        M0_PRE_EX(htable_invariant(htable));

        bucket_id = htable->h_descr->hd_hash_func(htable, key);

        m0_tlist_for(htable->h_descr->hd_tldescr,
                     &htable->h_buckets[bucket_id].hb_objects, scan) {
                if (htable->h_descr->hd_key_eq(obj_key(htable->h_descr, scan),
                                               key))
                        break;
        } m0_tlist_endfor;

        return scan;
}

M0_INTERNAL void m0_htable_cc_add(struct m0_htable *htable,
                                  void             *amb)
{
        M0_PRE(amb != NULL);

        m0_hbucket_lock(htable, obj_key(htable->h_descr, amb));
        m0_htable_add(htable, amb);
        m0_hbucket_unlock(htable, obj_key(htable->h_descr, amb));
}

M0_INTERNAL void m0_htable_cc_del(struct m0_htable *htable,
                                  void             *amb)
{
        M0_PRE(amb != NULL);

        m0_hbucket_lock(htable, obj_key(htable->h_descr, amb));
        m0_htable_del(htable, amb);
        m0_hbucket_unlock(htable, obj_key(htable->h_descr, amb));
}

M0_INTERNAL void *m0_htable_cc_lookup(struct m0_htable *htable,
                                      const void  *key)
{
        void *obj;

        M0_PRE(key != NULL);

        m0_hbucket_lock(htable, key);
        obj = m0_htable_lookup(htable, key);
        m0_hbucket_unlock(htable, key);
        return obj;
}

M0_INTERNAL void m0_hbucket_lock(struct m0_htable *htable,
                                 const void       *key)
{
        uint64_t bucket_id;

        M0_PRE_EX(htable_invariant(htable));

        bucket_id = htable->h_descr->hd_hash_func(htable, key);
        m0_mutex_lock(&htable->h_buckets[bucket_id].hb_mutex);
}

M0_INTERNAL void m0_hbucket_unlock(struct m0_htable *htable,
                                   const void       *key)
{
        uint64_t bucket_id;

        M0_PRE_EX(htable_invariant(htable));

        bucket_id = htable->h_descr->hd_hash_func(htable, key);
        m0_mutex_unlock(&htable->h_buckets[bucket_id].hb_mutex);
}

M0_INTERNAL void m0_htable_fini(struct m0_htable *htable)
{
        uint64_t nr;

        M0_PRE_EX(htable_invariant(htable));

        for (nr = 0; nr < htable->h_bucket_nr; ++nr)
                hbucket_fini(htable->h_descr, &htable->h_buckets[nr]);
        m0_free(htable->h_buckets);
        m0_htable_bob_fini(htable);
        htable->h_buckets   = NULL;
        htable->h_bucket_nr = 0;
        htable->h_descr     = NULL;
}

M0_INTERNAL bool m0_htable_is_empty(const struct m0_htable *htable)
{
        uint64_t nr;

        M0_PRE_EX(htable_invariant(htable));

        for (nr = 0; nr < htable->h_bucket_nr; ++nr) {
                if (!m0_tlist_is_empty(htable->h_descr->hd_tldescr,
                                &htable->h_buckets[nr].hb_objects))
                        break;
        }
        return nr == htable->h_bucket_nr;
}

M0_INTERNAL uint64_t m0_htable_size(const struct m0_htable *htable)
{
        uint64_t nr;
        uint64_t len = 0;

        M0_PRE_EX(htable_invariant(htable));

        for (nr = 0; nr < htable->h_bucket_nr; ++nr)
                len += m0_tlist_length(htable->h_descr->hd_tldescr,
                                &htable->h_buckets[nr].hb_objects);
        return len;
}

M0_INTERNAL uint64_t m0_hash(uint64_t x)
{
        uint64_t y;

        y = x;
        y <<= 18;
        x -= y;
        y <<= 33;
        x -= y;
        y <<= 3;
        x += y;
        y <<= 3;
        x -= y;
        y <<= 4;
        x += y;
        y <<= 2;

        return x + y;
}

#undef M0_TRACE_SUBSYSTEM

/*
 *  Local variables:
 *  c-indentation-style: "K&R"
 *  c-basic-offset: 8
 *  tab-width: 8
 *  fill-column: 80
 *  scroll-step: 1
 *  End:
 */