19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include <stdio.h> 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "Tokenizer.h" 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// ---------------------------------------------------------------------------- 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectnamespace android { 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectANDROID_BASIC_TYPES_TRAITS(Tokenizer::run_t) 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectTokenizer::Tokenizer() 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectTokenizer::Tokenizer(const Tokenizer& other) 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project : mRanges(other.mRanges) 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectTokenizer::~Tokenizer() 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectuint32_t Tokenizer::acquire() 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!mRanges.size() || mRanges[0].first) { 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project _insertTokenAt(0,0); 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return 0; 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // just extend the first run 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t& run = mRanges[0]; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project uint32_t token = run.first + run.length; 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project _insertTokenAt(token, 1); 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return token; 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectbool Tokenizer::isAcquired(uint32_t token) const 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (_indexOrderOf(token) >= 0); 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectstatus_t Tokenizer::reserve(uint32_t token) 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project size_t o; 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const ssize_t i = _indexOrderOf(token, &o); 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return BAD_VALUE; // this token is already taken 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ssize_t err = _insertTokenAt(token, o); 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (err<0) ? err : status_t(NO_ERROR); 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectstatus_t Tokenizer::release(uint32_t token) 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const ssize_t i = _indexOrderOf(token); 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t& run = mRanges[i]; 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((token >= run.first) && (token < run.first+run.length)) { 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // token in this range, we need to split 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run_t& run = mRanges.editItemAt(i); 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((token == run.first) || (token == run.first+run.length-1)) { 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (token == run.first) { 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run.first += 1; 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run.length -= 1; 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (run.length == 0) { 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // XXX: should we systematically remove a run that's empty? 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mRanges.removeItemsAt(i); 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // split the run 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run_t new_run; 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project new_run.first = token+1; 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project new_run.length = run.first+run.length - new_run.first; 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run.length = token - run.first; 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mRanges.insertAt(new_run, i+1); 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return NO_ERROR; 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return NAME_NOT_FOUND; 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectssize_t Tokenizer::_indexOrderOf(uint32_t token, size_t* order) const 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // binary search 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ssize_t err = NAME_NOT_FOUND; 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ssize_t l = 0; 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ssize_t h = mRanges.size()-1; 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ssize_t mid; 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t* a = mRanges.array(); 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (l <= h) { 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mid = l + (h - l)/2; 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t* const curr = a + mid; 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int c = 0; 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (token < curr->first) c = 1; 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else if (token >= curr->first+curr->length) c = -1; 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (c == 0) { 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project err = l = mid; 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project break; 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else if (c < 0) { 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project l = mid + 1; 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project h = mid - 1; 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (order) *order = l; 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return err; 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectssize_t Tokenizer::_insertTokenAt(uint32_t token, size_t index) 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const size_t c = mRanges.size(); 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (index >= 1) { 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // do we need to merge with the previous run? 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run_t& p = mRanges.editItemAt(index-1); 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (p.first+p.length == token) { 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p.length += 1; 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (index < c) { 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t& n = mRanges[index]; 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (token+1 == n.first) { 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p.length += n.length; 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mRanges.removeItemsAt(index); 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return index; 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (index < c) { 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // do we need to merge with the next run? 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project run_t& n = mRanges.editItemAt(index); 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (token+1 == n.first) { 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project n.first -= 1; 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project n.length += 1; 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return index; 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mRanges.insertAt(run_t(token,1), index); 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid Tokenizer::dump() const 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const run_t* ranges = mRanges.array(); 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project const size_t c = mRanges.size(); 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project printf("Tokenizer (%p, size = %lu)\n", this, c); 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (size_t i=0 ; i<c ; i++) { 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project printf("%lu: (%u, %u)\n", i, ranges[i].first, ranges[i].length); 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project}; // namespace android 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 173