winamp/Src/Wasabi/bfc/ptrlist.h

778 lines
19 KiB
C
Raw Permalink Normal View History

2024-09-24 12:54:57 +00:00
#ifndef _PTRLIST_H
#define _PTRLIST_H
#include <bfc/std_math.h>
//#include <bfc/memblock.h>
#include <bfc/bfc_assert.h>
#include <bfc/platform/platform.h>
//#include <wasabicfg.h>
#ifdef _DEBUG
extern int ptrlist_totalnitems;
#endif
// Disable the "identifier was truncated to '255' characters..." warning.
#pragma warning( disable : 4786 )
/*
a generic pointer list template. only takes up 12 bytes when empty. auto-grows
the array as necessary, NEVER shrinks it unless you removeAll() or equivalent
Use, PtrList<typename>, never PtrListRoot
*/
// yes, this really should be an enum or something
#define PTRLIST_POS_LAST -1
// 4k each, leaving 16 bytes for MALLOC overhead
//#define DEF_PTRLIST_INCREMENT (4096/sizeof(void*)-16)
// in average, 4k doubles the VM working set of a skin, 128bytes (32 elements) seems most optimal
#define DEF_PTRLIST_INCREMENT (128)
class __foreach;
// base class, to share as much code as possible
class NOVTABLE PtrListRoot
{
friend class __foreach;
protected:
PtrListRoot(int initial_size = 0);
PtrListRoot(const PtrListRoot *from);
virtual ~PtrListRoot();
void copyFrom(const PtrListRoot *from);
void appendFrom(const PtrListRoot *from);
void setMinimumSize(int nslots); // expand to at least this many slots
int getNumItems() const;
int size() const { return nitems; }
bool empty() { return nitems == 0; }
void *enumItem(int n) const;
void moveItem(int from, int to);
int removeItem(void *item);
void removeEveryItem(void *item);
void removeByPos(int pos);
void removeLastItem();
void removeAll();
void freeAll();
void purge();
// gross-ass linear search to find index of item
// note that PtrListSorted provides a binary search version
int searchItem(void *item) const;
#if 0//fuct
// speedy binary search. although it'll be fuct if it's not sorted right
int bsearchItem(void *item) const;
#endif
void *addItem(void *item, int pos, int inc);
void *setItem(void *item, int pos); // replace what's in the slot with the new value
void reverse();
void **getItemList() const { return items; } // try to avoid! this is inline to make q() fast
private:
#undef verify // for Mac
void verify();
int nitems, nslots;
void **items;
};
// now we add the methods that refer specifically to the pointer type
template <class T>
class PtrList : public PtrListRoot
{
friend class __foreach;
public:
PtrList(int initial_size = 0) {}
PtrList(const PtrList<T> &r) { copyFrom(&r); }
PtrList(const PtrList<T> *r) { copyFrom(r); }
~PtrList() {}
// copy another PtrList
// deletes previous contents
void copyFrom(const PtrList<T> *from) { PtrListRoot::copyFrom(from); }
// append contents of another PtrList to the end of this one
// preserves previous contents
void appendFrom(const PtrList<T> *from) { PtrListRoot::appendFrom(from); }
// adding
// expand freelist to at least this many slots, even if 0 items in list
void setMinimumSize(int nslots) { PtrListRoot::setMinimumSize(nslots); }
// provide a public addItem for the pointer type
T *addItem(const T *item, int pos = PTRLIST_POS_LAST, int inc = DEF_PTRLIST_INCREMENT)
{
return static_cast<T *>(PtrListRoot::addItem(const_cast<T*>(item), pos, inc));
}
void push_back(const T* item) { return addItem(item); }
// replace what's in the slot with the new value
T *setItem(const T *item, int pos) { return static_cast<T *>(PtrListRoot::setItem(const_cast<T*>(item), pos)); }
// reverse the order of the list in place
void reverse() { PtrListRoot::reverse(); }
// enumerating
// returns # of items in list
int getNumItems() const { return PtrListRoot::getNumItems(); }
// basic list enumerator. returns NULL for out of bounds
T *enumItem(int n) const { return static_cast<T *>(PtrListRoot::enumItem(n)); }
T *operator[](int n) const { return enumItem(n); }
// this will safely return NULL if 0 items due to enumItems's boundscheck
T *getFirst() const { return enumItem(0); }
T *getLast() const { return enumItem(getNumItems() - 1); }
// this is a NON-BOUNDS-CHECKING lookup
T *q(int n) { return static_cast<T*>(getItemList()[n]); }
// gross-ass linear search to find index of item
// note that PtrListSorted provides a binary search version
int searchItem(T *item) const { return PtrListRoot::searchItem(item); }
int haveItem(T *item) const { return searchItem(item) >= 0; }
// deleteing
// removes first instance of a pointer in list, returns how many are left
int removeItem(T *item) { return PtrListRoot::removeItem(item); }
//DEPRECATED
int delItem(T *item) { return removeItem(item); }
// removes all instances of this pointer
void removeEveryItem(const T *item) { PtrListRoot::removeEveryItem(const_cast<T*>(item)); }
// removes pointer at specified position regardless of value
void removeByPos(int pos) { PtrListRoot::removeByPos(pos); }
// DEPRECATED
void delByPos(int pos) { removeByPos(pos); }
// removes last item
void removeLastItem() { PtrListRoot::removeLastItem(); }
// removes all entries, also deletes memory space
void removeAll() { PtrListRoot::removeAll(); }
// removes all entries, calling FREE on the pointers
void freeAll() { PtrListRoot::freeAll(); }
// removes all entries, calling delete on the pointers
void deleteAll()
{
int i, nitems = getNumItems();
for (i = 0; i < nitems; i++)
delete enumItem(i);
removeAll();
}
// removes all entries, calling delete on the pointers
// FG>this version removes each entry as it deletes it so if
// one of the object uses this list in its destructor, it will
// still work. It is MUCH slower than deleteAll tho.
void deleteAllSafe()
{
//CUT ASSERT(!(nitems != 0 && items == NULL));
while (getNumItems())
{
T *i = enumItem(0);
delete i;
removeItem(i);
}
}
void deleteItem(int item)
{
if (item < getNumItems())
{
deleteItem(enumItem(item));
}
}
void deleteItem(T *item)
{
delete item;
removeItem(item);
}
void moveItem(int from, int to) { PtrListRoot::moveItem(from, to); }
static T *castFor(void *ptr) { return static_cast<T*>(ptr); }
using PtrListRoot::purge;
protected:
T **getItemList()
{
return reinterpret_cast<T **>(PtrListRoot::getItemList());
}
};
class NotSorted
{
public:
// comparator for searching -- override
static int compareAttrib(const wchar_t *attrib, void *item) { return 0; }
// comparator for sorting -- override , -1 p1 < p2, 0 eq, 1 p1 > p2
static int compareItem(void *p1, void* p2) { return CMP3(p1, p2); }
};
//template <class T, class C> class NoSort {
// static void _sort(T **, int) {}
//};
// a base class to sort the pointers
// you must implement the comparisons (C) and the sort algorithm (S)
template < class T, class C, class S >
class PtrListSorted : public PtrList<T>
{
public:
PtrListSorted(int initial_size = 0) : PtrList<T>(initial_size)
{
need_sorting = 0;
auto_sort = true;
dups_low = dups_hi = dups_pos = 0;
}
void copyFrom(const PtrList<T> *from)
{
PtrList<T>::copyFrom(from);
need_sorting = 1;
if (auto_sort) sort();
}
T *addItem(T *item, int pos = PTRLIST_POS_LAST, int inc = DEF_PTRLIST_INCREMENT)
{
#if 1
// check for appending in sorted order
if (pos == PTRLIST_POS_LAST && !need_sorting && auto_sort)
{
int n = PtrList<T>::getNumItems();
if (n > 0 && C::compareItem(item, q(n - 1)) < 0) need_sorting = 1;
}
else
#endif
need_sorting = 1;
return PtrList<T>::addItem(item, pos, inc);
}
void sort(bool force_sort = false)
{
if (need_sorting || force_sort)
S::_sort(PtrList<T>::getItemList(), PtrList<T>::getNumItems());
need_sorting = 0;
}
T *enumItem(int n)
{ // NOT const since we might call sort()
if (auto_sort) sort();
return PtrList<T>::enumItem(n);
}
T *operator[](int n) { return PtrListSorted<T, C, S>::enumItem(n); }
T *q(int n)
{
if (auto_sort) sort();
return static_cast<T*>(PtrList<T>::getItemList()[n]);
}
T *findItem(const wchar_t *attrib, int *pos = NULL)
{
ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
sort();
#if 1 // do binary search
if (PtrList<T>::getNumItems() == 0) return NULL;
int bot = 0, top = PtrList<T>::getNumItems() - 1, mid;
for (int c = 0; c < PtrList<T>::getNumItems() + 1; c++)
{
if (bot > top) return NULL;
mid = (bot + top) / 2;
int r = C::compareAttrib(attrib, PtrList<T>::getItemList()[mid]);
if (r == 0)
{
if (pos != NULL) *pos = mid;
return PtrList<T>::getItemList()[mid];
}
if (r < 0)
{
top = mid - 1;
}
else
{
bot = mid + 1;
}
}
ASSERTPR(0, "binary search fucked up");
#else
// re-enable this in case of fuckup
for (int i = 0; i < nitems; i++)
{
if (C::compareAttrib(attrib, static_cast<T *>(items[i])) == 0)
return static_cast<T *>items[i];
}
#endif
return NULL;
}
T *findItem(T *attrib, int *pos = NULL)
{
return findItem((const wchar_t *)attrib, pos);
}
int beginEnumDups(const char *attrib)
{
int pos;
findItem(attrib, &pos);
if (pos < 0)
return -1;
dups_hi = pos;
dups_low = pos;
int i;
for (i = pos - 1;i >= 0;i--)
{
if (C::compareAttrib(attrib, static_cast<T *>(enumItem(i))) == 0)
break;
dups_low = i;
}
for (i = pos + 1;i < PtrList<T>::getNumItems();i++)
{
if (C::compareAttrib(attrib, static_cast<T *>(enumItem(i))) == 0)
break;
dups_hi = i;
}
dups_pos = dups_low;
return dups_pos;
}
int getNextDup()
{ // returns -1 when done
if (dups_pos >= dups_hi)
return -1;
return ++dups_pos;
}
#if 0
// replace search with binary search
int searchItem(T *item) const
{
ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
sort();
return bsearchItem(item);
}
#endif
void setAutoSort(bool as) { auto_sort = as; }
bool getAutoSort() const { return auto_sort; }
void removeDups()
{
ASSERTPR(!(!auto_sort && need_sorting), "must call sort() first if auto-sorting is disabled");
sort();
for (int i = 1; i < PtrList<T>::getNumItems(); i++)
{
if (C::compareItem(enumItem(i - 1), enumItem(i)) == 0)
{
PtrList<T>::delByPos(i);
i--;
}
}
}
private:
int need_sorting;
bool auto_sort;
int dups_low, dups_hi, dups_pos;
};
// quicksort -- you still need to override the compare fns
template <class T, class C>
class QuickSorted
{
public:
static void _sort(T **items, int nitems)
{
if (items == NULL || nitems <= 1)
return ;
Qsort(items, 0, nitems - 1);
}
private:
static void swapItem(T **items, int a, int b)
{ // no bounds checking!
T *tmp = items[a];
items[a] = items[b];
items[b] = tmp;
}
static void Qsort(T **items, int lo0, int hi0)
{
int lo = lo0, hi = hi0;
if (hi0 > lo0)
{
T *mid = items[(lo0 + hi0) / 2];
while (lo <= hi)
{
while ((lo < hi0) && (C::compareItem(items[lo], mid) < 0))
lo++;
while ((hi > lo0) && (C::compareItem(items[hi], mid) > 0))
hi--;
if (lo <= hi)
{
swapItem(items, lo, hi);
lo++;
hi--;
}
}
if (lo0 < hi)
Qsort(items, lo0, hi);
if (lo < hi0)
Qsort(items, lo, hi0);
}
}
};
// easy way to specify quicksorting, just data type and comparison class
template <class T, class C> class PtrListQuickSorted : public PtrListSorted<T, C, QuickSorted<T, C> >
{
public:
PtrListQuickSorted(int initial_size = 0) : PtrListSorted<T, C, QuickSorted<T, C> >(initial_size) {}
};
// easy way to get a list sorted by pointer val
class SortByPtrVal
{
public:
static int compareItem(void *p1, void *p2) { return CMP3(p1, p2); }
static int compareAttrib(const wchar_t *attrib, void *item) { return CMP3((void *)attrib, item); }
};
template <class T> class PtrListQuickSortedByPtrVal : public PtrListQuickSorted<T, SortByPtrVal > {};
// this class automatically inserts at the correct position, so
// the binary searches are very fast if you need to insert and search often (no need to sort)
template < class T, class C >
class PtrListInsertSorted : public PtrList<T>
{
public:
PtrListInsertSorted() : last_insert_pos(0) { disable_sort = 0; }
T *addItem(T *item)
{
int numItems = PtrList<T>::getNumItems();
if (numItems == 0)
{
last_insert_pos = 0;
return PtrList<T>::addItem(item);
}
int insertpoint = -1;
if (!disable_sort)
{
int bot = 0, top = numItems - 1, mid;
// benski>
// optimization based on profiler info. Too many string compares!
// Most of the use of this comes from GuiObjectWnd's constructor (and derived classes)
// so I've changed GuiObjectWnd to add things in alphabetical order.
// Before we start the binary search, we'll check the new item against the LAST item inserted
// Most of the time, we'll finish the insert in O(1)
// Even if we fail, we mitigate the loss somewhat by limiting the binary search
if (last_insert_pos >= numItems) // the list may have shrunk since last time
last_insert_pos = numItems - 1;
int quickTest = C::compareItem(item, PtrList<T>::getItemList()[last_insert_pos]);
if (quickTest == 0) // right on the money.. we'll go ahead and insert ourselves next
return PtrList<T>::addItem(item, last_insert_pos);
if (quickTest > 0) // ok we go after the last inserted item (good), but we need to make sure we go before the next one
{
last_insert_pos++;
if (last_insert_pos == numItems) // we're at the end? cool...
return PtrList<T>::addItem(item, PTRLIST_POS_LAST);
quickTest = C::compareItem(item, PtrList<T>::getItemList()[last_insert_pos]); // test against the next item
if (quickTest <= 0) // and we're not bigger than the next one... perfect!
return PtrList<T>::addItem(item, last_insert_pos);
else // too bad
bot = last_insert_pos; // help out the binary search ... We're at least bigger than everything before last_insert_pos
}
else // ok our optimization failed, but we can still help out the binary search
top = last_insert_pos - 1; // we're at least smaller than everything before last_insert_pos
// end optimization code
for (int c = 0; c < numItems + 1; c++)
{
if (bot > top)
{
// insert here
insertpoint = bot;
break;
}
mid = (bot + top) / 2;
int r = C::compareItem(item, PtrList<T>::getItemList()[mid]);
if (r == 0)
{
// insert here
insertpoint = mid;
break;
}
if (r < 0)
{
top = mid - 1;
}
else
{
bot = mid + 1;
}
}
last_insert_pos = insertpoint;
ASSERTPR(insertpoint != -1, "insertsort/binary search fucked up");
}
else // no sorting
{
last_insert_pos = numItems;
insertpoint = PTRLIST_POS_LAST;
}
return PtrList<T>::addItem(item, insertpoint);
}
T *getInsertionPoint(T *item, int *pos)
{
if (PtrList<T>::getNumItems() == 0)
{
if (pos)
*pos = 0;
return NULL;
}
int bot = 0, top = PtrList<T>::getNumItems() - 1, mid;
int insertpoint = -1;
if (!disable_sort )
{
for (int c = 0; c < PtrList<T>::getNumItems() + 1; c++)
{
if (bot > top)
{
// insert here
insertpoint = bot;
break;
}
mid = (bot + top) / 2;
int r = C::compareItem(item, PtrList<T>::getItemList()[mid]);
if (r == 0)
{
// insert here
insertpoint = mid;
break;
}
if (r < 0)
{
top = mid - 1;
}
else
{
bot = mid + 1;
}
}
ASSERTPR(insertpoint != -1, "insertsort/binary search fucked up");
}
else
insertpoint = PTRLIST_POS_LAST;
if (pos)
*pos = insertpoint;
return PtrList<T>::enumItem(insertpoint);
}
T *findItem(const wchar_t *attrib, int *pos = NULL)
{
if (isSorted())
{
// binary search
if (PtrList<T>::getNumItems() == 0)
return NULL;
int bot = 0, top = PtrList<T>::getNumItems() - 1, mid;
for (int c = 0; c < PtrList<T>::getNumItems() + 1; c++)
{
if (bot > top)
return NULL;
mid = (bot + top) / 2;
int r = C::compareAttrib(attrib, PtrList<T>::getItemList()[mid]);
if (r == 0)
{
if (pos != NULL)
*pos = mid;
return PtrList<T>::getItemList()[mid];
}
if (r < 0)
{
top = mid - 1;
}
else
{
bot = mid + 1;
}
}
ASSERTPR(0, "binary search fucked up");
}
else
{
// linear search
for (int i = 0; i < PtrList<T>::getNumItems(); i++)
{
int r = C::compareAttrib(attrib, PtrList<T>::getItemList()[i]);
if (r == 0)
{
if (pos != NULL)
*pos = i;
return PtrList<T>::getItemList()[i];
}
}
}
return NULL;
}
T *findItem(T *attrib, int *pos = NULL) { return findItem((const wchar_t *)attrib, pos); }
void setSorted(int dosort) { disable_sort = !dosort; }
int isSorted() { return !disable_sort; }
int disable_sort;
int last_insert_pos;
};
// this list allows you to have multiple items with same attrib and adds findLastItem so you can
// sort on more than just one item. this can be used to make autosorting lists of overriding items
// which you can add and remove at will.
template <class T, class C> class PtrListQuickMultiSorted : public PtrListQuickSorted<T, C>
{
public:
PtrListQuickMultiSorted(int initial_size = 0) : PtrListQuickSorted<T, C>(initial_size) {}
T *findLastItem(const wchar_t *attrib, int *pos = NULL)
{
PtrListQuickSorted<T, C>::sort();
int p = 0;
int fp = 0;
T *item = PtrListQuickSorted<T, C>::findItem(attrib, &fp);
if (!item)
return NULL;
p = fp;
for(;;)
{
p++;
if (p >= PtrListQuickSorted<T, C>::getNumItems())
break;
T* i = PtrListQuickSorted<T, C>::enumItem(p);
if (!C::compareAttrib(attrib, i))
{
fp = p;
item = i;
}
else
break;
}
if (pos != NULL)
*pos = fp;
return item;
}
};
//same thing but Insert sorted. use this one if you insert and search items often (no need to sort on findItem)
template <class T, class C> class PtrListInsertMultiSorted : public PtrListInsertSorted<T, C>
{
public:
PtrListInsertMultiSorted() : PtrListInsertSorted<T, C>() {}
T *findLastItem(const wchar_t *attrib, int *pos = NULL)
{
//sort();
int p = 0;
int fp = 0;
T *item = PtrListInsertSorted<T, C>::findItem(attrib, &fp);
if (!item)
return NULL;
p = fp;
for (;;)
{
p++;
if (p >= PtrListInsertSorted<T, C>::getNumItems())
break;
T* i = PtrListInsertSorted<T, C>::enumItem(p);
if (!C::compareAttrib(attrib, i))
{
fp = p;
item = i;
}
else
break;
}
if (pos != NULL)
*pos = fp;
return item;
}
};
#include <bfc/foreach.h>
#endif