Vicare Scheme: objects pairs

13.6 Pair objects and lists

A pair is a fixed–length block of memory composed of two machine words; the 3 least significant bits of an ikptr_t reference to a pair are the pair tag.

|-------------------------|-------------| reference to pair
      heap pointer           pair tag

|-------------------|-------------------| pair memory block
    word 0 = car        word 1 = cdr

The empty list is not a pair: it is a special constant fitting in a single ikptr_t machine word, and it is defined by the preprocessor symbol IK_NULL_OBJECT, shortly IK_NULL.

Basic operations

Pairs are allocated as follows, leaving the car and cdr uninitialised:

ikpcb_t *  pcb    = ik_the_pcb();
ikptr_t    s_pair = IKA_PAIR_ALLOC(pcb);

the car and cdr of a pair are extracted as follows:

ikptr_t   s_pair = ...;
ikptr_t   s_car, s_cdr;

s_car = IK_CAR(s_pair);
s_cdr = IK_CDR(s_pair);

the car and cdr of a pair are set as follows:

ikpcb_t * pcb    = ...;
ikptr_t   s_pair = ...;
ikptr_t   s_car  = ...;
ikptr_t   s_cdr  = ...;

IK_CAR(s_pair) = s_car;
IK_SIGNAL_DIRT(pcb, IK_CAR_PTR(s_pair));

IK_CDR(s_pair) = s_car;
IK_SIGNAL_DIRT(pcb, IK_CDR_PTR(s_pair));

Preprocessor Symbol: pair_mask
Preprocessor Symbol: pair_tag
Preprocessor Symbol: pair_size: pair_mask is the bit pattern used to isolate a pair tag from a reference ikptr_t; pair_tag is the tag of ikptr_t values referencing a pair; pair_size is the number of bytes in a pair memory block on the heap.

Preprocessor Symbol: disp_car
Preprocessor Symbol: disp_cdr
Preprocessor Symbol: off_car
Preprocessor Symbol: off_cdr: disp_car and disp_cdr are the offsets in bytes of the car and cdr from the beginning of a pair memory block; off_car and off_cdr are integers to be added to a reference ikptr_t tagged as pair to retrieve the car and the cdr from a pair memory block.

Convenience preprocessor macros

Preprocessor Macro: int IK_IS_PAIR (ikptr_t X): Evaluate to true if the machine word X is tagged as pair.

Preprocessor Macro: ikptr_t IKA_PAIR_ALLOC (ikpcb_t * pcb): Allocate a new pair object using ik_safe_alloc() and return a tagged reference to it. The pair words are left uninitialised.

Preprocessor Macro: ikptr_t IKU_PAIR_ALLOC (ikpcb_t * pcb): Allocate a new pair object using ik_unsafe_alloc() and return a tagged reference to it. The pair words are left uninitialised.

Preprocessor Macro: ikptr_t IK_CAR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDR (ikptr_t pair): Evaluate to the locations of the car and cdr of a pair; uses of these macros can appear both as operands and as left–side of assignments.

Preprocessor Macro: ikptr_t IK_CAR_PTR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDR_PTR (ikptr_t pair): Evaluate to the pointers to the memory locations holding the car and cdr of a pair.

Preprocessor Macro: ikptr_t IK_CAAR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDAR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CADR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDDR (ikptr_t pair): Return, respectively: the car of the car, the cdr of the car, the car of the cdr, the cdr of the cdr.

Preprocessor Macro: ikptr_t IK_CAAR_PTR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDAR_PTR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CADR_PTR (ikptr_t pair)
Preprocessor Macro: ikptr_t IK_CDDR_PTR (ikptr_t pair): Evaluate to the pointers to the memory locations hokding the caar, cdar, cadr and cddr of the pair.

Operations on pairs and lists

Function: ikptr_t ika_pair_alloc (ikpcb_t * pcb)

Function: ikptr_t iku_pair_alloc (ikpcb_t * pcb)

Allocate and return a new pair object using, respectively, ik_safe_alloc() and ik_unsafe_alloc() and return a tagged reference to it. Both the car and cdr are initialised to IK_VOID_OBJECT.

These functions do not call ik_signal_dirt_in_page_of_pointer().

Function: ikuword_t ik_list_length (ikptr_t list): Return the length of the proper list referenced by list. Do not handle circular lists. If the length exceeds LONG_MAX: terminate the process with ik_abort().

Function: void ik_list_to_argv (ikptr_t list, char ** argv): Given a reference list to a proper list of bytevectors, fill argv with pointers to the data areas, setting the last element of argv to NULL. The array referenced by argv must be wide enough to hold all the pointers from list plus the terminating NULL.

Function: void ik_list_to_argv_and_argc (ikptr_t list, char ** argv, long * argc): Given a reference list to a proper list of bytevectors: fill argv with pointers to the data areas, setting the last element of argv to NULL; fill argc with the lengths of the bytevectors. The array referenced by argv must be wide enough to hold all the pointers from list plus the terminating NULL; the array referenced by argc must be wide enough to hold all the lengths.

Function: ikptr_t ika_list_from_argv (ikpcb_t * pcb, char ** argv)

Given a pointer argv to a NULL–terminated array of ASCIIZ strings build and return a list of bytevectors holding a copy of the ASCIIZ strings. Make use of pcb->root8 and pcb->root9.

This function takes care of calling ik_signal_dirt_in_page_of_pointer() when appropriate.

Function: ikptr_t ika_list_from_argv_and_argc (ikpcb_t * pcb, char ** argv, int argc)

Given a pointer argv to an array of ASCIIZ strings holding argc pointers: build and return a list of bytevectors holding a copy of the ASCIIZ strings. Make use of pcb->root8 and pcb->root9.

This function takes care of calling ik_signal_dirt_in_page_of_pointer() when appropriate.

Pairs and lists code examples

The suggested general way to allocate and initialise a pair is as follows:

ikpcb_t * pcb   = ...;
ikptr_t   s_pair;

s_pair = ika_pair_alloc(pcb);
pcb->root0 = &s_pair;
{
  IK_ASS(IK_CAR(s_pair), ...);
  IK_SIGNAL_DIRT(pcb, IK_CAR_PTR(s_pair));

  IK_ASS(IK_CDR(s_pair), ...);
  IK_SIGNAL_DIRT(pcb, IK_CDR_PTR(s_pair));
}
pcb->root0 = NULL;

notice how we take care of allocating the new pair with a function that initialises the component words and of registering the pair as garbage collection root before calling the constructors for the car and cdr.

If the component words do not need memory allocation, for example because they are fixnums or already existing objects, we can use the faster code:

ikpcb_t * pcb    = ik_the_pcb();
ikptr_t   s_pair = IKA_PAIR_ALLOC(pcb);

IK_CAR(s_pair) = IK_FIX(123);
IK_CDR(s_pair) = IK_FIX(456);

Let’s say we need to build a list of bytevectors from ASCIIZ strings in the array argv and there are argc of them:

ikpcb_t * pcb  = ik_the_pcb();
char **   argv = ...;
long      argc = ...;
ikptr_t   s_list;

if (argc) {
  ikptr_t  s_spine;
  long   i;

  s_list = s_spine = ika_pair_alloc(pcb);
  pcb->root0 = &s_list;
  pcb->root1 = &s_spine;
  {
    for (i=0; i<argc;) {
      IK_ASS(IK_CAR(s_spine),
             ika_bytevector_from_cstring(pcb, argv[i]));
      IK_SIGNAL_DIRT(pcb, IK_CAR_PTR(s_spine));
      if (++i < argc) {
        IK_ASS(IK_CDR(s_spine), ika_pair_alloc(pcb));
        IK_SIGNAL_DIRT(pcb, IK_CDR_PTR(s_spine));
        s_spine = IK_CDR(s_spine);
      } else {
        IK_CDR(s_spine) = IK_NULL_OBJECT;
        break;
      }
    }
  }
  pcb->root1 = NULL;
  pcb->root0 = NULL;
} else
  s_list = IK_NULL_OBJECT;

/* make use of S_LIST */