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