Home | History | Annotate | Download | only in utils 
      1 /*
      2  * Copyright (C) 2010 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "SortedListImpl.h"
     18 
     19 namespace android {
     20 namespace uirenderer {
     21 
     22 ///////////////////////////////////////////////////////////////////////////////
     23 // Sorted list implementation, not for direct use
     24 ///////////////////////////////////////////////////////////////////////////////
     25 
     26 SortedListImpl::SortedListImpl(size_t itemSize, uint32_t flags): VectorImpl(itemSize, flags) {
     27 }
     28 
     29 SortedListImpl::SortedListImpl(const VectorImpl& rhs): VectorImpl(rhs) {
     30 }
     31 
     32 SortedListImpl::~SortedListImpl() {
     33 }
     34 
     35 SortedListImpl& SortedListImpl::operator =(const SortedListImpl& rhs) {
     36     return static_cast<SortedListImpl&>
     37             (VectorImpl::operator =(static_cast<const VectorImpl&> (rhs)));
     38 }
     39 
     40 ssize_t SortedListImpl::indexOf(const void* item) const {
     41     return _indexOrderOf(item);
     42 }
     43 
     44 size_t SortedListImpl::orderOf(const void* item) const {
     45     size_t o;
     46     _indexOrderOf(item, &o);
     47     return o;
     48 }
     49 
     50 ssize_t SortedListImpl::_indexOrderOf(const void* item, size_t* order) const {
     51     // binary search
     52     ssize_t err = NAME_NOT_FOUND;
     53     ssize_t l = 0;
     54     ssize_t h = size() - 1;
     55     ssize_t mid;
     56     const void* a = arrayImpl();
     57     const size_t s = itemSize();
     58     while (l <= h) {
     59         mid = l + (h - l) / 2;
     60         const void* const curr = reinterpret_cast<const char *> (a) + (mid * s);
     61         const int c = do_compare(curr, item);
     62         if (c == 0) {
     63             err = l = mid;
     64             break;
     65         } else if (c < 0) {
     66             l = mid + 1;
     67         } else {
     68             h = mid - 1;
     69         }
     70     }
     71     if (order) {
     72         *order = l;
     73     }
     74     return err;
     75 }
     76 
     77 ssize_t SortedListImpl::add(const void* item) {
     78     size_t order;
     79     ssize_t index = _indexOrderOf(item, &order);
     80     index = VectorImpl::insertAt(item, order, 1);
     81     return index;
     82 }
     83 
     84 ssize_t SortedListImpl::merge(const VectorImpl& vector) {
     85     // naive merge...
     86     if (!vector.isEmpty()) {
     87         const void* buffer = vector.arrayImpl();
     88         const size_t is = itemSize();
     89         size_t s = vector.size();
     90         for (size_t i = 0; i < s; i++) {
     91             ssize_t err = add(reinterpret_cast<const char*> (buffer) + i * is);
     92             if (err < 0) {
     93                 return err;
     94             }
     95         }
     96     }
     97     return NO_ERROR;
     98 }
     99 
    100 ssize_t SortedListImpl::merge(const SortedListImpl& vector) {
    101     // we've merging a sorted vector... nice!
    102     ssize_t err = NO_ERROR;
    103     if (!vector.isEmpty()) {
    104         // first take care of the case where the vectors are sorted together
    105         if (do_compare(vector.itemLocation(vector.size() - 1), arrayImpl()) <= 0) {
    106             err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&> (vector), 0);
    107         } else if (do_compare(vector.arrayImpl(), itemLocation(size() - 1)) >= 0) {
    108             err = VectorImpl::appendVector(static_cast<const VectorImpl&> (vector));
    109         } else {
    110             // this could be made a little better
    111             err = merge(static_cast<const VectorImpl&> (vector));
    112         }
    113     }
    114     return err;
    115 }
    116 
    117 ssize_t SortedListImpl::remove(const void* item) {
    118     ssize_t i = indexOf(item);
    119     if (i >= 0) {
    120         VectorImpl::removeItemsAt(i, 1);
    121     }
    122     return i;
    123 }
    124 
    125 }; // namespace uirenderer
    126 }; // namespace android
    127