hash.h

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.
 *
 */


#pragma once

#ifndef __MOTR_LIB_HASH_H__
#define __MOTR_LIB_HASH_H__

#include "lib/types.h"
#include "lib/tlist.h"
#include "lib/mutex.h"

struct m0_htable;
struct m0_hbucket;
struct m0_ht_descr;

struct m0_hbucket {
        struct m0_mutex hb_mutex;
        struct m0_tl    hb_objects;
};

struct m0_htable {
        uint64_t                  h_magic;

        uint64_t                  h_bucket_nr;

        struct m0_hbucket        *h_buckets;

        const struct m0_ht_descr *h_descr;
};

struct m0_ht_descr {
        const struct m0_tl_descr *hd_tldescr;

        size_t                    hd_key_offset;

        uint64_t (*hd_hash_func) (const struct m0_htable *htable,
                                  const void             *key);

        bool (*hd_key_eq)        (const void *key1, const void *key2);
};

struct m0_hlink {
        struct m0_tlink hl_link;
};

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

/* Checks if hash-table is initialised. */
M0_INTERNAL bool m0_htable_is_init(const struct m0_htable *htable);

M0_INTERNAL void m0_htable_fini(struct m0_htable *htable);

M0_INTERNAL void m0_htable_add(struct m0_htable *htable,
                               void             *amb);
M0_INTERNAL void m0_htable_cc_add(struct m0_htable *htable,
                                  void             *amb);
M0_INTERNAL void m0_htable_del(struct m0_htable *htable,
                               void             *amb);

M0_INTERNAL void m0_htable_cc_del(struct m0_htable *htable,
                                  void             *amb);

M0_INTERNAL void *m0_htable_lookup(const struct m0_htable *htable,
                                   const void             *key);

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

M0_INTERNAL bool m0_htable_is_empty(const struct m0_htable *htable);

M0_INTERNAL uint64_t m0_htable_size(const struct m0_htable *htable);

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

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

#define M0_HT_DESCR(name, amb_type, key_field, hash_func, key_eq)       \
{                                                                       \
        .hd_tldescr    = &name ## _tl,                                  \
        .hd_key_eq     = key_eq,                                        \
        .hd_hash_func  = hash_func,                                     \
        .hd_key_offset = offsetof(amb_type, key_field),                 \
};

#define M0_HT_DESCR_DEFINE(name, htname, scope, amb_type, amb_link_field,\
                           amb_magic_field, amb_magic, head_magic,      \
                           key_field, hash_func, key_eq)                \
                                                                        \
M0_BASSERT(sizeof(hash_func(NULL, &M0_FIELD_VALUE(amb_type, key_field))) > 0);\
M0_BASSERT(sizeof(key_eq(&M0_FIELD_VALUE(amb_type, key_field),          \
                         &M0_FIELD_VALUE(amb_type, key_field))) > 0);   \
                                                                        \
M0_TL_DESCR_DEFINE(name, htname, scope, amb_type, amb_link_field.hl_link,       \
                   amb_magic_field, amb_magic, head_magic);             \
                                                                        \
scope const struct m0_ht_descr name ## _ht = M0_HT_DESCR(name,          \
                                                         amb_type,      \
                                                         key_field,     \
        (uint64_t (*)(const struct m0_htable *, const void *))hash_func,\
        (bool (*)(const void *, const void *))key_eq)

#define M0_HT_DESCR_DECLARE(name, scope)                                \
scope const struct m0_ht_descr name ## _ht

#define M0_HT_DECLARE(name, scope, amb_type, key_type)                       \
                                                                             \
M0_TL_DECLARE(name, scope, amb_type);                                        \
                                                                             \
scope int name ## _htable_init(struct m0_htable *htable,                     \
                               uint64_t          bucket_nr);                 \
scope void name ## _htable_add(struct m0_htable *htable, amb_type *amb);     \
scope void name ## _htable_del(struct m0_htable *htable, amb_type *amb);     \
scope amb_type *name ## _htable_lookup(const struct m0_htable *htable,       \
                                       const key_type         *key);         \
scope void name ## _htable_cc_add(struct m0_htable *htable, amb_type *amb);  \
scope void name ## _htable_cc_del(struct m0_htable *htable, amb_type *amb);  \
scope amb_type *name ## _htable_cc_lookup(struct m0_htable *htable,          \
                                          const key_type   *key);            \
scope void name ## _hbucket_lock(struct m0_htable *htable,                   \
                                 const key_type   *key);                     \
scope void name ## _hbucket_unlock(struct m0_htable *htable,                 \
                                   const key_type *key);                     \
scope void name ## _htable_fini(struct m0_htable *htable);                   \
scope bool name ## _htable_is_empty(const struct m0_htable *htable);         \
scope uint64_t name ## _htable_size(const struct m0_htable *htable);

#define M0_HT_DEFINE(name, scope, amb_type, key_type)                        \
                                                                             \
M0_TL_DEFINE(name, scope, amb_type);                                         \
                                                                             \
scope __AUN int name ## _htable_init(struct m0_htable *htable,               \
                                     uint64_t          bucket_nr)            \
{                                                                            \
        return m0_htable_init(&name ## _ht, htable, bucket_nr);              \
}                                                                            \
                                                                             \
scope __AUN void name ## _htable_add(struct m0_htable *htable,               \
                                     amb_type         *amb)                  \
{                                                                            \
        m0_htable_add(htable, amb);                                          \
}                                                                            \
                                                                             \
scope __AUN void name ## _htable_del(struct m0_htable *htable,               \
                                     amb_type         *amb)                  \
{                                                                            \
        m0_htable_del(htable, amb);                                          \
}                                                                            \
                                                                             \
scope __AUN amb_type *name ## _htable_lookup(const struct m0_htable *htable, \
                                             const key_type         *key)    \
{                                                                            \
        return m0_htable_lookup(htable, key);                                \
}                                                                            \
                                                                             \
scope __AUN void name ## _hbucket_lock(struct m0_htable *htable,             \
                                       const  key_type  *key)                \
{                                                                            \
        m0_hbucket_lock(htable, key);                                        \
}                                                                            \
                                                                             \
scope __AUN void name ## _hbucket_unlock(struct m0_htable *htable,           \
                                         const  key_type  *key)              \
{                                                                            \
        m0_hbucket_unlock(htable, key);                                      \
}                                                                            \
                                                                             \
scope __AUN void name ## _htable_cc_add(struct m0_htable *htable,            \
                                        amb_type         *amb)               \
{                                                                            \
        m0_htable_cc_add(htable, amb);                                       \
}                                                                            \
                                                                             \
scope __AUN void name ## _htable_cc_del(struct m0_htable *htable,            \
                                        amb_type          *amb)              \
{                                                                            \
        m0_htable_cc_del(htable, amb);                                       \
}                                                                            \
                                                                             \
scope __AUN amb_type * name ## _htable_cc_lookup(struct m0_htable *htable,   \
                                                 const key_type   *key)      \
{                                                                            \
        return m0_htable_cc_lookup(htable, key);                             \
}                                                                            \
                                                                             \
scope __AUN void name ## _htable_fini(struct m0_htable *htable)              \
{                                                                            \
        m0_htable_fini(htable);                                              \
}                                                                            \
                                                                             \
scope __AUN bool name ## _htable_is_empty(const struct m0_htable *htable)    \
{                                                                            \
        return m0_htable_is_empty(htable);                                   \
}                                                                            \
                                                                             \
scope __AUN uint64_t name ## _htable_size(const struct m0_htable *htable)    \
{                                                                            \
        return m0_htable_size(htable);                                       \
}                                                                            \


#define m0_hbucket_forall(name, var, bucket, ...)                           \
({                                                                          \
        typeof (bucket) __bucket = (bucket);                                \
                                                                            \
        m0_tl_forall(name, var, &__bucket->hb_objects, ({ __VA_ARGS__ ; }));\
})

#define m0_htable_forall(name, var, htable, ...)                            \
({                                                                          \
        uint64_t cnt;                                                       \
        typeof (htable) ht = (htable);                                      \
                                                                            \
        for (cnt = 0; cnt < ht->h_bucket_nr; ++cnt)     {                   \
                if (!(m0_hbucket_forall(name, var, &ht->h_buckets[cnt],     \
                                         ({ __VA_ARGS__ ; }))))             \
                        break;                                              \
        }                                                                   \
        cnt == ht->h_bucket_nr;                                             \
})

#define m0_htable_for(name, var, htable)                                    \
({                                                                          \
        uint64_t __cnt;                                                     \
        typeof (htable) ht = (htable);                                      \
                                                                            \
        for (__cnt = 0; __cnt < ht->h_bucket_nr; ++__cnt) {                 \
                m0_tl_for(name, &ht->h_buckets[__cnt].hb_objects, var)

#define m0_htable_endfor m0_tl_endfor; }; })

#define m0_hbucket_for(descr, var, bucket)                                  \
({                                                                          \
        m0_tlist_for (descr, &bucket->hb_objects, var)

#define m0_hbucket_endfor m0_tlist_endfor; })

#define m0_hbucket_forall_ol(descr, var, bucket, ...)                       \
({                                                                          \
        typeof(descr) d = descr;                                            \
        m0_hbucket_for (d, var, bucket) {                                   \
                if (!({ __VA_ARGS__; }))                                    \
                        break;                                              \
        } m0_hbucket_endfor;                                                \
        var == NULL;                                                        \
})

M0_INTERNAL uint64_t m0_hash(uint64_t x);

#endif /* __MOTR_LIB_HASH_H__ */

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