src/third_party/vulkan-validation-layers/src/layers/vk_layer_data.h - cobalt - Git at Google

 /* Copyright (c) 2015-2017, 2019 The Khronos Group Inc.
  * Copyright (c) 2015-2017, 2019 Valve Corporation
  * Copyright (c) 2015-2017, 2019 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.
  *
  * Author: Tobin Ehlis <tobine@google.com>
  */

 #ifndef LAYER_DATA_H
 #define LAYER_DATA_H

 #include <cassert>
 #include <unordered_map>
 #include <unordered_set>

 // 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;

   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 (value_type_helper().compare_equal(small_data[i], key) && small_data_allocated[i]) {
                 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 (value_type_helper().compare_equal(small_data[i], value) && small_data_allocated[i]) {
                 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(value_type_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;
                     value_type_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 (value_type_helper().compare_equal(small_data[i], key) && small_data_allocated[i]) {
                 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 Key, typename T>
 class value_type_helper_map {
   public:
     bool compare_equal(const std::pair<const Key, T> &lhs, const Key &rhs) const { return lhs.first == rhs; }
     bool compare_equal(const std::pair<const Key, T> &lhs, const std::pair<const Key, T> &rhs) const {
         return lhs.first == rhs.first;
     }

     void assign(std::pair<const Key, T> &lhs, const std::pair<Key, T> &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 std::pair<const Key, T> &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, std::pair<const Key, T>, std::unordered_map<Key, T>, value_type_helper_map<Key, T>, N> {
   public:
     T &operator[](const Key &key) {
         for (int i = 0; i < N; ++i) {
             if (value_type_helper_map<Key, T>().compare_equal(this->small_data[i], key) && this->small_data_allocated[i]) {
                 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;
                     value_type_helper_map<Key, T>().assign(this->small_data[i], std::make_pair(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, std::unordered_set<Key>, value_type_helper_set<Key>, N> {};

 // For the given data key, look up the layer_data instance from given layer_data_map
 template <typename DATA_T>
 DATA_T *GetLayerDataPtr(void *data_key, small_unordered_map<void *, DATA_T *, 2> &layer_data_map) {
     /* TODO: We probably should lock here, or have caller lock */
     DATA_T *&got = layer_data_map[data_key];

     if (got == nullptr) {
         got = new DATA_T;
     }

     return got;
 }

 template <typename DATA_T>
 void FreeLayerDataPtr(void *data_key, small_unordered_map<void *, DATA_T *, 2> &layer_data_map) {
     delete layer_data_map[data_key];
     layer_data_map.erase(data_key);
 }

 // For the given data key, look up the layer_data instance from given layer_data_map
 template <typename DATA_T>
 DATA_T *GetLayerDataPtr(void *data_key, std::unordered_map<void *, DATA_T *> &layer_data_map) {
     DATA_T *debug_data;
     typename std::unordered_map<void *, DATA_T *>::const_iterator got;

     /* TODO: We probably should lock here, or have caller lock */
     got = layer_data_map.find(data_key);

     if (got == layer_data_map.end()) {
         debug_data = new DATA_T;
         layer_data_map[(void *)data_key] = debug_data;
     } else {
         debug_data = got->second;
     }

     return debug_data;
 }

 template <typename DATA_T>
 void FreeLayerDataPtr(void *data_key, std::unordered_map<void *, DATA_T *> &layer_data_map) {
     auto got = layer_data_map.find(data_key);
     assert(got != layer_data_map.end());

     delete got->second;
     layer_data_map.erase(got);
 }

 #endif  // LAYER_DATA_H
	/* Copyright (c) 2015-2017, 2019 The Khronos Group Inc.
	* Copyright (c) 2015-2017, 2019 Valve Corporation
	* Copyright (c) 2015-2017, 2019 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.
	*
	* Author: Tobin Ehlis <tobine@google.com>
	*/

	#ifndef LAYER_DATA_H
	#define LAYER_DATA_H

	#include <cassert>
	#include <unordered_map>
	#include <unordered_set>

	// 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;

	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 (value_type_helper().compare_equal(small_data[i], key) && small_data_allocated[i]) {
	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 (value_type_helper().compare_equal(small_data[i], value) && small_data_allocated[i]) {
	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(value_type_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;
	value_type_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 (value_type_helper().compare_equal(small_data[i], key) && small_data_allocated[i]) {
	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 Key, typename T>
	class value_type_helper_map {
	public:
	bool compare_equal(const std::pair<const Key, T> &lhs, const Key &rhs) const { return lhs.first == rhs; }
	bool compare_equal(const std::pair<const Key, T> &lhs, const std::pair<const Key, T> &rhs) const {
	return lhs.first == rhs.first;
	}

	void assign(std::pair<const Key, T> &lhs, const std::pair<Key, T> &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 std::pair<const Key, T> &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, std::pair<const Key, T>, std::unordered_map<Key, T>, value_type_helper_map<Key, T>, N> {
	public:
	T &operator[](const Key &key) {
	for (int i = 0; i < N; ++i) {
	if (value_type_helper_map<Key, T>().compare_equal(this->small_data[i], key) && this->small_data_allocated[i]) {
	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;
	value_type_helper_map<Key, T>().assign(this->small_data[i], std::make_pair(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, std::unordered_set<Key>, value_type_helper_set<Key>, N> {};

	// For the given data key, look up the layer_data instance from given layer_data_map
	template <typename DATA_T>
	DATA_T GetLayerDataPtr(void data_key, small_unordered_map<void , DATA_T , 2> &layer_data_map) {
	/* TODO: We probably should lock here, or have caller lock */
	DATA_T *&got = layer_data_map[data_key];

	if (got == nullptr) {
	got = new DATA_T;
	}

	return got;
	}

	template <typename DATA_T>
	void FreeLayerDataPtr(void data_key, small_unordered_map<void , DATA_T *, 2> &layer_data_map) {
	delete layer_data_map[data_key];
	layer_data_map.erase(data_key);
	}

	// For the given data key, look up the layer_data instance from given layer_data_map
	template <typename DATA_T>
	DATA_T GetLayerDataPtr(void data_key, std::unordered_map<void , DATA_T > &layer_data_map) {
	DATA_T *debug_data;
	typename std::unordered_map<void , DATA_T >::const_iterator got;

	/* TODO: We probably should lock here, or have caller lock */
	got = layer_data_map.find(data_key);

	if (got == layer_data_map.end()) {
	debug_data = new DATA_T;
	layer_data_map[(void *)data_key] = debug_data;
	} else {
	debug_data = got->second;
	}

	return debug_data;
	}

	template <typename DATA_T>
	void FreeLayerDataPtr(void data_key, std::unordered_map<void , DATA_T *> &layer_data_map) {
	auto got = layer_data_map.find(data_key);
	assert(got != layer_data_map.end());

	delete got->second;
	layer_data_map.erase(got);
	}

	#endif // LAYER_DATA_H