Infinite loop using phobos sort

December 16, 2010

Posted by Craig Black

Permalink

Craig Black

Permalink

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[]);
}

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/

Forums