stack.c File Reference

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

Include dependency graph for stack.c:

Go to the source code of this file.

Data Structures
struct	__stack_bucket
	STACK STRUCTURES. More...
struct	__stack_head
	the stack head More...
struct	__stack_iterator
	STACK ITERATOR. More...

Macros
#define	STACK_PTR_NULL   ((_stack_ptr) NULL)
	and also *stack (in headers) More...
#define	STACK_PTR_NULL_P(x)   ((x)==STACK_PTR_NULL)
#define	STACK_DEFAULT_SIZE   50
#define	STACK_ITERATOR_END_P(i)   STACK_PTR_NULL_P(i->bucket)
#define	DEFINE_ITERATOR(i, blk, idx, dwn, lst)
#define	UPDATE_ITERATOR_DOWNWARD(i)
#define	UPDATE_ITERATOR_UPWARD(i)
#define	NEXT_ITERATION(i)
#define	STACK_OBSERVER(name, what)    int stack_##name(const stack s) { STACK_CHECK(s); return(what); }
	STACK MISCELLANEOUS. More...

Typedefs
typedef struct __stack_bucket	_stack_bucket
	STACK STRUCTURES. More...
typedef struct __stack_bucket *	_stack_ptr
typedef struct __stack_head	_stack_head
	the stack head More...
typedef struct __stack_iterator	_stack_iterator
	STACK ITERATOR. More...

Functions
static void	update_iterator_upward (stack_iterator i)
	and also *stack_iterator (in headers) More...
static void	stack_iterator_internal_init (const stack s, int down, stack_iterator i)
stack_iterator	stack_iterator_init (const stack s, bool down)
	stack iterator More...
bool	stack_iterator_next_and_go (stack_iterator i, void **pitem)
	X-ward. More...
bool	stack_iterator_end_p (stack_iterator i)
void	stack_iterator_end (stack_iterator *pi)
static _stack_ptr	allocate_bucket (int size)
	allocates a bucket of size size More...
static _stack_ptr	find_or_allocate (stack s)
	search for a new bucket, first in the available list, if none are available, a new bucket is allocated More...
stack	stack_make (int type, int bucket_size, int policy)
	ALLOCATEs a new stack of type. More...
stack	stack_copy (const stack s)
	duplicate a stack with its contents. More...
static void	free_bucket (_stack_ptr x)
	FREEs the stack. More...
static void	free_buckets (_stack_ptr x)
void	stack_free (stack *ps)
	type, bucket_size, policy More...
	STACK_OBSERVER (consistent_p, 1)
	Here we define stack_size(), stack_bsize(), stack_policy() and stack_max_extent(): More...
void	stack_map (const stack s, gen_iter_func_t f)
	APPLY f to all items of stack s;. More...
static int	number_of_buckets (_stack_ptr x)
void	stack_info (FILE *f, const stack s)
void	stack_push (void *item, stack s)
	STACK USE. More...
void *	stack_pop (stack s)
	POPs one item from stack s. More...
void *	stack_head (const stack s)
	returns the item on top of stack s More...
void *	stack_nth (const stack s, int nskip)
	returns the nth item starting from the head and counting from 1, when possible, or NULL, elsewhere. More...
void *	stack_replace (void *item, stack s)
	REPLACEs the item on top of stack s, and returns the old item. More...

Macro Definition Documentation

DEFINE_ITERATOR

#define DEFINE_ITERATOR	(		i,
			blk,
			idx,
			dwn,
			lst
	)

Value:

  {                                                                     \
    i->bucket=(blk);                                                    \
    i->index=(idx);                                                     \
    i->list=lst;                                                        \
    i->downward=dwn;                                                    \
  }

Definition at line 106 of file stack.c.

NEXT_ITERATION

#define NEXT_ITERATION

(

i

)

Value:

  if (i->downward)                              \
  {                                             \
    i->index--; UPDATE_ITERATOR_DOWNWARD(i);    \
  }                                             \
  else                                          \
  {                                             \
    i->index++; UPDATE_ITERATOR_UPWARD(i);      \
  }

Definition at line 125 of file stack.c.

STACK_DEFAULT_SIZE

#define STACK_DEFAULT_SIZE   50

Definition at line 78 of file stack.c.

STACK_ITERATOR_END_P

#define STACK_ITERATOR_END_P

(

i

)

STACK_PTR_NULL_P(i->bucket)

Definition at line 104 of file stack.c.

STACK_OBSERVER

#define STACK_OBSERVER	(		name,
			what
	)		int stack_##name(const stack s) { STACK_CHECK(s); return(what); }

STACK MISCELLANEOUS.

Definition at line 302 of file stack.c.

STACK_PTR_NULL

#define STACK_PTR_NULL   ((_stack_ptr) NULL)

and also *stack (in headers)

usefull defines

Definition at line 76 of file stack.c.

STACK_PTR_NULL_P

#define STACK_PTR_NULL_P

(

x

)

((x)==STACK_PTR_NULL)

Definition at line 77 of file stack.c.

UPDATE_ITERATOR_DOWNWARD

#define UPDATE_ITERATOR_DOWNWARD

(

i

)

Value:

  if (i->index == (size_t) -1)                                          \
    {                                                                   \
      i->bucket = i->bucket->succ;                                      \
      i->index = (i->bucket) ? (i->bucket->n_item)-1 : (size_t) -1;     \
    }

Definition at line 114 of file stack.c.

UPDATE_ITERATOR_UPWARD

#define UPDATE_ITERATOR_UPWARD

(

i

)

Value:

  if (i->index==i->bucket->n_item)                              \
    update_iterator_upward(i);

Definition at line 121 of file stack.c.

Typedef Documentation

_stack_bucket

typedef struct __stack_bucket _stack_bucket

STACK STRUCTURES.

the stack buckets, i.e. arrays containing the elements

_stack_head

typedef struct __stack_head _stack_head

the stack head

_stack_iterator

typedef struct __stack_iterator _stack_iterator

STACK ITERATOR.

_stack_ptr

typedef struct __stack_bucket * _stack_ptr

Function Documentation

allocate_bucket()

static _stack_ptr allocate_bucket ( int  size )

static

allocates a bucket of size size

Definition at line 201 of file stack.c.

{
  _stack_ptr x = (_stack_ptr) malloc(sizeof(_stack_bucket));
  message_assert("pointer was allocated", x);
 
  x->n_item = 0;
  x->max_items = size;
  x->items = (void **) malloc(sizeof(void *)*size);
  message_assert("pointer was allocated", x->items);
  x->succ = STACK_PTR_NULL;
 
  return x;
}

References malloc(), message_assert, STACK_PTR_NULL, and x.

Referenced by find_or_allocate(), and stack_make().

Here is the call graph for this function:

Here is the caller graph for this function:

find_or_allocate()

static _stack_ptr find_or_allocate ( stack  s )

static

search for a new bucket, first in the available list, if none are available, a new bucket is allocated

clean the bucket to be returned

may depend from the policy?

Definition at line 218 of file stack.c.

{
  if (!STACK_PTR_NULL_P(s->avail))
  {
    _stack_ptr x = s->avail;
    s->avail = (s->avail)->succ;
    x->succ = STACK_PTR_NULL; /*  clean the bucket to be returned */
    return x;
  }
  else
  {
    s->n_buckets++;
    /* may depend from the policy? */
    return allocate_bucket(s->bucket_size);
  }
}

References allocate_bucket(), __stack_head::avail, __stack_head::bucket_size, __stack_head::n_buckets, STACK_PTR_NULL, STACK_PTR_NULL_P, and x.

Referenced by stack_push().

Here is the call graph for this function:

Here is the caller graph for this function:

free_bucket()

static void free_bucket ( _stack_ptr  x )

static

FREEs the stack.

Definition at line 276 of file stack.c.

{
  gen_free_area(x->items, x->max_items*sizeof(void*));
  gen_free_area((void**) x, sizeof(_stack_bucket));
}

References gen_free_area(), and x.

Referenced by free_buckets().

Here is the call graph for this function:

Here is the caller graph for this function:

free_buckets()

static void free_buckets ( _stack_ptr  x )

static

Definition at line 282 of file stack.c.

{
  _stack_ptr tmp;
  while(!STACK_PTR_NULL_P(x))
  {
    tmp=x, x=x->succ, tmp->succ=STACK_PTR_NULL;
    free_bucket(tmp);
  }
}

References free_bucket(), STACK_PTR_NULL, STACK_PTR_NULL_P, __stack_bucket::succ, and x.

Referenced by stack_free().

Here is the call graph for this function:

Here is the caller graph for this function:

number_of_buckets()

static int number_of_buckets ( _stack_ptr  x )

static

Definition at line 335 of file stack.c.

{
  int n=0;
  for(; !STACK_PTR_NULL_P(x); x=x->succ, n++);
  return n;
}

References STACK_PTR_NULL_P, and x.

Referenced by stack_info().

Here is the caller graph for this function:

stack_copy()

stack stack_copy

(

const stack

s

)

duplicate a stack with its contents.

Definition at line 267 of file stack.c.

{
  stack n = stack_make(s->type, s->bucket_size, s->policy);
  STACK_MAP_X(i, void*, stack_push(i, n), s, 0);
  return n;
}

References __stack_head::bucket_size, __stack_head::policy, stack_make(), STACK_MAP_X, stack_push(), and __stack_head::type.

Referenced by RenameFunctionEntity(), store_call_context(), and SubstituteDummyParameters().

Here is the call graph for this function:

Here is the caller graph for this function:

stack_free()

void stack_free

(

stack *

ps

)

type, bucket_size, policy

Definition at line 292 of file stack.c.

{
  free_buckets((*ps)->stack), (*ps)->stack=STACK_PTR_NULL;
  free_buckets((*ps)->avail), (*ps)->avail=STACK_PTR_NULL;
  gen_free_area((void**) *ps, sizeof(stack_head));
  *ps = STACK_NULL;
}

References free_buckets(), gen_free_area(), stack_head(), STACK_NULL, and STACK_PTR_NULL.

Referenced by actual_c_parser(), bottom_up_abc_statement(), c_parser_error(), force_reset_c_parser_scope_stack(), force_reset_preprocessor_scope_stack(), ForceResetTypedefStack(), free_statement_global_stack(), gen_internal_context_multi_recurse(), initial_code_abc_statement(), interprocedural_abc_statement(), loop_statistics(), pips_code_abc_statement(), remove_entity_type_stack(), reset_c_parser_scope_stack(), reset_entity_type_stack_table(), reset_preprocessor_scope_stack(), reset_statement_points_to_context(), ResetCurrentModule(), ResetTypedefStack(), string_buffer_free(), top_down_abc_statement(), typing_of_expressions(), xml_Boxes(), xml_Task(), and xml_tasks().

Here is the call graph for this function:

Here is the caller graph for this function:

stack_head()

void* stack_head

(

const stack

s

)

returns the item on top of stack s

HEAD

Definition at line 420 of file stack.c.

{
  _stack_ptr x = s->stack;
  if (x->n_item==0) x = x->succ;
  assert(!STACK_PTR_NULL_P(x) && x->n_item>0);
 
  /*   HEAD
   */
  return x->items[(x->n_item)-1];
}

References assert, __stack_head::stack, STACK_PTR_NULL_P, and x.

Referenced by abc_instrumentation_insert_before_statement(), add_arc_to_statement_points_to_context(), arguments_are_something(), bottom_up_abc_insert_before_statement(), call_rwt(), check_format(), check_io_list(), check_spec(), check_this_loop(), check_this_test(), check_this_whileloop(), EnterScope(), eov_stack_task_pop_task(), ExitScope(), FindOrCreateCurrentEntity(), gen_get_recurse_current_ancestor(), get_c_parser_current_scope(), get_current_statement_from_statement_global_stack(), get_preprocessor_current_scope(), GetContext(), GetContextCopy(), GetFunction(), GetScope(), interprocedural_abc_insert_before_statement(), is_integer_specifier(), is_label_integer_string_specifier(), is_label_specifier(), is_string_specifier(), is_unit_specifier(), is_varibale_array_element_specifier(), loop_flt(), loop_rwt(), MakeBreakStatement(), MakeCaseStatement(), MakeContinueStatement(), MakeDefaultStatement(), MakeForloop(), MakeParameterList(), MakeSwitchStatement(), MakeWhileLoop(), points_to_context_statement_in(), PopContext(), push_if(), push_loop(), pv_context_statement_head(), quick_multi_already_seen_p(), seq_rwt(), stack_free(), StackPop(), StackPush(), statement_with_at_most_one_expression_integer(), statement_with_at_most_one_integer_or_character(), statement_without_argument(), stmt_rwt(), store_call_context(), test_rwt(), top_down_abc_insert_before_statement(), type_this_entity_if_needed(), type_this_expression(), type_this_instruction(), typing_arguments_of_user_function(), typing_assign_substring(), typing_buffer_inout(), typing_function_argument_type_to_return_type(), typing_implied_do(), typing_of_assign(), typing_substring(), uns_rwt(), update_statement_points_to_context_with_arc(), UpdateAbstractEntity(), UpdateDerivedEntity(), UpdateEntity(), and wl_rwt().

stack_info()

void stack_info	(	FILE *	f,
		const stack	s
	)

else

else

Definition at line 342 of file stack.c.

{
  fprintf(f, "stack_info about stack %p\n", s);
 
  if (STACK_NULL_P(s))
  {
    fprintf(f, " - is null\n");
    return;
  }
  /* else */
  if (stack_undefined_p(s))
  {
    fprintf(f, " - is undefined\n");
    return;
  }
  /* else */
  fprintf(f, " - type %d, size %zd, max extent %zd\n",
          s->type, s->size, s->max_extent);
  fprintf(f, " - buckets: %d in use, %d available\n",
          number_of_buckets(s->stack), number_of_buckets(s->avail));
}

References __stack_head::avail, f(), fprintf(), __stack_head::max_extent, number_of_buckets(), __stack_head::size, __stack_head::stack, STACK_NULL_P, stack_undefined_p, and __stack_head::type.

Here is the call graph for this function:

stack_iterator_end()

void stack_iterator_end

(

stack_iterator *

pi

)

Definition at line 184 of file stack.c.

{
  (*pi)->bucket = NEWGEN_FREED;
  (*pi)->downward = 0;
  (*pi)->index = 0;
  (*pi)->list = NEWGEN_FREED;
  free(*pi);
  *pi=(stack_iterator) NULL;
}

References free(), and NEWGEN_FREED.

Here is the call graph for this function:

stack_iterator_end_p()

bool stack_iterator_end_p

(

stack_iterator

i

)

Definition at line 179 of file stack.c.

{
  return STACK_ITERATOR_END_P(i);
}

References STACK_ITERATOR_END_P.

stack_iterator_init()

stack_iterator stack_iterator_init	(	const	stack,
		bool	down
	)

stack iterator

This way the stack type is fully encapsulated, but it is not very efficient, due to the many function calls. Consider "stack_map" first which has a very small overhead.

Definition at line 157 of file stack.c.

{
  stack_iterator i = (stack_iterator) malloc(sizeof(_stack_iterator));
  stack_iterator_internal_init(s, down, i);
  return i;
}

References malloc(), and stack_iterator_internal_init().

Here is the call graph for this function:

stack_iterator_internal_init()

static void stack_iterator_internal_init ( const stack  s, int  down, stack_iterator  i  )

static

NOT the define!

Definition at line 135 of file stack.c.

{
  STACK_CHECK(s);
 
  if ((s->size)==0)
    DEFINE_ITERATOR(i, STACK_PTR_NULL, -1, down, STACK_PTR_NULL)
  else
  {
    if (down)
    {
      DEFINE_ITERATOR(i, s->stack, (s->stack->n_item)-1, down, s->stack);
      UPDATE_ITERATOR_DOWNWARD(i);
    }
    else
    {
      DEFINE_ITERATOR(i, STACK_PTR_NULL, 0, down, s->stack);
      update_iterator_upward(i); /* NOT the define! */
    }
  }
}

References DEFINE_ITERATOR, __stack_bucket::n_item, __stack_head::size, __stack_head::stack, STACK_CHECK, STACK_PTR_NULL, UPDATE_ITERATOR_DOWNWARD, and update_iterator_upward().

Referenced by stack_iterator_init(), and stack_nth().

Here is the call graph for this function:

Here is the caller graph for this function:

stack_iterator_next_and_go()

bool stack_iterator_next_and_go	(	stack_iterator	i,
		void **	pitem
	)

X-ward.

Definition at line 164 of file stack.c.

{
  if (STACK_ITERATOR_END_P(i))
  {
    *pitem = (void*) NULL;
    return false;
  }
  else
  {
    *pitem = (i->bucket->items)[i->index];
    NEXT_ITERATION(i);
    return true;
  }
}

References __stack_iterator::bucket, __stack_iterator::index, __stack_bucket::items, NEXT_ITERATION, and STACK_ITERATOR_END_P.

Referenced by stack_nth().

Here is the caller graph for this function:

stack_make()

stack stack_make	(	int	type,
		int	bucket_size,
		int	policy
	)

ALLOCATEs a new stack of type.

allocation

Parameters

type	record newgen domain of stack contents. should be used to check the type of appended elements.
bucket_size	is the number of elements in the elemental stack container. If you now you will have big stacks, try big numbers here to save memory.
policy	not used, 0 is fine.

not too small

not used

Definition at line 246 of file stack.c.

{
  stack s = (stack) malloc(sizeof(_stack_head));
  message_assert("pointer was allocated", s);
 
  if (bucket_size<10) bucket_size=STACK_DEFAULT_SIZE; /* not too small */
 
  s->size = 0;
  s->type = type;
  s->policy = policy; /* not used */
  s->bucket_size = bucket_size;
  s->max_extent = 0;
  s->n_buckets = 0;
  s->stack = allocate_bucket(bucket_size);
  s->avail = STACK_PTR_NULL;
 
  return s;
}

References allocate_bucket(), __stack_head::avail, __stack_head::bucket_size, malloc(), __stack_head::max_extent, message_assert, __stack_head::n_buckets, __stack_head::policy, __stack_head::size, __stack_head::stack, STACK_DEFAULT_SIZE, STACK_PTR_NULL, and __stack_head::type.

Referenced by actual_c_parser(), bottom_up_abc_statement(), eov_make_ctx(), gen_internal_context_multi_recurse(), guard_elimination(), init_c_parser_scope_stack(), init_preprocessor_scope_stack(), init_statement_points_to_context(), initial_code_abc_statement(), InitializeBlock(), interprocedural_abc_statement(), loop_statistics(), make_simple_pv_context(), make_statement_global_stack(), MakeCurrentModule(), MakeTypedefStack(), pips_code_abc_statement(), push_pips_context(), stack_copy(), string_buffer_make(), tiling_sequence(), top_down_abc_statement(), typing_of_expressions(), xml_Boxes(), xml_Task(), and xml_tasks().

Here is the call graph for this function:

Here is the caller graph for this function:

stack_map()

void stack_map	(	const stack	s,
		gen_iter_func_t	f
	)

APPLY f to all items of stack s;.

Definition at line 323 of file stack.c.

{
  _stack_ptr x;
  int i;
 
  STACK_CHECK(s);
 
  for(x=s->stack; x!=NULL; x=x->succ)
    for(i=(x->n_item)-1; i>=0; i--)
      (*f)(x->items[i]);
}

References __stack_head::stack, STACK_CHECK, and x.

stack_nth()

void* stack_nth	(	const stack	s,
		int	nskip
	)

returns the nth item starting from the head and counting from 1, when possible, or NULL, elsewhere.

stack_nth(stack,1)==stack_head(stack) if stack_size(stack)>=1.

Definition at line 436 of file stack.c.

{
  void * value = NULL;
  message_assert("positive nskip", nskip>=0);
  // message_assert("deep enough stack", stack_size(s)>=nskip);
  _stack_iterator si;
  stack_iterator_internal_init(s, true, &si);
  while (nskip && stack_iterator_next_and_go(&si, &value))
    nskip--;
  return value;
}

References message_assert, stack_iterator_internal_init(), and stack_iterator_next_and_go().

Referenced by get_c_parser_nth_scope(), get_preprocessor_nth_scope(), and GetParentScope().

Here is the call graph for this function:

Here is the caller graph for this function:

STACK_OBSERVER()

STACK_OBSERVER	(	consistent_p	,
		1
	)

Here we define stack_size(), stack_bsize(), stack_policy() and stack_max_extent():

well, it is not implemented

Definition at line 311 of file stack.c.

{
  STACK_CHECK(s);
  return s->size==0;
}

References STACK_CHECK.

stack_pop()

void* stack_pop

(

stack

s

)

POPs one item from stack s.

the empty buckets are not freed here. stack_free does the job.

POP!

Definition at line 399 of file stack.c.

{
  _stack_ptr x = s->stack;
 
  if (x->n_item==0)
  {
    _stack_ptr saved = x->succ;
    x->succ = s->avail, s->avail = x;
    s->stack = saved, x = saved;
  }
 
  assert(!STACK_PTR_NULL_P(x) && x->n_item>0);
 
  /*   POP!
   */
  s->size--;
  return x->items[--x->n_item];
}

References assert, __stack_head::avail, __stack_head::size, __stack_head::stack, STACK_PTR_NULL_P, and x.

Referenced by eov_stack_task_pop_task(), ExitScope(), gen_internal_context_multi_recurse(), MakeForloop(), NStackPop(), pop_c_parser_scope_stack(), pop_current_statement(), pop_if(), pop_loop(), pop_pips_context(), pop_preprocessor_scope(), pop_statement_global_stack(), pop_statement_points_to_context(), pop_uns(), PopContext(), PopFunction(), PopTypedef(), pv_context_statement_pop(), quick_multi_recurse_obj_out(), stmt_rwt(), string_buffer_reset(), UpdateAbstractEntity(), UpdateDerivedEntity(), and UpdateEntity().

Here is the caller graph for this function:

stack_push()

void stack_push	(	void *	item,
		stack	s
	)

STACK USE.

stack use

PUSHes the item on stack s

a new bucket is allocated if necessary. the size it the same than the initial bucket size. Other policies may be considered.

PUSH!

Definition at line 373 of file stack.c.

{
  _stack_ptr x = s->stack;
 
  assert(!STACK_PTR_NULL_P(x));
 
  if (x->n_item == x->max_items)
  {
    _stack_ptr saved = x;
    x = find_or_allocate(s);
    x->succ = saved;
    s->stack = x;
  }
 
  /*   PUSH!
   */
  s->size++;
  if (s->size > s->max_extent) s->max_extent = s->size;
  x->items[x->n_item++] = item;
}

References assert, find_or_allocate(), __stack_head::max_extent, __stack_head::size, __stack_head::stack, STACK_PTR_NULL_P, and x.

Referenced by EnterScope(), eov_stack_task_push_task(), gen_internal_context_multi_recurse(), push_current_statement(), push_if(), push_loop(), push_new_c_parser_scope(), push_new_preprocessor_scope(), push_pips_context(), push_statement_on_statement_global_stack(), push_statement_points_to_context(), push_uns(), PushContext(), PushFunction(), PushTypedef(), pv_context_statement_push(), quick_multi_recurse_obj_in(), stack_copy(), StackPush(), stmt_flt(), and string_buffer_append_internal().

Here is the call graph for this function:

Here is the caller graph for this function:

stack_replace()

void* stack_replace	(	void *	item,
		stack	s
	)

REPLACEs the item on top of stack s, and returns the old item.

REPLACE

Definition at line 450 of file stack.c.

{
  _stack_ptr x = s->stack;
  void *old;
 
  if (x->n_item==0) x = x->succ;
  assert(!STACK_PTR_NULL_P(x) && x->n_item>0);
 
  /*    REPLACE
   */
  old = x->items[(x->n_item)-1];
  x->items[(x->n_item)-1] = item;
 
  return old;
}

References assert, __stack_head::stack, STACK_PTR_NULL_P, and x.

update_iterator_upward()

static void update_iterator_upward ( stack_iterator  i )

static

and also *stack_iterator (in headers)

Definition at line 91 of file stack.c.

{
  _stack_ptr x=i->list;
 
  while(!STACK_PTR_NULL_P(x) && x->succ!=i->bucket)
    x=x->succ;
 
  i->bucket=x, i->index=0;
 
  if (x && i->bucket->n_item==0)
    i->bucket = STACK_PTR_NULL;
}

References __stack_iterator::bucket, __stack_iterator::index, __stack_iterator::list, __stack_bucket::n_item, STACK_PTR_NULL, STACK_PTR_NULL_P, and x.

Referenced by stack_iterator_internal_init().

Here is the caller graph for this function: