18550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy/* 28550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * Copyright (C) 2010 The Android Open Source Project 38550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * 48550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * Licensed under the Apache License, Version 2.0 (the "License"); 58550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * you may not use this file except in compliance with the License. 68550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * You may obtain a copy of the License at 78550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * 88550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * http://www.apache.org/licenses/LICENSE-2.0 98550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * 108550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * Unless required by applicable law or agreed to in writing, software 118550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * distributed under the License is distributed on an "AS IS" BASIS, 128550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * See the License for the specific language governing permissions and 148550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * limitations under the License. 158550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy */ 168550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 178550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy#include "SortedListImpl.h" 188550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 198550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guynamespace android { 208550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guynamespace uirenderer { 218550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 228550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy/////////////////////////////////////////////////////////////////////////////// 238550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy// Sorted list implementation, not for direct use 248550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy/////////////////////////////////////////////////////////////////////////////// 258550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 268550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain GuySortedListImpl::SortedListImpl(size_t itemSize, uint32_t flags): VectorImpl(itemSize, flags) { 278550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 288550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 298550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain GuySortedListImpl::SortedListImpl(const VectorImpl& rhs): VectorImpl(rhs) { 308550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 318550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 328550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain GuySortedListImpl::~SortedListImpl() { 338550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 348550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 358550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain GuySortedListImpl& SortedListImpl::operator =(const SortedListImpl& rhs) { 368550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return static_cast<SortedListImpl&> 378550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy (VectorImpl::operator =(static_cast<const VectorImpl&> (rhs))); 388550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 398550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 408550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::indexOf(const void* item) const { 418550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return _indexOrderOf(item); 428550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 438550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 448550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guysize_t SortedListImpl::orderOf(const void* item) const { 458550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy size_t o; 468550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy _indexOrderOf(item, &o); 478550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return o; 488550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 498550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 508550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::_indexOrderOf(const void* item, size_t* order) const { 518550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy // binary search 528550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t err = NAME_NOT_FOUND; 538550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t l = 0; 548550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t h = size() - 1; 558550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t mid; 568550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const void* a = arrayImpl(); 578550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const size_t s = itemSize(); 588550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy while (l <= h) { 598550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy mid = l + (h - l) / 2; 608550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const void* const curr = reinterpret_cast<const char *> (a) + (mid * s); 618550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const int c = do_compare(curr, item); 628550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (c == 0) { 638550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy err = l = mid; 648550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy break; 658550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } else if (c < 0) { 668550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy l = mid + 1; 678550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } else { 688550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy h = mid - 1; 698550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 708550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 718550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (order) { 728550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy *order = l; 738550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 748550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return err; 758550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 768550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 778550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::add(const void* item) { 788550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy size_t order; 798550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t index = _indexOrderOf(item, &order); 808550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy index = VectorImpl::insertAt(item, order, 1); 818550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return index; 828550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 838550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 848550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::merge(const VectorImpl& vector) { 858550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy // naive merge... 868550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (!vector.isEmpty()) { 878550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const void* buffer = vector.arrayImpl(); 888550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy const size_t is = itemSize(); 898550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy size_t s = vector.size(); 908550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy for (size_t i = 0; i < s; i++) { 918550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t err = add(reinterpret_cast<const char*> (buffer) + i * is); 928550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (err < 0) { 938550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return err; 948550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 958550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 968550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 978550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return NO_ERROR; 988550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 998550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 1008550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::merge(const SortedListImpl& vector) { 1018550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy // we've merging a sorted vector... nice! 1028550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t err = NO_ERROR; 1038550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (!vector.isEmpty()) { 1048550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy // first take care of the case where the vectors are sorted together 1058550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (do_compare(vector.itemLocation(vector.size() - 1), arrayImpl()) <= 0) { 1068550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&> (vector), 0); 1078550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } else if (do_compare(vector.arrayImpl(), itemLocation(size() - 1)) >= 0) { 1088550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy err = VectorImpl::appendVector(static_cast<const VectorImpl&> (vector)); 1098550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } else { 1108550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy // this could be made a little better 1118550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy err = merge(static_cast<const VectorImpl&> (vector)); 1128550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 1138550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 1148550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return err; 1158550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 1168550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 1178550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guyssize_t SortedListImpl::remove(const void* item) { 1188550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy ssize_t i = indexOf(item); 1198550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy if (i >= 0) { 1208550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy VectorImpl::removeItemsAt(i, 1); 1218550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy } 1228550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy return i; 1238550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy} 1248550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy 1258550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy}; // namespace uirenderer 1268550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy}; // namespace android 127