| /* |
| * Copyright 2003-2004 Sun Microsystems, Inc. All Rights Reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * - Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * - Neither the name of Sun Microsystems nor the names of its |
| * contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
| * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
| * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /* Simple stack storage mechanism (or simple List). */ |
| |
| /* |
| * Stack is any depth (grows as it needs to), elements are arbitrary |
| * length but known at stack init time. |
| * |
| * Stack elements can be accessed via pointers (be careful, if stack |
| * moved while you point into stack you have problems) |
| * |
| * Pointers to stack elements passed in are copied. |
| * |
| * Since the stack can be inspected, it can be used for more than just |
| * a simple stack. |
| * |
| */ |
| |
| #include "hprof.h" |
| |
| static void |
| resize(Stack *stack) |
| { |
| void *old_elements; |
| void *new_elements; |
| int old_size; |
| int new_size; |
| |
| HPROF_ASSERT(stack!=NULL); |
| HPROF_ASSERT(stack->elements!=NULL); |
| HPROF_ASSERT(stack->size>0); |
| HPROF_ASSERT(stack->elem_size>0); |
| HPROF_ASSERT(stack->incr_size>0); |
| old_size = stack->size; |
| old_elements = stack->elements; |
| if ( (stack->resizes % 10) && stack->incr_size < (old_size >> 2) ) { |
| stack->incr_size = old_size >> 2; /* 1/4 the old_size */ |
| } |
| new_size = old_size + stack->incr_size; |
| new_elements = HPROF_MALLOC(new_size*stack->elem_size); |
| (void)memcpy(new_elements, old_elements, old_size*stack->elem_size); |
| stack->size = new_size; |
| stack->elements = new_elements; |
| HPROF_FREE(old_elements); |
| stack->resizes++; |
| } |
| |
| Stack * |
| stack_init(int init_size, int incr_size, int elem_size) |
| { |
| Stack *stack; |
| void *elements; |
| |
| HPROF_ASSERT(init_size>0); |
| HPROF_ASSERT(elem_size>0); |
| HPROF_ASSERT(incr_size>0); |
| stack = (Stack*)HPROF_MALLOC((int)sizeof(Stack)); |
| elements = HPROF_MALLOC(init_size*elem_size); |
| stack->size = init_size; |
| stack->incr_size = incr_size; |
| stack->elem_size = elem_size; |
| stack->count = 0; |
| stack->elements = elements; |
| stack->resizes = 0; |
| return stack; |
| } |
| |
| void * |
| stack_element(Stack *stack, int i) |
| { |
| HPROF_ASSERT(stack!=NULL); |
| HPROF_ASSERT(stack->elements!=NULL); |
| HPROF_ASSERT(stack->count>i); |
| HPROF_ASSERT(i>=0); |
| return (void*)(((char*)stack->elements) + i * stack->elem_size); |
| } |
| |
| void * |
| stack_top(Stack *stack) |
| { |
| void *element; |
| |
| HPROF_ASSERT(stack!=NULL); |
| element = NULL; |
| if ( stack->count > 0 ) { |
| element = stack_element(stack, (stack->count-1)); |
| } |
| return element; |
| } |
| |
| int |
| stack_depth(Stack *stack) |
| { |
| HPROF_ASSERT(stack!=NULL); |
| return stack->count; |
| } |
| |
| void * |
| stack_pop(Stack *stack) |
| { |
| void *element; |
| |
| element = stack_top(stack); |
| if ( element != NULL ) { |
| stack->count--; |
| } |
| return element; |
| } |
| |
| void |
| stack_push(Stack *stack, void *element) |
| { |
| void *top_element; |
| |
| HPROF_ASSERT(stack!=NULL); |
| if ( stack->count >= stack->size ) { |
| resize(stack); |
| } |
| stack->count++; |
| top_element = stack_top(stack); |
| (void)memcpy(top_element, element, stack->elem_size); |
| } |
| |
| void |
| stack_term(Stack *stack) |
| { |
| HPROF_ASSERT(stack!=NULL); |
| if ( stack->elements != NULL ) { |
| HPROF_FREE(stack->elements); |
| } |
| HPROF_FREE(stack); |
| } |