cons.c File Reference

Implementation of cons cell operations. More...

#include <cons.h>
#include <stdlib.h>

Include dependency graph for cons.c:

Go to the source code of this file.

Functions
static bool	cons_delete_p (struct cons **list, struct cons *cell, void *user)
static bool	cons_remove_p (struct cons **list, struct cons *cell, void *user)
struct cons **	cons (struct cons **list, struct cons *cell)
	Prepends a cons cell to a list.
struct cons **	cons_prepend (struct cons **list, struct cons *cell)
	Prepends a cons cell to a list, returning the updated list pointer.
struct cons **	cons_loop (struct cons **list, bool(*pred)(struct cons **list, struct cons *cell, void *user), void *user)
	Loops through a list of cons cells, applying a predicate function to each cell.
static bool	cons_find_p (struct cons **list, struct cons *cell, void *user)
struct cons **	cons_find (struct cons **list, void *cell)
	Finds the first cons cell in a list that matches a given identity.
struct cons *	cons_delete (struct cons **list, void *car)
	Destructively deletes the first cons cell with the specified car value from the list.
struct cons *	cons_remove (struct cons **list, struct cons *cell)
	Destructively removes the specified cons cell from the list.
void	cons_reverse (struct cons **list)
	Reverses a linked list of cons cells in place.
size_t	cons_length (const struct cons *cell)
	Computes the length of a linked list of cons cells.
struct cons *	cons_last (struct cons *cell)
	Returns the last cons cell in a linked list of cons cells.
struct cons *	cons_nth (struct cons *cell, size_t nth)
	Returns the n'th cons cell in a linked list of cons cells.
struct cons *	cons_member (struct cons *cell, void *car)
	Returns the first cons cell in a linked list of cons cells whose car field matches the specified value.
struct cons *	cons_append (struct cons *cell1, struct cons *cell2)
	Appends one list of cons cells to another.
struct cons *	cons_heap (void *car)
	Allocates a new cons cell on the heap.
void	cons_free (struct cons *cell)
	Frees a heap-allocated cons cell.

Detailed Description

Implementation of cons cell operations.

This file implements functions for manipulating cons cells, which are fundamental data structures in Lisp-like languages. The functions link caller-provided cons cells into lists, remove cells from a list, and reverse a list of cons cells. The operations work with the structure defined in cons.h to link and manipulate linked lists and other complex data structures.

Definition in file cons.c.

Function Documentation

cons()

struct cons ** cons	(	struct cons **	list,
		struct cons *	cell
	)

Prepends a cons cell to a list.

Parameters

list	Pointer to the list head to which the new cell will be prepended. This is a pointer to a pointer to a cons cell, allowing the function to update the list pointer to point to the new cell.
cell	The cons cell to prepend to the list.

Returns

Pointer to the cdr field of the new cell for chaining. Use the return value to further add elements to the list by chaining additional cons cells together.

The cons function takes a pointer to a list (which is a pointer to a cons cell) and a cons cell to prepend. It initialises the cdr of the new cell to point to the existing list and updates the list pointer to point to the new cell. This effectively adds the new cell to the front of the list. The cons function is a fundamental operation in Lisp-like languages, where it is used to construct lists and other complex data structures. The car field of the new cell can hold any type of data, while the cdr field is specifically designed to link to another cons cell, facilitating the construction of linked lists and other complex data structures. The cons function allows for efficient list manipulation by enabling the addition of new elements to the front of the list without needing to traverse the entire list, making it a powerful tool for building and modifying lists in a flexible and efficient manner.

Definition at line 24 of file cons.c.

                                                          {
  cons_rplacd(cell, *list);
  *list = cell;
  return &cell->cdr;
}

cons_append()

struct cons * cons_append	(	struct cons *	cell1,
		struct cons *	cell2
	)

Appends one list of cons cells to another.

Parameters

cell1	The first list to which the second list will be appended. This list will be modified to include the second list at its end.
cell2	The second list to append to the first list. This list will not be modified, but its cells will be linked into the first list.

Returns

Pointer to the head of the combined list, which is the same as cell1 if it is not empty, or cell2 if cell1 is empty.

This function takes two lists of cons cells and appends the second list to the end of the first list. If the first list is empty (i.e., if cell1 is CONS_NIL), it simply returns cell2 as the new combined list. If the first list is not empty, it finds the last cell of the first list and updates its cdr pointer to point to the head of the second list, effectively linking the two lists together. The function then returns a pointer to the head of the combined list, which is the same as cell1.

Definition at line 151 of file cons.c.

                                                                 {
  struct cons *last = cons_last(cell1);
  if (CONS_NIL_P(last)) {
    return cell2;
  }
  cons_rplacd(last, cell2);
  return cell1;
}

cons_delete()

struct cons * cons_delete	(	struct cons **	list,
		void *	car
	)

Destructively deletes the first cons cell with the specified car value from the list.

Parameters

list	Pointer to the list head.
car	The value to match for deletion.

Returns

Pointer to the deleted cons cell, or CONS_NIL if no matching cell was found.

This function traverses the list of cons cells, looking for the first cell whose car field matches the specified value. If such a cell is found, it is removed from the list by updating the cdr pointer of the previous cell (or the head pointer if the cell to delete is the first cell) to point to the next cell, effectively bypassing the deleted cell. The function then returns a pointer to the deleted cell. If no matching cell is found after traversing the entire list, the function returns CONS_NIL to indicate that no deletion occurred. This operation is destructive because it modifies the original list structure by removing a cell from it. The caller is responsible for managing the memory of the deleted cell if necessary, as this function does not free the memory of the deleted cell; it only removes it from the list.

Definition at line 71 of file cons.c.

                                                        {
  struct cons **found = cons_loop(list, cons_delete_p, car);
  if (found == NULL) {
    return CONS_NIL;
  }
  struct cons *deleted = *found;
  *found = cons_cdr(deleted);
  return deleted;
}

cons_delete_p()

static bool cons_delete_p ( struct cons **  list, struct cons *  cell, void *  user  )

static

Definition at line 66 of file cons.c.

                                                                             {
  (void)list;
  return cons_car(cell) == user;
}

cons_find()

struct cons ** cons_find	(	struct cons **	list,
		void *	cell
	)

Finds the first cons cell in a list that matches a given identity.

Parameters

list	Pointer to the list head to search through. This is a pointer to a pointer to a cons cell.
cell	The cons cell to find by identity.

Returns

Pointer to the list pointer of the first cons cell that matches the specified identity, or NULL if no such cell is found.

Definition at line 62 of file cons.c.

                                                        {
  return cons_loop(list, cons_find_p, cell);
}

cons_find_p()

static bool cons_find_p ( struct cons **  list, struct cons *  cell, void *  user  )

static

Definition at line 57 of file cons.c.

                                                                           {
  (void)list;
  return cell == user;
}

cons_free()

void cons_free

(

struct cons *

cell

)

Frees a heap-allocated cons cell.

Definition at line 168 of file cons.c.

                                  {
  /*
   * Check for CONS_NIL before freeing the cell, as CONS_NIL is a
   * special value that represents "the" empty list and should not be
   * freed. If the cell is not CONS_NIL, assume it is safe to free the
   * heap-allocated memory for that cell. This check prevents accidental
   * deallocation of the CONS_NIL sentinel value; although, strictly
   * speaking, the implementation can free(NULL) without causing
   * undefined behavior.
   */
  if (CONS_NOT_NIL_P(cell)) {
    free(cell);
  }
}

cons_heap()

struct cons * cons_heap

(

void *

car

)

Allocates a new cons cell on the heap.

Allocates memory for a new cons cell and initialises it with the provided car value. The caller is responsible for freeing the allocated memory when it is no longer needed.

Parameters

car	The value to store in the car field of the new cons cell.

Returns

Pointer to the newly allocated cons cell, or CONS_NIL if memory allocation fails.

Definition at line 160 of file cons.c.

                                  {
  struct cons *cell = (struct cons *)malloc(sizeof(struct cons));
  if (CONS_NOT_NIL_P(cell)) {
    cons_init(cell, car);
  }
  return cell;
}

cons_last()

struct cons * cons_last

(

struct cons *

cell

)

Returns the last cons cell in a linked list of cons cells.

Parameters

cell	The head of the list to find the last cell of, or CONS_NIL for an empty list.

Returns

Pointer to the last cons cell in the list, or CONS_NIL if the list is empty.

This function iteratively traverses the linked list of cons cells until it reaches the last cell, which is identified by having its cdr field equal to CONS_NIL. It returns a pointer to this last cell. If the input list is empty (i.e., if the input pointer is CONS_NIL), the function returns CONS_NIL to indicate that there are no cells in the list.

Definition at line 120 of file cons.c.

                                          {
  if (CONS_NIL_P(cell)) {
    return CONS_NIL;
  }
  /*
   * The last cell in a list is the one having its cdr field equal to CONS_NIL.
   */
  struct cons *tail;
  while (CONS_NOT_NIL_P(tail = cons_cdr(cell))) {
    cell = tail;
  }
  return cell;
}

cons_length()

size_t cons_length

(

const struct cons *

cell

)

Computes the length of a linked list of cons cells.

Parameters

cell	The head of the list to compute the length of, or CONS_NIL for an empty list.

Returns

The number of cons cells in the list.

This function iteratively traverses the linked list of cons cells, counting the number of cells until it reaches the end of the list (indicated by CONS_NIL). It returns the total count as the length of the list.

Definition at line 111 of file cons.c.

                                            {
  size_t length = 0;
  while (CONS_NOT_NIL_P(cell)) {
    length++;
    cell = cons_cdr(cell);
  }
  return length;
}

cons_loop()

struct cons ** cons_loop	(	struct cons **	list,
		bool(*)(struct cons **list, struct cons *cell, void *user)	pred,
		void *	user
	)

Loops through a list of cons cells, applying a predicate function to each cell.

Parameters

list	Pointer to the list head to loop through. This is a pointer to a pointer to a cons cell.
pred	A predicate function that takes a pointer to the current list pointer, the current cons cell, and a user-defined pointer. The predicate should return true if the current cell matches the desired condition, and false otherwise.
user	A user-defined pointer that can be passed to the predicate function for additional context or data needed for the predicate's logic.

Returns

Pointer to the list pointer of the first cons cell for which the predicate returns true, or NULL if no such cell is found. The returned pointer allows the caller to modify the list starting from the found cell if needed. If the predicate does not find a matching cell in the list, the function returns NULL to indicate that the search was unsuccessful. This design allows the function to signal the absence of a matching cell without returning a pointer to a cons cell, which would be misleading since it would suggest that a valid cell was found when in fact it was not. By returning NULL, the function provides a clear and unambiguous way to indicate that the search was unsuccessful.

Definition at line 35 of file cons.c.

                                                                                                                         {
  for (struct cons *cell = *list; CONS_NOT_NIL_P(cell); list = &cell->cdr, cell = cons_cdr(cell)) {
    if (pred(list, cell, user)) {
      return list;
    }
  }
  /*
   * Returning NULL is correct. It is a NULL pointer to a pointer to a
   * cons cell---a pointer to the head of a list. Therefore not itself a
   * cons cell pointer. Returning NULL indicates that the predicate did
   * not find a matching cell in the list, and thus there is no pointer
   * to a cons cell that satisfies the predicate.
   *
   * This design allows the function to signal the absence of a matching
   * cell without returning a pointer to a cons cell, which would be
   * misleading since it would suggest that a valid cell was found when
   * in fact it was not. By returning NULL, the function provides a
   * unambiguous way to indicate that the search was unsuccessful.
   */
  return NULL;
}

cons_member()

struct cons * cons_member	(	struct cons *	cell,
		void *	car
	)

Returns the first cons cell in a linked list of cons cells whose car field matches the specified value.

Parameters

cell	The head of the list to search, or CONS_NIL for an empty list.
car	The value to match in the car field of the cons cells.

Returns

Pointer to the first matching cons cell, or CONS_NIL if no match is found.

Iteratively traverses the linked list of cons cells, comparing the car field of each cell with the specified value. If a match is found, a pointer to the matching cell is returned. If the end of the list is reached without finding a match, CONS_NIL is returned.

Definition at line 142 of file cons.c.

                                                       {
  for (; CONS_NOT_NIL_P(cell); cell = cons_cdr(cell)) {
    if (cons_car(cell) == car) {
      return cell;
    }
  }
  return CONS_NIL;
}

cons_nth()

struct cons * cons_nth	(	struct cons *	cell,
		size_t	nth
	)

Returns the n'th cons cell in a linked list of cons cells.

Parameters

cell	The head of the list to find the n'th cell of, or CONS_NIL for an empty list.
nth	The zero-based index of the cell to retrieve.

Returns

Pointer to the n'th cons cell in the list, or CONS_NIL if the index is out of bounds.

Iteratively traverses the linked list of cons cells, counting the cells as it goes. When the count reaches the specified index nth, it returns a pointer to the current cell. If the end of the list is reached before finding the n'th cell (i.e., if the input pointer becomes CONS_NIL), the function returns CONS_NIL to indicate that the index is out of bounds.

Definition at line 134 of file cons.c.

                                                     {
  while (CONS_NOT_NIL_P(cell) && nth != 0) {
    cell = cons_cdr(cell);
    nth--;
  }
  return cell;
}

cons_prepend()

struct cons ** cons_prepend	(	struct cons **	list,
		struct cons *	cell
	)

Prepends a cons cell to a list, returning the updated list pointer.

Parameters

list	Pointer to the list head to which the new cell will be prepended.
cell	The cons cell to prepend to the list.

Returns

Pointer to the updated list pointer, now pointing to the new cell.

A wrapper around cons that allows convenient chaining of cons cell additions without separately managing the list pointer.

Definition at line 30 of file cons.c.

                                                                  {
  (void)cons(list, cell);
  return list;
}

cons_remove()

struct cons * cons_remove	(	struct cons **	list,
		struct cons *	cell
	)

Destructively removes the specified cons cell from the list.

Parameters

list	Pointer to the list head.
cell	The cons cell to remove from the list, matched by identity.

Return values

The	removed cons cell if the specified cell was found and removed.

c CONS_NIL if the specified cell was not found in the list.

Traverses the list of cons cells, looking for the specified cell. If the cell is found, it is removed from the list by updating the cdr pointer of the previous cell (or the head pointer if the cell to remove is the first cell) to point to the next cell, thereby bypassing the removed cell.

Definition at line 81 of file cons.c.

                                                                {
  struct cons **found = cons_find(list, cell);
  if (found == NULL) {
    return CONS_NIL;
  }
  struct cons *removed = *found;
  *found = cons_cdr(removed);
  return removed;
}

cons_reverse()

void cons_reverse

(

struct cons **

list

)

Reverses a linked list of cons cells in place.

This function takes a pointer to the head of a linked list of cons cells and reverses the order of the cells in the list. It iteratively traverses the list, reassigning the cdr pointers to point to the previous cell, effectively reversing the list.

Parameters

list	The list to reverse. This is a pointer to the head of the list, and it will be updated to point to the new head of the reversed list.

Definition at line 91 of file cons.c.

                                      {
  /*
   * Maintain a pointer to the reversed list (initially CONS_NIL) and
   * iteratively traverse the original list. For each cell, save the next cell
   * (cdr) before reassigning the cdr of the current cell to point to the
   * reversed list. Then update the reversed list to be the current cell and
   * move to the next cell in the original list. This process continues until
   * reversing has traversed the entire original list, at which point the
   * reversed list will contain all the cells in reverse order.
   */
  struct cons *reversed = CONS_NIL, *cell = *list;
  while (CONS_NOT_NIL_P(cell)) {
    struct cons *tail = cons_cdr(cell);
    cons_rplacd(cell, reversed);
    reversed = cell;
    cell = tail;
  }
  *list = reversed;
}