www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Infinite loop using phobos sort

reply "Craig Black" <craigblack2 cox.net> writes:
When I try to use Phobos to sort my custom Array, it goes into an infinite 
loop.  I suspect I did something wrong with my Range struct.  Does anyone 
see an obvious flaw here?

-Craig

import std.stdio;
import std.random;
import std.conv;
import std.algorithm;
import std.c.stdlib;

struct Array(T)
{
public:

  this(int length) { resize(length); }
  this(T[] a) { append(a); }

  this(this)
  {
    if(!base.array) return;
    ArrayBase!T old;
    old = base;
    base.array = null;
    reserve(old.length(), old.length());
    copyData(old);
    old.array = null;
  }

  void clear() { base.clear(); }

  void resize(int sz)
  {
    assert(sz >= 0);
    if(sz == 0) return clear();
    if(!base.array) reserve(sz, sz);
    *base.lengthPtr() = sz;
  }

  void reserve(int capacity, int length)
  {
    assert(length <= capacity);
    if(capacity == 0) return clear();
    ArrayBase!T old;
    if(base.array)
    {
      if(base.capacity() >= capacity) return;
      old.array = base.array;
      base.array = null;
    }
    base.array = cast(ubyte*)malloc(capacity*T.sizeof+8);
    *base.lengthPtr() = length;
    *base.capacityPtr() = capacity;
    for(int i = 0; i < capacity; i++) emplace!T(base.data()+i);
    if(old.array) copyData(old);
  }

  int length() const { return base.length(); }
  int capacity() const { return base.capacity(); }

  bool empty() const { return base.array == null; }

  ref T at(int i)
  {
    assert(!empty(), "Array of " ~ T.stringof ~ ": index " ~ to!string(i) ~ 
" out of bounds of empty array");
    assert(i >= 0 && i < length(), "Array of " ~ T.stringof ~ ": index " ~ 
to!string(i) ~ " out of bounds 0-" ~ to!string(length()-1));
    return *cast(T*)(base.array+8+i*T.sizeof);
  }

  ref const T at(int i) const
  {
    assert(!empty(), "Array of " ~ T.stringof ~ ": index " ~ to!string(i) ~ 
" out of bounds of empty array");
    assert(i >= 0 && i < length(), "Array of " ~ T.stringof ~ ": index " ~ 
to!string(i) ~ " out of bounds 0-" ~ to!string(length()-1));
    return *cast(T*)(base.array+8+i*T.sizeof);
  }

  const ref T opIndex(int i) const { return 
*cast(T*)(base.array+8+i*T.sizeof); }

  void opIndexAssign(T t, int i) { at(i) = t; }
  void opIndexAssign(ref T t, int i) { at(i) = t; }

  void opAssign(ref const Array!T array)
  {
    copy(array);
  }

  void opAssign(T[] array)
  {
    int len = array.length;
    resize(len);
    for(int i = 0; i < len; i++) at(i) = array[i];
  }

  void copy(ref const Array!T array)
  {
    if(array.empty()) return clear();
    int len = array.length();
    reserve(len, len);
    for(int i = 0; i < len; i++) at(i) = array[i];
  }

  void opOpAssign(string op, A...)(A a) if(op == "~")
  {
    appendComposite(a);
  }

  ref T front() { return at(0); }
  const ref T front() const { return at(0); }
  ref T back() { return at(length()-1); }
  const ref T back() const { return at(length()-1); }

  ref T appendOne()
  {
    int sz = length();
    int sp = capacity();
    if(sp > sz) (*base.lengthPtr())++;
    else
    {
      sz++;
      sp = max(2, sp+sp/2, sz);
      reserve(sp, sz);
    }
    return back();
  }

  void append(A...)(A a)
  {
    static if(a.length == 1 && (is(typeof(a[0]) == Array!T) || 
is(typeof(a[0]) == T[])))
    {
      appendComposite(a[0]);
    } else {
      appendTuple(a);
    }
  }

  void appendTuple(A...)(A a)
  {
    foreach(x; a) appendOne() = x;
  }

  void appendComposite(A)(A a)
  {
    int prevLen = length();
    int alen = a.length;
    resize(prevLen + alen);
    T *d = base.data();
    T *e = &a[0];
    for(int i = 0; i < alen; i++) d[i+prevLen] = e[i];
  }

  static struct Range
 {
 public:
  this(ref Array!T array)
  {
    if(array.empty()) return;
   start = &array.front();
   end = &array.back();
  }
  this(T *_start, T *_end)
  {
   start = _start;
   end = _end;
  }
  T* start, end;
  bool empty() const { return end < start; }
  void popFront() { start++; }
  void popBack() { end--; }
  ref T front() { return *start; }
  ref T back() { return *end; }
   property size_t length() { return end-start+1; }
  ref T opIndex(int i) { return start[i]; }
   Range opSlice(int a, int b) { return Range(start+a, start+b); }
  Range save() { return this; }
 }

  Range opSlice() { return Range(this); }
  Range opSlice(int a, int b) { return Range(base.data()+a, 
base.data()+b); }

  void sort(alias L = less!T)()
 {
  quickSort!(T*, L)(base.data(), 0, length()-1);
 }

private:

  static struct ArrayBase(T)
  {
  public:

    ~this() { clear(); }
    void clear()
    {
      if(!array) return;
      int cap = capacity();
      T *d = data();
      for(int i = 0; i < cap; i++) .clear(d[i]);
      free(array);
    }

    int length() const { return array ? *lengthPtr() : 0; }
    int capacity() const { return array ? *capacityPtr() : 0; }
    int* lengthPtr() const { return cast(int*)(array); }
    int* capacityPtr() const { return cast(int*)(array+4); }
    T* data() const { return cast(T*)(array+8); }

    ubyte* array;
  }

  ArrayBase!T base;

  void copyData(ref ArrayBase!T array)
  {
    int copyLen = min(length, array.length());
    T *a = base.data();
    T *b = array.data();
    for(int i = 0; i < copyLen; i++) { a[i] = b[i]; }
  }
}

void main()
{
  Array!double vals = 10;
  foreach(ref i; vals) i = uniform(0.0,1000.0);
  sort!"a<b"(vals[]);
}
Dec 15 2010
parent reply "Nick Voronin" <elfy.nv gmail.com> writes:
On Thu, 16 Dec 2010 03:11:40 +0300, Craig Black <craigblack2 cox.net>  
wrote:


 When I try to use Phobos to sort my custom Array, it goes into an  
 infinite loop.  I suspect I did something wrong with my Range struct.   
 Does anyone see an obvious flaw here?


bordercase


   this(ref Array!T array)
   {
     if(array.empty()) return;
    start = &array.front();
    end = &array.back();


end points to last actual element


   }
   this(T *_start, T *_end)
   {
    start = _start;
    end = _end;


same


   }
    Range opSlice(int a, int b) { return Range(start+a, start+b); }


in opSlice second index points _after_ last element you want. a[0..1] --  
range of length 1. You need to fix b by -1.

I wonder what kind of assert would catch this one...

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
Dec 15 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/15/10 7:15 PM, Nick Voronin wrote:

 On Thu, 16 Dec 2010 03:11:40 +0300, Craig Black <craigblack2 cox.net>
 wrote:


 When I try to use Phobos to sort my custom Array, it goes into an
 infinite loop. I suspect I did something wrong with my Range struct.
 Does anyone see an obvious flaw here?


 bordercase


 this(ref Array!T array)
 {
 if(array.empty()) return;
 start = &array.front();
 end = &array.back();


 end points to last actual element


Perfect, I logged on to answer the same. Tip: always use begin = first 
element, end = past-last element.

Andrei
Dec 15 2010