The Ecere SDK - sdk/blob - ecere/src/com/containers/LinkList.ec

   1 namespace com;
   2
   3 import "Container"
   4 import "List"  // Ugly dependency for List optimization in Sort()
   5
   6 default:
   7 extern int __ecereVMethodID_class_OnCompare;
   8 private:
   9
  10 public struct LinkElement<class T:void *>
  11 {
  12    T prev, next;
  13 };
  14
  15 public class ListItem : IteratorPointer
  16 {
  17    class_fixed
  18 public:
  19    union
  20    {
  21       LinkElement<thisclass> link;
  22       struct { thisclass prev, next; };
  23    };
  24 }
  25
  26 public class LinkList<class LT:void * = ListItem, bool circ = false, link = LT::link> : Container<LT>
  27 {
  28    class_fixed
  29 public:
  30    LT first, last;
  31    int count;
  32
  33    // Generic iterator support
  34    LT GetFirst() { return first; }
  35    LT GetLast() { return last; }
  36    LT GetPrev(IteratorPointer item) { return ((LT)item).link.prev; }
  37    LT GetNext(IteratorPointer item) { return ((LT)item).link.next; }
  38    LT GetData(IteratorPointer pointer) { return (LT)pointer; }
  39
  40    IteratorPointer GetAtPosition(const I pos, bool create, bool * justAdded)
  41    {
  42       int c;
  43       LT item;
  44       for(c = 0, item = first; c < (int)pos && item; c++, item = item.link.next);
  45       return (IteratorPointer)item;
  46    }
  47    bool SetData(IteratorPointer pointer, LT data)
  48    {
  49       // Not supported for LinkList
  50       return false;
  51    }
  52
  53    IteratorPointer Add(LT item)
  54    {
  55       if(item)
  56       {
  57          item.link.prev = last;
  58          if(item.link.prev)
  59             item.link.prev.link.next = item;
  60          if(!first) first = item;
  61          last = item;
  62          item.link.next = circ ? first : null;
  63          if(circ)
  64             first.link.prev = item;
  65          count++;
  66       }
  67       return (IteratorPointer)item;
  68    }
  69
  70    IteratorPointer Insert(IteratorPointer _prevItem, T item)
  71    {
  72       LT prevItem = (LT)_prevItem;
  73       if(item && prevItem != item)
  74       {
  75          item.link.prev = prevItem ? prevItem : (circ ? last : null);
  76          if(prevItem)
  77          {
  78             item.link.next = prevItem.link.next;
  79             prevItem.link.next = item;
  80          }
  81          else
  82          {
  83             item.link.next = first;
  84             first = item;
  85             if(circ)
  86             {
  87                if(item.link.prev)
  88                   item.link.prev.link.next = item;
  89                else
  90                   item.link.next = item;
  91             }
  92          }
  93          if(prevItem == last) last = item;
  94          if(item.link.next)
  95             item.link.next.link.prev = item;
  96          count++;
  97          return (IteratorPointer)item;
  98       }
  99       return null;
 100    }
 101
 102    void Remove(IteratorPointer _item)
 103    {
 104       LT item = (LT)_item;
 105       if(item)
 106       {
 107          if(item.link.prev)
 108             item.link.prev.link.next = item.link.next;
 109          if(item.link.next)
 110             item.link.next.link.prev = item.link.prev;
 111          if(circ && last == first)
 112             last = first = null;
 113          else
 114          {
 115             if(last == item) last = item.link.prev;
 116             if(first == item) first = item.link.next;
 117          }
 118          item.link.prev = null;
 119          item.link.next = null;
 120          count--;
 121       }
 122    }
 123
 124    void Move(IteratorPointer _item, IteratorPointer _prevItem)
 125    {
 126       LT item = (LT)_item;
 127       LT prevItem = (LT)_prevItem;
 128       if(item)
 129       {
 130          if(prevItem != item && (first != item || prevItem))
 131          {
 132             if(item.link.prev)
 133                item.link.prev.link.next = item.link.next;
 134             if(item.link.next)
 135                item.link.next.link.prev = item.link.prev;
 136             if(item == first) first = item.link.next;
 137             if(item == last)  last = item.link.prev;
 138
 139             if(prevItem == last)
 140                last = item;
 141
 142             item.link.prev = prevItem ? prevItem : (circ ? last : null);
 143             if(prevItem)
 144             {
 145                item.link.next = prevItem.link.next;
 146                prevItem.link.next = item;
 147             }
 148             else
 149             {
 150                item.link.next = first;
 151                first = item;
 152                if(circ)
 153                {
 154                    if(item.link.prev)
 155                       item.link.prev.link.next = item;
 156                    else
 157                       item.link.next = item;
 158                }
 159             }
 160             if(item.link.next)
 161                item.link.next.link.prev = item;
 162          }
 163       }
 164    }
 165
 166    IteratorPointer Find(LT value)
 167    {
 168       return (IteratorPointer)value;
 169    }
 170
 171    void Free()
 172    {
 173       LT item;
 174       while((item = first))
 175       {
 176          Remove(item);
 177          delete item;
 178       }
 179    }
 180
 181    // TOFIX: This compiles without error but produces bad code, since the virtual method prototype is an IteratorPointer which should be a pointer, not a uint64
 182    //void Delete(LT item)
 183    void Delete(void * item)
 184    {
 185       Remove(item);
 186       delete item;
 187    }
 188
 189    // Optimized Merge Sort Reusing List Nodes
 190    static void _Sort(bool ascending, LinkList * lists)
 191    {
 192       // Only sort containers with more than 1 items and which are integer indexable
 193       if(count >= 2)
 194       {
 195          LT a, b, mid;
 196          Class Dclass = class(D);
 197          bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
 198          bool isList = GetData == List::GetData;
 199          bool isLinkList = GetData == LinkList::GetData;
 200          bool isStruct = Dclass.type == structClass;
 201          int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
 202          LinkList listA = lists[0];
 203          LinkList listB = lists[1];
 204
 205          // Find midpoint
 206          mid = GetAtPosition(count / 2-1, false, null);
 207
 208          // Split into 2 lists
 209          a = first;
 210          b = mid.link.next;
 211
 212          while(a)
 213          {
 214             LT i = a;
 215             bool done = (a == mid);
 216             a = a.link.next;
 217             listA.LinkList::Add((void *)(uintptr)i);
 218             if(done) break;
 219          }
 220
 221          while(b)
 222          {
 223             LT i = b;
 224             b = b.link.next;
 225             listB.LinkList::Add((void *)(uintptr)i);
 226          }
 227
 228          first = null, last = null, count = 0;
 229
 230          // Sort each of the 2 lists
 231          listA._Sort(ascending, lists+2);
 232          listB._Sort(ascending, lists+2);
 233
 234          // Merge
 235          a = listA.first;
 236          b = listB.first;
 237
 238          while(a || b)
 239          {
 240             int r;
 241             if(a && b)
 242             {
 243                if(isLinkList)
 244                   r = onCompare(Dclass, a, b);
 245                else if(isList)
 246                {
 247                   if(isStruct || byRef)
 248                      r = onCompare(Dclass, &((Link)a).data, &((Link)b).data);
 249                   else
 250                      r = onCompare(Dclass, (const void *)(uintptr)((Link)a).data, (const void *)(uintptr)((Link)b).data);
 251                }
 252                else
 253                {
 254                   D dataA = GetData(a), dataB = GetData(b);
 255                   r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
 256                }
 257             }
 258             else if(a)
 259                r = -1;
 260             else
 261                r = 1;
 262             if(!ascending) r *= -1;
 263
 264             if(r < 0)
 265             {
 266                LT i = a;
 267                a = a.link.next;
 268                LinkList::Add((void *)(uintptr)i);
 269             }
 270             else
 271             {
 272                LT i = b;
 273                b = b.link.next;
 274                LinkList::Add((void *)(uintptr)i);
 275             }
 276          }
 277          listA.first = null, listA.last = null, listA.count = 0;
 278          listB.first = null, listB.last = null, listB.count = 0;
 279       }
 280    }
 281
 282    void Sort(bool ascending)
 283    {
 284       // Pre-allocate 2 log2(n) lists
 285       int i, numLists = log2i(count) * 2;
 286       LinkList * lists = new LinkList[numLists];
 287       for(i = 0; i < numLists; i++)
 288          lists[i] = eInstance_New(_class);
 289       _Sort(ascending, lists);
 290       for(i = 0; i < numLists; i++)
 291          delete lists[i];
 292       delete lists;
 293    }
 294 }