Now using hash tables to speed up cSchedule::GetEvent()

8 files changed, 153 insertions, 22 deletions

diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index cac3fb7a..7e1a22d0 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -1361,3 +1361,4 @@ Paavo Hartikainen <pahartik@sci.fi>
 Georg Acher <acher@baycom.de>
  for making tChannelID::operator==() inline for better performance
  for introducing cListBase::count for better performance
+ for a patch that was used to implement hash tables to speed up cSchedule::GetEvent()
diff --git a/HISTORY b/HISTORY
index 53861b24..1bca9213 100644
--- a/HISTORY
+++ b/HISTORY
@@ -3568,3 +3568,5 @@ Video Disk Recorder Revision History
 - Introduced cListBase::count for better performance (thanks to Georg Acher).
 - cEvent no longer stores the channelID directly, but rather has a pointer to
   the schedule it is in.
+- Now using hash tables to speed up cSchedule::GetEvent() (partially based on
+  a patch from Georg Acher).
diff --git a/eit.c b/eit.c
index d43a2013..a8ac9df2 100644
--- a/eit.c
+++ b/eit.c
@@ -8,7 +8,7 @@
  * Robert Schneider <Robert.Schneider@web.de> and Rolf Hakenes <hakenes@hippomi.de>.
  * Adapted to 'libsi' for VDR 1.3.0 by Marcel Wiesweg <marcel.wiesweg@gmx.de>.
  *
- * $Id: eit.c 1.106 2005/05/28 10:07:12 kls Exp $
+ * $Id: eit.c 1.107 2005/05/28 11:35:55 kls Exp $
  */
 
 #include "eit.h"
@@ -52,11 +52,12 @@ cEIT::cEIT(cSchedules *Schedules, int Source, u_char Tid, const u_char *Data)
       if (SiEitEvent.getStartTime() == 0 || SiEitEvent.getDuration() == 0)
          continue;
       Empty = false;
+      cEvent *newEvent = NULL;
       cEvent *pEvent = (cEvent *)pSchedule->GetEvent(SiEitEvent.getEventId(), SiEitEvent.getStartTime());
       if (!pEvent) {
          // If we don't have that event yet, we create a new one.
          // Otherwise we copy the information into the existing event anyway, because the data might have changed.
-         pEvent = pSchedule->AddEvent(new cEvent(pSchedule, SiEitEvent.getEventId()));
+         pEvent = newEvent = new cEvent(SiEitEvent.getEventId());
          if (!pEvent)
             continue;
          }
@@ -221,6 +222,9 @@ cEIT::cEIT(cSchedules *Schedules, int Source, u_char Tid, const u_char *Data)
       delete ExtendedEventDescriptors;
       delete ShortEventDescriptor;
 
+      if (newEvent)
+         pSchedule->AddEvent(newEvent);
+
       pEvent->SetComponents(Components);
 
       pEvent->FixEpgBugs();
diff --git a/epg.c b/epg.c
index 440e7fa0..841e02f2 100644
--- a/epg.c
+++ b/epg.c
@@ -7,7 +7,7 @@
  * Original version (as used in VDR before 1.3.0) written by
  * Robert Schneider <Robert.Schneider@web.de> and Rolf Hakenes <hakenes@hippomi.de>.
  *
- * $Id: epg.c 1.32 2005/05/28 10:03:39 kls Exp $
+ * $Id: epg.c 1.33 2005/05/28 13:17:20 kls Exp $
  */
 
 #include "epg.h"
@@ -81,9 +81,9 @@ void cComponents::SetComponent(int Index, uchar Stream, uchar Type, const char *
 
 // --- cEvent ----------------------------------------------------------------
 
-cEvent::cEvent(cSchedule *Schedule, u_int16_t EventID)
+cEvent::cEvent(u_int16_t EventID)
 {
-  schedule = Schedule;
+  schedule = NULL;
   eventID = EventID;
   tableID = 0;
   version = 0xFF; // actual version numbers are 0..31
@@ -119,7 +119,13 @@ tChannelID cEvent::ChannelID(void) const
 
 void cEvent::SetEventID(u_int16_t EventID)
 {
-  eventID = EventID;
+  if (eventID != EventID) {
+     if (schedule)
+        schedule->UnhashEvent(this);
+     eventID = EventID;
+     if (schedule)
+        schedule->HashEvent(this);
+     }
 }
 
 void cEvent::SetTableID(uchar TableID)
@@ -163,7 +169,13 @@ void cEvent::SetComponents(cComponents *Components)
 
 void cEvent::SetStartTime(time_t StartTime)
 {
-  startTime = StartTime;
+  if (startTime != StartTime) {
+     if (schedule)
+        schedule->UnhashEvent(this);
+     startTime = StartTime;
+     if (schedule)
+        schedule->HashEvent(this);
+     }
 }
 
 void cEvent::SetDuration(int Duration)
@@ -285,12 +297,15 @@ bool cEvent::Read(FILE *f, cSchedule *Schedule)
                           int n = sscanf(t, "%u %ld %d %X", &EventID, &StartTime, &Duration, &TableID);
                           if (n == 3 || n == 4) {
                              Event = (cEvent *)Schedule->GetEvent(EventID, StartTime);
+                             cEvent *newEvent = NULL;
                              if (!Event)
-                                Event = Schedule->AddEvent(new cEvent(Schedule, EventID));
+                                Event = newEvent = new cEvent(EventID);
                              if (Event) {
                                 Event->SetTableID(TableID);
                                 Event->SetStartTime(StartTime);
                                 Event->SetDuration(Duration);
+                                if (newEvent)
+                                   Schedule->AddEvent(newEvent);
                                 }
                              }
                           }
@@ -638,9 +653,32 @@ cSchedule::cSchedule(tChannelID ChannelID)
 cEvent *cSchedule::AddEvent(cEvent *Event)
 {
   events.Add(Event);
+  Event->schedule = this;
+  HashEvent(Event);
   return Event;
 }
 
+void cSchedule::DelEvent(cEvent *Event)
+{
+  if (Event->schedule == this) {
+     UnhashEvent(Event);
+     events.Del(Event);
+     Event->schedule = NULL;
+     }
+}
+
+void cSchedule::HashEvent(cEvent *Event)
+{
+  eventsHashID.Add(Event, Event->EventID());
+  eventsHashStartTime.Add(Event, Event->StartTime());
+}
+
+void cSchedule::UnhashEvent(cEvent *Event)
+{
+  eventsHashID.Del(Event, Event->EventID());
+  eventsHashStartTime.Del(Event, Event->StartTime());
+}
+
 const cEvent *cSchedule::GetPresentEvent(bool CheckRunningStatus) const
 {
   const cEvent *pe = NULL;
@@ -669,13 +707,9 @@ const cEvent *cSchedule::GetEvent(u_int16_t EventID, time_t StartTime) const
 {
   // Returns either the event info with the given EventID or, if that one can't
   // be found, the one with the given StartTime (or NULL if neither can be found)
-  cEvent *pt = NULL;
-  for (cEvent *pe = events.First(); pe; pe = events.Next(pe)) {
-      if (pe->EventID() == EventID)
-         return pe;
-      if (StartTime > 0 && pe->StartTime() == StartTime) // 'StartTime < 0' is apparently used with NVOD channels
-         pt = pe;
-      }
+  cEvent *pt = eventsHashID.Get(EventID);
+  if (!pt && StartTime > 0) // 'StartTime < 0' is apparently used with NVOD channels
+     pt = eventsHashStartTime.Get(StartTime);
   return pt;
 }
 
@@ -742,7 +776,7 @@ void cSchedule::Cleanup(time_t Time)
       if (!Event)
          break;
       if (!Event->HasTimer() && Event->EndTime() + Setup.EPGLinger * 60 + 3600 < Time) { // adding one hour for safety
-         events.Del(Event);
+         DelEvent(Event);
          a--;
          }
       }
diff --git a/epg.h b/epg.h
index 1b65e637..83ae0d21 100644
--- a/epg.h
+++ b/epg.h
@@ -7,7 +7,7 @@
  * Original version (as used in VDR before 1.3.0) written by
  * Robert Schneider <Robert.Schneider@web.de> and Rolf Hakenes <hakenes@hippomi.de>.
  *
- * $Id: epg.h 1.24 2005/05/28 10:00:12 kls Exp $
+ * $Id: epg.h 1.25 2005/05/28 11:32:36 kls Exp $
  */
 
 #ifndef __EPG_H
@@ -47,6 +47,7 @@ public:
 class cSchedule;
 
 class cEvent : public cListObject {
+  friend class cSchedule;
 private:
   cSchedule *schedule;     // The Schedule this event belongs to
   u_int16_t eventID;       // Event ID of this event
@@ -62,7 +63,7 @@ private:
   time_t vps;              // Video Programming Service timestamp (VPS, aka "Programme Identification Label", PIL)
   time_t seen;             // When this event was last seen in the data stream
 public:
-  cEvent(cSchedule *Schedule, u_int16_t EventID);
+  cEvent(u_int16_t EventID);
   ~cEvent();
   virtual int Compare(const cListObject &ListObject) const;
   tChannelID ChannelID(void) const;
@@ -110,6 +111,8 @@ class cSchedule : public cListObject  {
 private:
   tChannelID channelID;
   cList<cEvent> events;
+  cHash<cEvent> eventsHashID;
+  cHash<cEvent> eventsHashStartTime;
   bool hasRunning;
   time_t modified;
   time_t presentSeen;
@@ -128,6 +131,9 @@ public:
   void Cleanup(time_t Time);
   void Cleanup(void);
   cEvent *AddEvent(cEvent *Event);
+  void DelEvent(cEvent *Event);
+  void cSchedule::HashEvent(cEvent *Event);
+  void cSchedule::UnhashEvent(cEvent *Event);
   const cList<cEvent> *Events(void) const { return &events; }
   const cEvent *GetPresentEvent(bool CheckRunningStatus = false) const;
   const cEvent *GetFollowingEvent(bool CheckRunningStatus = false) const;
diff --git a/recording.c b/recording.c
index cefbef02..8ee26c8a 100644
--- a/recording.c
+++ b/recording.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: recording.c 1.105 2005/05/28 10:04:24 kls Exp $
+ * $Id: recording.c 1.106 2005/05/28 11:36:14 kls Exp $
  */
 
 #include "recording.h"
@@ -228,7 +228,7 @@ cRecordingInfo::cRecordingInfo(const cEvent *Event)
      ownEvent = NULL;
      }
   else
-     event = ownEvent = new cEvent(NULL, 0);
+     event = ownEvent = new cEvent(0);
 }
 
 cRecordingInfo::~cRecordingInfo()
diff --git a/tools.c b/tools.c
index 9e1ea1d0..58028398 100644
--- a/tools.c
+++ b/tools.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: tools.c 1.93 2005/05/26 11:40:14 kls Exp $
+ * $Id: tools.c 1.94 2005/05/28 11:46:44 kls Exp $
  */
 
 #include "tools.h"
@@ -1060,3 +1060,55 @@ void cListBase::Sort(void)
       }
 }
 
+// --- cHashBase -------------------------------------------------------------
+
+cHashBase::cHashBase(int Size)
+{
+  size = Size;
+  hashTable = (cList<cHashObject>**)calloc(size, sizeof(cList<cHashObject>*));
+}
+
+cHashBase::~cHashBase(void)
+{
+  for (int i = 0; i < size; i++)
+      delete hashTable[i];
+  free(hashTable);
+}
+
+void cHashBase::Add(cListObject *Object, int Id)
+{
+  int hash = hashfn(Id);
+  if (!hashTable[hash])
+     hashTable[hash] = new cList<cHashObject>;
+  hashTable[hash]->Add(new cHashObject(Object, Id));
+}
+
+void cHashBase::Del(cListObject *Object, int Id)
+{
+  cList<cHashObject> *list = hashTable[hashfn(Id)];
+  if (list) {
+     for (cHashObject *hob = list->First(); hob; hob = list->Next(hob)) {
+         if (hob->object == Object) {
+            list->Del(hob);
+            break;
+            }
+         }
+     }
+}
+
+cListObject *cHashBase::Get(int Id) const
+{
+  cList<cHashObject> *list = hashTable[hashfn(Id)];
+  if (list) {
+     for (cHashObject *hob = list->First(); hob; hob = list->Next(hob)) {
+         if (hob->id == Id)
+            return hob->object;
+         }
+     }
+  return NULL;
+}
+
+cList<cHashObject> *cHashBase::GetList(int Id) const
+{
+  return hashTable[hashfn(Id)];
+}
diff --git a/tools.h b/tools.h
index a45facbf..2c1f2a13 100644
--- a/tools.h
+++ b/tools.h
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: tools.h 1.70 2005/05/26 11:34:01 kls Exp $
+ * $Id: tools.h 1.71 2005/05/28 11:24:49 kls Exp $
  */
 
 #ifndef __TOOLS_H
@@ -236,4 +236,36 @@ public:
   T *Next(const T *object) const { return (T *)object->cListObject::Next(); } // avoid ambiguities in case of a "list of lists"
   };
 
+class cHashObject : public cListObject {
+  friend class cHashBase;
+private:
+  int id;
+  cListObject *object;
+public:
+  cHashObject(cListObject *Object, int Id) { object = Object; id = Id; }
+  };
+
+class cHashBase {
+private:
+  cList<cHashObject> **hashTable;
+  int size;
+  int hashfn(int Id) const { return Id % size; }
+protected:
+  cHashBase(int Size);
+public:
+  virtual ~cHashBase();
+  void Add(cListObject *Object, int Id);
+  void Del(cListObject *Object, int Id);
+  cListObject *Get(int Id) const;
+  cList<cHashObject> *GetList(int Id) const;
+  };
+
+#define HASHSIZE 512
+
+template<class T> class cHash : public cHashBase {
+public:
+  cHash(int Size = HASHSIZE) : cHashBase(Size) {}
+  T *Get(int Id) const { return (T *)cHashBase::Get(Id); }
+};
+
 #endif //__TOOLS_H