Quelltext /~heha/hs/borg.zip/LIST.H

/************************************************************************
*	       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
Vorgefundene Kodierung: UTF-80