1 /*

     2  * Copyright (c) 2003, 2011, Oracle and/or its affiliates. All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions

     6  * are met:

     7  *

     8  *   - Redistributions of source code must retain the above copyright

     9  *     notice, this list of conditions and the following disclaimer.

    10  *

    11  *   - Redistributions in binary form must reproduce the above copyright

    12  *     notice, this list of conditions and the following disclaimer in the

    13  *     documentation and/or other materials provided with the distribution.

    14  *

    15  *   - Neither the name of Oracle nor the names of its

    16  *     contributors may be used to endorse or promote products derived

    17  *     from this software without specific prior written permission.

    18  *

    19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS

    20  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,

    21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR

    23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF

    27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

    28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

    29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    30  */

    31 

    32 /*

    33  * This source code is provided to illustrate the usage of a given feature

    34  * or technique and has been deliberately simplified. Additional steps

    35  * required for a production-quality application, such as security checks,

    36  * input validation and proper error handling, might not be present in

    37  * this sample code.

    38  */

    39 

    40 

    41 /* Simple stack storage mechanism (or simple List). */

    42 

    43 /*

    44  * Stack is any depth (grows as it needs to), elements are arbitrary

    45  *   length but known at stack init time.

    46  *

    47  * Stack elements can be accessed via pointers (be careful, if stack

    48  *   moved while you point into stack you have problems)

    49  *

    50  * Pointers to stack elements passed in are copied.

    51  *

    52  * Since the stack can be inspected, it can be used for more than just

    53  *    a simple stack.

    54  *

    55  */

    56 

    57 #include "hprof.h"

    58 

    59 static void

    60 resize(Stack *stack)

    61 {

    62     void  *old_elements;

    63     void  *new_elements;

    64     int    old_size;

    65     int    new_size;

    66 

    67     HPROF_ASSERT(stack!=NULL);

    68     HPROF_ASSERT(stack->elements!=NULL);

    69     HPROF_ASSERT(stack->size>0);

    70     HPROF_ASSERT(stack->elem_size>0);

    71     HPROF_ASSERT(stack->incr_size>0);

    72     old_size     = stack->size;

    73     old_elements = stack->elements;

    74     if ( (stack->resizes % 10) && stack->incr_size < (old_size >> 2) ) {

    75         stack->incr_size = old_size >> 2; /* 1/4 the old_size */

    76     }

    77     new_size = old_size + stack->incr_size;

    78     new_elements = HPROF_MALLOC(new_size*stack->elem_size);

    79     (void)memcpy(new_elements, old_elements, old_size*stack->elem_size);

    80     stack->size     = new_size;

    81     stack->elements = new_elements;

    82     HPROF_FREE(old_elements);

    83     stack->resizes++;

    84 }

    85 

    86 Stack *

    87 stack_init(int init_size, int incr_size, int elem_size)

    88 {

    89     Stack *stack;

    90     void  *elements;

    91 

    92     HPROF_ASSERT(init_size>0);

    93     HPROF_ASSERT(elem_size>0);

    94     HPROF_ASSERT(incr_size>0);

    95     stack            = (Stack*)HPROF_MALLOC((int)sizeof(Stack));

    96     elements         = HPROF_MALLOC(init_size*elem_size);

    97     stack->size      = init_size;

    98     stack->incr_size = incr_size;

    99     stack->elem_size = elem_size;

   100     stack->count       = 0;

   101     stack->elements  = elements;

   102     stack->resizes   = 0;

   103     return stack;

   104 }

   105 

   106 void *

   107 stack_element(Stack *stack, int i)

   108 {

   109     HPROF_ASSERT(stack!=NULL);

   110     HPROF_ASSERT(stack->elements!=NULL);

   111     HPROF_ASSERT(stack->count>i);

   112     HPROF_ASSERT(i>=0);

   113     return (void*)(((char*)stack->elements) + i * stack->elem_size);

   114 }

   115 

   116 void *

   117 stack_top(Stack *stack)

   118 {

   119     void *element;

   120 

   121     HPROF_ASSERT(stack!=NULL);

   122     element = NULL;

   123     if ( stack->count > 0 ) {

   124         element = stack_element(stack, (stack->count-1));

   125     }

   126     return element;

   127 }

   128 

   129 int

   130 stack_depth(Stack *stack)

   131 {

   132     HPROF_ASSERT(stack!=NULL);

   133     return stack->count;

   134 }

   135 

   136 void *

   137 stack_pop(Stack *stack)

   138 {

   139     void *element;

   140 

   141     element = stack_top(stack);

   142     if ( element != NULL ) {

   143         stack->count--;

   144     }

   145     return element;

   146 }

   147 

   148 void

   149 stack_push(Stack *stack, void *element)

   150 {

   151     void *top_element;

   152 

   153     HPROF_ASSERT(stack!=NULL);

   154     if ( stack->count >= stack->size ) {

   155         resize(stack);

   156     }

   157     stack->count++;

   158     top_element = stack_top(stack);

   159     (void)memcpy(top_element, element, stack->elem_size);

   160 }

   161 

   162 void

   163 stack_term(Stack *stack)

   164 {

   165     HPROF_ASSERT(stack!=NULL);

   166     if ( stack->elements != NULL ) {

   167         HPROF_FREE(stack->elements);

   168     }

   169     HPROF_FREE(stack);

   170 }