class Tokenizer
{
public:
Tokenizer();
Tokenizer(const Tokenizer& other);
~Tokenizer();
uint32_t acquire();
status_t reserve(uint32_t token);
status_t release(uint32_t token);
bool isAcquired(uint32_t token) const;
void dump() const;
struct run_t {
run_t() {};
run_t(uint32_t f, uint32_t l) : first(f), length(l) {}
uint32_t first;
uint32_t length;
};
private:
ssize_t _indexOrderOf(uint32_t token, size_t* order=0) const;
ssize_t _insertTokenAt(uint32_t token, size_t index);
Vector<run_t> mRanges;
};
}; // namespace android
Tokenizer::Tokenizer()
{
}
Tokenizer::Tokenizer(const Tokenizer& other)
: mRanges(other.mRanges)
{
}
Tokenizer::~Tokenizer()
{
}
uint32_t Tokenizer::acquire()
{
if (!mRanges.size() || mRanges[0].first) {
_insertTokenAt(0,0);
return 0;
}
// just extend the first run
const run_t& run = mRanges[0];
uint32_t token = run.first + run.length;
_insertTokenAt(token, 1);
return token;
}
bool Tokenizer::isAcquired(uint32_t token) const
{
return (_indexOrderOf(token) >= 0);
}
status_t Tokenizer::reserve(uint32_t token)
{
size_t o;
const ssize_t i = _indexOrderOf(token, &o);
if (i >= 0) {
return BAD_VALUE; // this token is already taken
}
ssize_t err = _insertTokenAt(token, o);
return (err<0) ? err : status_t(NO_ERROR);
}
status_t Tokenizer::release(uint32_t token)
{
const ssize_t i = _indexOrderOf(token);
if (i >= 0) {
const run_t& run = mRanges[i];
if ((token >= run.first) && (token < run.first+run.length)) {
// token in this range, we need to split
run_t& run = mRanges.editItemAt(i);
if ((token == run.first) || (token == run.first+run.length-1)) {
if (token == run.first) {
run.first += 1;
}
run.length -= 1;
if (run.length == 0) {
// XXX: should we systematically remove a run that's empty?
mRanges.removeItemsAt(i);
}
} else {
// split the run
run_t new_run;
new_run.first = token+1;
new_run.length = run.first+run.length - new_run.first;
run.length = token - run.first;
mRanges.insertAt(new_run, i+1);
}
return NO_ERROR;
}
}
return NAME_NOT_FOUND;
}
ssize_t Tokenizer::_indexOrderOf(uint32_t token, size_t* order) const
{
// binary search
ssize_t err = NAME_NOT_FOUND;
ssize_t l = 0;
ssize_t h = mRanges.size()-1;
ssize_t mid;
const run_t* a = mRanges.array();
while (l <= h) {
mid = l + (h - l)/2;
const run_t* const curr = a + mid;
int c = 0;
if (token < curr->first) c = 1;