Now using qsort() to sort cListBase lists

13 files changed, 95 insertions, 74 deletions

diff --git a/HISTORY b/HISTORY
index b95b8a04..6ae727c6 100644
--- a/HISTORY
+++ b/HISTORY
@@ -3078,7 +3078,7 @@ Video Disk Recorder Revision History
   This avoids shortly seeing the wrong events in the channel display when
   switching to a channel that hasn't been tuned to in a while.
 
-2004-10-31: Version 1.3.15
+2004-11-01: Version 1.3.15
 
 - Fixed some typos in the Makefile's 'font' target (thanks to Uwe Hanke).
 - Added more checks and polling when getting frontend events (based on a patch
@@ -3105,3 +3105,7 @@ Video Disk Recorder Revision History
   swapped (see man vdr(5)).
 - Added the 'portal name' to cChannels (thanks to Marco Schlüßler).
 - Fixed handling key codes that start with 0x1B in the KBD remote control code.
+- Now using qsort() to sort cListBase lists. For this, the virtual function
+  cListObject::operator<() has been replaced with cListObject::Compare().
+  Plugins that implement derived cListObject classes may need to adjust their
+  code.
diff --git a/config.c b/config.c
index ef362f6d..36ecb126 100644
--- a/config.c
+++ b/config.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: config.c 1.127 2004/05/16 12:43:55 kls Exp $
+ * $Id: config.c 1.128 2004/10/31 16:17:39 kls Exp $
  */
 
 #include "config.h"
@@ -193,19 +193,19 @@ cSetupLine::~cSetupLine()
   free(value);
 }
 
-bool cSetupLine::operator< (const cListObject &ListObject)
+int cSetupLine::Compare(const cListObject &ListObject) const
 {
   const cSetupLine *sl = (cSetupLine *)&ListObject;
   if (!plugin && !sl->plugin)
-     return strcasecmp(name, sl->name) < 0;
+     return strcasecmp(name, sl->name);
   if (!plugin)
-     return true;
+     return -1;
   if (!sl->plugin)
-     return false;
+     return 1;
   int result = strcasecmp(plugin, sl->plugin);
   if (result == 0)
      result = strcasecmp(name, sl->name);
-  return result < 0;
+  return result;
 }
 
 bool cSetupLine::Parse(char *s)
diff --git a/config.h b/config.h
index 0666de09..bc9052ae 100644
--- a/config.h
+++ b/config.h
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: config.h 1.202 2004/10/30 11:52:41 kls Exp $
+ * $Id: config.h 1.203 2004/10/31 16:17:02 kls Exp $
  */
 
 #ifndef __CONFIG_H
@@ -185,7 +185,7 @@ public:
   cSetupLine(void);
   cSetupLine(const char *Name, const char *Value, const char *Plugin = NULL);
   virtual ~cSetupLine();
-  virtual bool operator< (const cListObject &ListObject);
+  virtual int Compare(const cListObject &ListObject) const;
   const char *Plugin(void) { return plugin; }
   const char *Name(void) { return name; }
   const char *Value(void) { return value; }
diff --git a/eitscan.c b/eitscan.c
index 4e2bb426..a1bff662 100644
--- a/eitscan.c
+++ b/eitscan.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: eitscan.c 1.22 2004/04/16 13:33:34 kls Exp $
+ * $Id: eitscan.c 1.23 2004/10/31 16:19:49 kls Exp $
  */
 
 #include "eitscan.h"
@@ -20,10 +20,10 @@ private:
   cChannel channel;
 public:
   cScanData(const cChannel *Channel);
-  virtual bool operator< (const cListObject &ListObject);
-  int Source(void) { return channel.Source(); }
-  int Transponder(void) { return channel.Transponder(); }
-  const cChannel *GetChannel(void) { return &channel; }
+  virtual int Compare(const cListObject &ListObject) const;
+  int Source(void) const { return channel.Source(); }
+  int Transponder(void) const { return channel.Transponder(); }
+  const cChannel *GetChannel(void) const { return &channel; }
   };
 
 cScanData::cScanData(const cChannel *Channel)
@@ -31,10 +31,13 @@ cScanData::cScanData(const cChannel *Channel)
   channel = *Channel;
 }
 
-bool cScanData::operator< (const cListObject &ListObject)
+int cScanData::Compare(const cListObject &ListObject) const
 {
-  cScanData *sd = (cScanData *)&ListObject;
-  return Source() < sd->Source() || Source() == sd->Source() && Transponder() < sd->Transponder();
+  const cScanData *sd = (const cScanData *)&ListObject;
+  int r = Source() - sd->Source();
+  if (r == 0)
+     r = Transponder() - sd->Transponder();
+  return r;
 }
 
 // --- cScanList -------------------------------------------------------------
diff --git a/epg.c b/epg.c
index 39b029e5..ffd61a43 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.20 2004/10/24 15:01:50 kls Exp $
+ * $Id: epg.c 1.21 2004/10/31 16:12:36 kls Exp $
  */
 
 #include "epg.h"
@@ -40,10 +40,10 @@ cEvent::~cEvent()
   free(description);
 }
 
-bool cEvent::operator< (const cListObject &ListObject)
+int cEvent::Compare(const cListObject &ListObject) const
 {
   cEvent *e = (cEvent *)&ListObject;
-  return startTime < e->startTime;
+  return startTime - e->startTime;
 }
 
 void cEvent::SetEventID(u_int16_t EventID)
diff --git a/epg.h b/epg.h
index 6c31049d..3268b17c 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.16 2004/10/24 13:56:00 kls Exp $
+ * $Id: epg.h 1.17 2004/10/31 16:17:10 kls Exp $
  */
 
 #ifndef __EPG_H
@@ -40,7 +40,7 @@ private:
 public:
   cEvent(tChannelID ChannelID, u_int16_t EventID);
   ~cEvent();
-  virtual bool operator< (const cListObject &ListObject);
+  virtual int Compare(const cListObject &ListObject) const;
   tChannelID ChannelID(void) const { return channelID; }
   u_int16_t EventID(void) const { return eventID; }
   uchar TableID(void) const { return tableID; }
diff --git a/menu.c b/menu.c
index f15144e9..5ebf5183 100644
--- a/menu.c
+++ b/menu.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: menu.c 1.317 2004/10/31 12:53:00 kls Exp $
+ * $Id: menu.c 1.318 2004/11/01 10:40:38 kls Exp $
  */
 
 #include "menu.h"
@@ -667,7 +667,7 @@ private:
   cTimer *timer;
 public:
   cMenuTimerItem(cTimer *Timer);
-  virtual bool operator< (const cListObject &ListObject);
+  virtual int Compare(const cListObject &ListObject) const;
   virtual void Set(void);
   cTimer *Timer(void) { return timer; }
   };
@@ -678,9 +678,9 @@ cMenuTimerItem::cMenuTimerItem(cTimer *Timer)
   Set();
 }
 
-bool cMenuTimerItem::operator< (const cListObject &ListObject)
+int cMenuTimerItem::Compare(const cListObject &ListObject) const
 {
-  return *timer < *((cMenuTimerItem *)&ListObject)->timer;
+  return timer->Compare(*((cMenuTimerItem *)&ListObject)->timer);
 }
 
 void cMenuTimerItem::Set(void)
diff --git a/recording.c b/recording.c
index 5cb06571..e21ccae2 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.90 2004/10/31 10:09:36 kls Exp $
+ * $Id: recording.c 1.91 2004/10/31 16:22:33 kls Exp $
  */
 
 #include "recording.h"
@@ -451,7 +451,7 @@ char *cRecording::StripEpisodeName(char *s)
   return s;
 }
 
-char *cRecording::SortName(void)
+char *cRecording::SortName(void) const
 {
   if (!sortBuffer) {
      char *s = StripEpisodeName(strdup(FileName() + strlen(VideoDirectory) + 1));
@@ -472,10 +472,10 @@ int cRecording::GetResume(void) const
   return resume;
 }
 
-bool cRecording::operator< (const cListObject &ListObject)
+int cRecording::Compare(const cListObject &ListObject) const
 {
   cRecording *r = (cRecording *)&ListObject;
-  return strcasecmp(SortName(), r->SortName()) < 0;
+  return strcasecmp(SortName(), r->SortName());
 }
 
 const char *cRecording::FileName(void) const
diff --git a/recording.h b/recording.h
index 88b90d3b..184f49ef 100644
--- a/recording.h
+++ b/recording.h
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: recording.h 1.31 2004/07/17 11:09:49 kls Exp $
+ * $Id: recording.h 1.32 2004/10/31 16:24:38 kls Exp $
  */
 
 #ifndef __RECORDING_H
@@ -36,12 +36,12 @@ class cRecording : public cListObject {
 private:
   mutable int resume;
   mutable char *titleBuffer;
-  char *sortBuffer;
+  mutable char *sortBuffer;
   mutable char *fileName;
   mutable char *name;
   char *summary;
-  char *StripEpisodeName(char *s);
-  char *SortName(void);
+  static char *StripEpisodeName(char *s);
+  char *SortName(void) const;
   int GetResume(void) const;
 public:
   time_t start;
@@ -50,7 +50,7 @@ public:
   cRecording(cTimer *Timer, const char *Title, const char *Subtitle, const char *Summary);
   cRecording(const char *FileName);
   ~cRecording();
-  virtual bool operator< (const cListObject &ListObject);
+  virtual int Compare(const cListObject &ListObject) const;
   const char *Name(void) const { return name; }
   const char *FileName(void) const;
   const char *Title(char Delimiter = ' ', bool NewIndicator = false, int Level = -1) const;
diff --git a/timers.c b/timers.c
index 20391d3a..38fbf394 100644
--- a/timers.c
+++ b/timers.c
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: timers.c 1.15 2004/10/31 10:07:43 kls Exp $
+ * $Id: timers.c 1.16 2004/10/31 16:41:30 kls Exp $
  */
 
 #include "timers.h"
@@ -95,12 +95,15 @@ cTimer& cTimer::operator= (const cTimer &Timer)
   return *this;
 }
 
-bool cTimer::operator< (const cListObject &ListObject)
+int cTimer::Compare(const cListObject &ListObject) const
 {
   cTimer *ti = (cTimer *)&ListObject;
   time_t t1 = StartTime();
   time_t t2 = ti->StartTime();
-  return t1 < t2 || (t1 == t2 && priority > ti->priority);
+  int r = t1 - t2;
+  if (r == 0)
+     r = ti->priority - priority;
+  return r;
 }
 
 const char *cTimer::ToText(bool UseChannelID)
@@ -248,25 +251,25 @@ bool cTimer::Save(FILE *f)
   return fprintf(f, ToText(true)) > 0;
 }
 
-bool cTimer::IsSingleEvent(void)
+bool cTimer::IsSingleEvent(void) const
 {
   return (day & 0x80000000) == 0;
 }
 
-int cTimer::GetMDay(time_t t)
+int cTimer::GetMDay(time_t t) const
 {
   struct tm tm_r;
   return localtime_r(&t, &tm_r)->tm_mday;
 }
 
-int cTimer::GetWDay(time_t t)
+int cTimer::GetWDay(time_t t) const
 {
   struct tm tm_r;
   int weekday = localtime_r(&t, &tm_r)->tm_wday;
   return weekday == 0 ? 6 : weekday - 1; // we start with monday==0!
 }
 
-bool cTimer::DayMatches(time_t t)
+bool cTimer::DayMatches(time_t t) const
 {
   return IsSingleEvent() ? GetMDay(t) == day : (day & (1 << GetWDay(t))) != 0;
 }
@@ -301,7 +304,7 @@ char *cTimer::SetFile(const char *File)
   return file;
 }
 
-bool cTimer::Matches(time_t t, bool Directly)
+bool cTimer::Matches(time_t t, bool Directly) const
 {
   startTime = stopTime = 0;
   if (t == 0)
@@ -363,14 +366,14 @@ int cTimer::Matches(const cEvent *Event)
   return tmNone;
 }
 
-time_t cTimer::StartTime(void)
+time_t cTimer::StartTime(void) const
 {
   if (!startTime)
      Matches();
   return startTime;
 }
 
-time_t cTimer::StopTime(void)
+time_t cTimer::StopTime(void) const
 {
   if (!stopTime)
      Matches();
@@ -425,7 +428,7 @@ void cTimer::InvFlags(int Flags)
   flags ^= Flags;
 }
 
-bool cTimer::HasFlags(int Flags)
+bool cTimer::HasFlags(int Flags) const
 {
   return (flags & Flags) == Flags;
 }
@@ -506,7 +509,7 @@ cTimer *cTimers::GetNextActiveTimer(void)
 {
   cTimer *t0 = NULL;
   for (cTimer *ti = First(); ti; ti = Next(ti)) {
-      if ((ti->HasFlags(tfActive)) && (!t0 || *ti < *t0))
+      if ((ti->HasFlags(tfActive)) && (!t0 || ti->Compare(*t0) < 0))
          t0 = ti;
       }
   return t0;
diff --git a/timers.h b/timers.h
index 03ff4b01..24f54adf 100644
--- a/timers.h
+++ b/timers.h
@@ -4,7 +4,7 @@
  * See the main source file 'vdr.c' for copyright information and
  * how to reach the author.
  *
- * $Id: timers.h 1.9 2004/10/31 10:06:54 kls Exp $
+ * $Id: timers.h 1.10 2004/10/31 16:41:17 kls Exp $
  */
 
 #ifndef __TIMERS_H
@@ -26,7 +26,7 @@ enum eTimerMatch { tmNone, tmPartial, tmFull };
 class cTimer : public cListObject {
   friend class cMenuEditTimer;
 private:
-  time_t startTime, stopTime;
+  mutable time_t startTime, stopTime;
   static char *buffer;
   bool recording, pending, inVpsMargin;
   int flags;
@@ -37,7 +37,7 @@ private:
   int priority;
   int lifetime;
   char file[MaxFileName];
-  time_t firstday;
+  mutable time_t firstday;
   char *summary;
   const cEvent *event;
 public:
@@ -45,7 +45,7 @@ public:
   cTimer(const cEvent *Event);
   virtual ~cTimer();
   cTimer& operator= (const cTimer &Timer);
-  virtual bool operator< (const cListObject &ListObject);
+  virtual int Compare(const cListObject &ListObject) const;
   bool Recording(void) { return recording; }
   bool Pending(void) { return pending; }
   bool InVpsMargin(void) { return inVpsMargin; }
@@ -63,17 +63,17 @@ public:
   const cEvent *Event(void) { return event; }
   bool Parse(const char *s);
   bool Save(FILE *f);
-  bool IsSingleEvent(void);
-  int GetMDay(time_t t);
-  int GetWDay(time_t t);
-  bool DayMatches(time_t t);
+  bool IsSingleEvent(void) const;
+  int GetMDay(time_t t) const;
+  int GetWDay(time_t t) const;
+  bool DayMatches(time_t t) const;
   static time_t IncDay(time_t t, int Days);
   static time_t SetTime(time_t t, int SecondsFromMidnight);
   char *SetFile(const char *File);
-  bool Matches(time_t t = 0, bool Directly = false);
+  bool Matches(time_t t = 0, bool Directly = false) const;
   int Matches(const cEvent *Event);
-  time_t StartTime(void);
-  time_t StopTime(void);
+  time_t StartTime(void) const;
+  time_t StopTime(void) const;
   void SetEvent(const cEvent *Event);
   void SetRecording(bool Recording);
   void SetPending(bool Pending);
@@ -81,7 +81,7 @@ public:
   void SetFlags(int Flags);
   void ClrFlags(int Flags);
   void InvFlags(int Flags);
-  bool HasFlags(int Flags);
+  bool HasFlags(int Flags) const;
   void Skip(void);
   void OnOff(void);
   const char *PrintFirstDay(void);
diff --git a/tools.c b/tools.c
index 0f42182e..ecb57c31 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.80 2004/06/13 14:36:41 kls Exp $
+ * $Id: tools.c 1.81 2004/10/31 16:42:36 kls Exp $
  */
 
 #include "tools.h"
@@ -939,19 +939,28 @@ int cListBase::Count(void) const
   return n;
 }
 
+static int CompareListObjects(const void *a, const void *b)
+{
+  const cListObject *la = *(const cListObject **)a;
+  const cListObject *lb = *(const cListObject **)b;
+  return la->Compare(*lb);
+}
+
 void cListBase::Sort(void)
 {
-  bool swapped;
-  do {
-     swapped = false;
-     cListObject *object = objects;
-     while (object) {
-           if (object->Next() && *object->Next() < *object) {
-              Move(object->Next(), object);
-              swapped = true;
-              }
-           object = object->Next();
-           }
-     } while (swapped);
+  int n = Count();
+  cListObject *a[n];
+  cListObject *object = objects;
+  int i = 0;
+  while (object && i < n) {
+        a[i++] = object;
+        object = object->Next();
+        }
+  qsort(a, n, sizeof(cListObject *), CompareListObjects);
+  objects = lastObject = NULL;
+  for (i = 0; i < n; i++) {
+      a[i]->Unlink();
+      Add(a[i]);
+      }
 }
 
diff --git a/tools.h b/tools.h
index 071e35e0..9e0abff4 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.57 2004/06/13 14:13:26 kls Exp $
+ * $Id: tools.h 1.58 2004/10/31 16:16:37 kls Exp $
  */
 
 #ifndef __TOOLS_H
@@ -148,7 +148,9 @@ private:
 public:
   cListObject(void);
   virtual ~cListObject();
-  virtual bool operator< (const cListObject &ListObject) { return false; }
+  virtual int Compare(const cListObject &ListObject) const { return 0; }
+      ///< Must return 0 if this object is equal to ListObject, a positive value
+      ///< if it is "greater", and a negative value if it is "smaller".
   void Append(cListObject *Object);
   void Insert(cListObject *Object);
   void Unlink(void);