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 }