References and Pointers, Part Two

References and Pointers, Part Two

Rate This
  • Comments 31

Here's a handy type I whipped up when I was translating some complex pointer-manipulation code from C to C#. It lets you make a safe "managed pointer" to the interior of an array. You get all the operations you can do on an unmanaged pointer: you can dereference it as an offset into an array, do addition and subtraction, compare two pointers for equality or inequality, and represent a null pointer. But unlike the corresponding unsafe code, this code doesn't mess up the garbage collector and will assert if you do something foolish, like try to compare two pointers that are interior to different arrays. (*) Enjoy!

internal struct ArrayPtr<T>
{
  public static ArrayPtr<T> Null { get { return default(ArrayPtr<T>); } }
  private readonly T[] source;
  private readonly int index;

  private ArrayPtr(ArrayPtr<T> old, int delta)
  {
    this.source = old.source;
    this.index = old.index + delta;
    Debug.Assert(index >= 0);
    Debug.Assert(index == 0 || this.source != null && index < this.source.Length);
  }

  public ArrayPtr(T[] source)
  {
    this.source = source;
    index = 0;
  }

  public bool IsNull()
  {
    return this.source == null;
  }

  public static bool operator <(ArrayPtr<T> a, ArrayPtr<T> b)
  {
    Debug.Assert(Object.ReferenceEquals(a.source, b.source));
    return a.index < b.index;
  }
       
  public static bool operator >(ArrayPtr<T> a, ArrayPtr<T> b)
  {
    Debug.Assert(Object.ReferenceEquals(a.source, b.source));
    return a.index > b.index;
  }
       
  public static bool operator <=(ArrayPtr<T> a, ArrayPtr<T> b)
  {
    Debug.Assert(Object.ReferenceEquals(a.source, b.source));
    return a.index <= b.index;
  }
       
  public static bool operator >=(ArrayPtr<T> a, ArrayPtr<T> b)
  {
    Debug.Assert(Object.ReferenceEquals(a.source, b.source));
    return a.index >= b.index;
  }
      
  public static int operator -(ArrayPtr<T> a, ArrayPtr<T> b)
  {
    Debug.Assert(Object.ReferenceEquals(a.source, b.source));
    return a.index - b.index;
  }
       
  public static ArrayPtr<T> operator +(ArrayPtr<T> a, int count)
  {
    return new ArrayPtr<T>(a, +count);
  }
       
  public static ArrayPtr<T> operator -(ArrayPtr<T> a, int count)
  {
    return new ArrayPtr<T>(a, -count);
  }
       
  public static ArrayPtr<T> operator ++(ArrayPtr<T> a)
  {
    return a + 1;
  }
     
  public static ArrayPtr<T> operator --(ArrayPtr<T> a)
  {
    return a - 1;
  }

  public static implicit operator ArrayPtr<T>(T[] x)
  {
    return new ArrayPtr<T>(x);
  }

  public static bool operator ==(ArrayPtr<T> x, ArrayPtr<T> y)
  {
    return x.source == y.source && x.index == y.index;
  }

  public static bool operator !=(ArrayPtr<T> x, ArrayPtr<T> y)
  {
    return !(x == y);
  }

  public override bool Equals(object x)
  {
    if (x == null) return this.source == null;
    var ptr = x as ArrayPtr<T>?;
    if (!ptr.HasValue) return false;
    return this == ptr.Value;
  }

  public override int GetHashCode()
  {
    unchecked
    {
      int hash = this.source == null ? 0 : this.source.GetHashCode();
      return hash + this.index;
    }
  }

  public T this[int index]
  {
    get { return source[index + this.index]; }
    set { source[index + this.index] = value; }
  }
}

Now we can do stuff like:

double[] arr = new double[10];
var p0 = (ArrayPtr<double>)arr;
var p5 = p0 + 5;
p5[0] = 123.4; // sets arr[5] to 123.4
var p7 = p0 + 7;
int diff = p7 - p5; // 2

Pretty neat, eh?

UPDATE:

A number of people in the comments have asked why the code disallows a pointer "past the end" of the array. In fact the original C code that I was porting did use an invalid "marker" value as the "end of array" marker, and the code did thereby manipulate pointers "past the end" of the array. The original version of the ArrayPtr class that I actually used in the port to C# supported having a pointer one past the end of the array, and threw an exception if you ever tried to dereference it. I thought this detail was distracting from the point of the article so I eliminated the feature from the C# code before I posted it. Perhaps that was a premature optimization.

I have a similar C# wrapper type for strings, where again, I permit a pointer "past the end" of the string where the null-terminating character would be in a C program. That class also supports common C idioms like "strlen" and whatnot. Such types are very handy when porting C code to C#; ultimately of course it is better to use C# idioms in the long run, but in the short run it is very useful to be able to get things working quickly.

------------

(*) Were this to be a public type then I'd make the assertions into exceptions because there is no telling what crazy thing the public is going to do; since this is an internal type I can guarantee that I'm using it correctly, so I'll use an assertion instead.

  •  public static bool operator ==(ArrayPtr<T> x, ArrayPtr<T> y)

     {

       return x.source == y.source || x.index == y.index;

     }

    Looks like there's a bug here ;-)

  • why did you make your == operator

    x.source == y.source || x.index == y.index?

    I would think it should be

    x.source == y.source && x.index == y.index?

  • I've often wanted to be able to write...

    foreach (MyClass x in myarray)    x = DoSomething(x);

    ... but this doesn't work because x is a value extracted, no longer linked to the context of the array from whence it came. (So I end up doing a old-school for loop instead.) I wonder if this could be customised to provide a general purpose array itterator that can modify the current item.

    Thankies, billpg.

  • @Bill: No it could not.  No matter what trick you do to wrap your foreach, x will be a reference.  What you *could* do is use: foreach (MyClassWrapper x in myarray) x.Value = DoSomething(x.value)

    or even

    foreach (MyClassWrapper x in myarray) x.Value = DoSomething(x)

    The 2nd version would require an implicit cast.

  • Rather than (or in addition to?) implementing this[int index], I'd like to see it implementing IList<T> so that you can enumerate it, sort it, and so on.

  • @Gabe: And what does enumerating, sorting, etc. work on? The entire array? The array starting at that point? When you sort it, what happens to the elements before the current index?

  • var ptr = x as ArrayPtr<T>?;

    I did not know 'as' can be used with value types when using Nullable<T>. This is amazing!

  • I found this equally amazing:  the implicit cast allows equallity to null ... didn't know you could do that with a structure.

    var a = ArrayPtr<int>.Null;

    Console.Writeline(a == null); // prints True

  • I'm assuming that the reason you don't do bounds checking is so that you can safely do an addition, and then worry later about whether it went off the end.

    If that's the case, a method to get a pointer to the end of the array(or 1 past) might be nice, something like:

    static ArrayPtr<T> EndPtr<T>( this T[] array )

    {

       return new ArrayPtr<T>( array, array.size );

    }

  • Now I feel stupic because I realise that the reason you don't do bounds checking is that you do it in the constructor.

    Still, since your dealing with "pointers" going off the end with an addition is not automatically a bad thing. I would leave out that assert.

  • Shouldn't there be more distribution in the hash codes? A set of pointers to sequential elements will have sequential hash codes.

  • How is havin a pointer outside the bounds not a bad thing. We're in a managed language here...

    It's better to know about an invalid state where you create it rather than when you use it, the former is vastly easier to debug and fix

  • @Gabe. IList is perhaps a tad confusing, but IEnumerable<T> would be reasonable.

  • @Shuggy: I must reiterate my question... When would enumeration actually return in this case?

  • In the equals method your chaning the value of x to ArrayPtr<T>?. But if x isn't a ArrayPtr<T>? won't ptr be null and you have a null reference exception in the line?

Page 1 of 3 (31 items) 123