creating a Dynamic array class in ruby using FFI and C function

Question

I would like to create my own dynamic array class in ruby (as a training). The idea is to have a class DynamicArray that has a capacity (the number of elements it can hold at one given moment), a size (the number of elements that were actually pushed in the array at a given moment) and a static_array which is a static array of ints of a fixed sized. Whenever this static_array is full, we will create a new static array with twice the capacity of the original static_array and copy every elements inside the new static_array. As there is no static array in ruby, my idea was to use FFI https://github.com/ffi/ffi. to create a function in c that creates a static array of int of size n then be able to use it in my ruby program. I have very little knowledge in C and am having a hard time understanding the doc of FFI Here's what I have so far, a create_array.c file that defines my c function to create an array.

#include<stdio.h>
int * createArray ( int size )
{
  int array[size];
  return 0;

}

a create_array.h file (from what I understood of FFI, you need to put your c functions in a c library.):

int * createArray ( int size )

and this is my dynamic_array.rb file that would do something along this lines :

require 'ffi'
class DynamicArray
  extend FFI::Library
  ffi_lib "./create_array.h"
  attach_function :create_array, [:int], :int
  def initialize
    @size = 0
    @capacity = 1
    @current_index = 0
    @static_array = create_array(@capacity)
  end

  def add(element)
    @size += 1
    resize_array if @size > @capacity
    @static_array[@current_index] = element
    @current_index += 1
  end

  private

  def resize_array
    @capacity = @capacity*2
    new_arr = create_array(@capacity)
    @static_array.each_with_index do |val, index|
      new_arr[index] = val
    end
    @static_array = new_arr
  end
end

Here are some tests for add and resize :

  def test_add
    dynamic_arr = DynamicArray.new
    dynamic_arr.add(1)
    dynamic_arr.add(2)
    assert_equal(1, dynamic_arr.static_array[0])
    assert_equal(2, dynamic_arr.static_array[1])
  end

  def test_resize_array
    dynamic_arr = DynamicArray.new
    dynamic_arr.add(1)
    dynamic_arr.add(2)
    assert_equal(2, dynamic_arr.capacity)
    dynamic_arr.resize_array
    assert_equal(4, dynamic_arr.capacity)
    assert_equal
  end

Can you please explain me what I should do to make this work ?

Answer 1

It seems that you are not working with the C code properly.

In create_array C function:

• you are not returning the array, so there's no way the ruby code will work with the newly created array, you need to return it
• if you want to return an array you actually need to return it's pointer
• In C, in order to create an array and the size is not known before compilation you need to allocate it's memory with malloc (or some other function in the allocfamily)

to put it all together, this is how your create_array.c file would look like:

#include <stdlib.h> /* in order to use malloc */

int * create_array (int size){
  int *a = malloc(size * sizeof(int));
  return a; /* returning the pointer to the array a*/
}

and your header file create_array.h:

int * create_array(int);

and to wrap everything up you still need to compile it before ruby can touch it:

gcc -shared -o create_array.so -fPIC create_array.c

this command is using gcc to compile your C code into a shared library called create_array.so from create_array.c source file. gcc needs to be installed for this to work.

Finally you can use the C function in ruby, with some modifications in your dynamic_array.rb:

require 'ffi'
class DynamicArray
  extend FFI::Library
  ffi_lib "./create_array.so" # using the shared lib
  attach_function :create_array, [:int], :pointer # receiving a pointer to the array
  # rest of your code

Now, this should work! But there are still some issues with your ruby code:

• when you do @static_array = create_array(@capacity) you are receiving a C pointer to the allocated array, not the array itself, not at least in ruby.
• writing @static_array[@current_index] = element will not work NoMethodError: undefined method '[]=' for #<FFI::Pointer address=0x000055d50e798600>
• If you want to add an element to the array, C code must do it. Something like:

void add_to_array (int * array, int index, int number){
  array[index] = number;
}

attach_function :add_to_array, [:pointer, :int, :int], :void
add_to_array(@static_array, @current_index, element)

• Same goes for the @static_array.each_with_index you need to code this in C.

Answer 2

The following function in your question does not allocate the Array you want:

#include<stdio.h>
int * createArray ( int size )
{
  int array[size];
  return 0;

}

The array object in the function you wrote is allocated automatically on the stack and it's destroyed automatically once the function returns. In fact, because it's left unused, the C compiler will probably optimize the array away.

What you were, probably, hoping to do was:

VALUE * create_array(size_t size) {
   VALUE * a = calloc(size, sizeof(*a));
   return a;
}

Now, the returned a is a an array of VALUE (or, technically, a pointer to the first member of the array).

VALUE is the C equivalent of a Ruby Object (usually this will map to a tagged pointer converted to unsigned long).

A resizing could use realloc, which automatically copies the existing data to the new memory (or array):

VALUE * tmp = realloc(tmp, new_size * sizeof(*a));
if(!tmp) {
   /* deal with error, print message, whatever... */
   free(a);
   exit(-1);
}
a = tmp;

You still need to connect the C code to the Ruby layer with the FFI, but this should answer your question about how to resize an array (and fix your mistake about creating one).

Note: For big allocations, realloc could optimize away the copying stage, which is very beneficial in large arrays and has a significant positive performance impact. This can be performed by leveraging the fact that memory addresses are virtual and don't have to map to continuous memory segments. i.e., the same memory page could receive a new address as part of a new allocation.