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

   1 namespace sys;
   2
   3 import "instance"
   4
   5 public class Item : struct
   6 {
   7 public:
   8    class_fixed
   9    Item prev, next;
  10
  11    void Copy(Item src, int size)
  12    {
  13       memcpy((byte *)this + sizeof(class Item), (byte *)src + sizeof(class Item), size - sizeof(Item));
  14    }
  15 };
  16 public class NamedItem : struct
  17 {
  18 public:
  19    class_fixed
  20    NamedItem prev, next;
  21    char * name;
  22 };
  23 public class OldLink : struct
  24 {
  25 public:
  26    OldLink prev, next;
  27    void * data;
  28    class_fixed
  29
  30    void Free()
  31    {
  32       delete data;
  33    }
  34 };
  35 public class NamedLink : struct
  36 {
  37 public:
  38    class_fixed
  39    NamedLink prev, next;
  40    char * name;
  41    void * data;
  42 };
  43
  44 public class NamedLink64 : struct
  45 {
  46 public:
  47    class_fixed
  48    NamedLink64 prev, next;
  49    char * name;
  50    int64 data;
  51 };
  52
  53 public struct OldList
  54 {
  55 private:
  56
  57    void Merge(OldList list1, OldList list2, int (*compare)(void *, void *, void *), void * data)
  58    {
  59       void * item;
  60
  61       Clear();
  62       offset = list1.offset;
  63
  64       // Add the smallest elements while we have two lists
  65       while((list1.first && list2.first))
  66       {
  67          if(compare(list1.first, list2.first, data) <= 0)
  68          {
  69             item = list1.first;
  70             list1.Remove(item);
  71          }
  72          else
  73          {
  74             item = list2.first;
  75             list2.Remove(item);
  76          }
  77          Add(item);
  78       }
  79
  80       // Add the remaining elements
  81       while((item = list1.first))
  82       {
  83          list1.Remove(item);
  84          Add(item);
  85       }
  86       while((item = list2.first))
  87       {
  88          list2.Remove(item);
  89          Add(item);
  90       }
  91    }
  92
  93 public:
  94    void * first, * last;
  95    int count;
  96    uint offset;
  97    bool circ;
  98
  99    void Add(void * item)
 100    {
 101       if(item)
 102       {
 103          Item link = (Item) ((byte *)item + offset);
 104
 105 #ifdef MEMINFO // _DEBUG
 106          {
 107             void * i;
 108             OldLink l;
 109             for(i = first; i; i = l.next)
 110             {
 111                if(item == i)
 112                   break;
 113                l = (OldLink)((byte *)i + offset);
 114                if(i == last) { i = null; break; }
 115             }
 116             if(i)
 117             {
 118                printf("Adding item already in list\n");
 119                return;
 120             }
 121             if(link.prev || link.next)
 122                printf("Adding item with non-zero prev/next pointers\n");
 123          }
 124 #endif
 125
 126          link.prev = last;
 127          if(link.prev)
 128             ((Item) ((byte *)link.prev + offset)).next = item;
 129          if(!first) first = item;
 130          last = item;
 131          link.next = circ ? first : null;
 132          if(circ)
 133             ((Item) ((byte *)first + offset)).prev = item;
 134          count++;
 135       }
 136    }
 137
 138    bool Insert(void * prevItem, void * item)
 139    {
 140       if(item && prevItem != item)
 141       {
 142          Item prevLink = (Item) ((byte *)prevItem + offset);
 143          Item link = (Item) ((byte *)item + offset);
 144
 145 #ifdef MEMINFO // _DEBUG
 146          {
 147             void * i;
 148             OldLink l;
 149             for(i = first; i; i = l.next)
 150             {
 151                if(item == i)
 152                   break;
 153                l = (OldLink)((byte *)i + offset);
 154                if(i == last) { i = null; break; }
 155             }
 156             if(i)
 157             {
 158                printf("Inserting item already in list\n");
 159                return false;
 160             }
 161          }
 162 #endif
 163          link.prev = prevItem ? prevItem : (circ ? last : null);
 164          if(prevItem)
 165          {
 166             link.next = prevLink.next;
 167             prevLink.next = item;
 168          }
 169          else
 170          {
 171             link.next = first;
 172             first = item;
 173             if(circ)
 174             {
 175                 if(link.prev)
 176                   ((Item)((byte *)link.prev + offset)).next = item;
 177                 else
 178                    link.next = item;
 179             }
 180          }
 181          if(prevItem == last) last = item;
 182          if(link.next)
 183             ((Item)((byte *)link.next + offset)).prev = item;
 184          count++;
 185          return true;
 186       }
 187       return false;
 188    }
 189
 190    void Remove(void * item)
 191    {
 192       if(item)
 193       {
 194          Item link = (Item) ((byte *)item + offset);
 195
 196 #ifdef MEMINFO // _DEBUG
 197          {
 198             void * i;
 199             OldLink l;
 200             for(i = first; i; i = l.next)
 201             {
 202                if(item == i)
 203                   break;
 204                l = (OldLink)((byte *)i + offset);
 205                if(i == last) { i = null; break; }
 206             }
 207             if(!i)
 208                printf("Removing item not found in list\n");
 209          }
 210 #endif
 211
 212          if(link.prev)
 213             ((Item) ((byte *)link.prev + offset)).next = link.next;
 214          if(link.next)
 215             ((Item) ((byte *)link.next + offset)).prev = link.prev;
 216          if(circ && last == first)
 217             last = first = null;
 218          else
 219          {
 220             if(last == item) last = link.prev;
 221             if(first == item) first = link.next;
 222          }
 223          link.prev = null;
 224          link.next = null;
 225          count--;
 226       }
 227    }
 228
 229    void Delete(void * item)
 230    {
 231       if(item)
 232       {
 233          Remove(item);
 234          delete item;
 235       }
 236    }
 237
 238    void Free(void (* freeFn)(void *))
 239    {
 240       void * item, * next;
 241
 242       for(item = first; item; item = next)
 243       {
 244          Item link = (Item) ((byte *)item + offset);
 245          next = link.next;
 246
 247          if(freeFn)
 248             freeFn(item);
 249          delete item;
 250
 251          // Handle list->circular linked lists
 252          if(next == first) break;
 253       }
 254       first = last = null;
 255       count = 0;
 256    }
 257
 258    void RemoveAll(void (* freeFn)(void *))
 259    {
 260       void * item, * next;
 261
 262       for(item = first; item; item = next)
 263       {
 264          Item link = (Item) ((byte *)item + offset);
 265          next = link.next;
 266
 267          if(freeFn)
 268             freeFn(item);
 269
 270          // Handle list->circular linked lists
 271          if(next == first) break;
 272       }
 273       first = last = null;
 274       count = 0;
 275    }
 276
 277    void Clear(void)
 278    {
 279       // Should this be done in Clear??
 280       offset = 0;
 281       circ = false;
 282
 283       count = 0;
 284       first = last = null;
 285    }
 286
 287    void Move(void * item, void * prevItem)
 288    {
 289       if(item)
 290       {
 291          Item link = (Item) ((byte *)item + offset);
 292          Item prevLink = (Item) ((byte *)prevItem + offset);
 293
 294          if(prevItem != item && (first != item || prevItem))
 295          {
 296             if(link.prev)
 297                ((Item)((byte *)link.prev + offset)).next = link.next;
 298             if(link.next)
 299                ((Item)((byte *)link.next + offset)).prev = link.prev;
 300             if(item == first) first = link.next;
 301             if(item == last)  last = link.prev;
 302
 303             if(prevItem == last)
 304                last = item;
 305
 306             link.prev = prevItem ? prevItem : (circ ? last : null);
 307             if(prevItem)
 308             {
 309                link.next = prevLink.next;
 310                prevLink.next = item;
 311             }
 312             else
 313             {
 314                link.next = first;
 315                first = item;
 316                if(circ)
 317                {
 318                    if(link.prev)
 319                      ((Item)((byte *)link.prev + offset)).next = item;
 320                    else
 321                       link.next = item;
 322                }
 323             }
 324             if(link.next)
 325                ((Item) ((byte *)link.next + offset)).prev = item;
 326          }
 327       }
 328    }
 329
 330    void Swap(void * item1, void * item2)
 331    {
 332       Item link1 = (Item) ((byte *)item1 + offset);
 333       Item link2 = (Item) ((byte *)item2 + offset);
 334       Item prev1 = link1.prev, next1 = link1.next;
 335       void * tmp1 = item1, * tmp2 = item2;
 336
 337       link1.prev = link2.prev;
 338       link1.next = link2.next;
 339       link2.prev = prev1;
 340       link2.next = next1;
 341
 342       if(first == tmp1)      first = item2;
 343       else if(first == tmp2) first = item1;
 344
 345       if(last == tmp1)       last = item1;
 346       else if(last == tmp2)  last = item2;
 347
 348       if(link1.next) ((Item) ((byte *)link1.next + offset)).prev = item2;
 349       if(link1.prev) ((Item) ((byte *)link1.prev + offset)).next = item2;
 350       if(link2.next) ((Item) ((byte *)link2.next + offset)).prev = item1;
 351       if(link2.prev) ((Item) ((byte *)link2.prev + offset)).next = item1;
 352    }
 353
 354    void Sort(int (*compare)(void *, void *, void *), void * data)
 355    {
 356       if(first && ((Item) ((byte *)first + offset)).next)
 357       {
 358          OldList list1, list2;
 359          void * middle, * end;
 360
 361          // Find a middle point
 362          for(middle = first, list1.count = 0, list2.count = 0,
 363              end = ((Item) ((byte *)first + offset)).next;
 364              middle && end;
 365              middle = ((Item)((byte *)middle + offset)).next, list1.count++,
 366              end    = ((Item)((byte *)end    + offset)).next, list2.count++)
 367          {
 368             end = ((Item)((byte *)end + offset)).next;
 369             if(!end) break;
 370          }
 371
 372          // Split into two lists
 373          list1.offset = offset;
 374          list2.offset = offset;
 375          list1.circ = circ;
 376          list2.circ = circ;
 377
 378          list1.first = first;
 379          list1.last = middle;
 380          list2.first = ((Item)((byte *)middle + offset)).next;
 381          list2.last = last;
 382
 383          ((Item)((byte *)list1.last  + offset)).next = null;
 384          ((Item)((byte *)list2.first + offset)).prev = null;
 385
 386          // Recurse with those two lists
 387          list1.Sort(compare, data);
 388          list2.Sort(compare, data);
 389
 390          // Merge the two lists together
 391          Merge(list1, list2, compare, data);
 392       }
 393    }
 394
 395    void * FindName(const char * name, bool warn)
 396    {
 397       void * result = null;
 398       if(name)
 399       {
 400          void * item;
 401          NamedItem link;
 402
 403          int compare = 1;
 404          for(item = first; item; item = link.next)
 405          {
 406             link = (NamedItem)(((byte *)item) + offset);
 407             if(link.name && (compare = strcmp(link.name, name)) >= 0)
 408                break;
 409          }
 410          if(!compare)
 411             result = item;
 412          else if(warn)
 413             ; //LogErrorCode(ERR_NAME_INEXISTANT, name);
 414       }
 415       return result;
 416    }
 417
 418    bool PlaceName(const char * name, void ** place)
 419    {
 420       bool result = true;
 421       void * item;
 422       NamedItem link;
 423       int compare = 1;
 424
 425       for(item = first; item; item = link.next)
 426       {
 427          link = (NamedItem)((byte *)item + offset);
 428          if(link.name && (compare = strcmp(link.name, name)) >= 0)
 429             break;
 430       }
 431
 432       if(!item)
 433          *place = last;
 434       else
 435          *place = link.prev;
 436
 437       if(compare)
 438          result = true;
 439       else
 440          ; //LogErrorCode(ERR_NAME_EXISTS, name);
 441       return result;
 442    }
 443
 444    bool AddName(void * item)
 445    {
 446       bool result = false;
 447       void * place;
 448       NamedItem link = ((NamedItem)((byte *)item + offset));
 449
 450       if(PlaceName(link.name, &place))
 451       {
 452          Insert(place, item);
 453          result = true;
 454       }
 455       return result;
 456    }
 457
 458    OldLink FindLink(void * data)
 459    {
 460       void * item;
 461       OldLink link;
 462       for(item = first; item; item = link.next)
 463       {
 464          link = (OldLink)((byte *)item + offset);
 465          if(link.data == data)
 466             break;
 467       }
 468       return item;
 469    }
 470
 471    void * FindNamedLink(const char * name, bool warn)
 472    {
 473       if(name)
 474       {
 475          void * item = FindName(name, warn);
 476          return item ? ((NamedLink)((byte *)item + offset)).data : null;
 477       }
 478       return null;
 479    }
 480
 481    void Copy(OldList src, int size, void (* copy)(void * dest, void * src))
 482    {
 483       Item item;
 484       Clear();
 485       for(item = src.first; item; item = item.next)
 486       {
 487          Item newItem = (Item) new0 byte[size];
 488          Add(newItem);
 489          newItem.Copy(item, size);
 490          if(copy) copy(newItem, item);
 491       }
 492    }
 493 };