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