From b5a98acdf25b3d2eae7858d30ac29f629d589703 Mon Sep 17 00:00:00 2001 From: Vadim Zeitlin Date: Thu, 17 Jul 2003 23:59:49 +0000 Subject: [PATCH] applied event speed up patch (752928) git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@22067 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- docs/changes.txt | 1 + include/wx/event.h | 70 +++++++++++++- src/common/event.cpp | 211 +++++++++++++++++++++++++++++++++++++++---- 3 files changed, 260 insertions(+), 22 deletions(-) diff --git a/docs/changes.txt b/docs/changes.txt index 8510ea0e2d..de110c9810 100644 --- a/docs/changes.txt +++ b/docs/changes.txt @@ -122,6 +122,7 @@ All GUI ports: styles for use with conservative idle and update event modes. - wxMSW and wxGTK now send menu update events only when a menu is about to be used. +- improved event processing performance (Hans Van Leemputten) Unix: diff --git a/include/wx/event.h b/include/wx/event.h index 809db844b7..a6850785f4 100644 --- a/include/wx/event.h +++ b/include/wx/event.h @@ -27,6 +27,8 @@ #include "wx/thread.h" +#include "wx/dynarray.h" + // ---------------------------------------------------------------------------- // forward declarations // ---------------------------------------------------------------------------- @@ -86,6 +88,8 @@ typedef int wxEventType; #define DECLARE_EVENT_TABLE_ENTRY(type, winid, idLast, fn, obj) \ wxEventTableEntry(type, winid, idLast, fn, obj) +#define EMPTY_PARAMETER_VALUE /* Fake macro parameter value */ + #define BEGIN_DECLARE_EVENT_TYPES() #define END_DECLARE_EVENT_TYPES() #define DECLARE_EXPORTED_EVENT_TYPE(expdecl, name, value) \ @@ -93,7 +97,7 @@ typedef int wxEventType; #define DECLARE_EVENT_TYPE(name, value) \ DECLARE_EXPORTED_EVENT_TYPE(WXDLLIMPEXP_CORE, name, value) #define DECLARE_LOCAL_EVENT_TYPE(name, value) \ - DECLARE_EXPORTED_EVENT_TYPE(/* */, name, value) + DECLARE_EXPORTED_EVENT_TYPE(EMPTY_PARAMETER_VALUE, name, value) #define DEFINE_EVENT_TYPE(name) const wxEventType name = wxNewEventType(); #define DEFINE_LOCAL_EVENT_TYPE(name) DEFINE_EVENT_TYPE(name) @@ -2082,6 +2086,56 @@ struct WXDLLIMPEXP_BASE wxEventTable const wxEventTableEntry *entries; // bottom of entry array }; +// ---------------------------------------------------------------------------- +// wxEventHashTable: a helper of wxEvtHandler to speed up wxEventTable lookups. +// ---------------------------------------------------------------------------- + +WX_DEFINE_ARRAY(const wxEventTableEntry*, wxEventTableEntryPointerArray); +class WXDLLIMPEXP_BASE wxEvtHandler; + +class WXDLLIMPEXP_BASE wxEventHashTable +{ +private: + // Internal data structs + struct EventTypeTable + { + wxEventType eventType; + wxEventTableEntryPointerArray eventEntryTable; + }; + typedef EventTypeTable* EventTypeTablePointer; + +public: + // Constructor, needs the event table it needs to hash later on. + // Note: hashing of the event table is not done in the constructor as it + // can be that the event table is not yet full initialize, the hash + // will gets initialized when handling the first event look-up request. + wxEventHashTable(const wxEventTable &table); + // Destructor. + ~wxEventHashTable(); + + // Handle the given event, in other words search the event table hash + // and call self->ProcessEvent() if a match was found. + bool HandleEvent(wxEvent &event, wxEvtHandler *self); + +protected: + // Init the hash table with the entries of the static event table. + void InitHashTable(); + // Helper funtion of InitHashTable() to insert 1 entry into the hash table. + void AddEntry(const wxEventTableEntry &entry); + // Allocate and init with null pointers the base hash table. + void AllocEventTypeTable(size_t size); + // Grow the hash table in size and transfer all items currently + // in the table to the correct location in the new table. + void GrowEventTypeTable(); + +protected: + const wxEventTable &m_table; + bool m_rebuildHash; + + size_t m_size; + EventTypeTablePointer *m_eventTypeTable; +}; + // ---------------------------------------------------------------------------- // wxEvtHandler: the base class for all objects handling wxWindows events // ---------------------------------------------------------------------------- @@ -2201,10 +2255,12 @@ protected: virtual bool TryParent(wxEvent& event); - static const wxEventTable sm_eventTable; - + static const wxEventTable sm_eventTable; virtual const wxEventTable *GetEventTable() const; + static wxEventHashTable sm_eventHashTable; + virtual wxEventHashTable& GetEventHashTable() const; + wxEvtHandler* m_nextHandler; wxEvtHandler* m_previousHandler; wxList* m_dynamicEvents; @@ -2303,16 +2359,22 @@ typedef void (wxEvtHandler::*wxMouseCaptureChangedEventFunction)(wxMouseCaptureC static const wxEventTableEntry sm_eventTableEntries[]; \ protected: \ static const wxEventTable sm_eventTable; \ - virtual const wxEventTable* GetEventTable() const; + virtual const wxEventTable* GetEventTable() const; \ + static wxEventHashTable sm_eventHashTable; \ + virtual wxEventHashTable& GetEventHashTable() const; // N.B.: when building DLL with Borland C++ 5.5 compiler, you must initialize // sm_eventTable before using it in GetEventTable() or the compiler gives // E2233 (see http://groups.google.com/groups?selm=397dcc8a%241_2%40dnews) + #define BEGIN_EVENT_TABLE(theClass, baseClass) \ const wxEventTable theClass::sm_eventTable = \ { &baseClass::sm_eventTable, &theClass::sm_eventTableEntries[0] }; \ const wxEventTable *theClass::GetEventTable() const \ { return &theClass::sm_eventTable; } \ + wxEventHashTable theClass::sm_eventHashTable(theClass::sm_eventTable); \ + wxEventHashTable &theClass::GetEventHashTable() const \ + { return theClass::sm_eventHashTable; } \ const wxEventTableEntry theClass::sm_eventTableEntries[] = { \ #define END_EVENT_TABLE() DECLARE_EVENT_TABLE_ENTRY( wxEVT_NULL, 0, 0, 0, 0 ) }; diff --git a/src/common/event.cpp b/src/common/event.cpp index ee22ca1062..083e52a709 100644 --- a/src/common/event.cpp +++ b/src/common/event.cpp @@ -104,6 +104,11 @@ const wxEventTable *wxEvtHandler::GetEventTable() const const wxEventTable wxEvtHandler::sm_eventTable = { (const wxEventTable *)NULL, &wxEvtHandler::sm_eventTableEntries[0] }; +wxEventHashTable &wxEvtHandler::GetEventHashTable() const + { return wxEvtHandler::sm_eventHashTable; } + +wxEventHashTable wxEvtHandler::sm_eventHashTable(wxEvtHandler::sm_eventTable); + const wxEventTableEntry wxEvtHandler::sm_eventTableEntries[] = { DECLARE_EVENT_TABLE_ENTRY(wxEVT_NULL, 0, 0, (wxObjectEventFunction)NULL, NULL) }; @@ -123,7 +128,7 @@ wxList *wxPendingEvents = (wxList *)NULL; // common event types are defined here, other event types are defined by the // components which use them - + const wxEventType wxEVT_FIRST = 10000; const wxEventType wxEVT_USER_FIRST = wxEVT_FIRST + 2000; @@ -358,13 +363,12 @@ wxEvent::wxEvent(const wxEvent &src) */ wxCommandEvent::wxCommandEvent(wxEventType commandType, int theId) - : wxEvent(theId, commandType) + : wxEvent(theId, commandType) { m_clientData = (char *) NULL; m_clientObject = (wxClientData *) NULL; m_extraLong = 0; m_commandInt = 0; - m_commandString = wxEmptyString; m_isCommandEvent = TRUE; } @@ -389,7 +393,7 @@ bool wxUpdateUIEvent::CanUpdate(wxWindow* win) (GetMode() == wxUPDATE_UI_PROCESS_SPECIFIED && ((win->GetExtraStyle() & wxWS_EX_PROCESS_UI_UPDATES) == 0))) return FALSE; - + if (sm_updateInterval == -1) return FALSE; else if (sm_updateInterval == 0) @@ -404,7 +408,7 @@ bool wxUpdateUIEvent::CanUpdate(wxWindow* win) } #else // If we don't have wxStopWatch or wxLongLong, we - // should err on the safe side and update now anyway. + // should err on the safe side and update now anyway. return TRUE; #endif } @@ -430,7 +434,7 @@ void wxUpdateUIEvent::ResetUpdateTime() /* * Idle events */ - + wxIdleMode wxIdleEvent::sm_idleMode = wxIDLE_PROCESS_ALL; // Can we send an idle event? @@ -442,7 +446,7 @@ bool wxIdleEvent::CanSend(wxWindow* win) (GetMode() == wxIDLE_PROCESS_SPECIFIED && ((win->GetExtraStyle() & wxWS_EX_PROCESS_IDLE) == 0))) return FALSE; - + return TRUE; } @@ -704,6 +708,182 @@ wxChildFocusEvent::wxChildFocusEvent(wxWindow *win) #endif // wxUSE_GUI +// ---------------------------------------------------------------------------- +// wxEventHashTable +// ---------------------------------------------------------------------------- + +static const int EVENT_TYPE_TABLE_INIT_SIZE = 31; // Not to big not to small... + +wxEventHashTable::wxEventHashTable(const wxEventTable &table) + : m_table(table), + m_rebuildHash(TRUE) +{ + AllocEventTypeTable(EVENT_TYPE_TABLE_INIT_SIZE); +} + +wxEventHashTable::~wxEventHashTable() +{ + size_t i; + for(i = 0; i < m_size; i++) + { + EventTypeTablePointer eTTnode = m_eventTypeTable[i]; + if (eTTnode) + { + delete eTTnode; + } + } + + delete[] m_eventTypeTable; +} + +bool wxEventHashTable::HandleEvent(wxEvent &event, wxEvtHandler *self) +{ + if (m_rebuildHash) + { + InitHashTable(); + m_rebuildHash = FALSE; + } + + // Find all entries for the given event type. + wxEventType eventType = event.GetEventType(); + const EventTypeTablePointer eTTnode = m_eventTypeTable[eventType % m_size]; + if (eTTnode && eTTnode->eventType == eventType) + { + // Now start the search for an event handler + // that can handle an event with the given ID. + int eventId = event.GetId(); + const wxEventTableEntryPointerArray &eventEntryTable = eTTnode->eventEntryTable; + + size_t n; + size_t count = eventEntryTable.GetCount(); + for (n = 0; n < count; n++) + { + const wxEventTableEntry* entry = eventEntryTable[n]; + int tableId1 = entry->m_id, + tableId2 = entry->m_lastId; + + if ((tableId1 == -1) || + (tableId2 == -1 && tableId1 == eventId) || + (tableId2 != -1 && + (eventId >= tableId1 && eventId <= tableId2))) + { + event.Skip(FALSE); + event.m_callbackUserData = entry->m_callbackUserData; + + (self->*((wxEventFunction) (entry->m_fn)))(event); + + if (!event.GetSkipped()) + return TRUE; + } + } + + return FALSE; + } + + return FALSE; +} + +void wxEventHashTable::InitHashTable() +{ + // Loop over the event tables and all its base tables. + const wxEventTable *table = &m_table; + while (table) + { + // Retrieve all valid event handler entries + const wxEventTableEntry *entry = table->entries; + while (entry->m_fn != 0) + { + // Add the event entry in the Hash. + AddEntry(*entry); + + entry++; + } + + table = table->baseTable; + } + + // Lets free some memory. + size_t i; + for(i = 0; i < m_size; i++) + { + EventTypeTablePointer eTTnode = m_eventTypeTable[i]; + if (eTTnode) + { + eTTnode->eventEntryTable.Shrink(); + } + } +} + +void wxEventHashTable::AddEntry(const wxEventTableEntry &entry) +{ + EventTypeTablePointer *peTTnode = &m_eventTypeTable[entry.m_eventType % m_size]; + EventTypeTablePointer eTTnode = *peTTnode; + + if (eTTnode) + { + if (eTTnode->eventType != entry.m_eventType) + { + // Resize the table! + GrowEventTypeTable(); + // Try again to add it. + AddEntry(entry); + return; + } + } + else + { + eTTnode = new EventTypeTable; + eTTnode->eventType = entry.m_eventType; + *peTTnode = eTTnode; + } + + // Fill all hash entries between entry.m_id and entry.m_lastId... + eTTnode->eventEntryTable.Add(&entry); +} + +void wxEventHashTable::AllocEventTypeTable(size_t size) +{ + m_eventTypeTable = new EventTypeTablePointer[size]; + memset((void *)m_eventTypeTable, 0, sizeof(EventTypeTablePointer)*size); + m_size = size; +} + +void wxEventHashTable::GrowEventTypeTable() +{ + size_t oldSize = m_size; + EventTypeTablePointer *oldEventTypeTable = m_eventTypeTable; + + // TODO: Search the most optimal grow sequence + AllocEventTypeTable(/* GetNextPrime(oldSize) */oldSize*2+1); + + for ( size_t i = 0; i < oldSize; /* */ ) + { + EventTypeTablePointer eTToldNode = oldEventTypeTable[i]; + if (eTToldNode) + { + EventTypeTablePointer *peTTnode = &m_eventTypeTable[eTToldNode->eventType % m_size]; + EventTypeTablePointer eTTnode = *peTTnode; + + // Check for collision, we don't want any. + if (eTTnode) + { + GrowEventTypeTable(); + continue; // Don't increment the counter, + // as we still need to add this element. + } + else + { + // Get the old value and put it in the new table. + *peTTnode = oldEventTypeTable[i]; + } + } + + i++; + } + + delete[] oldEventTypeTable; +} + // ---------------------------------------------------------------------------- // wxEvtHandler // ---------------------------------------------------------------------------- @@ -765,7 +945,7 @@ wxEvtHandler::~wxEvtHandler() # if !defined(__VISAGECPP__) delete m_eventsLocker; # endif - + // Remove us from wxPendingEvents if necessary. if(wxPendingEventsLocker) wxENTER_CRIT_SECT(*wxPendingEventsLocker); @@ -930,15 +1110,9 @@ bool wxEvtHandler::ProcessEvent(wxEvent& event) if ( m_dynamicEvents && SearchDynamicEventTable(event) ) return TRUE; - // Then static per-class event tables (and search upwards through the - // inheritance hierarchy) - for ( const wxEventTable *table = GetEventTable(); - table; - table = table->baseTable ) - { - if ( SearchEventTable((wxEventTable&)*table, event) ) - return TRUE; - } + // Then static per-class event tables + if ( GetEventHashTable().HandleEvent(event, this) ) + return TRUE; } // Try going down the event handler chain @@ -953,6 +1127,7 @@ bool wxEvtHandler::ProcessEvent(wxEvent& event) return TryParent(event); } + bool wxEvtHandler::SearchEventTable(wxEventTable& table, wxEvent& event) { wxEventType eventType = event.GetEventType(); @@ -1089,7 +1264,7 @@ bool wxEvtHandler::SearchDynamicEventTable( wxEvent& event ) if (entry->m_eventSink) ((entry->m_eventSink)->*((wxEventFunction) (entry->m_fn)))(event); else -#endif +#endif (this->*((wxEventFunction) (entry->m_fn)))(event); if ( ! event.GetSkipped() ) -- 2.45.2