Libc-1439.40.11.tar.gz

[apple/libc.git] / collections / Source / collections_map.in.c

/*
* Copyright (c) 2019 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/

#include <sys/types.h>

#include "collections_utilities.h"

// =========== Required per-type definitions ===========
#define opaque_os_map_t IN_MAP(,_t)
#define os_map_hash IN_MAP(,_hash)
#define os_map_key_equals IN_MAP(,_key_equals)

// =========== Helpers, defined only once for all different types ===========

#ifndef _COLLETIONS_MAP_HELPERS_C
#define _COLLETIONS_MAP_HELPERS_C


#define _MAP_MAX_FILL_NUMER 4
#define _MAP_MAX_FILL_DENOM 5
#define _MAP_GROW_SHIFT_RATE 8
#define _MAP_MIN_FILL_DENOM 8

OS_ALWAYS_INLINE
static inline uint32_t
map_next(uint32_t i, uint32_t size)
{
    i++;
    return i >= size ? 0 : i;
}

OS_ALWAYS_INLINE
static inline uint32_t
map_prev(uint32_t i, uint32_t size)
{
    return ((i != 0) ? i : size) - 1;
}

struct _os_map_internal_struct {
                void            *data;
                uint32_t        count;
                uint32_t        size;
                uint16_t        grow_shift;
                uint16_t        max_bucket_offset;
                // Keys are at data; values are at (data + count * sizeof(keys))
};

#endif

// =========== Helpers, defined per map ===========

#define _os_map_t IN_MAP(_,_t)
typedef struct _os_map_internal_struct _os_map_t;

#define _os_map_data_segregated IN_MAP(_,_data_segregated)
struct _os_map_data_segregated {
        os_map_key_t    *keys;
        void            **vals;
};

#define _os_map_data_ref_t IN_MAP(_,_data_ref_t)
typedef struct _os_map_data_segregated _os_map_data_ref_t;

#define _alloc_data IN_MAP(_,_alloc_data)

static inline void *
_alloc_data(uint32_t size)
{
        assert(size < UINT32_MAX);
        void *result = calloc(size, sizeof(os_map_key_t) + sizeof(void *));
        assert(result != NULL);
        return result;
}


#define _get_data_ref IN_MAP(_,_get_data_ref)

static inline void
_get_data_ref(_os_map_t *m, _os_map_data_ref_t *data)
{
        data->keys = (os_map_key_t *)(m->data);
        data->vals = (void *)(((char *)(m->data)) +
                              (m->size * sizeof(os_map_key_t)));
}


#define _free_data IN_MAP(_,_free_data)

static inline void
_free_data(_os_map_data_ref_t *data)
{
        free((void *)data->keys);
}

#define _get_key(data, i) data.keys[i]

#define _get_val(data, i) data.vals[i]

#define _set_key(data, i, key) data.keys[i] = key

#define _set_val(data, i, val) data.vals[i] = val


#define _os_map_bucket IN_MAP(_,_probe_bucket)

static inline uint32_t
_os_map_bucket(_os_map_t *m, os_map_key_t key)
{
        return os_map_hash(key) % m->size;
}

#define _os_map_bucket_offset IN_MAP(_,_bucket_offset)

static inline uint32_t
_os_map_bucket_offset(_os_map_t *m, os_map_key_t key, uint32_t i)
{
        uint32_t bucket = _os_map_bucket(m, key);
        return (i - bucket) % m->size;
}

#ifdef DEBUG

#define _get_next_offset IN_MAP(_,_verify_next_offset)

inline int64_t
_get_next_offset(_os_map_t *m, _os_map_data_ref_t data,
                uint32_t index, uint32_t size)
{
        uint32_t next_index = map_next(index, size);

        if (_get_val(data, next_index) == NULL) {
                return -1;
        }

        return _os_map_bucket_offset(m, _get_key(data, next_index),
                                       next_index);
}

#define _os_map_verify IN_MAP(_,_verify)

void
_os_map_verify(_os_map_t *m)
{
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        int64_t current_bucket_offset;
        int64_t next_bucket_offset;
        if (_get_val(data, 0) == NULL) {
                next_bucket_offset = -1;
        } else {
                next_bucket_offset = _os_map_bucket_offset(m,
                                        _get_key(data, 0), 0);
        }

        uint32_t size = m->size;

        for (uint32_t index = 0; index < size; index++){
                current_bucket_offset = next_bucket_offset;
                next_bucket_offset = _get_next_offset(m, data, index, size);

                DEBUG_ASSERT(next_bucket_offset <= current_bucket_offset + 1);
        }

}
#else

#define _os_map_verify(A)

#endif

#define _swap_if_needed IN_MAP(_,_swap_if_needed)

static inline void
_swap_if_needed(_os_map_t *m, _os_map_data_ref_t data, os_map_key_t *key,
                void **val, uint32_t *bucket_offset, uint32_t i)
{
        if (*bucket_offset != 0) {
                os_map_key_t loop_key = _get_key(data, i);

                // Doesn't support inserting twice
                DEBUG_ASSERT(!os_map_key_equals(loop_key, *key));

                uint32_t loop_bucket_offset = _os_map_bucket_offset(m,
                                                loop_key, i);
                if (*bucket_offset > loop_bucket_offset) {
                        if (*bucket_offset > m->max_bucket_offset) {
                                assert(*bucket_offset <= UINT16_MAX);
                                DEBUG_ASSERT(*bucket_offset ==
                                             m->max_bucket_offset + 1);
                                m->max_bucket_offset = *bucket_offset;
                        }
                        void *new_val = _get_val(data, i);
                        _set_key(data, i, *key);
                        _set_val(data, i, *val);
                        *key = loop_key;
                        *val = new_val;
                        *bucket_offset = loop_bucket_offset;
                }
        }
}

#define _os_map_insert_no_rehash IN_MAP(_,_insert_no_rehash)

static void
_os_map_insert_no_rehash(_os_map_t *m, os_map_key_t key, void *val)
{
        uint32_t size = m->size, loop_limit = m->size;
        uint32_t i = os_map_hash(key) % size;
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        uint32_t bucket_offset = 0;
        for (;;) {
                DEBUG_ASSERT(bucket_offset ==
                             _os_map_bucket_offset(m, key, i));
                assert(loop_limit-- != 0);
                void *loop_val = _get_val(data, i);
                if (loop_val == NULL) {
                        break;
                }

                _swap_if_needed(m, data, &key, &val, &bucket_offset, i);

                bucket_offset++;
                i = map_next(i, size);
        }

        DEBUG_ASSERT(_get_val(data, i) == NULL);

        if (bucket_offset > m->max_bucket_offset) {
                assert(bucket_offset <= UINT16_MAX);
                DEBUG_ASSERT(bucket_offset == m->max_bucket_offset + 1);
                m->max_bucket_offset = bucket_offset;
        }
        _set_key(data, i, key);
        _set_val(data, i, val);
        m->count++;
}

#define _os_map_rehash IN_MAP(_,_rehash)

static void
_os_map_rehash(_os_map_t *m, int direction)
{
        _os_map_verify(m);

        uint32_t old_size = m->size;

        _os_map_data_ref_t old_data;
        _get_data_ref(m, &old_data);

        // Grow shift is used instead of simply doubling the size each time in
        // order to increase the expected utilization, thus decreasing overall
        // memory usage, at the cost of more frequent rehashing.

        if (direction > 0) {
                m->size += (1 << m->grow_shift);
                if (m->size ==
                    ((uint32_t)_MAP_GROW_SHIFT_RATE << m->grow_shift)) {
                        m->grow_shift++;
                }
        } else if (direction < 0) {
                if (m->grow_shift > MAP_MINSHIFT) {
                        m->grow_shift--;
                }
                m->size = roundup(m->size / 2, (1 << m->grow_shift));
        }

        m->count = 0;
        m->max_bucket_offset = 0;
        m->data = _alloc_data(m->size);
        assert(m->data);

        for (uint32_t i = 0; i < old_size; i++) {
                if (_get_val(old_data, i) == NULL) {
                        continue;
                }

                _os_map_insert_no_rehash(m, _get_key(old_data, i),
                        _get_val(old_data, i));
        }
        _free_data(&old_data);

        _os_map_verify(m);
}


#define _os_map_find_helper_empty_key IN_MAP(_,_find_helper_empty_key)

#define _os_map_find_helper IN_MAP(_,_find_helper)

static inline void *
_os_map_find_helper(_os_map_t *m, os_map_key_t key, uint32_t *i)
{
        if (m->count == 0) {
                return NULL;
        }

        
        uint32_t size = m->size, loop_limit = m->size;
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        *i = _os_map_bucket(m, key);

        uint32_t bucket_offset = 0;

        for (;;) {
                assert(loop_limit-- != 0);

                if (bucket_offset > m->max_bucket_offset ||
                    _get_val(data, *i) == NULL) {
                        return NULL;
                }

                os_map_key_t loop_key = _get_key(data, *i);
                
                if (os_map_key_equals(key, loop_key)) {
                        return _get_val(data, *i);
                }
                *i = map_next(*i, size);
                bucket_offset++;
        }
}

#define _os_map_remove_entry IN_MAP(_,_remove_entry)

void
_os_map_remove_entry(_os_map_t *m, uint32_t current_index)
{
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        uint32_t size = m->size;

        uint32_t next_index = map_next(current_index, size);
        void *next_val = _get_val(data, next_index);
        os_map_key_t next_key = _get_key(data, next_index);
        while(next_val != NULL &&
              _os_map_bucket(m, next_key) != next_index) {
                _set_key(data, current_index, next_key);
                _set_val(data, current_index, next_val);

                DEBUG_ASSERT(_os_map_bucket_offset(m,
                                        next_key, current_index) <
                             _os_map_bucket_offset(m, next_key,
                                        next_index));

                current_index = next_index;
                next_index = map_next(current_index, size);
                next_val = _get_val(data, next_index);
                next_key = _get_key(data, next_index);
        }

        _set_val(data, current_index, NULL);
        m->count--;

        if ((m->size >= MAP_MINSIZE * 2) &&
            (m->count < m->size / _MAP_MIN_FILL_DENOM)) {
                // if the map density drops below 12%, shrink it
                _os_map_rehash(m, -1);
        }
}

// =========== Implementation ===========


#define os_map_init IN_MAP(,_init)

void
os_map_init(opaque_os_map_t *m_raw, os_map_config_t *config,
              __unused int struct_version)
{
        static_assert(sizeof(opaque_os_map_t) == sizeof(_os_map_t),
                      "Opaque string map incorrect size");
        _os_map_t *m = (_os_map_t *)m_raw;

        if (config) {
                m->size =  MAX(config->initial_size, MAP_MINSIZE);
        } else {
                m->size = MAP_MINSIZE;
        }

        m->count = 0;
        m->max_bucket_offset = 0;
        m->data = _alloc_data(m->size);
        assert(m->data != NULL);
        m->grow_shift = MAP_MINSHIFT;
        DEBUG_ASSERT_MAP_INVARIANTS(m);
}


#define os_map_destroy IN_MAP(,_destroy)

void
os_map_destroy(opaque_os_map_t *m_raw)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        free(m->data);
        m->data = NULL;
        m->size = 0;
}

#define os_map_insert IN_MAP(,_insert)

void
os_map_insert(opaque_os_map_t *m_raw, os_map_key_t key, void *val)
{
        _os_map_t *m = (_os_map_str_t *)m_raw;

        assert(val != NULL);

        if (m->count >= _MAP_MAX_FILL_NUMER * m->size /
                _MAP_MAX_FILL_DENOM) {
                _os_map_rehash(m, 1);
        }

        _os_map_insert_no_rehash(m, key, val);

        DEBUG_ASSERT_MAP_INVARIANTS(m);
}


#define os_map_find IN_MAP(,_find)

void *
os_map_find(opaque_os_map_t *m_raw, os_map_key_t key)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        uint32_t i;
        return _os_map_find_helper(m, key, &i);
}


#define os_map_delete IN_MAP(,_delete)

void *
os_map_delete(opaque_os_map_t *m_raw, os_map_key_t key)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        uint32_t i;

        void *val = _os_map_find_helper(m, key, &i);
        if (val == NULL) {
                return NULL;
        }

        _os_map_remove_entry(m, i);

        return val;
}

#define os_map_payload_handler_t IN_MAP(,_payload_handler_t)
typedef bool (^os_map_payload_handler_t) (os_map_key_t, void *);

#define os_map_clear IN_MAP(,_clear)

void
os_map_clear(opaque_os_map_t *m_raw,
                    OS_NOESCAPE os_map_payload_handler_t handler)
{
        _os_map_t *m = (_os_map_t *)m_raw;

        _os_map_data_ref_t oldData;
        _get_data_ref(m, &oldData);
        uint32_t oldSize = m->size;

        m->count = 0;
        m->max_bucket_offset = 0;
        m->size =  MAP_MINSIZE;
        m->data = _alloc_data(m->size);
        m->grow_shift = MAP_MINSHIFT;
        DEBUG_ASSERT_MAP_INVARIANTS(m);

        if (handler != NULL) {
                for (uint32_t i = 0; i < oldSize; i++) {
                        void *val = _get_val(oldData, i);
                        
                        if (val != NULL) {
                                handler(_get_key(oldData, i), val);
                        }
                }
        }

        _free_data(&oldData);
}


#define os_map_count IN_MAP(,_count)

size_t
os_map_count(opaque_os_map_t *m_raw)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        return m->count;
}


#define os_map_foreach IN_MAP(,_foreach)

void
os_map_foreach(opaque_os_map_t *m_raw,
                 OS_NOESCAPE os_map_payload_handler_t handler)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        for (uint32_t i = 0; i < m->size; i++) {
                void *val = _get_val(data, i);

                if (val != NULL) {
                        if (!handler(_get_key(data, i), val)) break;
                }
        }
}

#ifdef MAP_SUPPORTS_ENTRY

#define os_map_entry IN_MAP(,_entry)

os_map_key_t
os_map_entry(opaque_os_map_t *m_raw, os_map_key_t key)
{
        _os_map_t *m = (_os_map_t *)m_raw;
        _os_map_data_ref_t data;
        _get_data_ref(m, &data);

        uint32_t i;
        if (_os_map_find_helper(m, key, &i) == NULL) {
                return (os_map_key_t)NULL;
        }
        return _get_key(data, i);
}

#endif