From X512 <danger_mail@xxxxxxx>:
X512 has uploaded this change for review. (
https://review.haiku-os.org/c/haiku/+/2976 ;)
Change subject: BList: speed up deleting item at end of list
......................................................................
BList: speed up deleting item at end of list
Introduce RemoveItemReverse that has O(1) time complexity when deleteting
last item.
Fixes #16336.
Change-Id: Ie941f45f363f6fe94062fc3acb8bd3bb876c1f1e
---
M headers/os/support/List.h
M src/kits/interface/Menu.cpp
M src/kits/support/List.cpp
3 files changed, 38 insertions(+), 2 deletions(-)
git pull ssh://git.haiku-os.org:22/haiku refs/changes/76/2976/1
diff --git a/headers/os/support/List.h b/headers/os/support/List.h
index dd38992..1180bb1 100644
--- a/headers/os/support/List.h
+++ b/headers/os/support/List.h
@@ -26,6 +26,7 @@
bool AddList(const BList*
list);
bool RemoveItem(void* item);
+ bool RemoveItemReverse(void*
item);
void* RemoveItem(int32 index);
bool RemoveItems(int32
index, int32 count);
bool ReplaceItem(int32
index, void* item);
@@ -52,6 +53,8 @@
bool HasItem(const void*
item) const;
int32 IndexOf(void* item)
const;
int32 IndexOf(const void*
item) const;
+ int32 ReverseIndexOf(void*
item) const;
+ int32 ReverseIndexOf(const
void* item) const;
int32 CountItems() const;
bool IsEmpty() const;
diff --git a/src/kits/interface/Menu.cpp b/src/kits/interface/Menu.cpp
index f280436..83aac7a 100644
--- a/src/kits/interface/Menu.cpp
+++ b/src/kits/interface/Menu.cpp
@@ -2339,7 +2339,7 @@
// The plan is simple: If we're given a BMenuItem directly, we use it
// and ignore index and count. Otherwise, we use them instead.
if (item != NULL) {
- if (fItems.RemoveItem(item)) {
+ if (fItems.RemoveItemReverse(item)) {
if (item == fSelected && window != NULL)
_SelectItem(NULL);
item->Uninstall();
@@ -2358,7 +2358,7 @@
for (; i >= index; i--) {
item = static_cast<BMenuItem*>(fItems.ItemAt(i));
if (item != NULL) {
- if (fItems.RemoveItem(item)) {
+ if (fItems.RemoveItemReverse(item)) {
if (item == fSelected && window != NULL)
_SelectItem(NULL);
item->Uninstall();
diff --git a/src/kits/support/List.cpp b/src/kits/support/List.cpp
index a9788d1..2152310 100644
--- a/src/kits/support/List.cpp
+++ b/src/kits/support/List.cpp
@@ -189,6 +189,17 @@
}
+bool
+BList::RemoveItemReverse(void* item)
+{
+ int32 index = ReverseIndexOf(item);
+ bool result = (index >= 0);
+ if (result)
+ RemoveItem(index);
+ return result;
+}
+
+
void*
BList::RemoveItem(int32 index)
{
@@ -389,6 +400,28 @@
int32
+BList::ReverseIndexOf(void* item) const
+{
+ for (int32 i = fItemCount - 1; i >= 0; i--) {
+ if (fObjectList[i] == item)
+ return i;
+ }
+ return -1;
+}
+
+
+int32
+BList::ReverseIndexOf(const void* item) const
+{
+ for (int32 i = fItemCount - 1; i >= 0; i--) {
+ if (fObjectList[i] == item)
+ return i;
+ }
+ return -1;
+}
+
+
+int32
BList::CountItems() const
{
return fItemCount;
--
To view, visit https://review.haiku-os.org/c/haiku/+/2976
To unsubscribe, or for help writing mail filters, visit
https://review.haiku-os.org/settings
Gerrit-Project: haiku
Gerrit-Branch: master
Gerrit-Change-Id: Ie941f45f363f6fe94062fc3acb8bd3bb876c1f1e
Gerrit-Change-Number: 2976
Gerrit-PatchSet: 1
Gerrit-Owner: X512 <danger_mail@xxxxxxx>
Gerrit-MessageType: newchange
