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    ALOGD("Tokenizer (%p, size = %zu)\n", this, c);
167    for (size_t i=0 ; i<c ; i++) {
168        ALOGD("%zu: (%u, %u)\n", i, ranges[i].first, ranges[i].length);
169    }
170}
171
172}; // namespace android
173
174