PointerSet.cpp revision c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2ef
199e53b86eebb605b70dd7591b89bf61a9414ed0eGlenn Kasten/* 265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Copyright (C) 2008 The Android Open Source Project 365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * 465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Licensed under the Apache License, Version 2.0 (the "License"); 565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * you may not use this file except in compliance with the License. 665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * You may obtain a copy of the License at 765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * 865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * http://www.apache.org/licenses/LICENSE-2.0 965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * 1065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Unless required by applicable law or agreed to in writing, software 1165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * distributed under the License is distributed on an "AS IS" BASIS, 1265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * See the License for the specific language governing permissions and 1465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * limitations under the License. 1565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 1665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 1765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Maintain an expanding set of unique pointer values. 1865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 1965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian#include "Dalvik.h" 2065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 2165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 2265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Sorted, expanding list of pointers. 2365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 2465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopianstruct PointerSet { 254ff14bae91075eb274eb1c2975982358946e7e63John Grossman u2 alloc; 264ff14bae91075eb274eb1c2975982358946e7e63John Grossman u2 count; 2765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian const void** list; 2865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian}; 2965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 3065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 31335787fe43596f38ea2fa50b24c54d0823a3fb1dGlenn Kasten * Verify that the set is in sorted order. 324ff14bae91075eb274eb1c2975982358946e7e63John Grossman */ 3365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian#ifndef NDEBUG 3465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopianstatic bool verifySorted(PointerSet* pSet) 3565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian{ 3665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian const void* last = NULL; 3765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian int i; 38799a70e7028a4d714436c3a744a775acfbd31aaeDima Zavin 3965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian for (i = 0; i < pSet->count; i++) { 4065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian const void* cur = pSet->list[i]; 415462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian if (cur < last) 425462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian return false; 435462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian last = cur; 4464760240f931714858a59c1579f07264d7182ba2Dima Zavin } 457394a4f358fa9908a9f0a7c954b65c399f4268e6Dima Zavin 46a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent return true; 4765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian} 482dd4bdd715f586d4d30cf90cc6fc2bbfbce60fe0Glenn Kasten#endif 492dd4bdd715f586d4d30cf90cc6fc2bbfbce60fe0Glenn Kasten 5058912562617941964939a4182cda71eaeb153d4bGlenn Kasten/* 512dd4bdd715f586d4d30cf90cc6fc2bbfbce60fe0Glenn Kasten * Allocate a new PointerSet. 52c15d6657a17d7cef91f800f40d11760e2e7340afGlenn Kasten * 5365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Returns NULL on failure. 54feb0db689c17dced50afaee54c659f1676e2d505Eric Laurent */ 55feb0db689c17dced50afaee54c659f1676e2d505Eric LaurentPointerSet* dvmPointerSetAlloc(int initialSize) 5665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian{ 5765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian PointerSet* pSet = (PointerSet*)calloc(1, sizeof(PointerSet)); 5865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (pSet != NULL) { 5965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (initialSize > 0) { 6065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->list = (const void**)malloc(sizeof(void*) * initialSize); 6165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (pSet->list == NULL) { 6265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian free(pSet); 6358912562617941964939a4182cda71eaeb153d4bGlenn Kasten return NULL; 6465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 6565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->alloc = initialSize; 6665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 6753d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten } 6853d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten 6953d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten return pSet; 7053d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten} 7153d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten 7253d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten/* 7353d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten * Free up a PointerSet. 7453d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kasten */ 7553d76dbe7c55821e89d9da02e7a563f7fb45de87Glenn Kastenvoid dvmPointerSetFree(PointerSet* pSet) 764ff14bae91075eb274eb1c2975982358946e7e63John Grossman{ 7765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (pSet == NULL) 785462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian return; 795462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian 805462fc9a38fa8c9dff434cd53fa5fb1782ae3042Mathias Agopian if (pSet->list != NULL) { 8165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian free(pSet->list); 821998661fdb6b0b5ae103e047e3d653c5da1b99e3Glenn Kasten pSet->list = NULL; 8365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 8454c3b66444ebfb9f2265ee70ac3b76ccefa0506aGlenn Kasten free(pSet); 8565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian} 8665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 8765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 882f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * Clear the contents of a pointer set. 8965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 9065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopianvoid dvmPointerSetClear(PointerSet* pSet) 91fff6d715a8db0daf08a50634f242c40268de3d49Glenn Kasten{ 9265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->count = 0; 9358f30210ea540b6ce5aa6a46330cd3499483cb97Glenn Kasten} 94dd8104cc5367262f0e5f13df4e79f131e8d560bbGlenn Kasten 9565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 96a075db4ff9b086ac2885df77bb6da0869293df92Glenn Kasten * Get the number of pointers currently stored in the list. 9765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 9872ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kastenint dvmPointerSetGetCount(const PointerSet* pSet) 993acbd053c842e76e1a40fc8a0bf62de87eebf00fGlenn Kasten{ 10065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian return pSet->count; 10165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian} 10265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 1032f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten/* 1042f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * Get the Nth entry from the list. 1052f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten */ 1062f732eb768004c6362fae8a02c60b69c9400b032Glenn Kastenconst void* dvmPointerSetGetEntry(const PointerSet* pSet, int i) 1072f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten{ 108dd8104cc5367262f0e5f13df4e79f131e8d560bbGlenn Kasten return pSet->list[i]; 1092f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten} 110a075db4ff9b086ac2885df77bb6da0869293df92Glenn Kasten 1111879fff068422852c1483dcf8365c2ff0e2fadfcGlenn Kasten/* 1122f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * Insert a new entry into the list. If it already exists, this returns 1132f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * without doing anything. 1142f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * 11572ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten * Returns "true" if the value was added. 11672ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten */ 11772ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kastenbool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr) 11872ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten{ 11972ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten int nearby; 12065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 12165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (dvmPointerSetHas(pSet, ptr, &nearby)) 12265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian return false; 12365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 12465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian /* ensure we have space to add one more */ 12565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (pSet->count == pSet->alloc) { 12665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian /* time to expand */ 12772ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten const void** newList; 12872ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten 129fff6d715a8db0daf08a50634f242c40268de3d49Glenn Kasten if (pSet->alloc == 0) 13065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->alloc = 4; 13172ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten else 13272ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten pSet->alloc *= 2; 133fff6d715a8db0daf08a50634f242c40268de3d49Glenn Kasten LOGVV("expanding %p to %d", pSet, pSet->alloc); 13465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian newList = (const void**)realloc(pSet->list, pSet->alloc * sizeof(void*)); 135f78aee70d15daf4690de7e7b4983ee68b0d1381dGlenn Kasten if (newList == NULL) { 13665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian ALOGE("Failed expanding ptr set (alloc=%d)", pSet->alloc); 13765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian dvmAbort(); 13865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 13965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->list = newList; 14072ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten } 14172ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten 14265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (pSet->count == 0) { 14365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian /* empty list */ 14465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian assert(nearby == 0); 145dd8104cc5367262f0e5f13df4e79f131e8d560bbGlenn Kasten } else { 146dd8104cc5367262f0e5f13df4e79f131e8d560bbGlenn Kasten /* 14765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Determine the insertion index. The binary search might have 148a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent * terminated "above" or "below" the value. 149a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent */ 150a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent if (nearby != 0 && ptr < pSet->list[nearby-1]) { 151a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent //ALOGD("nearby-1=%d %p, inserting %p at -1", 152a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent // nearby-1, pSet->list[nearby-1], ptr); 153a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent nearby--; 1540ca3cf94c0dfc173ad7886ae162c4b67067539f6Eric Laurent } else if (ptr < pSet->list[nearby]) { 15565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian //ALOGD("nearby=%d %p, inserting %p at +0", 15672ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten // nearby, pSet->list[nearby], ptr); 15772ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten } else { 15865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian //ALOGD("nearby+1=%d %p, inserting %p at +1", 15972ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten // nearby+1, pSet->list[nearby+1], ptr); 16065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian nearby++; 16172ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten } 16265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 16372ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten /* 16465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Move existing values, if necessary. 165a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent */ 166a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent if (nearby != pSet->count) { 167a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent /* shift up */ 168a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent memmove(&pSet->list[nearby+1], &pSet->list[nearby], 169a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent (pSet->count - nearby) * sizeof(pSet->list[0])); 17065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 17172ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten } 17265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 17372ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten pSet->list[nearby] = ptr; 17465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->count++; 17565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 17665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian assert(verifySorted(pSet)); 17772ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten return true; 17872ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten} 17965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 1802f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten/* 1812f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten * Returns "true" if the element was successfully removed. 18265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 18365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopianbool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr) 1843a34befc6fb04a4945a849e8bda8b84e4bf973feMarco Nelissen{ 1853a34befc6fb04a4945a849e8bda8b84e4bf973feMarco Nelissen int where; 1863a34befc6fb04a4945a849e8bda8b84e4bf973feMarco Nelissen 1873a34befc6fb04a4945a849e8bda8b84e4bf973feMarco Nelissen if (!dvmPointerSetHas(pSet, ptr, &where)) 188f587ba5b991c7cd91e4df093d0d796bd419e5d67Glenn Kasten return false; 18965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 190f587ba5b991c7cd91e4df093d0d796bd419e5d67Glenn Kasten if (where != pSet->count-1) { 19165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian /* shift down */ 1925e92a7861196ddae14638d4b7a63fc4892b7ef59Glenn Kasten memmove(&pSet->list[where], &pSet->list[where+1], 193f587ba5b991c7cd91e4df093d0d796bd419e5d67Glenn Kasten (pSet->count-1 - where) * sizeof(pSet->list[0])); 19465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian } 19565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 19665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->count--; 19765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 19865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian return true; 19972ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten} 20065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 20165ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 20265ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * Returns the index if "ptr" appears in the list. If it doesn't appear, 20365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian * this returns a negative index for a nearby element. 20465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian */ 20572ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kastenbool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex) 20672ef00de10fa95bfcb948ed88ab9b7a177ed0b48Glenn Kasten{ 20765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian int hi, lo, mid; 208a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent 209a4c5a550e2a3bc237179b8684e51718e05894492Eric Laurent lo = mid = 0; 210cc0f1cfb69ce8b8985fc2c0984847a06a13ad22dGlenn Kasten hi = pSet->count-1; 211cc0f1cfb69ce8b8985fc2c0984847a06a13ad22dGlenn Kasten 212cc0f1cfb69ce8b8985fc2c0984847a06a13ad22dGlenn Kasten /* array is sorted, use a binary search */ 21365ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian while (lo <= hi) { 21465ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian mid = (lo + hi) / 2; 21565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian const void* listVal = pSet->list[mid]; 21665ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian 21765ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian if (ptr > listVal) { 21865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian lo = mid + 1; 2192f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten } else if (ptr < listVal) { 2202f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten hi = mid - 1; 221a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } else /* listVal == ptr */ { 222a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent if (pIndex != NULL) 223a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent *pIndex = mid; 224a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent return true; 225a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } 226a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } 227a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent 228a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent if (pIndex != NULL) 229a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent *pIndex = mid; 230a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent return false; 231a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent} 232a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent 233a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent/* 234a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent * Compute the intersection of the set and the array of pointers passed in. 235a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent * 236a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent * Any pointer in "pSet" that does not appear in "ptrArray" is removed. 237a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent */ 238a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurentvoid dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count) 239106e8a42038f9e90d5ff97f8ab6f1a42258bde9eGlenn Kasten{ 240106e8a42038f9e90d5ff97f8ab6f1a42258bde9eGlenn Kasten int i, j; 241a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent 242a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent for (i = 0; i < pSet->count; i++) { 243a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent for (j = 0; j < count; j++) { 244a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent if (pSet->list[i] == ptrArray[j]) { 245a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent /* match, keep this one */ 246a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent break; 247a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } 248a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } 249a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent 250a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent if (j == count) { 251a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent /* no match, remove entry */ 252106e8a42038f9e90d5ff97f8ab6f1a42258bde9eGlenn Kasten if (i != pSet->count-1) { 253a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent /* shift down */ 254a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent memmove(&pSet->list[i], &pSet->list[i+1], 255a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent (pSet->count-1 - i) * sizeof(pSet->list[0])); 256a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent } 257a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent 258a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent pSet->count--; 259a011e35b22f95f558d81dc9c94b68b1465c4661dEric Laurent pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 260717e128691f083a9469a1d0e363ac6ecd5c65d58Eric Laurent i--; /* adjust loop counter */ 2612f732eb768004c6362fae8a02c60b69c9400b032Glenn Kasten } 262ee578c0330319f04a48bccbdb26b53fea0388d04John Grossman } 263ee578c0330319f04a48bccbdb26b53fea0388d04John Grossman} 264f78aee70d15daf4690de7e7b4983ee68b0d1381dGlenn Kasten 26565ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian/* 266c59c004a3a6042c0990d71179f88eee2ce781e3cGlenn Kasten * Print the list contents to stdout. For debugging. 26759bd0da8373af0e5159b799495fda51e03120ea4Eric Laurent */ 26865ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopianvoid dvmPointerSetDump(const PointerSet* pSet) 26965ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian{ 27065ab47156e1c7dfcd8cc4266253a5ff30219e7f0Mathias Agopian ALOGI("PointerSet %p", pSet); 2712b213bc220768d2b984239511cd4554a96bc0079Glenn Kasten int i; 2722b213bc220768d2b984239511cd4554a96bc0079Glenn Kasten for (i = 0; i < pSet->count; i++) 2732b213bc220768d2b984239511cd4554a96bc0079Glenn Kasten ALOGI(" %2d: %p", i, pSet->list[i]); 274000f0e39b4d0c88441297a05ab5f8da6832c1640Glenn Kasten} 2755a61d2f277af3098fc10b2881babca16391362daDima Zavin