layers/containers/small_container.h - external/github.com/KhronosGroup/Vulkan-ValidationLayers - Git at Google

 /* Copyright (c) 2015-2017, 2019-2025 The Khronos Group Inc.
  * Copyright (c) 2015-2017, 2019-2025 Valve Corporation
  * Copyright (c) 2015-2017, 2019-2025 LunarG, Inc.
  *
  * 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.

  */

 #pragma once
 #include <utility>
 #include "custom_containers.h"

 // This is a wrapper around unordered_map that optimizes for the common case
 // of only containing a small number of elements. The first N elements are stored
 // inline in the object and don't require hashing or memory (de)allocation.

 template <typename Key, typename value_type, typename inner_container_type, typename value_type_helper, int N>
 class small_container {
   protected:
     bool small_data_allocated[N];
     value_type small_data[N];

     inner_container_type inner_cont;

     value_type_helper helper;

   public:
     small_container() {
         for (int i = 0; i < N; ++i) {
             small_data_allocated[i] = false;
         }
     }

     class iterator {
         typedef typename inner_container_type::iterator inner_iterator;
         friend class small_container<Key, value_type, inner_container_type, value_type_helper, N>;

         small_container<Key, value_type, inner_container_type, value_type_helper, N> *parent;
         int index;
         inner_iterator it;

       public:
         iterator() {}

         iterator operator++() {
             if (index < N) {
                 index++;
                 while (index < N && !parent->small_data_allocated[index]) {
                     index++;
                 }
                 if (index < N) {
                     return *this;
                 }
                 it = parent->inner_cont.begin();
                 return *this;
             }
             ++it;
             return *this;
         }

         bool operator==(const iterator &other) const {
             if ((index < N) != (other.index < N)) {
                 return false;
             }
             if (index < N) {
                 return (index == other.index);
             }
             return it == other.it;
         }

         bool operator!=(const iterator &other) const { return !(*this == other); }

         value_type &operator*() const {
             if (index < N) {
                 return parent->small_data[index];
             }
             return *it;
         }
         value_type *operator->() const {
             if (index < N) {
                 return &parent->small_data[index];
             }
             return &*it;
         }
     };

     class const_iterator {
         typedef typename inner_container_type::const_iterator inner_iterator;
         friend class small_container<Key, value_type, inner_container_type, value_type_helper, N>;

         const small_container<Key, value_type, inner_container_type, value_type_helper, N> *parent;
         int index;
         inner_iterator it;

       public:
         const_iterator() {}

         const_iterator operator++() {
             if (index < N) {
                 index++;
                 while (index < N && !parent->small_data_allocated[index]) {
                     index++;
                 }
                 if (index < N) {
                     return *this;
                 }
                 it = parent->inner_cont.begin();
                 return *this;
             }
             ++it;
             return *this;
         }

         bool operator==(const const_iterator &other) const {
             if ((index < N) != (other.index < N)) {
                 return false;
             }
             if (index < N) {
                 return (index == other.index);
             }
             return it == other.it;
         }

         bool operator!=(const const_iterator &other) const { return !(*this == other); }

         const value_type &operator*() const {
             if (index < N) {
                 return parent->small_data[index];
             }
             return *it;
         }
         const value_type *operator->() const {
             if (index < N) {
                 return &parent->small_data[index];
             }
             return &*it;
         }
     };

     iterator begin() {
         iterator it;
         it.parent = this;
         // If index 0 is allocated, return it, otherwise use operator++ to find the first
         // allocated element.
         it.index = 0;
         if (small_data_allocated[0]) {
             return it;
         }
         ++it;
         return it;
     }

     iterator end() {
         iterator it;
         it.parent = this;
         it.index = N;
         it.it = inner_cont.end();
         return it;
     }

     const_iterator begin() const {
         const_iterator it;
         it.parent = this;
         // If index 0 is allocated, return it, otherwise use operator++ to find the first
         // allocated element.
         it.index = 0;
         if (small_data_allocated[0]) {
             return it;
         }
         ++it;
         return it;
     }

     const_iterator end() const {
         const_iterator it;
         it.parent = this;
         it.index = N;
         it.it = inner_cont.end();
         return it;
     }

     bool contains(const Key &key) const {
         for (int i = 0; i < N; ++i) {
             if (small_data_allocated[i] && helper.compare_equal(small_data[i], key)) {
                 return true;
             }
         }
         // check size() first to avoid hashing key unnecessarily.
         if (inner_cont.size() == 0) {
             return false;
         }
         return inner_cont.find(key) != inner_cont.end();
     }

     typename inner_container_type::size_type count(const Key &key) const { return contains(key) ? 1 : 0; }

     std::pair<iterator, bool> insert(const value_type &value) {
         for (int i = 0; i < N; ++i) {
             if (small_data_allocated[i] && helper.compare_equal(small_data[i], value)) {
                 iterator it;
                 it.parent = this;
                 it.index = i;
                 return std::make_pair(it, false);
             }
         }
         // check size() first to avoid hashing key unnecessarily.
         auto iter = inner_cont.size() > 0 ? inner_cont.find(helper.get_key(value)) : inner_cont.end();
         if (iter != inner_cont.end()) {
             iterator it;
             it.parent = this;
             it.index = N;
             it.it = iter;
             return std::make_pair(it, false);
         } else {
             for (int i = 0; i < N; ++i) {
                 if (!small_data_allocated[i]) {
                     small_data_allocated[i] = true;
                     helper.assign(small_data[i], value);
                     iterator it;
                     it.parent = this;
                     it.index = i;
                     return std::make_pair(it, true);
                 }
             }
             iter = inner_cont.insert(value).first;
             iterator it;
             it.parent = this;
             it.index = N;
             it.it = iter;
             return std::make_pair(it, true);
         }
     }

     typename inner_container_type::size_type erase(const Key &key) {
         for (int i = 0; i < N; ++i) {
             if (small_data_allocated[i] && helper.compare_equal(small_data[i], key)) {
                 small_data_allocated[i] = false;
                 return 1;
             }
         }
         return inner_cont.erase(key);
     }

     typename inner_container_type::size_type size() const {
         auto size = inner_cont.size();
         for (int i = 0; i < N; ++i) {
             if (small_data_allocated[i]) {
                 size++;
             }
         }
         return size;
     }

     bool empty() const {
         for (int i = 0; i < N; ++i) {
             if (small_data_allocated[i]) {
                 return false;
             }
         }
         return inner_cont.size() == 0;
     }

     void clear() {
         for (int i = 0; i < N; ++i) {
             small_data_allocated[i] = false;
         }
         inner_cont.clear();
     }
 };

 // Helper function objects to compare/assign/get keys in small_unordered_set/map.
 // This helps to abstract away whether value_type is a Key or a pair<Key, T>.
 template <typename MapType>
 class value_type_helper_map {
     using PairType = typename MapType::value_type;
     using Key = typename std::remove_const<typename PairType::first_type>::type;

   public:
     bool compare_equal(const PairType &lhs, const Key &rhs) const { return lhs.first == rhs; }
     bool compare_equal(const PairType &lhs, const PairType &rhs) const { return lhs.first == rhs.first; }

     void assign(PairType &lhs, const PairType &rhs) const {
         // While the const_cast may be unsatisfactory, we are using small_data as
         // stand-in for placement new and a small-block allocator, so the const_cast
         // is minimal, contained, valid, and allows operators * and -> to avoid copies
         const_cast<Key &>(lhs.first) = rhs.first;
         lhs.second = rhs.second;
     }

     Key get_key(const PairType &value) const { return value.first; }
 };

 template <typename Key>
 class value_type_helper_set {
   public:
     bool compare_equal(const Key &lhs, const Key &rhs) const { return lhs == rhs; }

     void assign(Key &lhs, const Key &rhs) const { lhs = rhs; }

     Key get_key(const Key &value) const { return value; }
 };

 template <typename Key, typename T, int N = 1>
 class small_unordered_map : public small_container<Key, typename vvl::unordered_map<Key, T>::value_type, vvl::unordered_map<Key, T>,
                                                    value_type_helper_map<vvl::unordered_map<Key, T>>, N> {
   public:
     T &operator[](const Key &key) {
         for (int i = 0; i < N; ++i) {
             if (this->small_data_allocated[i] && this->helper.compare_equal(this->small_data[i], key)) {
                 return this->small_data[i].second;
             }
         }
         auto iter = this->inner_cont.find(key);
         if (iter != this->inner_cont.end()) {
             return iter->second;
         } else {
             for (int i = 0; i < N; ++i) {
                 if (!this->small_data_allocated[i]) {
                     this->small_data_allocated[i] = true;
                     this->helper.assign(this->small_data[i], {key, T()});

                     return this->small_data[i].second;
                 }
             }
             return this->inner_cont[key];
         }
     }
 };

 template <typename Key, int N = 1>
 class small_unordered_set : public small_container<Key, Key, vvl::unordered_set<Key>, value_type_helper_set<Key>, N> {};
	/* Copyright (c) 2015-2017, 2019-2025 The Khronos Group Inc.
	* Copyright (c) 2015-2017, 2019-2025 Valve Corporation
	* Copyright (c) 2015-2017, 2019-2025 LunarG, Inc.
	*
	* 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.

	*/

	#pragma once
	#include <utility>
	#include "custom_containers.h"

	// This is a wrapper around unordered_map that optimizes for the common case
	// of only containing a small number of elements. The first N elements are stored
	// inline in the object and don't require hashing or memory (de)allocation.

	template <typename Key, typename value_type, typename inner_container_type, typename value_type_helper, int N>
	class small_container {
	protected:
	bool small_data_allocated[N];
	value_type small_data[N];

	inner_container_type inner_cont;

	value_type_helper helper;

	public:
	small_container() {
	for (int i = 0; i < N; ++i) {
	small_data_allocated[i] = false;
	}
	}

	class iterator {
	typedef typename inner_container_type::iterator inner_iterator;
	friend class small_container<Key, value_type, inner_container_type, value_type_helper, N>;

	small_container<Key, value_type, inner_container_type, value_type_helper, N> *parent;
	int index;
	inner_iterator it;

	public:
	iterator() {}

	iterator operator++() {
	if (index < N) {
	index++;
	while (index < N && !parent->small_data_allocated[index]) {
	index++;
	}
	if (index < N) {
	return *this;
	}
	it = parent->inner_cont.begin();
	return *this;
	}
	++it;
	return *this;
	}

	bool operator==(const iterator &other) const {
	if ((index < N) != (other.index < N)) {
	return false;
	}
	if (index < N) {
	return (index == other.index);
	}
	return it == other.it;
	}

	bool operator!=(const iterator &other) const { return !(*this == other); }

	value_type &operator*() const {
	if (index < N) {
	return parent->small_data[index];
	}
	return *it;
	}
	value_type *operator->() const {
	if (index < N) {
	return &parent->small_data[index];
	}
	return &*it;
	}
	};

	class const_iterator {
	typedef typename inner_container_type::const_iterator inner_iterator;
	friend class small_container<Key, value_type, inner_container_type, value_type_helper, N>;

	const small_container<Key, value_type, inner_container_type, value_type_helper, N> *parent;
	int index;
	inner_iterator it;

	public:
	const_iterator() {}

	const_iterator operator++() {
	if (index < N) {
	index++;
	while (index < N && !parent->small_data_allocated[index]) {
	index++;
	}
	if (index < N) {
	return *this;
	}
	it = parent->inner_cont.begin();
	return *this;
	}
	++it;
	return *this;
	}

	bool operator==(const const_iterator &other) const {
	if ((index < N) != (other.index < N)) {
	return false;
	}
	if (index < N) {
	return (index == other.index);
	}
	return it == other.it;
	}

	bool operator!=(const const_iterator &other) const { return !(*this == other); }

	const value_type &operator*() const {
	if (index < N) {
	return parent->small_data[index];
	}
	return *it;
	}
	const value_type *operator->() const {
	if (index < N) {
	return &parent->small_data[index];
	}
	return &*it;
	}
	};

	iterator begin() {
	iterator it;
	it.parent = this;
	// If index 0 is allocated, return it, otherwise use operator++ to find the first
	// allocated element.
	it.index = 0;
	if (small_data_allocated[0]) {
	return it;
	}
	++it;
	return it;
	}

	iterator end() {
	iterator it;
	it.parent = this;
	it.index = N;
	it.it = inner_cont.end();
	return it;
	}

	const_iterator begin() const {
	const_iterator it;
	it.parent = this;
	// If index 0 is allocated, return it, otherwise use operator++ to find the first
	// allocated element.
	it.index = 0;
	if (small_data_allocated[0]) {
	return it;
	}
	++it;
	return it;
	}

	const_iterator end() const {
	const_iterator it;
	it.parent = this;
	it.index = N;
	it.it = inner_cont.end();
	return it;
	}

	bool contains(const Key &key) const {
	for (int i = 0; i < N; ++i) {
	if (small_data_allocated[i] && helper.compare_equal(small_data[i], key)) {
	return true;
	}
	}
	// check size() first to avoid hashing key unnecessarily.
	if (inner_cont.size() == 0) {
	return false;
	}
	return inner_cont.find(key) != inner_cont.end();
	}

	typename inner_container_type::size_type count(const Key &key) const { return contains(key) ? 1 : 0; }

	std::pair<iterator, bool> insert(const value_type &value) {
	for (int i = 0; i < N; ++i) {
	if (small_data_allocated[i] && helper.compare_equal(small_data[i], value)) {
	iterator it;
	it.parent = this;
	it.index = i;
	return std::make_pair(it, false);
	}
	}
	// check size() first to avoid hashing key unnecessarily.
	auto iter = inner_cont.size() > 0 ? inner_cont.find(helper.get_key(value)) : inner_cont.end();
	if (iter != inner_cont.end()) {
	iterator it;
	it.parent = this;
	it.index = N;
	it.it = iter;
	return std::make_pair(it, false);
	} else {
	for (int i = 0; i < N; ++i) {
	if (!small_data_allocated[i]) {
	small_data_allocated[i] = true;
	helper.assign(small_data[i], value);
	iterator it;
	it.parent = this;
	it.index = i;
	return std::make_pair(it, true);
	}
	}
	iter = inner_cont.insert(value).first;
	iterator it;
	it.parent = this;
	it.index = N;
	it.it = iter;
	return std::make_pair(it, true);
	}
	}

	typename inner_container_type::size_type erase(const Key &key) {
	for (int i = 0; i < N; ++i) {
	if (small_data_allocated[i] && helper.compare_equal(small_data[i], key)) {
	small_data_allocated[i] = false;
	return 1;
	}
	}
	return inner_cont.erase(key);
	}

	typename inner_container_type::size_type size() const {
	auto size = inner_cont.size();
	for (int i = 0; i < N; ++i) {
	if (small_data_allocated[i]) {
	size++;
	}
	}
	return size;
	}

	bool empty() const {
	for (int i = 0; i < N; ++i) {
	if (small_data_allocated[i]) {
	return false;
	}
	}
	return inner_cont.size() == 0;
	}

	void clear() {
	for (int i = 0; i < N; ++i) {
	small_data_allocated[i] = false;
	}
	inner_cont.clear();
	}
	};

	// Helper function objects to compare/assign/get keys in small_unordered_set/map.
	// This helps to abstract away whether value_type is a Key or a pair<Key, T>.
	template <typename MapType>
	class value_type_helper_map {
	using PairType = typename MapType::value_type;
	using Key = typename std::remove_const<typename PairType::first_type>::type;

	public:
	bool compare_equal(const PairType &lhs, const Key &rhs) const { return lhs.first == rhs; }
	bool compare_equal(const PairType &lhs, const PairType &rhs) const { return lhs.first == rhs.first; }

	void assign(PairType &lhs, const PairType &rhs) const {
	// While the const_cast may be unsatisfactory, we are using small_data as
	// stand-in for placement new and a small-block allocator, so the const_cast
	// is minimal, contained, valid, and allows operators * and -> to avoid copies
	const_cast<Key &>(lhs.first) = rhs.first;
	lhs.second = rhs.second;
	}

	Key get_key(const PairType &value) const { return value.first; }
	};

	template <typename Key>
	class value_type_helper_set {
	public:
	bool compare_equal(const Key &lhs, const Key &rhs) const { return lhs == rhs; }

	void assign(Key &lhs, const Key &rhs) const { lhs = rhs; }

	Key get_key(const Key &value) const { return value; }
	};

	template <typename Key, typename T, int N = 1>
	class small_unordered_map : public small_container<Key, typename vvl::unordered_map<Key, T>::value_type, vvl::unordered_map<Key, T>,
	value_type_helper_map<vvl::unordered_map<Key, T>>, N> {
	public:
	T &operator[](const Key &key) {
	for (int i = 0; i < N; ++i) {
	if (this->small_data_allocated[i] && this->helper.compare_equal(this->small_data[i], key)) {
	return this->small_data[i].second;
	}
	}
	auto iter = this->inner_cont.find(key);
	if (iter != this->inner_cont.end()) {
	return iter->second;
	} else {
	for (int i = 0; i < N; ++i) {
	if (!this->small_data_allocated[i]) {
	this->small_data_allocated[i] = true;
	this->helper.assign(this->small_data[i], {key, T()});

	return this->small_data[i].second;
	}
	}
	return this->inner_cont[key];
	}
	}
	};

	template <typename Key, int N = 1>
	class small_unordered_set : public small_container<Key, Key, vvl::unordered_set<Key>, value_type_helper_set<Key>, N> {};