/*

* Copyright (C) 2016 Apple Inc. All rights reserved.

*

* 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 APPLE INC. ``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 APPLE INC. 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.

*/

#ifndef Map_h

#define Map_h

#include "BInline.h"

#include "Sizes.h"

#include "Vector.h"

namespace bmalloc {

class SmallPage;

template<typename Key, typename Value, typename Hash> class Map {

static_assert(std::is_trivially_destructible<Key>::value, "Map must have a trivial destructor.");

static_assert(std::is_trivially_destructible<Value>::value, "Map must have a trivial destructor.");

public:

struct Bucket {

Key key;

Value value;

};

size_t size() { return m_keyCount; }

size_t capacity() { return m_table.size(); }

// key must be in the map.

Value& get(const Key& key)

{

auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });

return bucket.value;

}

void set(const Key& key, const Value& value)

{

if (shouldGrow())

rehash();

auto& bucket = find(key, [&](const Bucket& bucket) { return !bucket.key || bucket.key == key; });

if (!bucket.key) {

bucket.key = key;

++m_keyCount;

}

bucket.value = value;

}

// key must be in the map.

Value remove(const Key& key)

{

if (shouldShrink())

rehash();

auto& bucket = find(key, [&](const Bucket& bucket) { return bucket.key == key; });

Value value = bucket.value;

bucket.key = Key();

--m_keyCount;

return value;

}

private:

static constexpr unsigned minCapacity = 16;

static constexpr unsigned maxLoad = 2;

static constexpr unsigned rehashLoad = 4;

static constexpr unsigned minLoad = 8;

bool shouldGrow() { return m_keyCount * maxLoad >= capacity(); }

bool shouldShrink() { return m_keyCount * minLoad <= capacity() && capacity() > minCapacity; }

void rehash();

template<typename Predicate>

Bucket& find(const Key& key, const Predicate& predicate)

{

for (unsigned h = Hash::hash(key); ; ++h) {

unsigned i = h & m_tableMask;

Bucket& bucket = m_table[i];

if (predicate(bucket))

return bucket;

}

}

unsigned m_keyCount;

unsigned m_tableMask;

Vector<Bucket> m_table;

};

template<typename Key, typename Value, typename Hash>

void Map<Key, Value, Hash>::rehash()

{

auto oldTable = std::move(m_table);

size_t newCapacity = std::max(minCapacity, m_keyCount * rehashLoad);

m_table.grow(newCapacity);

m_keyCount = 0;

m_tableMask = newCapacity - 1;

for (auto& bucket : oldTable) {

if (!bucket.key)

continue;

BASSERT(!shouldGrow());

set(bucket.key, bucket.value);

}

}

template<typename Key, typename Value, typename Hash> const unsigned Map<Key, Value, Hash>::minCapacity;

} // namespace bmalloc

#endif // Map_h