1/*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkTDict_DEFINED
9#define SkTDict_DEFINED
10
11#include "SkChunkAlloc.h"
12#include "SkTSearch.h"
13#include "SkTDArray.h"
14
15template <typename T> class SkTDict : SkNoncopyable {
16public:
17    SkTDict(size_t minStringAlloc) : fStrings(minStringAlloc) {}
18
19    void reset() {
20        fArray.reset();
21        fStrings.reset();
22    }
23
24    int count() const { return fArray.count(); }
25
26    bool set(const char name[], const T& value) {
27        return set(name, strlen(name), value);
28    }
29
30    bool set(const char name[], size_t len, const T& value) {
31        SkASSERT(name);
32
33        int index = this->find_index(name, len);
34
35        if (index >= 0) {
36            fArray[index].fValue = value;
37            return false;
38        } else {
39            Pair*   pair = fArray.insert(~index);
40            char*   copy = (char*)fStrings.alloc(len + 1, SkChunkAlloc::kThrow_AllocFailType);
41            memcpy(copy, name, len);
42            copy[len] = '\0';
43            pair->fName = copy;
44            pair->fValue = value;
45            return true;
46        }
47    }
48
49    bool find(const char name[]) const {
50        return this->find_index(name) >= 0;
51    }
52
53    bool find(const char name[], size_t len) const {
54        return this->find_index(name, len) >= 0;
55    }
56
57    bool find(const char name[], T* value) const {
58        return find(name, strlen(name), value);
59    }
60
61    bool find(const char name[], size_t len, T* value) const {
62        int index = this->find_index(name, len);
63
64        if (index >= 0) {
65            if (value) {
66                *value = fArray[index].fValue;
67            }
68            return true;
69        }
70        return false;
71    }
72
73    bool findKey(T& value, const char** name) const {
74        const Pair* end = fArray.end();
75        for (const Pair* pair = fArray.begin(); pair < end; pair++) {
76            if (pair->fValue != value) {
77                continue;
78            }
79            *name = pair->fName;
80            return true;
81        }
82        return false;
83    }
84
85public:
86    struct Pair {
87        const char* fName;
88        T           fValue;
89
90        friend int operator<(const Pair& a, const Pair& b) {
91            return strcmp(a.fName, b.fName);
92        }
93
94        friend int operator!=(const Pair& a, const Pair& b) {
95            return strcmp(a.fName, b.fName);
96        }
97    };
98    friend class Iter;
99
100public:
101    class Iter {
102    public:
103        Iter(const SkTDict<T>& dict) {
104            fIter = dict.fArray.begin();
105            fStop = dict.fArray.end();
106        }
107
108        const char* next(T* value) {
109            const char* name = NULL;
110            if (fIter < fStop) {
111                name = fIter->fName;
112                if (value) {
113                    *value = fIter->fValue;
114                }
115                fIter += 1;
116            }
117            return name;
118        }
119    private:
120        const Pair*   fIter;
121        const Pair*   fStop;
122    };
123
124private:
125    SkTDArray<Pair> fArray;
126    SkChunkAlloc    fStrings;
127
128    int find_index(const char name[]) const {
129        return find_index(name, strlen(name));
130    }
131
132    int find_index(const char name[], size_t len) const {
133        SkASSERT(name);
134
135        int count = fArray.count();
136        int index = ~0;
137
138        if (count) {
139            index = SkStrSearch(&fArray.begin()->fName, count, name, len, sizeof(Pair));
140        }
141        return index;
142    }
143    friend class Iter;
144};
145
146#endif
147