list.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "genC.h"
#include "newgen_include.h"

Include dependency graph for list.c:

Go to the source code of this file.

Data Structures
struct	__gen_sweep_state
	sweep status More...

Macros
#define	NEXT(cp)   (((cp) == NIL) ? NIL : (cp)->cdr)

Functions
bool	gen_eq (const void *obj1, const void *obj2)
bool	gen_list_cyclic_p (const list ml)
size_t	gen_length (const list l)
size_t	list_own_allocated_memory (const list l)
void	gen_mapl (gen_iter_func_t fp, const list l)
	MAP. More...
void	gen_map (gen_iter_func_t fp, const list l)
void *	gen_reduce (void *r, void *(*fp)(void *, const list), const list l)
bool	gen_equals (const list l0, const list l1, gen_eq_func_t equals)
	compares two lists using the functor given in parameters returns true if for all n, the n'th element of first list is equals to the n'th element of the second list More...
list	gen_some (gen_filter_func_t fp, const list l)
static bool	cons_of_gen_chunk (const list cp)
void	gen_insert_after (const void *no, const void *o, list l)
list	gen_insert_before (const void *no, const void *o, list l)
list	gen_insert_list (list nl, const void *item, list l, bool before)
	insert nl before or after item in list l, both initial lists are consumed More...
list	gen_nreverse (list cp)
	reverse a list in place More...
void	gen_free_list (list l)
	free the spine of the list More...
list	gen_nconc (list cp1, list cp2)
	physically concatenates CP1 and CP2 but do not duplicates the elements More...
void	gen_copy (void *a, void *b)
	#define CONS(type,x,l) gen_cons((void*) (x), (l)) More...
void *	gen_car (list l)
void *	gen_find_if (gen_filter_func_t test, const list l, gen_extract_func_t extract)
void *	gen_find_if_from_end (gen_filter_func_t test, const list l, gen_extract_func_t extract)
	the last match is returned More...
void *	gen_find (const void *item, const list seq, gen_filter2_func_t test, gen_extract_func_t extract)
void *	gen_find_from_end (const void *item, const list seq, gen_filter2_func_t test, gen_extract_func_t extract)
void *	gen_find_eq (const void *item, const list seq)
list	gen_concatenate (const list l1x, const list l2x)
	concatenate two lists. More...
list	gen_append (list l1, const list l2)
list	gen_copy_seq (list l)
	Copy a list structure. More...
list	gen_full_copy_list (list l)
	Copy a list structure with element copy. More...
list	gen_copy_string_list (list ls)
	of string More...
void	gen_free_string_list (list ls)
list	gen_last (list l)
	Return the last element of a list. More...
void	gen_substitute_chunk_by_list (list *pl, const void *o, list sl)
	substitute item o by list sl in list *pl, which is modified as a side effect. More...
bool	gen_replace_in_list (list l, const void *s, const void *t)
	substitute all item s by t in list l More...
void	gen_exchange_in_list (list l, const void *i1, const void *i2)
	exchange items i1 & i2 in the list More...
static void	gen_remove_from_list (list *pl, const void *o, bool once)
	remove item o from list *pl which is modified as a side effect. More...
void	gen_remove (list *cpp, const void *o)
	remove all occurences of item o from list *cpp, which is thus modified. More...
void	gen_remove_once (list *pl, const void *o)
	Remove the first occurence of o in list pl: More...
list	gen_nthcdr (int n, const list lx)
	caution: the first item is 0! was: return( (n<=0) ? l : gen_nthcdr( n-1, CDR( l ))) ; if n>gen_length(l), NIL is returned. More...
gen_chunk	gen_nth (int n, const list l)
	to be used as ENTITY(gen_nth(3, l))... More...
list	gen_once (const void *vo, list l)
	Prepend an item to a list only if it is not already in the list. More...
bool	gen_in_list_p (const void *vo, const list lx)
	tell whether vo belongs to lx More...
int	gen_occurences (const void *vo, const list l)
	count occurences of vo in l More...
bool	gen_once_p (list l)
	FC: ARGH...O(n^2)! More...
void	gen_free_area (void **p, int size)
	free an area. More...
void	gen_sort_list (list l, gen_cmp_func_t compare)
	Sorts a list of gen_chunks in place, to avoid allocations... More...
void	gen_closure (list(*iterate)(), list(*initial)())
	void gen_closure(iterate, initial) list [of X] (*iterate)([ X, list of X ]), initial; More...
list	gen_make_list (int domain,...)
void	gen_fprint (FILE *out, string name, const list l, gen_string_func_t item_name)
list	gen_cons (const void *item, const list next)
list	gen_typed_cons (_int type, const void *item, const list next)
	CONS a list with minimal type checking this cannot be done within the CONS macro because possible functions calls must not be replicated. More...
list	gen_bool_cons (bool b, const list l)
	typed cons for "basic" types More...
list	gen_int_cons (_int i, const list l)
list	gen_string_cons (string s, const list l)
list	gen_list_cons (const list i, const list l)
list	gen_CHUNK_cons (const gen_chunk *c, const list l)
list	gen_VOID_STAR_cons (const void *e, const list l)
void	gen_list_and (list *a, const list b)
	Compute A = A inter B: complexity in O(n2) More...
void	gen_list_and_not (list *a, const list b)
	Compute A = A inter non B: More...
void	gen_list_patch (list l, const void *x, const void *y)
	Replace all the reference to x in list l by a reference to y: More...
int	gen_position (const void *item, const list l)
	Element ranks are strictly positive as for first, second, and so on. More...
list	gen_list_head (list *lp, int n)
list	gen_common_prefix (const list l1, const list l2)
	return the common list prefix of lists l1 and l2. More...
gen_sweep_state	gen_sweep_init (list l, gen_sweep_direction dir, list *phead, list *ptail)
	initialize list l sweep in direction dir, with pointers for head & tail More...
bool	gen_sweep_update (gen_sweep_state state)
void	gen_sweep_done (gen_sweep_state state)

Variables
static gen_chunk *	gen_chunk_of_cons_of_gen_chunk = gen_chunk_undefined
	SPECIAL INSERTION. More...

Function Documentation

gen_sweep_done()

void gen_sweep_done

(

gen_sweep_state

state

)

Definition at line 1166 of file list.c.

{
  message_assert("some state", state != NULL);
 
  // complete sweep to relink the initial list
  state->phead = NULL;
  state->ptail = NULL;
  while (gen_sweep_update(state));
 
  // cleanup
  free(state);
}

References free(), gen_sweep_update(), message_assert, __gen_sweep_state::phead, and __gen_sweep_state::ptail.

Here is the call graph for this function:

gen_sweep_init()

gen_sweep_state gen_sweep_init	(	list	l,
		gen_sweep_direction	dir,
		list *	phead,
		list *	ptail
	)

initialize list l sweep in direction dir, with pointers for head & tail

Definition at line 1060 of file list.c.

{
  gen_sweep_state state = malloc(sizeof(struct __gen_sweep_state));
  message_assert("malloc ok", state != NULL);
 
  state->dir = dir;
  state->initial = l;
  state->phead = phead;
  state->ptail = ptail;
  state->done = (l == NIL);
 
  switch (dir)
  {
  case gen_sweep_forward:
    state->head = NIL;
    state->tail = l;
    state->last = NIL;
    state->reversed = NIL; // unused
    break;
 
  case gen_sweep_backward:
    state->head = l;
    state->tail = NIL;
    state->last = NIL; // unused
  {
    list nl = NIL, c = l;
    while (c != NIL) {
      nl = CONS(LIST, c, nl);
      c = CDR(c);
    }
    state->reversed = nl;
  }
    break;
 
  default:
    fprintf(stderr, "unexpected sweep direction: %d\n", dir);
    abort();
  }
 
  // update external pointers
  if (state->phead)
    *(state->phead) = state->head;
  if (state->ptail)
    *(state->ptail) = state->tail;
 
  return state;
}

References abort, CDR, CONS, __gen_sweep_state::dir, __gen_sweep_state::done, fprintf(), gen_sweep_backward, gen_sweep_forward, __gen_sweep_state::head, if(), __gen_sweep_state::initial, __gen_sweep_state::last, LIST, malloc(), message_assert, NIL, __gen_sweep_state::phead, __gen_sweep_state::ptail, __gen_sweep_state::reversed, and __gen_sweep_state::tail.

Here is the call graph for this function:

gen_sweep_update()

bool gen_sweep_update

(

gen_sweep_state

state

)

Definition at line 1108 of file list.c.

{
  if (state->done)
    return false;
 
  switch (state->dir)
  {
  case gen_sweep_forward:
    // first update
    if (state->head == NIL)
      state->head = state->last = state->tail;
    else
      // relink last cons
      CDR(state->last) = state->tail;
    // set new last cons
    state->last = state->tail;
    // move forward tail
    state->tail = CDR(state->tail);
    // check for end
    state->done = state->tail == NIL;
    // cut last const
    if (!state->done)
      CDR(state->last) = NIL;
    break;
 
  case gen_sweep_backward:
  {
    list previous_tail = state->tail, tmp = state->reversed;
    // tails move backwards
    state->tail = LIST(CAR(state->reversed));
    // relink tail
    CDR(state->tail) = previous_tail;
    // move backwards
    state->reversed = CDR(state->reversed);
    // cleanup
    free(tmp);
    // last one
    if (state->reversed == NIL)
      state->head = NIL;
    // check for end
    state->done = state->head == NIL;
  }
    break;
 
  default:
    fprintf(stderr, "unexpected sweep direction: %d\n", state->dir);
    abort();
  }
 
  // update external pointers
  if (state->phead)
    *(state->phead) = state->head;
  if (state->ptail)
    *(state->ptail) = state->tail;
 
  return true;
}

References abort, CAR, CDR, __gen_sweep_state::dir, __gen_sweep_state::done, fprintf(), free(), gen_sweep_backward, gen_sweep_forward, __gen_sweep_state::head, if(), __gen_sweep_state::last, LIST, NIL, __gen_sweep_state::phead, __gen_sweep_state::ptail, __gen_sweep_state::reversed, and __gen_sweep_state::tail.

Referenced by gen_sweep_done().

Here is the call graph for this function:

Here is the caller graph for this function: