/************************************************************************
* list.cpp *
* basic list class, use with inheritance. *
* - maintains a list class of pointers. *
* - can add/insert items *
* - can use binary search *
* - will resize array upwards in 4k chunks. *
* - downsizing has not been added but will be carried out when a *
* disassembly is saved and reloaded as a database. *
* this class is central to many other classes. *
* *
* Note: there is only one listiter per list. Some functions reset or *
* change listiter, like find, and so any derived classes must be *
* careful not to try and move through a list whilst inadvertently using *
* these functions. (It is also why the secondary program thread must be *
* often stopped during user searches, and dialogs since otherwise the *
* databases would be constantly changing. *
* *
* Rewritten for Version 2.22 this is now a template class, all *
* functions are below and are essentially compiled for each class *
* which uses the list. *
* - still work to be done clearing it up though *
* - delfunc and delfrom basically call delete item and so delfunc *
* should be overridden if this is not wanted *
************************************************************************/
#ifndef list_h
#define list_h
#include "common.h"
template <class listitem> class slist
{ private:
listitem *listptr;
dword listsize,maxsize,listiter;
public:
slist(void);
~slist(void);
virtual int compare(listitem a,listitem b);
virtual void delfunc(listitem d);
listitem addto(listitem);
void delfrom(listitem);
listitem find(listitem);
listitem findnext(listitem);
void resetiterator(void);
listitem nextiterator(void);
listitem lastiterator(void);
listitem processqueue(void);
listitem peekfirst(void);
dword numlistitems(void);
};
/************************************************************************
* constructor function *
* - resets list, with small size list and no items. *
* - sets compare function and deletion function to NULL. *
************************************************************************/
template <class listitem> slist<listitem>::slist(void) {
// listptr=new listitem[1024];
listptr=NULL;
listiter=0;
listsize=0;
// maxsize=1024;
maxsize=0;
}
/************************************************************************
* destructor function *
* - calls the deletion function for each item in the list *
************************************************************************/
template <class listitem> slist<listitem>::~slist(void) {
for (dword i=0;i<listsize; i++) {
delfunc(listptr[i]);
}
delete listptr;
}
/************************************************************************
* sets the compare function *
* - the compare function is used in ordering and searching the list *
* but it must be user defined, and so this routine should be called *
* as soon as possible to set up the compare function for each list *
************************************************************************/
template <class listitem> int slist<listitem>::compare(listitem a,listitem b)
{ if(a<b) return -1;
if (a>b) return 1;
return 0;
}
/************************************************************************
* the delete function *
* - the delete function is called when deleting items from a list and *
* can be overridden within some classes *
************************************************************************/
template <class listitem> void slist<listitem>::delfunc(listitem d)
{ delete d;
}
/************************************************************************
* add an item to the list *
* - this takes care of list size, resizing the list if more space is *
* needed. It inserts a new item, using the lists compare function to *
* order the list *
************************************************************************/
template <class listitem> listitem slist<listitem>::addto(listitem ptr) {
dword i;
if (listsize==maxsize) { // resize list
maxsize+=1024;
listitem *nlist=new listitem[maxsize];
if (listptr) {
// CopyMemory(nlist,listptr,listsize*sizeof(listitem));
for (i=0;i<listsize;i++) nlist[i]=listptr[i];
delete listptr;
}
listptr=nlist;
}
if (find(ptr)==NULL) { // empty list
listptr[0]=ptr;
listsize=1;
}else{ // use listiter set by find
// ensure can add to end
if (compare(listptr[listiter],ptr)==-1) listiter++;
// move array up
for (i=listsize;i>listiter;i--) listptr[i]=listptr[i-1];
listptr[listiter]=ptr;
listsize++;
}
return ptr;
}
/************************************************************************
* delete an item in the list *
* - this just deletes one item from the list, and closes the gap *
* afterwards. It does not perform downsizing of the allocation *
************************************************************************/
template <class listitem> void slist<listitem>::delfrom(listitem ptr) {
dword i;
if (!listsize) return;
if (!find(ptr)) { // empty list
return;
}
if (!compare(listptr[listiter],ptr)) { // ensure equal
delfunc(listptr[listiter]);
// move the rest down
listsize--;
for (i=listiter;i<listsize;i++) listptr[i]=listptr[i+1];
}
}
/************************************************************************
* find an item in a list *
* - this is used to find items, it performs a binary search using the *
* lists compare function. It returns a pointer to the nearest item *
* and sets the list iterator to that item. *
* The nearest item is: *
* - NULL if the list is empty *
* - the first item if ptr< first item *
* - the last item if ptr> last item *
* - the first item such that ptr=item *
* - the nth item if nth item<ptr and n+1th item> ptr *
************************************************************************/
template <class listitem> listitem slist<listitem>::find(listitem ptr)
{ dword i,j,k;
if(!listsize)
{ listiter=0;
return NULL;
}
// i moves from the front of the array and j from the back
// until they are equal which is the returned item
i=0;
j=listsize-1;
while(i!=j)
{ // k=middle item for binary search
k=(i+j)>>1;
switch(compare(listptr[k],ptr))
{ case -1: // listptr[k]->cmp < ptr->cmp
if(j-i==1) // special case
{ if(i==k)
{ if(compare(listptr[j],ptr)!=1)
i=j;
else
j=i;
}
else
i=j;
}
else
i=k; // move lower bound up
break;
case 0: // listptr[k]->cmp==ptr->cmp
j=k; // only gets the first one of this type
break;
case 1: // listptr[k]->cmp > ptr->cmp
if(j-i==1) // special case
{ if(i==k)
j=k;
else
j=i;
}
else
j=k; // move upper bound down
break;
}
}
listiter=i;
return listptr[i];
}
/************************************************************************
* findnext - finds an item in a list *
* - this is used to find items, it performs a binary search using the *
* lists compare function. It returns a pointer to the nearest item *
* after the request and sets the list iterator to that item. In this *
* way it differs slightly from find. *
* The nearest item is: *
* - NULL if the list is empty *
* - the first item if ptr< first item *
* - NULL if ptr> last item *
* - the first item such that ptr=item *
* - the n+1th item if nth item<ptr and n+1th item> ptr *
************************************************************************/
template <class listitem> listitem slist<listitem>::findnext(listitem ptr)
{ dword i,j,k;
if(!listsize)
{ listiter=0;
return NULL;
}
// i moves from the front of the array and j from the back
// until they are equal which is the returned item
i=0;
j=listsize-1;
// check if its beyond the bounds....
if(compare(listptr[j],ptr)==-1)
return NULL;
while(i!=j)
{ // k=middle item for binary search
k=(i+j)>>1;
switch(compare(listptr[k],ptr))
{ case -1: // listptr[k]->cmp < ptr->cmp
if(j-i==1) // special case
{ if(i==k)
i=j;
else
j=i;
}
else
i=k; // move lower bound up
break;
case 0: // listptr[k]->cmp==ptr->cmp
j=k; // only gets the first one of this type
break;
case 1: // listptr[k]->cmp > ptr->cmp
if(j-i==1) // special case
j=i;
else
j=k; // move upper bound down
break;
}
}
listiter=i;
return listptr[i];
}
/************************************************************************
* reset list iterator to start of list *
************************************************************************/
template <class listitem> void slist<listitem>::resetiterator(void)
{ listiter=0;
}
/************************************************************************
* return next item in list using list iterator *
* - if listiter is beyond list then returns NULL *
* - otherwise returns listiter item, and then increases listiter *
* NB after finding an item the next item returned by this function will *
* be the same item *
************************************************************************/
template <class listitem> listitem slist<listitem>::nextiterator(void)
{ if(listiter>=listsize)
{ listiter=0;
return NULL;
}
return listptr[listiter++];
}
/************************************************************************
* return previous item in list using list iterator *
* - if listiter is at start of list then returns NULL *
* - otherwise decreases listiter and then returns the listitem *
* NB after finding an item the next item returned by this function will *
* be the previous item *
************************************************************************/
template <class listitem> listitem slist<listitem>::lastiterator(void)
{ if(!listiter)
{ return NULL;
}
listiter--;
return listptr[listiter];
}
/************************************************************************
* process queue function *
* - this was written for the scheduler mainly. It is used to process *
* the list as a queue. It returns the first item from the list and also *
* removes it from the list *
************************************************************************/
template <class listitem> listitem slist<listitem>::processqueue(void)
{ dword i;
listitem t;
if(!listsize)
return NULL;
t=listptr[0];
for(i=0;i<listsize-1;i++)
listptr[i]=listptr[i+1];
listsize--;
return t;
}
/************************************************************************
* peekfirst *
* - returns the first item from the list, without removal *
************************************************************************/
template <class listitem> listitem slist<listitem>::peekfirst(void)
{ if(!listsize)
return NULL;
return listptr[0];
}
/************************************************************************
* numlistitems *
* - simply returns the number of items in the list *
************************************************************************/
template <class listitem> dword slist<listitem>::numlistitems(void)
{ return listsize;
}
#endif
| Detected encoding: ASCII (7 bit) | 2
|