1 #include <petscsys.h>
2
3 struct _PetscSegBufferLink {
4 struct _PetscSegBufferLink *tail;
5 size_t alloc;
6 size_t used;
7 size_t tailused;
8 union { /* Dummy types to ensure alignment */
9 PetscReal dummy_real;
10 PetscInt dummy_int;
11 char array[1]; /* This array is over-allocated for the size of the link */
12 } u;
13 };
14
15 /* Segmented (extendable) array implementation */
16 struct _n_PetscSegBuffer {
17 struct _PetscSegBufferLink *head;
18 size_t unitbytes;
19 };
20
PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count)21 static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count)
22 {
23 PetscErrorCode ierr;
24 size_t alloc;
25 struct _PetscSegBufferLink *newlink,*s;
26
27 PetscFunctionBegin;
28 s = seg->head;
29 /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */
30 alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused));
31 ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);CHKERRQ(ierr);
32 ierr = PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr);
33
34 newlink->tailused = s->used + s->tailused;
35 newlink->tail = s;
36 newlink->alloc = alloc;
37 seg->head = newlink;
38 PetscFunctionReturn(0);
39 }
40
41 /*@C
42 PetscSegBufferCreate - create segmented buffer
43
44 Not Collective
45
46 Input Arguments:
47 + unitbytes - number of bytes that each entry will contain
48 - expected - expected/typical number of entries
49
50 Output Argument:
51 . seg - segmented buffer object
52
53 Level: developer
54
55 .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
56 @*/
PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer * seg)57 PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg)
58 {
59 PetscErrorCode ierr;
60 struct _PetscSegBufferLink *head;
61
62 PetscFunctionBegin;
63 ierr = PetscNew(seg);CHKERRQ(ierr);
64 ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);CHKERRQ(ierr);
65 ierr = PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr);
66
67 head->alloc = expected;
68 (*seg)->unitbytes = unitbytes;
69 (*seg)->head = head;
70 PetscFunctionReturn(0);
71 }
72
73 /*@C
74 PetscSegBufferGet - get new buffer space from a segmented buffer
75
76 Not Collective
77
78 Input Arguments:
79 + seg - address of segmented buffer
80 - count - number of entries needed
81
82 Output Argument:
83 . buf - address of new buffer for contiguous data
84
85 Level: developer
86
87 .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
88 @*/
PetscSegBufferGet(PetscSegBuffer seg,size_t count,void * buf)89 PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf)
90 {
91 PetscErrorCode ierr;
92 struct _PetscSegBufferLink *s;
93
94 PetscFunctionBegin;
95 s = seg->head;
96 if (PetscUnlikely(s->used + count > s->alloc)) {ierr = PetscSegBufferAlloc_Private(seg,count);CHKERRQ(ierr);}
97 s = seg->head;
98 *(char**)buf = &s->u.array[s->used*seg->unitbytes];
99 s->used += count;
100 PetscFunctionReturn(0);
101 }
102
103 /*@C
104 PetscSegBufferDestroy - destroy segmented buffer
105
106 Not Collective
107
108 Input Arguments:
109 . seg - address of segmented buffer object
110
111 Level: developer
112
113 .seealso: PetscSegBufferCreate()
114 @*/
PetscSegBufferDestroy(PetscSegBuffer * seg)115 PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg)
116 {
117 PetscErrorCode ierr;
118 struct _PetscSegBufferLink *s;
119
120 PetscFunctionBegin;
121 if (!*seg) PetscFunctionReturn(0);
122 for (s=(*seg)->head; s;) {
123 struct _PetscSegBufferLink *tail = s->tail;
124 ierr = PetscFree(s);CHKERRQ(ierr);
125 s = tail;
126 }
127 ierr = PetscFree(*seg);CHKERRQ(ierr);
128 PetscFunctionReturn(0);
129 }
130
131 /*@C
132 PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer
133
134 Not Collective
135
136 Input Argument:
137 + seg - segmented buffer
138 - contig - allocated buffer to hold contiguous data
139
140 Level: developer
141
142 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace()
143 @*/
PetscSegBufferExtractTo(PetscSegBuffer seg,void * contig)144 PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig)
145 {
146 PetscErrorCode ierr;
147 size_t unitbytes;
148 struct _PetscSegBufferLink *s,*t;
149 char *ptr;
150
151 PetscFunctionBegin;
152 unitbytes = seg->unitbytes;
153 s = seg->head;
154 ptr = ((char*)contig) + s->tailused*unitbytes;
155 ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr);
156 for (t=s->tail; t;) {
157 struct _PetscSegBufferLink *tail = t->tail;
158 ptr -= t->used*unitbytes;
159 ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr);
160 ierr = PetscFree(t);CHKERRQ(ierr);
161 t = tail;
162 }
163 if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match");
164 s->used = 0;
165 s->tailused = 0;
166 s->tail = NULL;
167 PetscFunctionReturn(0);
168 }
169
170 /*@C
171 PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer
172
173 Not Collective
174
175 Input Argument:
176 . seg - segmented buffer
177
178 Output Argument:
179 . contiguous - address of new array containing contiguous data, caller frees with PetscFree()
180
181 Level: developer
182
183 Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done
184
185 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace()
186 @*/
PetscSegBufferExtractAlloc(PetscSegBuffer seg,void * contiguous)187 PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous)
188 {
189 PetscErrorCode ierr;
190 struct _PetscSegBufferLink *s;
191 void *contig;
192
193 PetscFunctionBegin;
194 s = seg->head;
195
196 ierr = PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);CHKERRQ(ierr);
197 ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr);
198 *(void**)contiguous = contig;
199 PetscFunctionReturn(0);
200 }
201
202 /*@C
203 PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse
204
205 Not Collective
206
207 Input Arguments:
208 . seg - segmented buffer object
209
210 Output Arguments:
211 . contig - address of pointer to contiguous memory
212
213 Level: developer
214
215 .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo()
216 @*/
PetscSegBufferExtractInPlace(PetscSegBuffer seg,void * contig)217 PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig)
218 {
219 PetscErrorCode ierr;
220 struct _PetscSegBufferLink *head;
221
222 PetscFunctionBegin;
223 head = seg->head;
224 if (PetscUnlikely(head->tail)) {
225 PetscSegBuffer newseg;
226
227 ierr = PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);CHKERRQ(ierr);
228 ierr = PetscSegBufferExtractTo(seg,newseg->head->u.array);CHKERRQ(ierr);
229 seg->head = newseg->head;
230 newseg->head = head;
231 ierr = PetscSegBufferDestroy(&newseg);CHKERRQ(ierr);
232 head = seg->head;
233 }
234 *(char**)contig = head->u.array;
235 head->used = 0;
236 PetscFunctionReturn(0);
237 }
238
239 /*@C
240 PetscSegBufferGetSize - get currently used size of segmented buffer
241
242 Not Collective
243
244 Input Arguments:
245 . seg - segmented buffer object
246
247 Output Arguments:
248 . usedsize - number of used units
249
250 Level: developer
251
252 .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet()
253 @*/
PetscSegBufferGetSize(PetscSegBuffer seg,size_t * usedsize)254 PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize)
255 {
256
257 PetscFunctionBegin;
258 *usedsize = seg->head->tailused + seg->head->used;
259 PetscFunctionReturn(0);
260 }
261
262 /*@C
263 PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet()
264
265 Not Collective
266
267 Input Arguments:
268 + seg - segmented buffer object
269 - unused - number of unused units
270
271 Level: developer
272
273 .seealso: PetscSegBufferCreate(), PetscSegBufferGet()
274 @*/
PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)275 PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)
276 {
277 struct _PetscSegBufferLink *head;
278
279 PetscFunctionBegin;
280 head = seg->head;
281 if (PetscUnlikely(head->used < unused)) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Attempt to return more unused entries (%D) than previously gotten (%D)",unused,head->used);
282 head->used -= unused;
283 PetscFunctionReturn(0);
284 }
285