stringcache.h 6.4 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 28
/****************************************************************************
**
** 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

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

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

namespace ClangBackEnd {

Marco Bubke's avatar
Marco Bubke committed
37 38 39 40 41 42 43 44
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
45 46 47 48 49 50 51 52 53 54
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
55 56
template <typename StringType>
class StringCacheEntry
Marco Bubke's avatar
Marco Bubke committed
57
{
Marco Bubke's avatar
Marco Bubke committed
58 59 60 61 62 63 64
public:
    StringCacheEntry(StringType &&string, uint id)
        : string(std::move(string)),
          id(id)
    {}

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

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

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

    StringType string;
    uint id;
};
Marco Bubke's avatar
Marco Bubke committed
82

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

template <typename StringType,
          typename Mutex = NonLockingMutex>
class StringCache
{
    using const_iterator = typename StringCacheEntries<StringType>::const_iterator;
Marco Bubke's avatar
Marco Bubke committed
91 92 93 94

    class Found
    {
    public:
Marco Bubke's avatar
Marco Bubke committed
95
        typename StringCacheEntries<StringType>::const_iterator iterator;
Marco Bubke's avatar
Marco Bubke committed
96 97 98 99 100 101 102 103 104 105
        bool wasFound;
    };

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

Marco Bubke's avatar
Marco Bubke committed
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
    void populate(StringCacheEntries<StringType> &&entries)
    {
        uncheckedPopulate(std::move(entries));

        checkEntries();
    }

    void uncheckedPopulate(StringCacheEntries<StringType> &&entries)
    {
        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
126 127
    uint stringId(Utils::SmallStringView stringView)
    {
Tim Jenssen's avatar
Tim Jenssen committed
128 129
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
130 131 132 133 134 135 136 137
        Found found = find(stringView);

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

        return found.iterator->id;
    }

Marco Bubke's avatar
Marco Bubke committed
138 139
    template <typename Container>
    std::vector<uint> stringIds(const Container &strings)
Marco Bubke's avatar
Marco Bubke committed
140
    {
Tim Jenssen's avatar
Tim Jenssen committed
141 142
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
143 144 145 146 147 148
        std::vector<uint> ids;
        ids.reserve(strings.size());

        std::transform(strings.begin(),
                       strings.end(),
                       std::back_inserter(ids),
Marco Bubke's avatar
Marco Bubke committed
149
                       [&] (const auto &string) { return this->stringId(string); });
Marco Bubke's avatar
Marco Bubke committed
150 151 152 153

        return ids;
    }

Marco Bubke's avatar
Marco Bubke committed
154 155 156 157 158 159
    std::vector<uint> stringIds(std::initializer_list<StringType> strings)
    {
        return stringIds<std::initializer_list<StringType>>(strings);
    }

    Utils::SmallStringView string(uint id) const
Marco Bubke's avatar
Marco Bubke committed
160
    {
Tim Jenssen's avatar
Tim Jenssen committed
161 162
        std::lock_guard<Mutex> lock(m_mutex);

Marco Bubke's avatar
Marco Bubke committed
163 164 165 166 167
        return m_strings.at(m_indices.at(id)).string;
    }

    std::vector<StringType> strings(const std::vector<uint> &ids) const
    {
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 173 174 175 176 177 178 179 180
        std::vector<StringType> strings;
        strings.reserve(ids.size());

        std::transform(ids.begin(),
                       ids.end(),
                       std::back_inserter(strings),
                       [&] (uint id) { return m_strings.at(m_indices.at(id)).string; });

        return strings;
    }

Marco Bubke's avatar
Marco Bubke committed
181 182 183 184 185
    bool isEmpty() const
    {
        return m_strings.empty() && m_indices.empty();
    }

Marco Bubke's avatar
Marco Bubke committed
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
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};
    }

    void incrementLargerOrEqualIndicesByOne(uint newIndex)
    {
        std::transform(m_indices.begin(),
                       m_indices.end(),
                       m_indices.begin(),
                       [&] (uint index) {
            return index >= newIndex ? ++index : index;
        });
    }

    uint insertString(const_iterator beforeIterator,
                      Utils::SmallStringView stringView)
    {
Marco Bubke's avatar
Marco Bubke committed
207
        auto id = uint(m_indices.size());
Marco Bubke's avatar
Marco Bubke committed
208 209 210 211 212 213 214 215 216 217 218 219

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

        auto newIndex = uint(std::distance(m_strings.begin(), inserted));

        incrementLargerOrEqualIndicesByOne(newIndex);

        m_indices.push_back(newIndex);

        return id;
    }

Marco Bubke's avatar
Marco Bubke committed
220 221 222 223 224 225 226 227
    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
228
private:
Marco Bubke's avatar
Marco Bubke committed
229
    StringCacheEntries<StringType> m_strings;
Marco Bubke's avatar
Marco Bubke committed
230
    std::vector<uint> m_indices;
Tim Jenssen's avatar
Tim Jenssen committed
231
    mutable Mutex m_mutex;
Marco Bubke's avatar
Marco Bubke committed
232 233
};

Marco Bubke's avatar
Marco Bubke committed
234 235 236
template <typename Mutex = NonLockingMutex>
using FilePathCache = StringCache<Utils::PathString, Mutex>;

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