stringcache.h 6.73 KB
Newer Older
Marco Bubke's avatar
Marco Bubke committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of Qt Creator.
**
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3 as published by the Free Software
** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-3.0.html.
**
****************************************************************************/

#pragma once

Marco Bubke's avatar
Marco Bubke committed
28 29
#include "stringcachefwd.h"

Marco Bubke's avatar
Marco Bubke committed
30
#include <utils/smallstringview.h>
Marco Bubke's avatar
Marco Bubke committed
31
#include <utils/smallstringfwd.h>
Marco Bubke's avatar
Marco Bubke committed
32 33

#include <algorithm>
Tim Jenssen's avatar
Tim Jenssen committed
34
#include <mutex>
Marco Bubke's avatar
Marco Bubke committed
35 36 37 38
#include <vector>

namespace ClangBackEnd {

Marco Bubke's avatar
Marco Bubke committed
39 40 41 42 43 44 45 46
class StringCacheException : public std::exception
{
    const char *what() const noexcept override
    {
        return "StringCache entries are in invalid state.";
    }
};

Tim Jenssen's avatar
Tim Jenssen committed
47 48 49 50 51 52 53 54 55 56
class NonLockingMutex
{
public:
    constexpr NonLockingMutex() noexcept {}
    NonLockingMutex(const NonLockingMutex&) = delete;
    NonLockingMutex& operator=(const NonLockingMutex&) = delete;
    void lock() {}
    void unlock() {}
};

Marco Bubke's avatar
Marco Bubke committed
57
template <typename StringType, typename IndexType>
Marco Bubke's avatar
Marco Bubke committed
58
class StringCacheEntry
Marco Bubke's avatar
Marco Bubke committed
59
{
Marco Bubke's avatar
Marco Bubke committed
60
public:
Marco Bubke's avatar
Marco Bubke committed
61
    StringCacheEntry(StringType &&string, IndexType id)
Marco Bubke's avatar
Marco Bubke committed
62 63 64 65 66
        : string(std::move(string)),
          id(id)
    {}

    friend bool operator<(const StringCacheEntry &entry, Utils::SmallStringView stringView)
Marco Bubke's avatar
Marco Bubke committed
67
    {
Marco Bubke's avatar
Marco Bubke committed
68 69
        return entry.string < stringView;
    }
Marco Bubke's avatar
Marco Bubke committed
70

Marco Bubke's avatar
Marco Bubke committed
71 72 73 74
    friend bool operator<(Utils::SmallStringView stringView, const StringCacheEntry &entry)
    {
        return stringView < entry.string;
    }
Marco Bubke's avatar
Marco Bubke committed
75

Marco Bubke's avatar
Marco Bubke committed
76 77 78 79 80 81
    friend bool operator<(const StringCacheEntry &first, const StringCacheEntry &second)
    {
        return first.string < second.string;
    }

    StringType string;
Marco Bubke's avatar
Marco Bubke committed
82
    IndexType id;
Marco Bubke's avatar
Marco Bubke committed
83
};
Marco Bubke's avatar
Marco Bubke committed
84

Marco Bubke's avatar
Marco Bubke committed
85 86 87 88 89
template <typename StringType, typename IndexType>
using StringCacheEntries = std::vector<StringCacheEntry<StringType, IndexType>>;

using FileCacheCacheEntry = StringCacheEntry<Utils::PathString, FilePathIndex>;
using FileCacheCacheEntries = std::vector<FileCacheCacheEntry>;
Marco Bubke's avatar
Marco Bubke committed
90 91

template <typename StringType,
Marco Bubke's avatar
Marco Bubke committed
92 93
          typename IndexType,
          typename Mutex>
Marco Bubke's avatar
Marco Bubke committed
94 95
class StringCache
{
Marco Bubke's avatar
Marco Bubke committed
96 97
    using CacheEnties = StringCacheEntries<StringType, IndexType>;
    using const_iterator = typename CacheEnties::const_iterator;
Marco Bubke's avatar
Marco Bubke committed
98 99 100 101

    class Found
    {
    public:
Marco Bubke's avatar
Marco Bubke committed
102
        typename CacheEnties::const_iterator iterator;
Marco Bubke's avatar
Marco Bubke committed
103 104 105 106 107 108 109 110 111 112
        bool wasFound;
    };

public:
    StringCache()
    {
        m_strings.reserve(1024);
        m_indices.reserve(1024);
    }

Marco Bubke's avatar
Marco Bubke committed
113
    void populate(CacheEnties &&entries)
Marco Bubke's avatar
Marco Bubke committed
114 115 116 117 118 119
    {
        uncheckedPopulate(std::move(entries));

        checkEntries();
    }

Marco Bubke's avatar
Marco Bubke committed
120
    void uncheckedPopulate(CacheEnties &&entries)
Marco Bubke's avatar
Marco Bubke committed
121 122 123 124 125 126 127 128 129 130 131 132
    {
        std::sort(entries.begin(), entries.end());

        m_strings = std::move(entries);
        m_indices.resize(m_strings.size());

        auto begin = m_strings.cbegin();
        for (auto current = begin; current != m_strings.end(); ++current)
            m_indices.at(current->id) = std::distance(begin, current);
    }


Marco Bubke's avatar
Marco Bubke committed
133
    IndexType stringId(Utils::SmallStringView stringView)
Marco Bubke's avatar
Marco Bubke committed
134
    {
Tim Jenssen's avatar
Tim Jenssen committed
135 136
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
137 138 139 140 141 142 143 144
        Found found = find(stringView);

        if (!found.wasFound)
            return insertString(found.iterator, stringView);

        return found.iterator->id;
    }

Marco Bubke's avatar
Marco Bubke committed
145
    template <typename Container>
Marco Bubke's avatar
Marco Bubke committed
146
    std::vector<IndexType> stringIds(const Container &strings)
Marco Bubke's avatar
Marco Bubke committed
147
    {
Tim Jenssen's avatar
Tim Jenssen committed
148 149
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
150
        std::vector<IndexType> ids;
Marco Bubke's avatar
Marco Bubke committed
151 152 153 154 155
        ids.reserve(strings.size());

        std::transform(strings.begin(),
                       strings.end(),
                       std::back_inserter(ids),
Marco Bubke's avatar
Marco Bubke committed
156
                       [&] (const auto &string) { return this->stringId(string); });
Marco Bubke's avatar
Marco Bubke committed
157 158 159 160

        return ids;
    }

Marco Bubke's avatar
Marco Bubke committed
161
    std::vector<IndexType> stringIds(std::initializer_list<StringType> strings)
Marco Bubke's avatar
Marco Bubke committed
162 163 164 165
    {
        return stringIds<std::initializer_list<StringType>>(strings);
    }

Marco Bubke's avatar
Marco Bubke committed
166
    Utils::SmallStringView string(IndexType id) const
Marco Bubke's avatar
Marco Bubke committed
167
    {
Tim Jenssen's avatar
Tim Jenssen committed
168 169
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
170 171 172
        return m_strings.at(m_indices.at(id)).string;
    }

Marco Bubke's avatar
Marco Bubke committed
173
    std::vector<StringType> strings(const std::vector<IndexType> &ids) const
Marco Bubke's avatar
Marco Bubke committed
174
    {
Tim Jenssen's avatar
Tim Jenssen committed
175 176
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
177 178 179 180 181 182
        std::vector<StringType> strings;
        strings.reserve(ids.size());

        std::transform(ids.begin(),
                       ids.end(),
                       std::back_inserter(strings),
Marco Bubke's avatar
Marco Bubke committed
183
                       [&] (IndexType id) { return m_strings.at(m_indices.at(id)).string; });
Marco Bubke's avatar
Marco Bubke committed
184 185 186 187

        return strings;
    }

Marco Bubke's avatar
Marco Bubke committed
188 189 190 191 192
    bool isEmpty() const
    {
        return m_strings.empty() && m_indices.empty();
    }

Marco Bubke's avatar
Marco Bubke committed
193 194 195 196 197 198 199 200
private:
    Found find(Utils::SmallStringView stringView)
    {
        auto range = std::equal_range(m_strings.cbegin(), m_strings.cend(), stringView);

        return {range.first, range.first != range.second};
    }

Marco Bubke's avatar
Marco Bubke committed
201
    void incrementLargerOrEqualIndicesByOne(IndexType newIndex)
Marco Bubke's avatar
Marco Bubke committed
202 203 204 205
    {
        std::transform(m_indices.begin(),
                       m_indices.end(),
                       m_indices.begin(),
Marco Bubke's avatar
Marco Bubke committed
206
                       [&] (IndexType index) {
Marco Bubke's avatar
Marco Bubke committed
207 208 209 210
            return index >= newIndex ? ++index : index;
        });
    }

Marco Bubke's avatar
Marco Bubke committed
211
    IndexType insertString(const_iterator beforeIterator,
Marco Bubke's avatar
Marco Bubke committed
212 213
                      Utils::SmallStringView stringView)
    {
Marco Bubke's avatar
Marco Bubke committed
214
        auto id = IndexType(m_indices.size());
Marco Bubke's avatar
Marco Bubke committed
215 216 217

        auto inserted = m_strings.emplace(beforeIterator, StringType(stringView), id);

Marco Bubke's avatar
Marco Bubke committed
218
        auto newIndex = IndexType(std::distance(m_strings.begin(), inserted));
Marco Bubke's avatar
Marco Bubke committed
219 220 221 222 223 224 225 226

        incrementLargerOrEqualIndicesByOne(newIndex);

        m_indices.push_back(newIndex);

        return id;
    }

Marco Bubke's avatar
Marco Bubke committed
227 228 229 230 231 232 233 234
    void checkEntries()
    {
        for (const auto &entry : m_strings) {
            if (entry.string != string(entry.id) || entry.id != stringId(entry.string))
                throw StringCacheException();
        }
    }

Marco Bubke's avatar
Marco Bubke committed
235
private:
Marco Bubke's avatar
Marco Bubke committed
236 237
    CacheEnties m_strings;
    std::vector<IndexType> m_indices;
Tim Jenssen's avatar
Tim Jenssen committed
238
    mutable Mutex m_mutex;
Marco Bubke's avatar
Marco Bubke committed
239 240
};

Marco Bubke's avatar
Marco Bubke committed
241 242 243
template <typename Mutex>
using FilePathCache = StringCache<Utils::PathString, FilePathIndex, Mutex>;
using FilePathIndices = std::vector<FilePathIndex>;
Marco Bubke's avatar
Marco Bubke committed
244

Marco Bubke's avatar
Marco Bubke committed
245
} // namespace ClangBackEnd