13.8 Vector objects

Vectors are variable length blocks of memory referenced by machine words tagged as vectors. The first machine word of a vector block contains a fixnum representing the vector length; this means that the first word of a vector is tagged as a fixnum.

|------------------------|-------------| reference to vector
      heap pointer         vector tag

|------------------------|-------------| vector first word
     number of words       fixnum tag

After the length machine word comes the data area: an array of machine words, one for each vector slot; slot indexes are zero–based.

      0   1   2   3   4   5   6   7
|---|---|---|---|---|---|---|---|---| vector memory block
  ^ |...............................|
  |        slots = data area
length
fixnum

A vector is capable of holding at most a number of values equal to the return value of greatest-fixnum. The fixnum representing the vector length, interpreted as raw signed integer, also represents the number of bytes in the data area.

A fixnum representing the index of slot N, interpreted as raw signed integer, also represents the offset in bytes of the first byte of the slot with respect the beginning of the data area.

Basic operations

Vector objects are allocated on the heap; to perform the allocation we compute the whole size of the data area, add to it room for meta data and finally compute the aligned block size:

ikpcb_t *  pcb            = ik_the_pcb();
ikuword_t  length         = the_number_of_items;
ikuword_t  requested_size = wordsize * length;
ikuword_t  block_size     = disp_vector_data + requested_size;
ikuword_t  align_size     = IK_ALIGN(block_size);
ikptr_t s_vec = ik_safe_alloc(pcb, align_size) | vector_tag;

ik_safe_alloc() returns an ikptr_t value representing the aligned pointer, having the 3 least significant bits set to zero; we add to it the vector tag (an integer value fitting in 3 bits) which allows to recognise vectors among all the other built in objects.

We have to explicitly store the vector length in the memory block as a fixnum, so usually a full allocation looks like this:

ikptr_t
ika_vector_alloc (ikpcb_t * pcb, ikuword_t number_of_items)
{
  ikptr_t    s_len      = IK_FIX(number_of_items);
  ikuword_t  align_size = IK_ALIGN(disp_vector_data + s_len);
  ikptr_t s_vec = ik_safe_alloc(pcb, align_size) | vector_tag;
  IK_VECTOR_LENGTH_FX(s_vec) = s_len;
  return s_vec;
}

notice how we exploit the fact that the fixnum representing the number of elements, interpreted as raw integer, equals the number of bytes in the data area needed to hold such elements.

The allocation operations described above leaves the data area uninitialised: its content is undefined. This is bad if the garbage collector processes the newly built vector before the elements are initialised to a correct Scheme value. The following function resets the data area to a vector of zero fixnums:

ikptr_t
ikrt_vector_clean (ikptr_t s_vec)
{
  ikptr_t	s_len = IK_VECTOR_LENGTH_FX(s_vec);
  memset(IK_VECTOR_DATA_VOIDP(s_vec), 0, s_len);
  return s_vec;
}

To fill a vector of 3 items with fixnums we should do:

ikptr_t  s_vec = the_vector;
IK_REF(s_vec, off_vector_data + 0 * wordsize) = IK_FIX(10);
IK_REF(s_vec, off_vector_data + 1 * wordsize) = IK_FIX(20);
IK_REF(s_vec, off_vector_data + 2 * wordsize) = IK_FIX(30);

or, shorter:

ikptr_t  s_vec = the_vector;
IK_ITEM(s_vec, 0) = IK_FIX(10);
IK_ITEM(s_vec, 1) = IK_FIX(20);
IK_ITEM(s_vec, 2) = IK_FIX(30);

in this case there is no need to call ik_signal_dirt_in_page_of_pointer() because the values are fixnums (which are immediate Scheme objects). To fill the slots of a vector with Scheme objects allocated on the heap we must do:

ikpcb_t *  pcb   = ik_the_pcb();
ikptr_t    s_vec = the_vector;

pcb->root0 = &s_vec;
{
  IK_ASS(IK_ITEM(s_vec, 0),
      ika_bytevector_from_cstring(pcb, "A"));
  IK_SIGNAL_DIRT(pcb, IK_ITEM_PTR(s_vec, 0));

  IK_ASS(IK_ITEM(s_vec, 1),
      ika_bytevector_from_cstring(pcb, "B"));
  IK_SIGNAL_DIRT(pcb, IK_ITEM_PTR(s_vec, 1));

  IK_ASS(IK_ITEM(s_vec, 2),
      ika_bytevector_from_cstring(pcb, "B"));
  IK_SIGNAL_DIRT(pcb, IK_ITEM_PTR(s_vec, 2));
}
pcb->root0 = NULL;

To retrieve the item at index 2 we do:

ikptr_t  s_vec  = the_vector;
ikptr_t  s_item = IK_REF(s_vec, off_vector_data + 2 * wordsize);

or, shorter:

ikptr_t  s_vec  = the_vector;
ikptr_t  s_item = IK_ITEM(s_vec, 2);

To retrieve the vector length:

ikptr_t    s_vec  = the_vector;
ikptr_t    s_len  = IK_REF(s_vec, off_vector_length);
ikuword_t  length = IK_UNFIX(s_len);

or, shorter:

ikptr_t    s_vec  = the_vector;
ikptr_t    s_len  = IK_VECTOR_LENGTH_FX(s_len);
ikuword_t  length = IK_UNFIX(s_len);

or, even shorter:

ikptr_t    s_vec  = the_vector;
ikuword_t  length = IK_VECTOR_LENGTH(s_len);

Preprocessor Symbol: vector_tag

An integer used to tag ikptr_t references to vector memory blocks.

Preprocessor Symbol: disp_vector_length

Displacement of length. The number of bytes to add to an untagged pointer to vector to get the pointer to the first byte in the word holding the vector length as fixnum.

Preprocessor Symbol: disp_vector_data

Displacement of data area. The number of bytes to add to an untagged pointer to vector to get the pointer to the first byte in the data area.

Preprocessor Symbol: off_vector_length

An integer to add to a tagged ikptr_t reference to retrieve the pointer to the first byte of the vector length as fixnum.

Preprocessor Symbol: off_vector_data

An integer to add to a tagged ikptr_t vector reference to retrieve the pointer to the first byte of the data area.

Convenience preprocessor macros

Preprocessor Macro: int IK_IS_VECTOR (ikptr_t vec)

Evaluate to true if vec is a reference to a vector object. This predicate tests that vec is tagged as vector reference and that the first machine word in the referenced memory block is a fixnum.

Preprocessor Macro: ikptr_t IK_VECTOR_LENGTH_FX (ikptr_t vec)

Return a fixnum representing the number of items in the vector vec.

Preprocessor Macro: ikuword_t IK_VECTOR_LENGTH (ikptr_t vec)

Return an integer representing the number of items in the vector vec.

Preprocessor Macro: ikptr_t IK_ITEM (ikptr_t vec, ikuword_t idx)

Evaluate to the item at index idx in the vector vec. A use of this macro can appear both as operand and as left–side of an assignment; example:

ikuword_t  idx   = the_index;
ikptr_t    s_vec = the_vector;
ikptr_t    fx;

IK_ITEM(s_vec, idx) = IK_FIX(10);
fx = IK_ITEM(s_vec, idx);

Preprocessor Macro: ikptr_t * IK_ITEM_PTR (ikptr_t vec, ikuword_t idx)

Return a pointer to the machine word holding the vector item at index idx. This is especially useful to build the second argument in a call to ik_signal_dirt_in_page_of_pointer().

Operations on vectors

Function: ikptr_t ika_vector_alloc_no_init (ikpcb_t * pcb, ikuword_t number_of_items)

Function: ikptr_t iku_vector_alloc_no_init (ikpcb_t * pcb, ikuword_t number_of_items)

Allocate, initialise and return a new vector object capable of holding the specified number of items. Leave the data area uninitialised.

These functions do not call ik_signal_dirt_in_page_of_pointer().

Function: ikptr_t ika_vector_alloc_and_init (ikpcb_t * pcb, ikuword_t number_of_items)

Function: ikptr_t iku_vector_alloc_and_init (ikpcb_t * pcb, ikuword_t number_of_items)

Allocate, initialise and return a new vector object capable of holding the specified number of items. Initialise the data area so that all the items are set to the fixnum zero.

These functions do not call ik_signal_dirt_in_page_of_pointer().

Function: int ik_is_vector (ikptr_t vec)

Return true if vec is a reference to a vector object. This predicate tests that vec is tagged as vector reference and that the first machine word in the referenced memory block is a fixnum.

Function: ikptr_t ikrt_vector_clean (ikptr_t vec)

Clean the data area so that all the items are set to the fixnum zero.

Function: ikptr_t ikrt_vector_copy (ikptr_t dst, ikptr_t dst_start, ikptr_t src, ikptr_t src_start, ikptr_t count, ikpcb_t * pcb)

Copy count items from vector src starting at offset src_start, to vector dst starting at offset dst_start; src_start, dst_start and count must be non–negative fixnums. Return unspecified values.