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 } |
|