1/* libs/opengles/Tokenizer.cpp 2** 3** Copyright 2006, The Android Open Source Project 4** 5** Licensed under the Apache License, Version 2.0 (the "License"); 6** you may not use this file except in compliance with the License. 7** You may obtain a copy of the License at 8** 9** http://www.apache.org/licenses/LICENSE-2.0 10** 11** Unless required by applicable law or agreed to in writing, software 12** distributed under the License is distributed on an "AS IS" BASIS, 13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14** See the License for the specific language governing permissions and 15** limitations under the License. 16*/ 17 18#include <stdio.h> 19 20#include "Tokenizer.h" 21 22// ---------------------------------------------------------------------------- 23 24namespace android { 25 26ANDROID_BASIC_TYPES_TRAITS(Tokenizer::run_t) 27 28Tokenizer::Tokenizer() 29{ 30} 31 32Tokenizer::Tokenizer(const Tokenizer& other) 33 : mRanges(other.mRanges) 34{ 35} 36 37Tokenizer::~Tokenizer() 38{ 39} 40 41uint32_t Tokenizer::acquire() 42{ 43 if (!mRanges.size() || mRanges[0].first) { 44 _insertTokenAt(0,0); 45 return 0; 46 } 47 48 // just extend the first run 49 const run_t& run = mRanges[0]; 50 uint32_t token = run.first + run.length; 51 _insertTokenAt(token, 1); 52 return token; 53} 54 55bool Tokenizer::isAcquired(uint32_t token) const 56{ 57 return (_indexOrderOf(token) >= 0); 58} 59 60status_t Tokenizer::reserve(uint32_t token) 61{ 62 size_t o; 63 const ssize_t i = _indexOrderOf(token, &o); 64 if (i >= 0) { 65 return BAD_VALUE; // this token is already taken 66 } 67 ssize_t err = _insertTokenAt(token, o); 68 return (err<0) ? err : status_t(NO_ERROR); 69} 70 71status_t Tokenizer::release(uint32_t token) 72{ 73 const ssize_t i = _indexOrderOf(token); 74 if (i >= 0) { 75 const run_t& run = mRanges[i]; 76 if ((token >= run.first) && (token < run.first+run.length)) { 77 // token in this range, we need to split 78 run_t& run = mRanges.editItemAt(i); 79 if ((token == run.first) || (token == run.first+run.length-1)) { 80 if (token == run.first) { 81 run.first += 1; 82 } 83 run.length -= 1; 84 if (run.length == 0) { 85 // XXX: should we systematically remove a run that's empty? 86 mRanges.removeItemsAt(i); 87 } 88 } else { 89 // split the run 90 run_t new_run; 91 new_run.first = token+1; 92 new_run.length = run.first+run.length - new_run.first; 93 run.length = token - run.first; 94 mRanges.insertAt(new_run, i+1); 95 } 96 return NO_ERROR; 97 } 98 } 99 return NAME_NOT_FOUND; 100} 101 102ssize_t Tokenizer::_indexOrderOf(uint32_t token, size_t* order) const 103{ 104 // binary search 105 ssize_t err = NAME_NOT_FOUND; 106 ssize_t l = 0; 107 ssize_t h = mRanges.size()-1; 108 ssize_t mid; 109 const run_t* a = mRanges.array(); 110 while (l <= h) { 111 mid = l + (h - l)/2; 112 const run_t* const curr = a + mid; 113 int c = 0; 114 if (token < curr->first) c = 1; 115 else if (token >= curr->first+curr->length) c = -1; 116 if (c == 0) { 117 err = l = mid; 118 break; 119 } else if (c < 0) { 120 l = mid + 1; 121 } else { 122 h = mid - 1; 123 } 124 } 125 if (order) *order = l; 126 return err; 127} 128 129ssize_t Tokenizer::_insertTokenAt(uint32_t token, size_t index) 130{ 131 const size_t c = mRanges.size(); 132 133 if (index >= 1) { 134 // do we need to merge with the previous run? 135 run_t& p = mRanges.editItemAt(index-1); 136 if (p.first+p.length == token) { 137 p.length += 1; 138 if (index < c) { 139 const run_t& n = mRanges[index]; 140 if (token+1 == n.first) { 141 p.length += n.length; 142 mRanges.removeItemsAt(index); 143 } 144 } 145 return index; 146 } 147 } 148 149 if (index < c) { 150 // do we need to merge with the next run? 151 run_t& n = mRanges.editItemAt(index); 152 if (token+1 == n.first) { 153 n.first -= 1; 154 n.length += 1; 155 return index; 156 } 157 } 158 159 return mRanges.insertAt(run_t(token,1), index); 160} 161 162void Tokenizer::dump() const 163{ 164 const run_t* ranges = mRanges.array(); 165 const size_t c = mRanges.size(); 166 LOGD("Tokenizer (%p, size = %u)\n", this, c); 167 for (size_t i=0 ; i<c ; i++) { 168 LOGD("%u: (%u, %u)\n", i, ranges[i].first, ranges[i].length); 169 } 170} 171 172}; // namespace android 173 174