10555265542

Committed 26 Aug 2024 07:09AM UTC coverage: 85.892% (+0.001%) from 85.891%

Build # 10555265542

Build Type

push

github

Committed by

sergepetrenko

Commit Message

memtx: skip excluded tuples in index count with MVCC enabled

Excluded tuples actually have their own history chains in MVCC - such
chains consist of only one `memtx_story` containing excluded tuple
itself. Such chains should be skipped when counting invisible tuples
because they are not inserted to the index - that's what the commit
does.

Closes #10396

NO_DOC=bugfix

(cherry picked from commit 8947cb04f)

Run Details

62980 of 114235 branches covered (55.13%)

3 of 3 new or added lines in 1 file covered. (100.0%)

22 existing lines in 10 files now uncovered.

93871 of 109289 relevant lines covered (85.89%)

2571498.56 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.34

/src/lib/salad/mhash.h

/*
 * *No header guard*: the header is allowed to be included twice
 * with different sets of defines.
 */
/*
 * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * 1. Redistributions of source code must retain the above
 *    copyright notice, this list of conditions and the
 *    following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
/* The MIT License

   Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk>

   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:

   The above copyright notice and this permission notice shall be
   included in all copies or substantial portions of the Software.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
   SOFTWARE.
*/

#ifndef MH_INCREMENTAL_RESIZE
#define MH_INCREMENTAL_RESIZE 1
#endif

#include <assert.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <string.h>

#include <trivia/util.h>

#define mh_cat(a, b) mh##a##_##b
#define mh_ecat(a, b) mh_cat(a, b)
#define _mh(x) mh_ecat(mh_name, x)

#define mh_unlikely(x)  __builtin_expect((x),0)

#ifndef MH_TYPEDEFS
#define MH_TYPEDEFS 1
typedef uint32_t mh_int_t;
#endif /* MH_TYPEDEFS */

#ifndef MH_HEADER
#define MH_HEADER

#ifndef mh_bytemap
#define mh_bytemap 0
#endif

struct _mh(t) {
        mh_node_t *p;
#if !mh_bytemap
        uint32_t *b;
#else
        uint8_t *b;
#endif
        mh_int_t n_buckets;
        mh_int_t n_dirty;
        mh_int_t size;
        mh_int_t upper_bound;
        mh_int_t prime;

        mh_int_t resize_cnt;
        mh_int_t resize_position;
        mh_int_t batch;
        struct _mh(t) *shadow;
};

#if !mh_bytemap
#define mh_exist(h, i)                ({ h->b[i >> 4] & (1 << (i % 16)); })
#define mh_dirty(h, i)                ({ h->b[i >> 4] & (1u << (i % 16 + 16)); })
#define mh_gethk(hash)                (1)
#define mh_mayeq(h, i, hk)        mh_exist(h, i)

#define mh_setfree(h, i)        ({ h->b[i >> 4] &= ~(1 << (i % 16)); })
#define mh_setexist(h, i, hk)        ({ h->b[i >> 4] |= (1 << (i % 16)); })
#define mh_setdirty(h, i)        ({ h->b[i >> 4] |= (1u << (i % 16 + 16)); })
#else
#define mh_exist(h, i)                ({ h->b[i] & 0x7f; })
#define mh_dirty(h, i)                ({ h->b[i] & 0x80; })
#define mh_gethk(hash)                ({ (hash) % 127 + 1; })
#define mh_mayeq(h, i, hk)        ({ mh_exist(h, i) == hk; })

#define mh_setfree(h, i)        ({ h->b[i] &= 0x80; })
#define mh_setexist(h, i, hk)        ({ h->b[i] |= hk; })
#define mh_setdirty(h, i)        ({ h->b[i] |= 0x80; })
#endif

#define mh_node(h, i)                ((const mh_node_t *) &((h)->p[(i)]))
#define mh_size(h)                ({ (h)->size;                })
#define mh_capacity(h)                ({ (h)->n_buckets;        })
#define mh_begin(h)                ({ 0;                        })
#define mh_end(h)                ({ (h)->n_buckets;        })

#define mh_first(h) ({                                                \
        mh_int_t i;                                                \
        for (i = 0; i < mh_end(h); i++) {                        \
                if (mh_exist(h, i))                                \
                        break;                                        \
        }                                                        \
        i;                                                        \
})

#define mh_next(h, i) ({                                        \
        mh_int_t n = i;                                                \
        if (n < mh_end(h)) {                                        \
                for (n = i + 1; n < mh_end(h); n++) {                \
                        if (mh_exist(h, n))                        \
                                break;                                \
                }                                                \
        }                                                        \
        n;                                                        \
})

#define mh_foreach(h, i) \
        for (i = mh_first(h); i < mh_end(h); i = mh_next(h, i))

#define MH_DENSITY 0.7

struct _mh(t) * _mh(new)();
void _mh(clear)(struct _mh(t) *h);
void _mh(delete)(struct _mh(t) *h);
void _mh(resize)(struct _mh(t) *h, mh_arg_t arg);
void _mh(start_resize)(struct _mh(t) *h, mh_int_t buckets, mh_int_t batch,
                       mh_arg_t arg);
void _mh(reserve)(struct _mh(t) *h, mh_int_t size, mh_arg_t arg);
void NOINLINE _mh(del_resize)(struct _mh(t) *h, mh_int_t x,
                                               mh_arg_t arg);
size_t _mh(memsize)(struct _mh(t) *h);
void _mh(dump)(struct _mh(t) *h);

#define put_slot(h, node, exist, arg) \
        _mh(put_slot)(h, node, exist, arg)

static inline mh_node_t *
_mh(node)(struct _mh(t) *h, mh_int_t x)
{
        return (mh_node_t *) &(h->p[x]);
}


static inline mh_int_t
_mh(next_slot)(mh_int_t slot, mh_int_t inc, mh_int_t size)
{
        slot += inc;
        return slot >= size ? slot - size : slot;
}

#if defined(mh_hash_key) && defined(mh_cmp_key)
/**
 * If it is necessary to search by something different
 * than a hash node, define mh_hash_key and mh_eq_key
 * and use mh_find().
 */
static inline mh_int_t
_mh(find)(struct _mh(t) *h, mh_key_t key, mh_arg_t arg)
{
        (void) arg;

        mh_int_t k = mh_hash_key(key, arg);
        uint8_t hk = mh_gethk(k); (void)hk;
        mh_int_t i = k % h->n_buckets;
        mh_int_t inc = 1 + k % (h->n_buckets - 1);
        for (;;) {
                if ((mh_mayeq(h, i, hk) &&
                    !mh_cmp_key(key, mh_node(h, i), arg)))
                        return i;

                if (!mh_dirty(h, i))
                        return h->n_buckets;

                i = _mh(next_slot)(i, inc, h->n_buckets);
        }
}
#endif

static inline mh_int_t
_mh(get)(struct _mh(t) *h, const mh_node_t *node,
         mh_arg_t arg)
{
        (void) arg;

        mh_int_t k = mh_hash(node, arg);
        uint8_t hk = mh_gethk(k); (void)hk;
        mh_int_t i = k % h->n_buckets;
        mh_int_t inc = 1 + k % (h->n_buckets - 1);
        for (;;) {
                if ((mh_mayeq(h, i, hk) && !mh_cmp(node, mh_node(h, i), arg)))
                        return i;

                if (!mh_dirty(h, i))
                        return h->n_buckets;

                i = _mh(next_slot)(i, inc, h->n_buckets);
        }
}

static inline mh_int_t
_mh(random)(struct _mh(t) *h, mh_int_t rnd)
{
        mh_int_t res = mh_next(h, rnd % mh_end(h));
        if (res != mh_end(h))
                return res;
        return mh_first(h);
}

static inline mh_int_t
_mh(put_slot)(struct _mh(t) *h, const mh_node_t *node, int *exist,
              mh_arg_t arg)
{
        (void) arg;

        mh_int_t k = mh_hash(node, arg); /* hash key */
        uint8_t hk = mh_gethk(k); (void)hk;
        mh_int_t i = k % h->n_buckets; /* offset in the hash table. */
        mh_int_t inc = 1 + k % (h->n_buckets - 1); /* overflow chain increment. */

        *exist = 1;
        /* Skip through all collisions. */
        while (mh_exist(h, i)) {
                if (mh_mayeq(h, i, hk) && !mh_cmp(node, mh_node(h, i), arg))
                        return i;               /* Found a duplicate. */
                /*
                 * Mark this link as part of a collision chain. The
                 * chain always ends with a non-marked link.
                 * Note: the collision chain for this key may share
                 * links with collision chains of other keys.
                 */
                mh_setdirty(h, i);
                i = _mh(next_slot)(i, inc, h->n_buckets);
        }
        /*
         * Found an unused, but possibly dirty slot. Use it.
         * However, if this is a dirty slot, first check that
         * there are no duplicates down the collision chain. The
         * current link can also be from a collision chain of some
         * other key, but this is can't be established, so check
         * anyway.
         */
        mh_int_t save_i = i;
        while (mh_dirty(h, i)) {
                i = _mh(next_slot)(i, inc, h->n_buckets);

                if (mh_mayeq(h, i, hk) && !mh_cmp(mh_node(h, i), node, arg))
                        return i;               /* Found a duplicate. */
        }
        /* Reached the end of the collision chain: no duplicates. */
        *exist = 0;
        h->size++;
        if (!mh_dirty(h, save_i))
                h->n_dirty++;
        mh_setexist(h, save_i, hk);
        return save_i;
}

/**
 * Find a node in the hash and replace it with a new value.
 * Save the old node in ret pointer, if it is provided.
 * If the old node didn't exist, just insert the new node.
 *
 * @retval != mh_end()   pos of the new node, ret is either NULL
 *                       or copy of the old node
 */
static inline mh_int_t
_mh(put)(struct _mh(t) *h, const mh_node_t *node, mh_node_t **ret,
         mh_arg_t arg)
{
        mh_int_t x = mh_end(h);
        int exist;

        assert(h->size < h->n_buckets);

#if MH_INCREMENTAL_RESIZE
        if (mh_unlikely(h->resize_position > 0))
                _mh(resize)(h, arg);
        else if (mh_unlikely(h->n_dirty >= h->upper_bound)) {
                _mh(start_resize)(h, h->n_buckets + 1, 0, arg);
        }
        if (h->resize_position)
                _mh(put)(h->shadow, node, NULL, arg);
#else
        if (mh_unlikely(h->n_dirty >= h->upper_bound)) {
                _mh(start_resize)(h, h->n_buckets + 1, h->size, arg);
        }
#endif

        x = put_slot(h, node, &exist, arg);

        if (ret) {
                if (exist)
                        memcpy(*ret, &(h->p[x]), sizeof(mh_node_t));
                else
                        *ret = NULL;
        }
        memcpy(&(h->p[x]), node, sizeof(mh_node_t));
        return x;
}

static inline void
_mh(del)(struct _mh(t) *h, mh_int_t x,
         mh_arg_t arg)
{
        if (x != h->n_buckets && mh_exist(h, x)) {
                mh_setfree(h, x);
                h->size--;
                if (!mh_dirty(h, x))
                        h->n_dirty--;
#if MH_INCREMENTAL_RESIZE
                if (mh_unlikely(h->resize_position))
                        _mh(del_resize)(h, x, arg);
#endif
        }
}
#endif

static inline void
_mh(remove)(struct _mh(t) *h, const mh_node_t *node,
         mh_arg_t arg)
{
        mh_int_t k = _mh(get)(h, node, arg);
        if (k != mh_end(h))
                _mh(del)(h, k, arg);
}

#ifdef MH_SOURCE

#ifndef __ac_HASH_PRIME_SIZE
#define __ac_HASH_PRIME_SIZE 31
static const mh_int_t __ac_prime_list[__ac_HASH_PRIME_SIZE] = {
        3ul,                11ul,                23ul,                53ul,
        97ul,                193ul,                389ul,                769ul,
        1543ul,                3079ul,                6151ul,                12289ul,
        24593ul,        49157ul,        98317ul,        196613ul,
        393241ul,        786433ul,        1572869ul,        3145739ul,
        6291469ul,        12582917ul,        25165843ul,        50331653ul,
        100663319ul,        201326611ul,        402653189ul,        805306457ul,
        1610612741ul,        3221225473ul,        4294967291ul
};
#endif /* __ac_HASH_PRIME_SIZE */

NOINLINE void
_mh(del_resize)(struct _mh(t) *h, mh_int_t x,
                mh_arg_t arg)
{
        struct _mh(t) *s = h->shadow;
        mh_int_t y = _mh(get)(s, (const mh_node_t *) &(h->p[x]),
                              arg);
        _mh(del)(s, y, arg);
        _mh(resize)(h, arg);
}

struct _mh(t) *
_mh(new)()
{
        struct _mh(t) *h = (struct _mh(t) *)xcalloc(1, sizeof(*h));
        h->shadow = (struct _mh(t) *)xcalloc(1, sizeof(*h));
        h->prime = 0;
        h->n_buckets = __ac_prime_list[h->prime];
        h->p = (mh_node_t *)xcalloc(h->n_buckets, sizeof(mh_node_t));
#if !mh_bytemap
        h->b = (uint32_t *)xcalloc(h->n_buckets / 16 + 1, sizeof(uint32_t));
#else
        h->b = (uint8_t *)xcalloc(h->n_buckets, sizeof(uint8_t));
#endif
        h->upper_bound = h->n_buckets * MH_DENSITY;
        return h;
}

void
_mh(clear)(struct _mh(t) *h)
{
        mh_int_t n_buckets = __ac_prime_list[h->prime];
        mh_node_t *p = (mh_node_t *)xcalloc(n_buckets, sizeof(mh_node_t));
#if !mh_bytemap
        uint32_t *b = (uint32_t *)xcalloc(n_buckets / 16 + 1, sizeof(uint32_t));
#else
        uint8_t *b = (uint8_t *)xcalloc(n_buckets, sizeof(uint8_t));
#endif
        if (h->shadow->p) {
                free(h->shadow->p);
                free(h->shadow->b);
                memset(h->shadow, 0, sizeof(*h->shadow));
        }
        free(h->p);
        free(h->b);
        h->prime = 0;
        h->n_buckets = n_buckets;
        h->p = p;
        h->b = b;
        h->size = 0;
        h->upper_bound = h->n_buckets * MH_DENSITY;
}

void
_mh(delete)(struct _mh(t) *h)
{
        if (h->shadow->p) {
                free(h->shadow->p);
                free(h->shadow->b);
                memset(h->shadow, 0, sizeof(*h->shadow));
        }
        free(h->shadow);
        free(h->b);
        free(h->p);
        free(h);
}

/** Calculate hash size. */
size_t
_mh(memsize)(struct _mh(t) *h)
{
    size_t sz = 2 * sizeof(struct _mh(t));

    sz += h->n_buckets * sizeof(mh_node_t);
#if !mh_bytemap
    sz += (h->n_buckets / 16 + 1) * sizeof(uint32_t);
#else
    sz += h->n_buckets;
#endif
    if (h->resize_position) {
            h = h->shadow;
            sz += h->n_buckets * sizeof(mh_node_t);
#if !mh_bytemap
            sz += (h->n_buckets / 16 + 1) * sizeof(uint32_t);
#else
            sz += h->n_buckets;
#endif
    }
    return sz;
}

void
_mh(resize)(struct _mh(t) *h, mh_arg_t arg)
{
        struct _mh(t) *s = h->shadow;
        int exist;
#if MH_INCREMENTAL_RESIZE
        mh_int_t  batch = h->batch;
#endif
        for (mh_int_t i = h->resize_position; i < h->n_buckets; i++) {
#if MH_INCREMENTAL_RESIZE
                if (batch-- == 0) {
                        h->resize_position = i;
                        return;
                }
#endif
                if (!mh_exist(h, i))
                        continue;
                mh_int_t n = put_slot(s, mh_node(h, i), &exist, arg);
                s->p[n] = h->p[i];
        }
        free(h->p);
        free(h->b);
        if (s->size != h->size)
                abort();
        memcpy(h, s, sizeof(*h));
        h->resize_cnt++;
        memset(s, 0, sizeof(*s));
}

void
_mh(start_resize)(struct _mh(t) *h, mh_int_t buckets, mh_int_t batch,
                  mh_arg_t arg)
{
        if (h->resize_position) {
                /* resize has already been started */
                return;
        }
        if (buckets < h->n_buckets) {
                /* hash size is already greater than requested */
                return;
        }
        mh_int_t new_prime = h->prime;
        while (new_prime < __ac_HASH_PRIME_SIZE - 1) {
                if (__ac_prime_list[new_prime] >= buckets)
                        break;
                new_prime += 1;
        }
        mh_int_t new_batch = batch > 0 ? batch : h->n_buckets / (256 * 1024);
        if (new_batch < 256) {
                /*
                 * Minimal batch must be greater or equal to
                 * 1 / (1 - f), where f is upper bound percent
                 * = MH_DENSITY
                 */
                new_batch = 256;
        }

        mh_int_t n_buckets = __ac_prime_list[new_prime];
        mh_node_t *p = (mh_node_t *)xmalloc(n_buckets * sizeof(mh_node_t));
#if !mh_bytemap
        uint32_t *b = (uint32_t *)xcalloc(n_buckets / 16 + 1, sizeof(uint32_t));
#else
        uint8_t *b = (uint8_t *)xcalloc(n_buckets, sizeof(uint8_t));
#endif
        h->prime = new_prime;
        h->batch = new_batch;
        struct _mh(t) *s = h->shadow;
        memcpy(s, h, sizeof(*h));
        s->resize_position = 0;
        s->n_buckets = n_buckets;
        s->upper_bound = s->n_buckets * MH_DENSITY;
        s->n_dirty = 0;
        s->size = 0;
        s->p = p;
        s->b = b;
        _mh(resize)(h, arg);
}

void
_mh(reserve)(struct _mh(t) *h, mh_int_t size,
             mh_arg_t arg)
{
        _mh(start_resize)(h, size/MH_DENSITY, h->size, arg);
}

#ifndef mh_stat
#define mh_stat(buf, h) ({                                                \
                tbuf_printf(buf, "  n_buckets: %" PRIu32 CRLF                \
                            "  n_dirty: %" PRIu32 CRLF                        \
                            "  size: %" PRIu32 CRLF                        \
                            "  resize_cnt: %" PRIu32 CRLF                \
                            "  resize_position: %" PRIu32 CRLF,                \
                            h->n_buckets,                                \
                            h->n_dirty,                                        \
                            h->size,                                        \
                            h->resize_cnt,                                \
                            h->resize_position);                        \
                        })
#endif

#ifdef MH_DEBUG
void
_mh(dump)(struct _mh(t) *h)
{
        printf("slots:\n");
        int k = 0;
        for(int i = 0; i < h->n_buckets; i++) {
                if (mh_dirty(h, i) || mh_exist(h, i)) {
                        printf("   [%i] ", i);
                        if (mh_exist(h, i)) {
                                /* TODO(roman): fix this printf */
                                printf("   -> %p", h->p[i]);
                                k++;
                        }
                        if (mh_dirty(h, i))
                                printf(" dirty");
                        printf("\n");
                }
        }
        printf("end(%i)\n", k);
}
#endif

#endif

#if defined(MH_SOURCE) || defined(MH_UNDEF)
#undef MH_HEADER
#undef mh_int_t
#undef mh_node_t
#undef mh_arg_t
#undef mh_key_t
#undef mh_name
#undef mh_hash
#undef mh_hash_key
#undef mh_cmp
#undef mh_cmp_key
#undef mh_node
#undef mh_dirty
#undef mh_place
#undef mh_setdirty
#undef mh_setexist
#undef mh_setvalue
#undef mh_unlikely
#undef slot
#undef slot_and_dirty
#undef MH_DENSITY
#undef mh_bytemap
#endif

#undef mh_cat
#undef mh_ecat
#undef _mh

1	/*
2	* No header guard: the header is allowed to be included twice
3	* with different sets of defines.
4	*/
5	/*
6	* Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
7	*
8	* Redistribution and use in source and binary forms, with or
9	* without modification, are permitted provided that the following
10	* conditions are met:
11	*
12	* 1. Redistributions of source code must retain the above
13	* copyright notice, this list of conditions and the
14	* following disclaimer.
15	*
16	* 2. Redistributions in binary form must reproduce the above
17	* copyright notice, this list of conditions and the following
18	* disclaimer in the documentation and/or other materials
19	* provided with the distribution.
20	*
21	* THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
22	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
23	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
25	* <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
26	* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
29	* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30	* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
32	* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33	* SUCH DAMAGE.
34	*/
35	/* The MIT License
36
37	Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk>
38
39	Permission is hereby granted, free of charge, to any person obtaining
40	a copy of this software and associated documentation files (the
41	"Software"), to deal in the Software without restriction, including
42	without limitation the rights to use, copy, modify, merge, publish,
43	distribute, sublicense, and/or sell copies of the Software, and to
44	permit persons to whom the Software is furnished to do so, subject to
45	the following conditions:
46
47	The above copyright notice and this permission notice shall be
48	included in all copies or substantial portions of the Software.
49
50	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
51	EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
52	MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
53	NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
54	BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
55	ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
56	CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
57	SOFTWARE.
58	*/
59
60	#ifndef MH_INCREMENTAL_RESIZE
61	#define MH_INCREMENTAL_RESIZE 1
62	#endif
63
64	#include <assert.h>
65	#include <stdlib.h>
66	#include <stdint.h>
67	#include <math.h>
68	#include <string.h>
69
70	#include <trivia/util.h>
71
72	#define mh_cat(a, b) mh##a##_##b
73	#define mh_ecat(a, b) mh_cat(a, b)
74	#define _mh(x) mh_ecat(mh_name, x)
75
76	#define mh_unlikely(x) __builtin_expect((x),0)
77
78	#ifndef MH_TYPEDEFS
79	#define MH_TYPEDEFS 1
80	typedef uint32_t mh_int_t;
81	#endif /* MH_TYPEDEFS */
82
83	#ifndef MH_HEADER
84	#define MH_HEADER
85
86	#ifndef mh_bytemap
87	#define mh_bytemap 0
88	#endif
89
90	struct _mh(t) {
91	mh_node_t *p;
92	#if !mh_bytemap
93	uint32_t *b;
94	#else
95	uint8_t *b;
96	#endif
97	mh_int_t n_buckets;
98	mh_int_t n_dirty;
99	mh_int_t size;
100	mh_int_t upper_bound;
101	mh_int_t prime;
102
103	mh_int_t resize_cnt;
104	mh_int_t resize_position;
105	mh_int_t batch;
106	struct _mh(t) *shadow;
107	};
108
109	#if !mh_bytemap
110	#define mh_exist(h, i) ({ h->b[i >> 4] & (1 << (i % 16)); })
111	#define mh_dirty(h, i) ({ h->b[i >> 4] & (1u << (i % 16 + 16)); })
112	#define mh_gethk(hash) (1)
113	#define mh_mayeq(h, i, hk) mh_exist(h, i)
114
115	#define mh_setfree(h, i) ({ h->b[i >> 4] &= ~(1 << (i % 16)); })
116	#define mh_setexist(h, i, hk) ({ h->b[i >> 4] \|= (1 << (i % 16)); })
117	#define mh_setdirty(h, i) ({ h->b[i >> 4] \|= (1u << (i % 16 + 16)); })
118	#else
119	#define mh_exist(h, i) ({ h->b[i] & 0x7f; })
120	#define mh_dirty(h, i) ({ h->b[i] & 0x80; })
121	#define mh_gethk(hash) ({ (hash) % 127 + 1; })
122	#define mh_mayeq(h, i, hk) ({ mh_exist(h, i) == hk; })
123
124	#define mh_setfree(h, i) ({ h->b[i] &= 0x80; })
125	#define mh_setexist(h, i, hk) ({ h->b[i] \|= hk; })
126	#define mh_setdirty(h, i) ({ h->b[i] \|= 0x80; })
127	#endif
128
129	#define mh_node(h, i) ((const mh_node_t *) &((h)->p[(i)]))
130	#define mh_size(h) ({ (h)->size; })
131	#define mh_capacity(h) ({ (h)->n_buckets; })
132	#define mh_begin(h) ({ 0; })
133	#define mh_end(h) ({ (h)->n_buckets; })
134
135	#define mh_first(h) ({ \
136	mh_int_t i; \
137	for (i = 0; i < mh_end(h); i++) { \
138	if (mh_exist(h, i)) \
139	break; \
140	} \
141	i; \
142	})
143
144	#define mh_next(h, i) ({ \
145	mh_int_t n = i; \
146	if (n < mh_end(h)) { \
147	for (n = i + 1; n < mh_end(h); n++) { \
148	if (mh_exist(h, n)) \
149	break; \
150	} \
151	} \
152	n; \
153	})
154
155	#define mh_foreach(h, i) \
156	for (i = mh_first(h); i < mh_end(h); i = mh_next(h, i))
157
158	#define MH_DENSITY 0.7
159
160	struct _mh(t) * _mh(new)();
161	void _mh(clear)(struct _mh(t) *h);
162	void _mh(delete)(struct _mh(t) *h);
163	void _mh(resize)(struct _mh(t) *h, mh_arg_t arg);
164	void _mh(start_resize)(struct _mh(t) *h, mh_int_t buckets, mh_int_t batch,
165	mh_arg_t arg);
166	void _mh(reserve)(struct _mh(t) *h, mh_int_t size, mh_arg_t arg);
167	void NOINLINE _mh(del_resize)(struct _mh(t) *h, mh_int_t x,
168	mh_arg_t arg);
169	size_t _mh(memsize)(struct _mh(t) *h);
170	void _mh(dump)(struct _mh(t) *h);
171
172	#define put_slot(h, node, exist, arg) \
173	_mh(put_slot)(h, node, exist, arg)
174
175	static inline mh_node_t *
176	_mh(node)(struct _mh(t) *h, mh_int_t x)	63,367,628✔
177	{
178	return (mh_node_t *) &(h->p[x]);	63,367,628✔
179	}
180
181
182	static inline mh_int_t
183	_mh(next_slot)(mh_int_t slot, mh_int_t inc, mh_int_t size)	7,723,428✔
184	{
185	slot += inc;	7,723,428✔
186	return slot >= size ? slot - size : slot;	7,723,428✔
187	}
188
189	#if defined(mh_hash_key) && defined(mh_cmp_key)
190	/**
191	* If it is necessary to search by something different
192	* than a hash node, define mh_hash_key and mh_eq_key
193	* and use mh_find().
194	*/
195	static inline mh_int_t
196	_mh(find)(struct _mh(t) *h, mh_key_t key, mh_arg_t arg)	83,639,494✔
197	{
198	(void) arg;
199
200	mh_int_t k = mh_hash_key(key, arg);	83,639,494✔
201	uint8_t hk = mh_gethk(k); (void)hk;	83,639,494✔
202	mh_int_t i = k % h->n_buckets;	83,639,494✔
203	mh_int_t inc = 1 + k % (h->n_buckets - 1);	83,639,494✔
204	for (;;) {
205	if ((mh_mayeq(h, i, hk) &&	86,208,596✔
206	!mh_cmp_key(key, mh_node(h, i), arg)))	82,148,811✔
207	return i;	62,851,121✔
208
209	if (!mh_dirty(h, i))	23,357,474✔
210	return h->n_buckets;	20,788,370✔
211
212	i = _mh(next_slot)(i, inc, h->n_buckets);	2,569,099✔
213	}
214	}
215	#endif
216
217	static inline mh_int_t
218	_mh(get)(struct _mh(t) h, const mh_node_t node,	230,071✔
219	mh_arg_t arg)
220	{
221	(void) arg;
222
223	mh_int_t k = mh_hash(node, arg);	230,071✔
224	uint8_t hk = mh_gethk(k); (void)hk;	230,071✔
225	mh_int_t i = k % h->n_buckets;	230,071✔
226	mh_int_t inc = 1 + k % (h->n_buckets - 1);	230,071✔
227	for (;;) {
228	if ((mh_mayeq(h, i, hk) && !mh_cmp(node, mh_node(h, i), arg)))	263,970✔
229	return i;	230,071✔
230
231	if (!mh_dirty(h, i))	33,899!
232	return h->n_buckets;	×
233
234	i = _mh(next_slot)(i, inc, h->n_buckets);	33,899✔
235	}
236	}
237
238	static inline mh_int_t
239	_mh(random)(struct _mh(t) *h, mh_int_t rnd)	102,018✔
240	{
241	mh_int_t res = mh_next(h, rnd % mh_end(h));	192,276!
242	if (res != mh_end(h))	102,018✔
243	return res;	101,691✔
244	return mh_first(h);	327!
245	}
246
247	static inline mh_int_t
248	_mh(put_slot)(struct _mh(t) h, const mh_node_t node, int *exist,	15,364,238✔
249	mh_arg_t arg)
250	{
251	(void) arg;
252
253	mh_int_t k = mh_hash(node, arg); /* hash key */	15,364,238✔
254	uint8_t hk = mh_gethk(k); (void)hk;	15,364,238✔
255	mh_int_t i = k % h->n_buckets; /* offset in the hash table. */	15,364,238✔
256	mh_int_t inc = 1 + k % (h->n_buckets - 1); /* overflow chain increment. */	15,364,238✔
257
258	*exist = 1;	15,364,238✔
259	/* Skip through all collisions. */
260	while (mh_exist(h, i)) {	20,393,965✔
261	if (mh_mayeq(h, i, hk) && !mh_cmp(node, mh_node(h, i), arg))	5,608,218!
262	return i; /* Found a duplicate. */	578,499✔
263	/*
264	* Mark this link as part of a collision chain. The
265	* chain always ends with a non-marked link.
266	* Note: the collision chain for this key may share
267	* links with collision chains of other keys.
268	*/
269	mh_setdirty(h, i);	5,029,720✔
270	i = _mh(next_slot)(i, inc, h->n_buckets);	5,029,720✔
271	}
272	/*
273	* Found an unused, but possibly dirty slot. Use it.
274	* However, if this is a dirty slot, first check that
275	* there are no duplicates down the collision chain. The
276	* current link can also be from a collision chain of some
277	* other key, but this is can't be established, so check
278	* anyway.
279	*/
280	mh_int_t save_i = i;	14,785,732✔
281	while (mh_dirty(h, i)) {	14,875,064✔
282	i = _mh(next_slot)(i, inc, h->n_buckets);	90,704✔
283
284	if (mh_mayeq(h, i, hk) && !mh_cmp(mh_node(h, i), node, arg))	90,704✔
285	return i; /* Found a duplicate. */	1,372✔
286	}
287	/* Reached the end of the collision chain: no duplicates. */
288	*exist = 0;	14,784,360✔
289	h->size++;	14,784,360✔
290	if (!mh_dirty(h, save_i))	14,784,360✔
291	h->n_dirty++;	14,728,702✔
292	mh_setexist(h, save_i, hk);	14,784,360✔
293	return save_i;	14,784,360✔
294	}
295
296	/**
297	* Find a node in the hash and replace it with a new value.
298	* Save the old node in ret pointer, if it is provided.
299	* If the old node didn't exist, just insert the new node.
300	*
301	* @retval != mh_end() pos of the new node, ret is either NULL
302	* or copy of the old node
303	*/
304	static inline mh_int_t
305	_mh(put)(struct _mh(t) h, const mh_node_t node, mh_node_t **ret,	7,857,913✔
306	mh_arg_t arg)
307	{
308	mh_int_t x = mh_end(h);	7,857,913✔
309	int exist;
310
311	assert(h->size < h->n_buckets);	7,857,913!
312
313	#if MH_INCREMENTAL_RESIZE
314	if (mh_unlikely(h->resize_position > 0))	7,857,913✔
315	_mh(resize)(h, arg);	13,007!
316	else if (mh_unlikely(h->n_dirty >= h->upper_bound)) {	7,844,906✔
317	_mh(start_resize)(h, h->n_buckets + 1, 0, arg);	178,767!
318	}
319	if (h->resize_position)	7,857,913✔
320	_mh(put)(h->shadow, node, NULL, arg);	13,007!
321	#else
322	if (mh_unlikely(h->n_dirty >= h->upper_bound)) {
323	_mh(start_resize)(h, h->n_buckets + 1, h->size, arg);
324	}
325	#endif
326
327	x = put_slot(h, node, &exist, arg);	7,857,913!
328
329	if (ret) {	7,857,913✔
330	if (exist)	3,254,214✔
331	memcpy(*ret, &(h->p[x]), sizeof(mh_node_t));	553,588✔
332	else
333	*ret = NULL;	2,700,626✔
334	}
335	memcpy(&(h->p[x]), node, sizeof(mh_node_t));	7,857,913✔
336	return x;	7,857,913✔
337	}
338
339	static inline void
340	_mh(del)(struct _mh(t) *h, mh_int_t x,	2,562,114✔
341	mh_arg_t arg)
342	{
343	if (x != h->n_buckets && mh_exist(h, x)) {	2,562,114!
344	mh_setfree(h, x);	2,562,114✔
345	h->size--;	2,562,114✔
346	if (!mh_dirty(h, x))	2,562,114✔
347	h->n_dirty--;	2,227,126✔
348	#if MH_INCREMENTAL_RESIZE
349	if (mh_unlikely(h->resize_position))	2,562,114!
350	_mh(del_resize)(h, x, arg);	×
351	#endif
352	}
353	}	2,562,114✔
354	#endif
355
356	static inline void
357	_mh(remove)(struct _mh(t) h, const mh_node_t node,	230,071✔
358	mh_arg_t arg)
359	{
360	mh_int_t k = _mh(get)(h, node, arg);	230,071✔
361	if (k != mh_end(h))	230,071!
362	_mh(del)(h, k, arg);	230,071✔
363	}	230,071✔
364
365	#ifdef MH_SOURCE
366
367	#ifndef __ac_HASH_PRIME_SIZE
368	#define __ac_HASH_PRIME_SIZE 31
369	static const mh_int_t __ac_prime_list[__ac_HASH_PRIME_SIZE] = {
370	3ul, 11ul, 23ul, 53ul,
371	97ul, 193ul, 389ul, 769ul,
372	1543ul, 3079ul, 6151ul, 12289ul,
373	24593ul, 49157ul, 98317ul, 196613ul,
374	393241ul, 786433ul, 1572869ul, 3145739ul,
375	6291469ul, 12582917ul, 25165843ul, 50331653ul,
376	100663319ul, 201326611ul, 402653189ul, 805306457ul,
377	1610612741ul, 3221225473ul, 4294967291ul
378	};
379	#endif /* __ac_HASH_PRIME_SIZE */
380
381	NOINLINE void
382	_mh(del_resize)(struct _mh(t) *h, mh_int_t x,	×
383	mh_arg_t arg)
384	{
385	struct _mh(t) *s = h->shadow;	×
386	mh_int_t y = _mh(get)(s, (const mh_node_t *) &(h->p[x]),	×
387	arg);
388	_mh(del)(s, y, arg);	×
389	_mh(resize)(h, arg);	×
390	}	×
391
392	struct _mh(t) *
393	_mh(new)()	2,058,551✔
394	{
395	struct _mh(t) h = (struct _mh(t) )xcalloc(1, sizeof(*h));	2,058,551!
396	h->shadow = (struct _mh(t) )xcalloc(1, sizeof(h));	2,058,551!
397	h->prime = 0;	2,058,551✔
398	h->n_buckets = __ac_prime_list[h->prime];	2,058,551✔
399	h->p = (mh_node_t *)xcalloc(h->n_buckets, sizeof(mh_node_t));	2,058,551!
400	#if !mh_bytemap
401	h->b = (uint32_t *)xcalloc(h->n_buckets / 16 + 1, sizeof(uint32_t));	2,058,551!
402	#else
403	h->b = (uint8_t *)xcalloc(h->n_buckets, sizeof(uint8_t));
404	#endif
405	h->upper_bound = h->n_buckets * MH_DENSITY;	2,058,551✔
406	return h;	2,058,551✔
407	}
408
409	void
410	_mh(clear)(struct _mh(t) *h)	8,869✔
411	{
412	mh_int_t n_buckets = __ac_prime_list[h->prime];	8,869✔
413	mh_node_t p = (mh_node_t )xcalloc(n_buckets, sizeof(mh_node_t));	8,869!
414	#if !mh_bytemap
415	uint32_t b = (uint32_t )xcalloc(n_buckets / 16 + 1, sizeof(uint32_t));	8,869!
416	#else
417	uint8_t b = (uint8_t )xcalloc(n_buckets, sizeof(uint8_t));
418	#endif
419	if (h->shadow->p) {	8,869!
420	free(h->shadow->p);	×
421	free(h->shadow->b);	×
422	memset(h->shadow, 0, sizeof(*h->shadow));	×
423	}
424	free(h->p);	8,869✔
425	free(h->b);	8,869✔
426	h->prime = 0;	8,869✔
427	h->n_buckets = n_buckets;	8,869✔
428	h->p = p;	8,869✔
429	h->b = b;	8,869✔
430	h->size = 0;	8,869✔
431	h->upper_bound = h->n_buckets * MH_DENSITY;	8,869✔
432	}	8,869✔
433
434	void
435	_mh(delete)(struct _mh(t) *h)	1,675,104✔
436	{
437	if (h->shadow->p) {	1,675,104!
UNCOV 438	free(h->shadow->p);	×
UNCOV 439	free(h->shadow->b);	×
UNCOV 440	memset(h->shadow, 0, sizeof(*h->shadow));	×
441	}
442	free(h->shadow);	1,675,104✔
443	free(h->b);	1,675,104✔
444	free(h->p);	1,675,104✔
445	free(h);	1,675,104✔
446	}	1,675,104✔
447
448	/** Calculate hash size. */
449	size_t
450	_mh(memsize)(struct _mh(t) *h)	×
451	{
452	size_t sz = 2 * sizeof(struct _mh(t));	×
453
454	sz += h->n_buckets * sizeof(mh_node_t);	×
455	#if !mh_bytemap
456	sz += (h->n_buckets / 16 + 1) * sizeof(uint32_t);	×
457	#else
458	sz += h->n_buckets;
459	#endif
460	if (h->resize_position) {	×
461	h = h->shadow;	×
462	sz += h->n_buckets * sizeof(mh_node_t);	×
463	#if !mh_bytemap
464	sz += (h->n_buckets / 16 + 1) * sizeof(uint32_t);	×
465	#else
466	sz += h->n_buckets;
467	#endif
468	}
469	return sz;	×
470	}
471
472	void
473	_mh(resize)(struct _mh(t) *h, mh_arg_t arg)	435,091✔
474	{
475	struct _mh(t) *s = h->shadow;	435,091✔
476	int exist;
477	#if MH_INCREMENTAL_RESIZE
478	mh_int_t batch = h->batch;	435,091✔
479	#endif
480	for (mh_int_t i = h->resize_position; i < h->n_buckets; i++) {	11,956,886✔
481	#if MH_INCREMENTAL_RESIZE
482	if (batch-- == 0) {	11,534,805✔
483	h->resize_position = i;	13,007✔
484	return;	13,007✔
485	}
486	#endif
487	if (!mh_exist(h, i))	11,521,807✔
488	continue;	4,016,599✔
489	mh_int_t n = put_slot(s, mh_node(h, i), &exist, arg);	7,505,206!
490	s->p[n] = h->p[i];	7,505,206✔
491	}
492	free(h->p);	422,084✔
493	free(h->b);	422,084✔
494	if (s->size != h->size)	422,084!
495	abort();	×
496	memcpy(h, s, sizeof(*h));	422,084✔
497	h->resize_cnt++;	422,084✔
498	memset(s, 0, sizeof(*s));	422,084✔
499	}
500
501	void
502	_mh(start_resize)(struct _mh(t) *h, mh_int_t buckets, mh_int_t batch,	588,585✔
503	mh_arg_t arg)
504	{
505	if (h->resize_position) {	588,585!
506	/* resize has already been started */
507	return;	×
508	}
509	if (buckets < h->n_buckets) {	588,585✔
510	/* hash size is already greater than requested */
511	return;	166,501✔
512	}
513	mh_int_t new_prime = h->prime;	422,084✔
514	while (new_prime < __ac_HASH_PRIME_SIZE - 1) {	889,634!
515	if (__ac_prime_list[new_prime] >= buckets)	889,634✔
516	break;	422,084✔
517	new_prime += 1;	467,550✔
518	}
519	mh_int_t new_batch = batch > 0 ? batch : h->n_buckets / (256 * 1024);	422,084!
520	if (new_batch < 256) {	422,084!
521	/*
522	* Minimal batch must be greater or equal to
523	* 1 / (1 - f), where f is upper bound percent
524	* = MH_DENSITY
525	*/
526	new_batch = 256;	422,084✔
527	}
528
529	mh_int_t n_buckets = __ac_prime_list[new_prime];	422,084✔
530	mh_node_t p = (mh_node_t )xmalloc(n_buckets * sizeof(mh_node_t));	422,084!
531	#if !mh_bytemap
532	uint32_t b = (uint32_t )xcalloc(n_buckets / 16 + 1, sizeof(uint32_t));	422,084!
533	#else
534	uint8_t b = (uint8_t )xcalloc(n_buckets, sizeof(uint8_t));
535	#endif
536	h->prime = new_prime;	422,084✔
537	h->batch = new_batch;	422,084✔
538	struct _mh(t) *s = h->shadow;	422,084✔
539	memcpy(s, h, sizeof(*h));	422,084✔
540	s->resize_position = 0;	422,084✔
541	s->n_buckets = n_buckets;	422,084✔
542	s->upper_bound = s->n_buckets * MH_DENSITY;	422,084✔
543	s->n_dirty = 0;	422,084✔
544	s->size = 0;	422,084✔
545	s->p = p;	422,084✔
546	s->b = b;	422,084✔
547	_mh(resize)(h, arg);	422,084✔
548	}
549
550	void
551	_mh(reserve)(struct _mh(t) *h, mh_int_t size,	409,818✔
552	mh_arg_t arg)
553	{
554	_mh(start_resize)(h, size/MH_DENSITY, h->size, arg);	409,818✔
555	}	409,818✔
556
557	#ifndef mh_stat
558	#define mh_stat(buf, h) ({ \
559	tbuf_printf(buf, " n_buckets: %" PRIu32 CRLF \
560	" n_dirty: %" PRIu32 CRLF \
561	" size: %" PRIu32 CRLF \
562	" resize_cnt: %" PRIu32 CRLF \
563	" resize_position: %" PRIu32 CRLF, \
564	h->n_buckets, \
565	h->n_dirty, \
566	h->size, \
567	h->resize_cnt, \
568	h->resize_position); \
569	})
570	#endif
571
572	#ifdef MH_DEBUG
573	void
574	_mh(dump)(struct _mh(t) *h)
575	{
576	printf("slots:\n");
577	int k = 0;
578	for(int i = 0; i < h->n_buckets; i++) {
579	if (mh_dirty(h, i) \|\| mh_exist(h, i)) {
580	printf(" [%i] ", i);
581	if (mh_exist(h, i)) {
582	/* TODO(roman): fix this printf */
583	printf(" -> %p", h->p[i]);
584	k++;
585	}
586	if (mh_dirty(h, i))
587	printf(" dirty");
588	printf("\n");
589	}
590	}
591	printf("end(%i)\n", k);
592	}
593	#endif
594
595	#endif
596
597	#if defined(MH_SOURCE) \|\| defined(MH_UNDEF)
598	#undef MH_HEADER
599	#undef mh_int_t
600	#undef mh_node_t
601	#undef mh_arg_t
602	#undef mh_key_t
603	#undef mh_name
604	#undef mh_hash
605	#undef mh_hash_key
606	#undef mh_cmp
607	#undef mh_cmp_key
608	#undef mh_node
609	#undef mh_dirty
610	#undef mh_place
611	#undef mh_setdirty
612	#undef mh_setexist
613	#undef mh_setvalue
614	#undef mh_unlikely
615	#undef slot
616	#undef slot_and_dirty
617	#undef MH_DENSITY
618	#undef mh_bytemap
619	#endif
620
621	#undef mh_cat
622	#undef mh_ecat
623	#undef _mh

tarantool / tarantool / 10555265542

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous