aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers
diff options
context:
space:
mode:
authorqrort <qrort@yandex-team.com>2022-12-02 11:31:25 +0300
committerqrort <qrort@yandex-team.com>2022-12-02 11:31:25 +0300
commitb1f4ffc9c8abff3ba58dc1ec9a9f92d2f0de6806 (patch)
tree2a23209faf0fea5586a6d4b9cee60d1b318d29fe /library/cpp/containers
parent559174a9144de40d6bb3997ea4073c82289b4974 (diff)
downloadydb-b1f4ffc9c8abff3ba58dc1ec9a9f92d2f0de6806.tar.gz
remove kikimr/driver DEPENDS
Diffstat (limited to 'library/cpp/containers')
-rw-r--r--library/cpp/containers/concurrent_hash/concurrent_hash.h128
-rw-r--r--library/cpp/containers/str_hash/str_hash.cpp60
-rw-r--r--library/cpp/containers/str_hash/str_hash.h181
3 files changed, 0 insertions, 369 deletions
diff --git a/library/cpp/containers/concurrent_hash/concurrent_hash.h b/library/cpp/containers/concurrent_hash/concurrent_hash.h
deleted file mode 100644
index f15a1c3d6e..0000000000
--- a/library/cpp/containers/concurrent_hash/concurrent_hash.h
+++ /dev/null
@@ -1,128 +0,0 @@
-#pragma once
-
-#include <util/generic/hash.h>
-#include <util/system/spinlock.h>
-
-#include <array>
-
-template <typename K, typename V, size_t BucketCount = 64, typename L = TAdaptiveLock>
-class TConcurrentHashMap {
-public:
- using TActualMap = THashMap<K, V>;
- using TLock = L;
-
- struct TBucket {
- friend class TConcurrentHashMap;
-
- private:
- TActualMap Map;
- mutable TLock Mutex;
-
- public:
- TLock& GetMutex() const {
- return Mutex;
- }
-
- TActualMap& GetMap() {
- return Map;
- }
- const TActualMap& GetMap() const {
- return Map;
- }
-
- const V& GetUnsafe(const K& key) const {
- typename TActualMap::const_iterator it = Map.find(key);
- Y_VERIFY(it != Map.end(), "not found by key");
- return it->second;
- }
-
- V& GetUnsafe(const K& key) {
- typename TActualMap::iterator it = Map.find(key);
- Y_VERIFY(it != Map.end(), "not found by key");
- return it->second;
- }
-
- V RemoveUnsafe(const K& key) {
- typename TActualMap::iterator it = Map.find(key);
- Y_VERIFY(it != Map.end(), "removing non-existent key");
- V r = std::move(it->second);
- Map.erase(it);
- return r;
- }
-
- bool HasUnsafe(const K& key) const {
- typename TActualMap::const_iterator it = Map.find(key);
- return (it != Map.end());
- }
- };
-
- std::array<TBucket, BucketCount> Buckets;
-
-public:
- TBucket& GetBucketForKey(const K& key) {
- return Buckets[THash<K>()(key) % BucketCount];
- }
-
- const TBucket& GetBucketForKey(const K& key) const {
- return Buckets[THash<K>()(key) % BucketCount];
- }
-
- void Insert(const K& key, const V& value) {
- TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- bucket.Map[key] = value;
- }
-
- void InsertUnique(const K& key, const V& value) {
- TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- if (!bucket.Map.insert(std::make_pair(key, value)).second) {
- Y_FAIL("non-unique key");
- }
- }
-
- V& InsertIfAbsent(const K& key, const V& value) {
- TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- return bucket.Map.insert(std::make_pair(key, value)).first->second;
- }
-
- template <typename Callable>
- V& InsertIfAbsentWithInit(const K& key, Callable initFunc) {
- TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- if (bucket.HasUnsafe(key)) {
- return bucket.GetUnsafe(key);
- }
-
- return bucket.Map.insert(std::make_pair(key, initFunc())).first->second;
- }
-
- V Get(const K& key) const {
- const TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- return bucket.GetUnsafe(key);
- }
-
- bool Get(const K& key, V& result) const {
- const TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- if (bucket.HasUnsafe(key)) {
- result = bucket.GetUnsafe(key);
- return true;
- }
- return false;
- }
-
- V Remove(const K& key) {
- TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- return bucket.RemoveUnsafe(key);
- }
-
- bool Has(const K& key) const {
- const TBucket& bucket = GetBucketForKey(key);
- TGuard<TLock> guard(bucket.Mutex);
- return bucket.HasUnsafe(key);
- }
-};
diff --git a/library/cpp/containers/str_hash/str_hash.cpp b/library/cpp/containers/str_hash/str_hash.cpp
deleted file mode 100644
index 1298638533..0000000000
--- a/library/cpp/containers/str_hash/str_hash.cpp
+++ /dev/null
@@ -1,60 +0,0 @@
-#include "str_hash.h"
-
-#include <library/cpp/charset/ci_string.h>
-#include <util/stream/output.h>
-#include <util/stream/input.h>
-
-HashSet::HashSet(const char** array, size_type size) {
- Resize(size);
- while (*array && **array)
- AddPermanent(*array++);
-}
-
-void HashSet::Read(IInputStream* input) {
- TString s;
-
- while (input->ReadLine(s)) {
- AddUniq(TCiString(s).c_str());
- }
-}
-
-void HashSet::Write(IOutputStream* output) const {
- for (const auto& it : *this) {
- *output << it.first << "\n";
- }
-}
-
-#ifdef TEST_STRHASH
-#include <ctime>
-#include <fstream>
-#include <cstdio>
-#include <cstdlib>
-
-using namespace std;
-
-int main(int argc, char* argv[]) {
- if (argc < 2) {
- printf("usage: stoplist <stop-words file ...\n");
- exit(EXIT_FAILURE); // FreeBSD: EX_USAGE
- }
- Hash hash;
- hash.Read(cin);
- for (--argc, ++argv; argc > 0; --argc, ++argv) {
- ifstream input(argv[0]);
- if (!input.good()) {
- perror(argv[0]);
- continue;
- }
- TCiString s;
- while (input >> s) {
- if (!hash.Has(s))
- cout << s << "\n";
- else
- cout << "[[" << s << "]]"
- << "\n";
- }
- }
- return EXIT_SUCCESS; // EX_OK
-}
-
-#endif
diff --git a/library/cpp/containers/str_hash/str_hash.h b/library/cpp/containers/str_hash/str_hash.h
deleted file mode 100644
index 25f960dbb5..0000000000
--- a/library/cpp/containers/str_hash/str_hash.h
+++ /dev/null
@@ -1,181 +0,0 @@
-#pragma once
-
-#include <library/cpp/containers/str_map/str_map.h>
-#include <library/cpp/charset/ci_string.h>
-#include <util/system/yassert.h>
-#include <util/memory/tempbuf.h>
-
-#include <memory>
-
-class IInputStream;
-class IOutputStream;
-
-template <class T, class Alloc = std::allocator<const char*>>
-class Hash;
-
-struct yvoid {
- yvoid() = default;
-};
-
-template <typename T, class Alloc>
-class Hash: public string_hash<T, ci_hash, ci_equal_to, Alloc> {
- using ci_string_hash = string_hash<T, ci_hash, ci_equal_to, Alloc>;
-
-protected:
- using ci_string_hash::pool;
-
-public:
- using size_type = typename ci_string_hash::size_type;
- using const_iterator = typename ci_string_hash::const_iterator;
- using iterator = typename ci_string_hash::iterator;
- using value_type = typename ci_string_hash::value_type;
- using ci_string_hash::begin;
- using ci_string_hash::end;
- using ci_string_hash::find;
- using ci_string_hash::size;
-
- Hash()
- : ci_string_hash()
- {
- }
- explicit Hash(size_type theSize)
- : ci_string_hash(theSize, theSize * AVERAGEWORD_BUF)
- {
- }
- Hash(const char** strings, size_type size = 0, T* = 0); // must end with NULL or "\0"
- virtual ~Hash();
- bool Has(const char* s, size_t len, T* pp = nullptr) const;
- bool Has(const char* s, T* pp = nullptr) const {
- const_iterator it;
- if ((it = find(s)) == end())
- return false;
- else if (pp)
- *pp = (*it).second;
- return true;
- }
- void Add(const char* s, T data) {
- // in fact it is the same insert_unique as in AddUnique.
- // it's impossible to have _FAST_ version of insert() in 'hash_map'
-
- // you have to use 'hash_mmap' to get the _kind_ of desired effect.
- // BUT still there will be "Checks" inside -
- // to make the same keys close to each other (see insert_equal())
- this->insert_copy(s, data);
- }
- bool AddUniq(const char* s, T data) {
- return this->insert_copy(s, data).second;
- }
- // new function to get rid of allocations completely! -- e.g. in constructors
- void AddPermanent(const char* s, T data) {
- this->insert(value_type(s, data));
- }
- T Detach(const char* s) {
- iterator it = find(s);
- if (it == end())
- return T();
- T data = (*it).second;
- this->erase(it);
- return data;
- }
- size_type NumEntries() const {
- return size();
- }
- bool ForEach(bool (*func)(const char* key, T data, void* cookie), void* cookie = nullptr);
- void Resize(size_type theSize) {
- this->reserve(theSize);
- // no pool resizing here.
- }
- virtual void Clear();
- char* Pool() {
- if (pool.Size() < 2 || pool.End()[-2] != '\0')
- pool.Append("\0", 1);
- return pool.Begin();
- }
-};
-
-template <class T, class Alloc>
-Hash<T, Alloc>::Hash(const char** array, size_type theSize, T* data) {
- // must end with NULL or "\0"
- Y_ASSERT(data != nullptr);
- Resize(theSize);
- while (*array && **array)
- AddPermanent(*array++, *data++);
-}
-
-template <class T, class Alloc>
-bool Hash<T, Alloc>::Has(const char* s, size_t len, T* pp) const {
- TTempArray<char> buf(len + 1);
- char* const allocated = buf.Data();
- memcpy(allocated, s, len);
- allocated[len] = '\x00';
- return Has(allocated, pp);
-}
-
-template <class T, class Alloc>
-Hash<T, Alloc>::~Hash() {
- Clear();
-}
-
-template <class T, class Alloc>
-void Hash<T, Alloc>::Clear() {
- ci_string_hash::clear_hash(); // to make the key pool empty
-}
-
-template <class T, class Alloc>
-bool Hash<T, Alloc>::ForEach(bool (*func)(const char* key, T data, void* cookie), void* cookie) {
- for (const_iterator it = begin(); it != end(); ++it)
- if (!func((*it).first, (*it).second, cookie))
- return false;
- return true;
-}
-
-class HashSet: public Hash<yvoid> {
-public:
- HashSet(const char** array, size_type size = 0);
- HashSet()
- : Hash<yvoid>()
- {
- }
- void Read(IInputStream* input);
- void Write(IOutputStream* output) const;
- void Add(const char* s) {
- // in fact it is the same insert_unique as in AddUnique.
- // it's impossible to have _FAST_ version of insert() in 'hash_map'
-
- // you have to use 'hash_mmap' to get the _kind_ of desired effect.
- // BUT still there will be "Checks" inside -
- // to make the same keys close to each other (see insert_equal())
- insert_copy(s, yvoid());
- }
- bool AddUniq(const char* s) {
- return insert_copy(s, yvoid()).second;
- }
- // new function to get rid of allocations completely! -- e.g. in constructors
- void AddPermanent(const char* s) {
- insert(value_type(s, yvoid()));
- }
-};
-
-template <class T, class HashFcn = THash<T>, class EqualKey = TEqualTo<T>, class Alloc = std::allocator<T>>
-class TStaticHash: private THashMap<T, T, HashFcn, EqualKey> {
-private:
- using TBase = THashMap<T, T, HashFcn, EqualKey>;
-
-public:
- TStaticHash(T arr[][2], size_t size) {
- TBase::reserve(size);
- while (size) {
- TBase::insert(typename TBase::value_type(arr[0][0], arr[0][1]));
- arr++;
- size--;
- }
- }
- T operator[](const T& key) const { // !!! it is not lvalue nor it used to be
- typename TBase::const_iterator it = TBase::find(key);
- if (it == TBase::end())
- return nullptr;
- return it->second;
- }
-};
-
-using TStHash = TStaticHash<const char*, ci_hash, ci_equal_to>;