1 /* Part of SWI-Prolog
2
3 Author: Jan Wielemaker
4 E-mail: J.Wielemaker@vu.nl
5 WWW: http://www.swi-prolog.org
6 Copyright (c) 2007-2013, University of Amsterdam
7 VU University Amsterdam
8 All rights reserved.
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions
12 are met:
13
14 1. Redistributions of source code must retain the above copyright
15 notice, this list of conditions and the following disclaimer.
16
17 2. Redistributions in binary form must reproduce the above copyright
18 notice, this list of conditions and the following disclaimer in
19 the documentation and/or other materials provided with the
20 distribution.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #ifndef PL_SEGSTACK_H_INCLUDED
37 #define PL_SEGSTACK_H_INCLUDED
38
39 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
40 The segchunk struct has its data attached to its back. The data field
41 itself is typed double to ensure that the data is properly aligned to
42 allow access of doubles. This is needed to get properly aligned pointers
43 after topsOfSegStack() in evalExpression().
44 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
45
46 typedef struct segchunk
47 { char *top; /* top when closed */
48 size_t size; /* size of the chunk */
49 /* below clean using memset() */
50 int allocated; /* must call free on it */
51 struct segchunk *next; /* double linked list */
52 struct segchunk *previous;
53 double data[1]; /* data on my back */
54 } segchunk;
55
56 #define CHUNK_DATA(c) ((char *)(c)->data)
57
58 typedef struct
59 { size_t unit_size;
60 /* below clean using memset() */
61 int chunk_count;
62 segchunk *first;
63 segchunk *last;
64 char *base;
65 char *top;
66 char *max;
67 } segstack;
68
69
70 static inline int
emptySegStack(segstack * s)71 emptySegStack(segstack *s)
72 { return (s->top == s->base) &&
73 (s->last == NULL || s->last->previous == NULL);
74 }
75
76
77 #define popSegStack(stack, to, type) \
78 ( ((stack)->top >= (stack)->base + sizeof(type)) \
79 ? ( (stack)->top -= sizeof(type), \
80 *to = *(type*)(stack)->top, \
81 TRUE \
82 ) \
83 : !(stack)->last || !(stack)->last->previous ? FALSE \
84 : popSegStack_((stack), to) \
85 )
86
87 #define pushSegStack(stack, data, type) \
88 ( ((stack)->top + sizeof(type) <= (stack)->max) \
89 ? ( *(type*)(stack)->top = data, \
90 (stack)->top += sizeof(type), \
91 TRUE \
92 ) \
93 : pushSegStack_((stack), &data) \
94 )
95
96 COMMON(int) pushSegStack_(segstack *stack, void* data) WUNUSED;
97 COMMON(int) pushRecordSegStack(segstack *stack, Record r) WUNUSED;
98 COMMON(int) popSegStack_(segstack *stack, void *data);
99 COMMON(void*) topOfSegStack(segstack *stack);
100 COMMON(void) popTopOfSegStack_(segstack *stack);
101 COMMON(void) scanSegStack(segstack *s, void (*func)(void *cell));
102 COMMON(void) clearSegStack_(segstack *s);
103
104 /*******************************
105 * INLINE *
106 *******************************/
107
108 static inline void
clearSegStack(segstack * s)109 clearSegStack(segstack *s)
110 { if ( s->first )
111 clearSegStack_(s);
112 }
113
114
115 static inline void
topsOfSegStack(segstack * stack,int count,void ** tops)116 topsOfSegStack(segstack *stack, int count, void **tops)
117 { char *p = stack->top - stack->unit_size;
118 char *base = stack->base;
119
120 for(;;)
121 { while(count > 0 && p >= base)
122 { *tops++ = p;
123 p -= stack->unit_size;
124 count--;
125 }
126
127 if ( count > 0 )
128 { segchunk *chunk = stack->last->previous;
129
130 p = chunk->top - stack->unit_size;
131 base = CHUNK_DATA(chunk);
132 } else
133 break;
134 }
135 }
136
137
138 /* quickPopTopOfSegStack() only performs a pop if we do not
139 need to discard a chunk. $collect_findall_bag/2 needs
140 addition synchronization in that case.
141 */
142
143 static inline int
quickPopTopOfSegStack(segstack * stack)144 quickPopTopOfSegStack(segstack *stack)
145 { if ( stack->top >= stack->base + stack->unit_size )
146 { stack->top -= stack->unit_size;
147 return TRUE;
148 }
149
150 return FALSE;
151 }
152
153
154 static inline void
popTopOfSegStack(segstack * stack)155 popTopOfSegStack(segstack *stack)
156 { if ( !quickPopTopOfSegStack(stack) )
157 popTopOfSegStack_(stack);
158 }
159
160
161 static inline void
initSegStack(segstack * stack,size_t unit_size,size_t len,void * data)162 initSegStack(segstack *stack, size_t unit_size, size_t len, void *data)
163 { stack->unit_size = unit_size;
164
165 if ( len )
166 { segchunk *chunk = data;
167
168 #if O_DEBUG
169 assert(len > sizeof(*chunk));
170 assert(unit_size%sizeof(void*) == 0);
171 #endif
172 chunk->size = len;
173 stack->base = stack->top = chunk->top = CHUNK_DATA(chunk);
174 stack->last = stack->first = chunk;
175 stack->max = addPointer(chunk, len);
176 stack->chunk_count = 1;
177 chunk->allocated = 0;
178 chunk->next = NULL;
179 chunk->previous = NULL;
180 } else
181 { memset(&stack->first, 0, sizeof(*stack)-offsetof(segstack,first));
182 }
183 }
184
185 #endif /*PL_SEGSTACK_H_INCLUDED*/
186