collect.cxx

pwlib源码库

/*
 * collect.cxx
 *
 * Container Classes
 *
 * Portable Windows Library
 *
 * Copyright (c) 1993-1998 Equivalence Pty. Ltd.
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 *
 * The Original Code is Portable Windows Library.
 *
 * The Initial Developer of the Original Code is Equivalence Pty. Ltd.
 *
 * Portions are Copyright (C) 1993 Free Software Foundation, Inc.
 * All Rights Reserved.
 *
 * Contributor(s): ______________________________________.
 *
 * $Log: collect.cxx,v $
 * Revision 1.70  2005/01/09 06:35:05  rjongbloed
 * Fixed ability to make Clone() or MakeUnique() of a sorted list.
 *
 * Revision 1.69  2004/04/24 07:01:04  rjongbloed
 * Fixed breaking of all lists with PAssertNULL chane. Oops.
 *
 * Revision 1.68  2004/04/24 06:27:56  rjongbloed
 * Fixed GCC 3.4.0 warnings about PAssertNULL and improved recoverability on
 *   NULL pointer usage in various bits of code.
 *
 * Revision 1.67  2004/04/03 08:22:21  csoutheren
 * Remove pseudo-RTTI and replaced with real RTTI
 *
 * Revision 1.66  2004/03/23 10:59:35  rjongbloed
 * Added some extra bulletproofing of containers to avoid complaints by some
 *   memory checking tools, thanks Ted Szoczei
 *
 * Revision 1.65  2004/02/15 03:04:52  rjongbloed
 * Fixed problem with PSortedList nil variable and assignment between instances,
 *   pointed out by Ben Lear.
 *
 * Revision 1.64  2004/02/09 06:23:32  csoutheren
 * Added fix for gcc 3.3.1 problem. Apparently, it is unable to correctly resolve
 * a function argument that is a reference to a const pointer. Changing the argument
 * to be a pointer to a pointer solves the problem. Go figure
 *
 * Revision 1.63  2004/02/08 22:46:35  csoutheren
 * Added casts to fix problems with gcc
 *
 * Revision 1.62  2004/02/08 11:13:20  rjongbloed
 * Fixed crash in heavily loaded multi-threaded systems using simultaneous sorted
 *   lists, Thanks Federico Pinna, Fabrizio Ammollo and the gang at Reitek S.p.A.
 *
 * Revision 1.61  2003/09/24 22:13:58  dereksmithies
 * Add fix for deleting an object, then readding it. Thanks Fabrizio Ammollo
 *
 * Revision 1.60  2003/08/31 22:11:30  dereksmithies
 * Fix from Diego Tartara for the SetAt function. Many thanks.
 *
 * Revision 1.59  2002/12/02 04:27:37  robertj
 * Added extra bullet proofing for some pathological conditions.
 *
 * Revision 1.58  2002/11/12 08:57:18  robertj
 * Changed scope of PAbstraSortedList::Element class so descendant classes
 *   can get at it.
 * Fixed problem with GetValuesIndex not returning first element of a certain
 *   value if the object was a PCaselessString.
 *
 * Revision 1.57  2002/06/25 02:24:59  robertj
 * Improved assertion system to allow C++ class name to be displayed if
 *   desired, especially relevant to container classes.
 *
 * Revision 1.56  2002/06/12 09:40:58  robertj
 * Fixed printing of a dictionary to utilise the stream fill character between
 *   each dictiionary element, as per general container semantics.
 *
 * Revision 1.55  2002/04/26 05:40:21  robertj
 * Removed assumption that GetAt() on a dictionary will automatically convert
 *   the index to a POrdinalyKey. This breaks the PCollection semantics for
 *   GetAt() which is to get based on the ordinal position not the hashed position.
 *
 * Revision 1.54  2002/04/16 07:58:13  robertj
 * Fixed MakeUnique for lists and sorted lists.
 *
 * Revision 1.53  2002/02/03 16:16:07  rogerh
 * make nil static. Submitted by Peter Johnson <[e-mail]>
 *
 * Revision 1.52  2002/01/31 05:02:50  robertj
 * Fixed PSortedList::Remove function for removing objects with equal keys.
 *
 * Revision 1.51  2001/06/07 04:49:26  robertj
 * Allowed for other separators than \n when printing elements of a collection.
 *
 * Revision 1.50  2001/01/24 06:19:14  yurik
 * Windows CE port-related changes
 *
 * Revision 1.49  2000/11/28 12:47:13  robertj
 * Added ability to separate collection entries with newline in PrintOn by using fillchar.
 *
 * Revision 1.48  1999/08/22 12:54:35  robertj
 * Fixed warnings about inlines on older GNU compiler
 *
 * Revision 1.47  1999/02/16 08:08:06  robertj
 * MSVC 6.0 compatibility changes.
 *
 * Revision 1.46  1998/11/02 12:53:52  robertj
 * Fixed yet another bug in the object array SetSize() for unix systems.
 *
 * Revision 1.45  1998/10/31 14:01:58  robertj
 * Fixed ANSI scoping of for loop variable.
 *
 * Revision 1.44  1998/10/30 10:41:57  robertj
 * Fixed bug cause by previous bug fix in PObjectArray, deleting deleted entries.
 *
 * Revision 1.43  1998/10/28 00:57:43  robertj
 * Fixed memory leak in PObjectArray.
 * Fixed crash when doing GetValuesIndex() on array with NULL elements.
 *
 * Revision 1.42  1998/10/13 14:06:16  robertj
 * Complete rewrite of memory leak detection code.
 *
 * Revision 1.41  1998/09/23 06:21:52  robertj
 * Added open source copyright license.
 *
 * Revision 1.40  1998/09/14 12:32:45  robertj
 * Fixed bug in ordinal dictionary GetAt() and SetAt() for scalar integer types.
 *
 * Revision 1.39  1998/08/20 05:48:51  robertj
 * Fixed bug on removing entries by index from a PSet().
 *
 * Revision 1.38  1998/05/17 02:29:46  robertj
 * Fixed GetObjectsIndex()/GetValuesIndex() finding elements that have a hash clash.
 *
 * Revision 1.37  1998/03/26 23:31:50  robertj
 * Fixed bug in RemoveAll() deleting objects twice.
 *
 * Revision 1.36  1998/03/26 11:19:50  robertj
 * Fix bug with unsigned PINDEX in array SetSize.
 *
 * Revision 1.35  1998/03/25 12:58:41  robertj
 * Fixed memory leak if resize PArray
 *
 * Revision 1.34  1998/03/24 02:58:52  robertj
 * Fixed uninitialised variable in dictionary MakeUnique() function.
 *
 * Revision 1.33  1998/01/26 01:41:19  robertj
 * GNU compatibility.
 *
 * Revision 1.32  1998/01/26 00:36:10  robertj
 * Fixed MakeUnique() function for dictionaries and sets.
 *
 * Revision 1.31  1998/01/06 12:00:15  robertj
 * Fixed "typesafe" templates/macros for dictionaries, especially on GNU.
 *
 * Revision 1.30  1997/12/11 10:30:02  robertj
 * Added type correct Contains() function to dictionaries.
 *
 * Revision 1.29  1997/06/08 04:48:30  robertj
 * Fixed problems in sorted list with multiple identical entries.
 *
 * Revision 1.28  1997/04/27 05:50:14  robertj
 * DLL support.
 *
 * Revision 1.27  1997/02/14 13:59:09  robertj
 * Rewrite of sorted list to use sentinel record rather than NULL pointer.
 *
 * Revision 1.26  1996/08/17 09:55:23  robertj
 * Optimised RemoveAll() for object arrays.
 *
 * Revision 1.25  1996/08/08 10:08:43  robertj
 * Directory structure changes for common files.
 *
 * Revision 1.24  1996/07/15 10:32:52  robertj
 * Fixed bug in sorted list (crash on remove).
 *
 * Revision 1.23  1996/05/26 03:46:24  robertj
 * Compatibility to GNU 2.7.x
 *
 * Revision 1.22  1996/03/26 00:52:38  robertj
 * Fixed bug in dictionary decrementing size when removing element even if already removed.
 *
 * Revision 1.21  1996/02/19 13:32:31  robertj
 * Fixed yet another bug in PSortedList, not setting cache index value correctly.
 *
 * Revision 1.20  1996/02/08 12:24:13  robertj
 * Added default print for dictionaries in form key=data\n.
 * Added missing GetAt() function on PSet to be consistent with all others.
 *
 * Revision 1.19  1996/02/03 11:07:59  robertj
 * A bit more bullet proofing of sorted list class.
 *
 * Revision 1.18  1996/01/30 23:30:40  robertj
 * Added optimisation to sorted list GetAt() to use cached element.
 *
 * Revision 1.17  1996/01/28 14:11:45  robertj
 * Fixed bug in sorted list for when getting entry one before last one cached.
 *
 * Revision 1.16  1996/01/28 02:52:45  robertj
 * Added assert into all Compare functions to assure comparison between compatible objects.
 *
 * Revision 1.15  1996/01/23 13:18:29  robertj
 * Fixed bug in sorted list GetObjectsIndex not checking if is same object
 * Fixed bug in sorted list append not returning correct value.
 *
 * Revision 1.14  1995/01/27 11:12:38  robertj
 * Fixed nasty bug in sorted lists.
 *
 * Revision 1.13  1995/01/09  12:31:49  robertj
 * Removed unnecesary return value from I/O functions.
 *
 * Revision 1.12  1994/12/13  11:50:52  robertj
 * Added MakeUnique() function to all container classes.
 *
 * Revision 1.11  1994/12/12  10:16:25  robertj
 * Restructuring and documentation of container classes.
 * Renaming of some macros for declaring container classes.
 * Added some extra functionality to PString.
 * Added start to 2 byte characters in PString.
 * Fixed incorrect overrides in PCaselessString.
 *
 * Revision 1.10  1994/12/05  11:24:58  robertj
 * Fixed bugs in InsertAt and RemoveAt in PObjectArray.
 *
 * Revision 1.9  1994/10/30  11:34:49  robertj
 * Fixed ObjectArray to have pointer to array object pointers.
 *
 * Revision 1.8  1994/10/23  03:41:31  robertj
 * Fixed dictionary functions that should work by index not key.
 *
 * Revision 1.7  1994/09/25  10:49:09  robertj
 * Removed redundent PAssertNULL.
 *
 * Revision 1.6  1994/08/21  23:43:02  robertj
 * Fixed bug in lists when inserting element.
 *
 * Revision 1.5  1994/07/27  05:58:07  robertj
 * Synchronisation.
 *
 * Revision 1.4  1994/07/17  10:46:06  robertj
 * Fixed searching in sorted lists.
 *
 * Revision 1.3  1994/07/02  03:03:49  robertj
 * Added container searching facilities..
 *
 * Revision 1.2  1994/06/25  11:55:15  robertj
 * Unix version synchronisation.
 *
// Revision 1.1  1994/04/20  12:17:44  robertj
// Initial revision
//
 */

#include <ptlib.h>

#ifndef _WIN32_WCE
#define new PNEW
#undef  __CLASS__
#define __CLASS__ GetClass()
#endif


///////////////////////////////////////////////////////////////////////////////

void PCollection::PrintOn(ostream &strm) const
{
  char separator = strm.fill();
  int width = strm.width();
  for (PINDEX  i = 0; i < GetSize(); i++) {
    if (i > 0 && separator != ' ')
      strm << separator;
    PObject * obj = GetAt(i);
    if (obj != NULL) {
      if (separator != ' ')
        strm.width(width);
      strm << *obj;
    }
  }
  if (separator == '\n')
    strm << '\n';
}


void PCollection::RemoveAll()
{
  while (GetSize() > 0)
    RemoveAt(0);
}


///////////////////////////////////////////////////////////////////////////////

void PArrayObjects::CopyContents(const PArrayObjects & array)
{
  theArray = array.theArray;
}


void PArrayObjects::DestroyContents()
{
  if (reference->deleteObjects && theArray != NULL) {
    for (PINDEX i = 0; i < theArray->GetSize(); i++) {
      if ((*theArray)[i] != NULL)
        delete (*theArray)[i];
    }
  }
  delete theArray;
  theArray = NULL;
}


void PArrayObjects::RemoveAll()
{
  SetSize(0);
}


void PArrayObjects::CloneContents(const PArrayObjects * array)
{
  ObjPtrArray & oldArray = *array->theArray;
  theArray = new ObjPtrArray(oldArray.GetSize());
  for (PINDEX i = 0; i < GetSize(); i++) {
    PObject * ptr = oldArray[i];
    if (ptr != NULL)
      SetAt(i, ptr->Clone());
  }
}


PObject::Comparison PArrayObjects::Compare(const PObject & obj) const
{
  PAssert(PIsDescendant(&obj, PArrayObjects), PInvalidCast);
  const PArrayObjects & other = (const PArrayObjects &)obj;
  PINDEX i;
  for (i = 0; i < GetSize(); i++) {
    if (i >= other.GetSize() || *(*theArray)[i] < *(*other.theArray)[i])
      return LessThan;
    if (*(*theArray)[i] > *(*other.theArray)[i])
      return GreaterThan;
  }
  return i < other.GetSize() ? GreaterThan : EqualTo;
}


PINDEX PArrayObjects::GetSize() const
{
  return theArray->GetSize();
}


BOOL PArrayObjects::SetSize(PINDEX newSize)
{
  PINDEX sz = theArray->GetSize();
  if (reference->deleteObjects && sz > 0) {
    for (PINDEX i = sz; i > newSize; i--) {
      PObject * obj = theArray->GetAt(i-1);
      if (obj != NULL)
        delete obj;
    }
  }
  return theArray->SetSize(newSize);
}


PINDEX PArrayObjects::Append(PObject * obj)
{
  PINDEX where = GetSize();
  SetAt(where, obj);
  return where;
}


PINDEX PArrayObjects::Insert(const PObject & before, PObject * obj)
{
  PINDEX where = GetObjectsIndex(&before);
  InsertAt(where, obj);
  return where;
}


BOOL PArrayObjects::Remove(const PObject * obj)
{
  PINDEX i = GetObjectsIndex(obj);
  if (i == P_MAX_INDEX)
    return FALSE;
  RemoveAt(i);
  return TRUE;
}


PObject * PArrayObjects::GetAt(PINDEX index) const
{
  return (*theArray)[index];
}


BOOL PArrayObjects::SetAt(PINDEX index, PObject * obj)
{
  if (!theArray->SetMinSize(index+1))
    return FALSE;
  PObject * oldObj = theArray->GetAt(index);
  if (oldObj != NULL && reference->deleteObjects)
    delete oldObj;
  (*theArray)[index] = obj;
  return TRUE;
}


PINDEX PArrayObjects::InsertAt(PINDEX index, PObject * obj)
{
  for (PINDEX i = GetSize(); i > index; i--)
    (*theArray)[i] = (*theArray)[i-1];
  (*theArray)[index] = obj;
  return index;
}


PObject * PArrayObjects::RemoveAt(PINDEX index)
{
  PObject * obj = (*theArray)[index];

  PINDEX size = GetSize()-1;
  PINDEX i;
  for (i = index; i < size; i++)
    (*theArray)[i] = (*theArray)[i+1];
  (*theArray)[i] = NULL;

  SetSize(size);

  if (obj != NULL && reference->deleteObjects) {
    delete obj;
    obj = NULL;
  }

  return obj;
}


PINDEX PArrayObjects::GetObjectsIndex(const PObject * obj) const
{
  for (PINDEX i = 0; i < GetSize(); i++) {
    if ((*theArray)[i] == obj)
      return i;
  }
  return P_MAX_INDEX;
}


PINDEX PArrayObjects::GetValuesIndex(const PObject & obj) const
{
  for (PINDEX i = 0; i < GetSize(); i++) {
    PObject * elmt = (*theArray)[i];
    if (elmt != NULL && *elmt == obj)
      return i;
  }
  return P_MAX_INDEX;
}


///////////////////////////////////////////////////////////////////////////////

void PAbstractList::DestroyContents()
{
  RemoveAll();
  delete info;
  info = NULL;
}


void PAbstractList::CopyContents(const PAbstractList & list)
{
  info = list.info;
}


void PAbstractList::CloneContents(const PAbstractList * list)
{
  Element * element = list->info->head;

  info = new Info;
  PAssert(info != NULL, POutOfMemory);

  while (element != NULL) {
    Element * newElement = new Element(element->data->Clone());

    if (info->head == NULL)
      info->head = info->tail = newElement;
    else {
      newElement->prev = info->tail;
      info->tail->next = newElement;
      info->tail = newElement;
    }

    element = element->next;
  }
}


PObject::Comparison PAbstractList::Compare(const PObject & obj) const
{
  PAssert(PIsDescendant(&obj, PAbstractList), PInvalidCast);
  Element * elmt1 = info->head;
  Element * elmt2 = ((const PAbstractList &)obj).info->head;
  while (elmt1 != NULL && elmt2 != NULL) {
    if (elmt1 == NULL)
      return LessThan;
    if (elmt2 == NULL)
      return GreaterThan;
    if (*elmt1->data < *elmt2->data)
      return LessThan;
    if (*elmt1->data > *elmt2->data)
      return GreaterThan;
    elmt1 = elmt1->next;
    elmt2 = elmt2->next;
  }
  return EqualTo;
}


BOOL PAbstractList::SetSize(PINDEX)
{
  return TRUE;
}


PINDEX PAbstractList::Append(PObject * obj)
{
  if (PAssertNULL(obj) == NULL)
    return P_MAX_INDEX;

  Element * element = new Element(obj);
  if (info->tail != NULL)
    info->tail->next = element;
  element->prev = info->tail;
  element->next = NULL;
  if (info->head == NULL)
    info->head = element;
  info->tail = element;
  info->lastElement = element;
  info->lastIndex = GetSize();
  reference->size++;
  return info->lastIndex;
}


PINDEX PAbstractList::Insert(const PObject & before, PObject * obj)
{
  if (PAssertNULL(obj) == NULL)
    return P_MAX_INDEX;
  
  PINDEX where = GetObjectsIndex(&before);
  InsertAt(where, obj);
  return where;
}


PINDEX PAbstractList::InsertAt(PINDEX index, PObject * obj)
{
  if (PAssertNULL(obj) == NULL)
    return P_MAX_INDEX;
  
  if (index >= GetSize())
    return Append(obj);

  PAssert(SetCurrent(index), PInvalidArrayIndex);

  Element * newElement = new Element(obj);
  if (info->lastElement->prev != NULL)
    info->lastElement->prev->next = newElement;
  else
    info->head = newElement;
  newElement->prev = info->lastElement->prev;
  newElement->next = info->lastElement;
  info->lastElement->prev = newElement;
  info->lastElement = newElement;
  info->lastIndex = index;
  reference->size++;
  return index;
}


BOOL PAbstractList::Remove(const PObject * obj)
{
  PINDEX i = GetObjectsIndex(obj);
  if (i == P_MAX_INDEX)