1/*
2 * Copyright (C) 2010 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef AtomicStringKeyedMRUCache_h
27#define AtomicStringKeyedMRUCache_h
28
29#include <wtf/text/AtomicString.h>
30
31namespace WebCore {
32
33template<typename T, size_t capacity = 4>
34class AtomicStringKeyedMRUCache {
35public:
36    T get(const AtomicString& key)
37    {
38        if (key.isNull()) {
39            DEPRECATED_DEFINE_STATIC_LOCAL(T, valueForNull, (createValueForNullKey()));
40            return valueForNull;
41        }
42
43        for (size_t i = 0; i < m_cache.size(); ++i) {
44            if (m_cache[i].first == key) {
45                size_t foundIndex = i;
46                if (foundIndex + 1 < m_cache.size()) {
47                    Entry entry = m_cache[foundIndex];
48                    m_cache.remove(foundIndex);
49                    foundIndex = m_cache.size();
50                    m_cache.append(entry);
51                }
52                return m_cache[foundIndex].second;
53            }
54        }
55        if (m_cache.size() == capacity)
56            m_cache.remove(0);
57
58        m_cache.append(std::make_pair(key, createValueForKey(key)));
59        return m_cache.last().second;
60    }
61
62private:
63    T createValueForNullKey();
64    T createValueForKey(const AtomicString&);
65
66    typedef std::pair<AtomicString, T> Entry;
67    typedef Vector<Entry, capacity> Cache;
68    Cache m_cache;
69};
70
71}
72
73#endif // AtomicStringKeyedMRUCache_h
74