Actual source code: segbuffer.c
petsc-3.6.1 2015-08-06
1: #include <petscsys.h>
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: };
15: /* Segmented (extendable) array implementation */
16: struct _n_PetscSegBuffer {
17: struct _PetscSegBufferLink *head;
18: size_t unitbytes;
19: };
23: static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count)
24: {
25: PetscErrorCode ierr;
26: size_t alloc;
27: struct _PetscSegBufferLink *newlink,*s;
30: s = seg->head;
31: /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */
32: alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused));
33: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);
34: PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));
36: newlink->tailused = s->used + s->tailused;
37: newlink->tail = s;
38: newlink->alloc = alloc;
39: seg->head = newlink;
40: return(0);
41: }
45: /*@C
46: PetscSegBufferCreate - create segmented buffer
48: Not Collective
50: Input Arguments:
51: + unitbytes - number of bytes that each entry will contain
52: - expected - expected/typical number of entries
54: Output Argument:
55: . seg - segmented buffer object
57: Level: developer
59: .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
60: @*/
61: PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg)
62: {
64: struct _PetscSegBufferLink *head;
67: PetscMalloc(sizeof(struct _n_PetscSegBuffer),seg);
68: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);
69: PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));
71: head->alloc = expected;
72: (*seg)->unitbytes = unitbytes;
73: (*seg)->head = head;
74: return(0);
75: }
79: /*@C
80: PetscSegBufferGet - get new buffer space from a segmented buffer
82: Not Collective
84: Input Arguments:
85: + seg - address of segmented buffer
86: - count - number of entries needed
88: Output Argument:
89: . buf - address of new buffer for contiguous data
91: Level: developer
93: .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
94: @*/
95: PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf)
96: {
98: struct _PetscSegBufferLink *s;
101: s = seg->head;
102: if (PetscUnlikely(s->used + count > s->alloc)) {PetscSegBufferAlloc_Private(seg,count);}
103: s = seg->head;
104: *(char**)buf = &s->u.array[s->used*seg->unitbytes];
105: s->used += count;
106: return(0);
107: }
111: /*@C
112: PetscSegBufferDestroy - destroy segmented buffer
114: Not Collective
116: Input Arguments:
117: . seg - address of segmented buffer object
119: Level: developer
121: .seealso: PetscSegBufferCreate()
122: @*/
123: PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg)
124: {
125: PetscErrorCode ierr;
126: struct _PetscSegBufferLink *s;
129: if (!*seg) return(0);
130: for (s=(*seg)->head; s;) {
131: struct _PetscSegBufferLink *tail = s->tail;
132: PetscFree(s);
133: s = tail;
134: }
135: PetscFree(*seg);
136: return(0);
137: }
141: /*@C
142: PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer
144: Not Collective
146: Input Argument:
147: + seg - segmented buffer
148: - contig - allocated buffer to hold contiguous data
150: Level: developer
152: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace()
153: @*/
154: PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig)
155: {
156: PetscErrorCode ierr;
157: size_t unitbytes;
158: struct _PetscSegBufferLink *s,*t;
159: char *ptr;
162: unitbytes = seg->unitbytes;
163: s = seg->head;
164: ptr = ((char*)contig) + s->tailused*unitbytes;
165: PetscMemcpy(ptr,s->u.array,s->used*unitbytes);
166: for (t=s->tail; t;) {
167: struct _PetscSegBufferLink *tail = t->tail;
168: ptr -= t->used*unitbytes;
169: PetscMemcpy(ptr,t->u.array,t->used*unitbytes);
170: PetscFree(t);
171: t = tail;
172: }
173: if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match");
174: s->used = 0;
175: s->tailused = 0;
176: s->tail = NULL;
177: return(0);
178: }
182: /*@C
183: PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer
185: Not Collective
187: Input Argument:
188: . seg - segmented buffer
190: Output Argument:
191: . contiguous - address of new array containing contiguous data, caller frees with PetscFree()
193: Level: developer
195: Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done
197: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace()
198: @*/
199: PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous)
200: {
201: PetscErrorCode ierr;
202: struct _PetscSegBufferLink *s;
203: void *contig;
206: s = seg->head;
208: PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);
209: PetscSegBufferExtractTo(seg,contig);
210: *(void**)contiguous = contig;
211: return(0);
212: }
216: /*@C
217: PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse
219: Not Collective
221: Input Arguments:
222: . seg - segmented buffer object
224: Output Arguments:
225: . contig - address of pointer to contiguous memory
227: Level: developer
229: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo()
230: @*/
231: PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig)
232: {
234: struct _PetscSegBufferLink *head;
237: head = seg->head;
238: if (PetscUnlikely(head->tail)) {
239: PetscSegBuffer newseg;
241: PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);
242: PetscSegBufferExtractTo(seg,newseg->head->u.array);
243: seg->head = newseg->head;
244: newseg->head = head;
245: PetscSegBufferDestroy(&newseg);
246: head = seg->head;
247: }
248: *(char**)contig = head->u.array;
249: head->used = 0;
250: return(0);
251: }
255: /*@C
256: PetscSegBufferGetSize - get currently used size of segmented buffer
258: Not Collective
260: Input Arguments:
261: . seg - segmented buffer object
263: Output Arguments:
264: . usedsize - number of used units
266: Level: developer
268: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet()
269: @*/
270: PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize)
271: {
274: *usedsize = seg->head->tailused + seg->head->used;
275: return(0);
276: }
280: /*@C
281: PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet()
283: Not Collective
285: Input Arguments:
286: + seg - segmented buffer object
287: - unused - number of unused units
289: Level: developer
291: .seealso: PetscSegBufferCreate(), PetscSegBufferGet()
292: @*/
293: PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)
294: {
295: struct _PetscSegBufferLink *head;
298: head = seg->head;
299: 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);
300: head->used -= unused;
301: return(0);
302: }