X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/621793f45e003588e32f7a6ca10cd238f7c96fe6..fd3f686c274a264e89ea97505350a82c1134f307:/src/common/list.cpp diff --git a/src/common/list.cpp b/src/common/list.cpp index 80841b6ea6..730134ae7d 100644 --- a/src/common/list.cpp +++ b/src/common/list.cpp @@ -1,14 +1,21 @@ -///////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////// // Name: list.cpp // Purpose: wxList implementation // Author: Julian Smart -// Modified by: +// Modified by: VZ at 16/11/98: WX_DECLARE_LIST() and typesafe lists added // Created: 04/01/98 // RCS-ID: $Id$ // Copyright: (c) Julian Smart and Markus Holzem -// Licence: wxWindows license -///////////////////////////////////////////////////////////////////////////// +// Licence: wxWindows license +//////////////////////////////////////////////////////////////////////////////// +// ============================================================================= +// declarations +// ============================================================================= + +// ----------------------------------------------------------------------------- +// headers +// ----------------------------------------------------------------------------- #ifdef __GNUG__ #pragma implementation "list.h" #endif @@ -17,389 +24,364 @@ #include "wx/wxprec.h" #ifdef __BORLANDC__ -#pragma hdrstop + #pragma hdrstop #endif +#include +#include +#include + #ifndef WX_PRECOMP -#include "wx/defs.h" -#include "wx/list.h" -#include "wx/utils.h" -#include + #include "wx/defs.h" + #include "wx/list.h" + #include "wx/utils.h" // for copystring() (beurk...) #endif // Sun CC compatibility (interference with xview/pkg.h, apparently...) #if defined(SUN_CC) && defined(__XVIEW__) -#undef va_start -#undef va_end -#undef va_arg -#undef va_list + #undef va_start + #undef va_end + #undef va_arg + #undef va_list #endif -#include -#include -#include +// ============================================================================= +// implementation +// ============================================================================= -#if !USE_SHARED_LIBRARY -IMPLEMENT_DYNAMIC_CLASS(wxNode, wxObject) -IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject) -IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxList) -#endif +// ----------------------------------------------------------------------------- +// wxNodeBase +// ----------------------------------------------------------------------------- -wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one, - wxObject * object) +wxNodeBase::wxNodeBase(wxListBase *list, + wxNodeBase *previous, wxNodeBase *next, + void *data, const wxListKey& key) { - data = object; - previous = last_one; - next = next_one; - list = the_list; - key.string = (char *) NULL; - - if (previous) - previous->next = this; + m_list = list; + m_data = data; + m_previous = previous; + m_next = next; + + switch ( key.GetKeyType() ) + { + case wxKEY_NONE: + break; + + case wxKEY_INTEGER: + m_key.integer = key.GetNumber(); + break; + + case wxKEY_STRING: + // to be free()d later + m_key.string = strdup(key.GetString()); + break; + + default: + wxFAIL_MSG("invalid key type"); + } + + if ( previous ) + previous->m_next = this; + + if ( next ) + next->m_previous = this; +} - if (next) - next->previous = this; +wxNodeBase::~wxNodeBase() +{ + // handle the case when we're being deleted from the list by the user (i.e. + // not by the list itself from DeleteNode) - we must do it for + // compatibility with old code + if ( m_list != NULL ) + { + m_list->DetachNode(this); + } } -// Keyed constructor -wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one, - wxObject * object, long the_key) +// ----------------------------------------------------------------------------- +// wxListBase +// ----------------------------------------------------------------------------- + +void wxListBase::Init(wxKeyType keyType = wxKEY_NONE) { - data = object; - previous = last_one; - next = next_one; - list = the_list; - key.integer = the_key; + m_nodeFirst = + m_nodeLast = (wxNodeBase *) NULL; + m_count = 0; + m_destroy = FALSE; + m_keyType = keyType; +} - if (previous) - previous->next = this; +wxListBase::wxListBase(size_t count, void *elements[]) +{ + Init(); - if (next) - next->previous = this; + for ( size_t n = 0; n < count; n++ ) + { + Append(elements[n]); + } } -wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one, - wxObject * object, const char *the_key) +void wxListBase::DoCopy(const wxListBase& list) { - data = object; - previous = last_one; - next = next_one; - list = the_list; - key.string = copystring (the_key); + wxASSERT_MSG( !list.m_destroy, + "copying list which owns it's elements is a bad idea" ); - if (previous) - previous->next = this; + m_count = list.m_count; + m_destroy = list.m_destroy; + m_keyType = list.m_keyType; + m_nodeFirst = + m_nodeLast = (wxNodeBase *) NULL; - if (next) - next->previous = this; + for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() ) + { + Append(node); + } } - -wxNode::~wxNode (void) +wxListBase::~wxListBase() { - if (list) - list->n--; - - if (list && list->destroy_data) - delete data; - - if (list && list->key_type == wxKEY_STRING && key.string) - delete[]key.string; - - // Make next node point back to the previous node from here - if (next) - next->previous = previous; - else if (list) - // If there's a new end of list (deleting the last one) - // make sure the list knows about it. - list->last_node = previous; - - // Make the previous node point to the next node from here - if (previous) - previous->next = next; - - // Or if no previous node (start of list), make sure list points at - // the next node which becomes the first!. - else if (list) - list->first_node = next; + wxNodeBase *each = m_nodeFirst; + while ( each != NULL ) + { + wxNodeBase *next = each->GetNext(); + DoDeleteNode(each); + each = next; + } } -wxList::wxList (void) +wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node) { - first_node = (wxNode *) NULL; - last_node = (wxNode *) NULL; - n = 0; - destroy_data = 0; - key_type = wxKEY_NONE; + if ( !m_nodeFirst ) + { + m_nodeFirst = node; + m_nodeLast = m_nodeFirst; + } + else + { + m_nodeLast->m_next = node; + m_nodeLast = node; + } + + m_count++; + + return node; } -wxList::wxList (int N, wxObject * Objects[]) +wxNodeBase *wxListBase::Append(void *object) { - wxNode *last = (wxNode *) NULL; + // all objects in a keyed list should have a key + wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL, + "need a key for the object to append" ); - int i; - for (i = 0; i < N; i++) - { - wxNode *next = new wxNode (this, last, (wxNode *) NULL, Objects[i]); - last = next; - if (i == 0) - first_node = next; - } - last_node = last; - n = N; - key_type = wxKEY_NONE; + wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object); + + return AppendCommon(node); } -wxList::wxList (const unsigned int the_key_type) +wxNodeBase *wxListBase::Append(long key, void *object) { - n = 0; - destroy_data = 0; - first_node = (wxNode *) NULL; - last_node = (wxNode *) NULL; - key_type = the_key_type; + wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) || + (m_keyType == wxKEY_NONE && m_count == 0), + (wxNodeBase *)NULL, + "can't append object with numeric key to this list" ); + + wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key); + return AppendCommon(node); } -// Variable argument list, terminated by a zero -wxList::wxList (wxObject * first_one...) +wxNodeBase *wxListBase::Append (const char *key, void *object) { -// #ifndef __SGI__ - va_list ap; + wxCHECK_MSG( (m_keyType == wxKEY_STRING) || + (m_keyType == wxKEY_NONE && m_count == 0), + (wxNodeBase *)NULL, + "can't append object with string key to this list" ); + + wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key); + return AppendCommon(node); +} - va_start (ap, first_one); +wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object) +{ + // all objects in a keyed list should have a key + wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL, + "need a key for the object to insert" ); - wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, first_one); - first_node = last; - n = 1; + wxNodeBase *prev = (wxNodeBase *)NULL; + if ( position ) + prev = position->GetPrevious(); + //else + // inserting in the beginning of the list - for (;;) + wxNodeBase *node = CreateNode(prev, position, object); + if ( !m_nodeFirst ) { - wxObject *object = va_arg (ap, wxObject *); -// if (object == NULL) // Doesn't work in Windows -- segment is non-zero for NULL! -#ifdef __WXMSW__ - if ((int) object == 0) -#else - if ((long) object == 0) -#endif - break; - else - { - wxNode *node = new wxNode (this, last, (wxNode *) NULL, object); - last = node; - n++; - } + m_nodeFirst = node; + m_nodeLast = node; } - last_node = last; - va_end (ap); - - destroy_data = 0; - key_type = wxKEY_NONE; -/* -#else - fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n"); -#endif -*/ -} -wxList::~wxList (void) -{ - wxNode *each = first_node; - while (each) + if ( prev == NULL ) { - wxNode *next = each->Next (); - delete each; - each = next; + m_nodeFirst = node; } -} -wxNode *wxList::Append(wxObject *object) -{ - wxNode *node = new wxNode(this, last_node, (wxNode *) NULL, object); - if (!first_node) - first_node = node; - last_node = node; - n ++; + m_count++; + return node; } -wxNode *wxList::Nth (int i) const +wxNodeBase *wxListBase::Item(size_t n) const { - int j = 0; - for (wxNode * current = First (); current; current = current->Next ()) + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) { - if (j++ == i) - return current; + if ( n-- == 0 ) + { + return current; + } } - return (wxNode *) NULL; // No such element -} + wxFAIL_MSG( "invalid index in wxListBase::Item" ); -wxNode *wxList::Find (long key) const -{ - wxNode *current = First(); - while (current) - { - if (current->key.integer == key) - return current; - current = current->Next(); - } - - return (wxNode *) NULL; // Not found! + return NULL; } -wxNode *wxList::Find (const char *key) const +wxNodeBase *wxListBase::Find(const wxListKey& key) const { - wxNode *current = First(); - while (current) - { - if (!current->key.string) - { - wxFatalError (_("wxList: string key not present, probably did not Append correctly!")); - break; - } - if (strcmp (current->key.string, key) == 0) - return current; - current = current->Next(); - } + wxASSERT_MSG( m_keyType == key.GetKeyType(), + "this list is not keyed on the type of this key" ); - return (wxNode *) NULL; // Not found! + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) + { + if ( key == current->m_key ) + { + return current; + } + } + // not found + return (wxNodeBase *)NULL; } -wxNode *wxList::Member (wxObject * object) const +wxNodeBase *wxListBase::Find(void *object) const { - for (wxNode * current = First (); current; current = current->Next ()) + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) { - wxObject *each = current->Data (); - if (each == object) - return current; + if ( current->GetData() == object ) + return current; } - return (wxNode *) NULL; + + // not found + return (wxNodeBase *)NULL; } -bool wxList::DeleteNode (wxNode * node) +void wxListBase::DoDeleteNode(wxNodeBase *node) { - if (node) + // free node's data + if ( m_keyType == wxKEY_STRING ) { - delete node; - return TRUE; + free(node->m_key.string); } - return FALSE; -} -bool wxList::DeleteObject (wxObject * object) -{ - // Search list for object - for (wxNode * current = first_node; current; current = current->Next ()) + if ( m_destroy ) { - if (current->Data () == object) - { - delete current; - return TRUE; - } + node->DeleteData(); } - return FALSE; // Did not find the object + delete node; } - -// Insert new node at front of list -wxNode *wxList::Insert (wxObject * object) +wxNodeBase *wxListBase::DetachNode(wxNodeBase *node) { - wxNode *node = new wxNode (this, (wxNode *) NULL, First (), object); - first_node = node; + wxCHECK_MSG( node, NULL, "detaching NULL wxNodeBase" ); + wxCHECK_MSG( node->m_list == this, NULL, + "detaching node which is not from this list" ); - if (!(node->Next ())) - last_node = node; - - n++; - return node; -} + // update the list + wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next + : &m_nodeFirst; + wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous + : &m_nodeLast; + *prevNext = node->GetNext(); + *nextPrev = node->GetPrevious(); -// Insert new node before given node. -wxNode *wxList::Insert (wxNode * position, wxObject * object) -{ - wxNode *prev = (wxNode *) NULL; - if (position) - prev = position->Previous (); + m_count--; - wxNode *node = new wxNode (this, prev, position, object); - if (!first_node) - { - first_node = node; - last_node = node; - } - if (!prev) - first_node = node; + // mark the node as not belonging to this list any more + node->m_list = NULL; - n++; - return node; + return node; } -// Keyed append -wxNode *wxList::Append (long key, wxObject * object) +bool wxListBase::DeleteNode(wxNodeBase *node) { - wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key); - if (!first_node) - first_node = node; - last_node = node; - n++; - return node; + if ( !DetachNode(node) ) + return FALSE; + + DoDeleteNode(node); + + return TRUE; } -wxNode *wxList::Append (const char *key, wxObject * object) +bool wxListBase::DeleteObject(void *object) { - wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key); - if (!first_node) - first_node = node; - last_node = node; - n++; - return node; + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) + { + if ( current->GetData() == object ) + { + DeleteNode(current); + return TRUE; + } + } + + // not found + return FALSE; } -void wxList::Clear (void) + +void wxListBase::Clear() { - wxNode *current = first_node; - while (current) + wxNodeBase *current = m_nodeFirst; + while ( current ) { - wxNode *next = current->Next (); - delete current; - current = next; + wxNodeBase *next = current->GetNext(); + DoDeleteNode(current); + current = next; } - first_node = (wxNode *) NULL; - last_node = (wxNode *) NULL; - n = 0; + + m_nodeFirst = + m_nodeLast = (wxNodeBase *)NULL; + + m_count = 0; } -//Executes function F with all items present in the list -void wxList::ForEach(wxListIterateFunction F) +void wxListBase::ForEach(wxListIterateFunction F) { - wxNode *each = first_node; - while (each) - { (*F)( each->Data ()); - each = each->Next(); + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) + { + (*F)(current->GetData()); } } -// Returns a pointer to the item which returns TRUE with function F -// or NULL if no such item found -wxObject *wxList::FirstThat(wxListIterateFunction F) + +void *wxListBase::FirstThat(wxListIterateFunction F) { - wxNode *each = first_node; - while (each) - { if ((*F)( each->Data ())) return each->Data(); - each = each->Next(); + for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() ) + { + if ( (*F)(current->GetData()) ) + return current->GetData(); } - return (wxNode *) NULL; + + return (wxNodeBase *)NULL; } -// Like FirstThat, but proceeds from the end backward -wxObject *wxList::LastThat(wxListIterateFunction F) + +void *wxListBase::LastThat(wxListIterateFunction F) { - wxNode *each = last_node; - while (each) - { if ((*F)( each->Data ())) return each->Data(); - each = each->Previous(); + for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() ) + { + if ( (*F)(current->GetData()) ) + return current->GetData(); } - return (wxNode *) NULL; + + return (wxNodeBase *)NULL; } // (stefan.hammes@urz.uni-heidelberg.de) @@ -421,8 +403,8 @@ wxObject *wxList::LastThat(wxListIterateFunction F) // } // // void main() -// { -// wxList list; +// { +// wxListBase list; // // list.Append(new wxString("DEF")); // list.Append(new wxString("GHI")); @@ -430,155 +412,115 @@ wxObject *wxList::LastThat(wxListIterateFunction F) // list.Sort(listcompare); // } -void wxList::Sort(const wxSortCompareFunction compfunc) +void wxListBase::Sort(const wxSortCompareFunction compfunc) { - // allocate an array for the wxObject pointers of the list - const size_t num = Number(); - wxObject **objArray = new wxObject *[num]; - wxObject **objPtr = objArray; - - // go through the list and put the pointers into the array - wxNode *node = First(); - while(node!=NULL){ - *objPtr++ = node->Data(); - node = node->Next(); - } - // sort the array - qsort((void *)objArray,num,sizeof(wxObject *),compfunc); - // put the sorted pointers back into the list - objPtr = objArray; - node = First(); - while(node!=NULL){ - node->SetData(*objPtr++); - node = node->Next(); - } - // free the array - delete[] objArray; + // allocate an array for the wxObject pointers of the list + const size_t num = GetCount(); + void **objArray = new void *[num]; + void **objPtr = objArray; + + // go through the list and put the pointers into the array + wxNodeBase *node; + for ( node = GetFirst(); node; node = node->Next() ) + { + *objPtr++ = node->Data(); + } + + // sort the array + qsort((void *)objArray,num,sizeof(wxObject *),compfunc); + + // put the sorted pointers back into the list + objPtr = objArray; + for ( node = GetFirst(); node; node = node->Next() ) + { + node->SetData(*objPtr++); + } + + // free the array + delete[] objArray; } -/* - * String list - * - */ +// ----------------------------------------------------------------------------- +// wxList (a.k.a. wxObjectList) +// ----------------------------------------------------------------------------- -wxStringList::wxStringList (void): -wxList () +void wxObjectListNode::DeleteData() { + delete (wxObject *)GetData(); } -wxStringList::wxStringList (const wxStringList& list) +// ----------------------------------------------------------------------------- +// wxStringList +// ----------------------------------------------------------------------------- + +// instead of WX_DEFINE_LIST(wxStringListBase) we define this function +// ourselves +void wxStringListNode::DeleteData() { - (*this) = list; + delete [] (char *)GetData(); } // Variable argument list, terminated by a zero // Makes new storage for the strings -wxStringList::wxStringList (const char *first...) +wxStringList::wxStringList (const char *first, ...) { -// #ifndef __SGI__ - n = 0; - destroy_data = 0; - key_type = wxKEY_NONE; - first_node = (wxNode *) NULL; - last_node = (wxNode *) NULL; - - if (!first) + if ( !first ) return; va_list ap; + va_start(ap, first); - va_start (ap, first); - - wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, (wxObject *) copystring (first)); - first_node = last; - n = 1; - + const char *s = first; for (;;) - { - char *s = va_arg (ap, char *); -// if (s == NULL) + { + Add(s); + + s = va_arg(ap, const char *); + // if (s == NULL) #ifdef __WXMSW__ if ((int) s == 0) #else if ((long) s == 0) #endif - break; - else - { - wxNode *node = new wxNode (this, last, (wxNode *) NULL, (wxObject *) copystring (s)); - last = node; - n++; - } - } - last_node = last; - va_end (ap); -/* -#else - fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n"); -#endif -*/ -} + break; + } -wxStringList::~wxStringList (void) -{ - Clear(); + va_end(ap); } -void wxStringList::Clear(void) +// Only makes new strings if arg is TRUE +char **wxStringList::ListToArray(bool new_copies) const { - wxNode *each = First(); - while (each) + char **string_array = new char *[GetCount()]; + wxStringListNode *node = GetFirst(); + for (size_t i = 0; i < GetCount(); i++) { - char *s = (char *) each->Data (); - delete[]s; - wxNode *next = each->Next (); - delete each; - each = next; + char *s = node->GetData(); + if ( new_copies ) + string_array[i] = copystring(s); + else + string_array[i] = s; + node = node->GetNext(); } - wxList::Clear(); -} - -wxNode *wxStringList::Add (const char *s) -{ - return Append ((wxObject *) (copystring (s))); -} - -void wxStringList::Delete (const char *s) -{ - for (wxNode * node = First (); node; node = node->Next ()) - { - char *string = (char *) node->Data (); - if (string == s || strcmp (string, s) == 0) - { - delete[]string; - delete node; - break; // Done! - - } - } // for + return string_array; } -// Only makes new strings if arg is TRUE -char **wxStringList::ListToArray (bool new_copies) const +// Checks whether s is a member of the list +bool wxStringList::Member(const char *s) const { - char **string_array = new char *[Number ()]; - wxNode *node = First (); - int i; - for (i = 0; i < n; i++) + for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() ) { - char *s = (char *) node->Data (); - if (new_copies) - string_array[i] = copystring (s); - else - string_array[i] = s; - node = node->Next (); + const char *s1 = node->GetData(); + if (s == s1 || strcmp (s, s1) == 0) + return TRUE; } - return string_array; + + return FALSE; } -static int -wx_comparestrings (const void *arg1, const void *arg2) +static int +wx_comparestrings(const void *arg1, const void *arg2) { char **s1 = (char **) arg1; char **s2 = (char **) arg2; @@ -587,53 +529,23 @@ wx_comparestrings (const void *arg1, const void *arg2) } // Sort a list of strings - deallocates old nodes, allocates new -void wxStringList::Sort (void) +void wxStringList::Sort() { - size_t N = n; - char **array = new char *[N]; - - size_t i = 0; - for (wxNode * node = First (); node; node = node->Next ()) - array[i++] = (char *) node->Data (); - - qsort (array, N, sizeof (char *), wx_comparestrings); - Clear (); - - for (i = 0; i < N; i++) - Append ((wxObject *) (array[i])); - - delete[]array; -} + size_t N = GetCount(); + char **array = new char *[N]; -// Checks whether s is a member of the list -bool wxStringList::Member (const char *s) const -{ - for (wxNode * node = First (); node; node = node->Next ()) + size_t i = 0; + for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() ) { - const char *s1 = (const char *) node->Data (); - if (s == s1 || strcmp (s, s1) == 0) - return TRUE; + array[i++] = node->GetData(); } - return FALSE; -} -void wxStringList::operator= (const wxStringList& list) -{ + qsort (array, N, sizeof (char *), wx_comparestrings); Clear(); - wxNode *node = list.First(); - while (node) - { - char *s = (char *) node->Data (); - Add(s); - node = node->Next(); - } -} - -char* wxStringList::operator[] (int i) const -{ - wxASSERT_MSG( (i < Number()), "Invalid index for wxStringList" ); + for (i = 0; i < N; i++) + Append (array[i]); - return (char*) (Nth(i)->Data()); + delete[]array; }