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
SortedListImpl(size_t itemSize,uint32_t flags)26 SortedListImpl::SortedListImpl(size_t itemSize, uint32_t flags): VectorImpl(itemSize, flags) {
27 }
28
SortedListImpl(const VectorImpl & rhs)29 SortedListImpl::SortedListImpl(const VectorImpl& rhs): VectorImpl(rhs) {
30 }
31
~SortedListImpl()32 SortedListImpl::~SortedListImpl() {
33 }
34
operator =(const SortedListImpl & rhs)35 SortedListImpl& SortedListImpl::operator =(const SortedListImpl& rhs) {
36 return static_cast<SortedListImpl&>
37 (VectorImpl::operator =(static_cast<const VectorImpl&> (rhs)));
38 }
39
indexOf(const void * item) const40 ssize_t SortedListImpl::indexOf(const void* item) const {
41 return _indexOrderOf(item);
42 }
43
orderOf(const void * item) const44 size_t SortedListImpl::orderOf(const void* item) const {
45 size_t o;
46 _indexOrderOf(item, &o);
47 return o;
48 }
49
_indexOrderOf(const void * item,size_t * order) const50 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
add(const void * item)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
merge(const VectorImpl & vector)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
merge(const SortedListImpl & vector)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
remove(const void * item)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