Actual source code: segbuffer.c
petsc-3.8.4 2018-03-24
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: };
21: static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count)
22: {
23: PetscErrorCode ierr;
24: size_t alloc;
25: struct _PetscSegBufferLink *newlink,*s;
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: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);
32: PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));
34: newlink->tailused = s->used + s->tailused;
35: newlink->tail = s;
36: newlink->alloc = alloc;
37: seg->head = newlink;
38: return(0);
39: }
41: /*@C
42: PetscSegBufferCreate - create segmented buffer
44: Not Collective
46: Input Arguments:
47: + unitbytes - number of bytes that each entry will contain
48: - expected - expected/typical number of entries
50: Output Argument:
51: . seg - segmented buffer object
53: Level: developer
55: .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
56: @*/
57: PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg)
58: {
60: struct _PetscSegBufferLink *head;
63: PetscNew(seg);
64: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);
65: PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));
67: head->alloc = expected;
68: (*seg)->unitbytes = unitbytes;
69: (*seg)->head = head;
70: return(0);
71: }
73: /*@C
74: PetscSegBufferGet - get new buffer space from a segmented buffer
76: Not Collective
78: Input Arguments:
79: + seg - address of segmented buffer
80: - count - number of entries needed
82: Output Argument:
83: . buf - address of new buffer for contiguous data
85: Level: developer
87: .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
88: @*/
89: PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf)
90: {
92: struct _PetscSegBufferLink *s;
95: s = seg->head;
96: if (PetscUnlikely(s->used + count > s->alloc)) {PetscSegBufferAlloc_Private(seg,count);}
97: s = seg->head;
98: *(char**)buf = &s->u.array[s->used*seg->unitbytes];
99: s->used += count;
100: return(0);
101: }
103: /*@C
104: PetscSegBufferDestroy - destroy segmented buffer
106: Not Collective
108: Input Arguments:
109: . seg - address of segmented buffer object
111: Level: developer
113: .seealso: PetscSegBufferCreate()
114: @*/
115: PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg)
116: {
117: PetscErrorCode ierr;
118: struct _PetscSegBufferLink *s;
121: if (!*seg) return(0);
122: for (s=(*seg)->head; s;) {
123: struct _PetscSegBufferLink *tail = s->tail;
124: PetscFree(s);
125: s = tail;
126: }
127: PetscFree(*seg);
128: return(0);
129: }
131: /*@C
132: PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer
134: Not Collective
136: Input Argument:
137: + seg - segmented buffer
138: - contig - allocated buffer to hold contiguous data
140: Level: developer
142: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace()
143: @*/
144: PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig)
145: {
146: PetscErrorCode ierr;
147: size_t unitbytes;
148: struct _PetscSegBufferLink *s,*t;
149: char *ptr;
152: unitbytes = seg->unitbytes;
153: s = seg->head;
154: ptr = ((char*)contig) + s->tailused*unitbytes;
155: PetscMemcpy(ptr,s->u.array,s->used*unitbytes);
156: for (t=s->tail; t;) {
157: struct _PetscSegBufferLink *tail = t->tail;
158: ptr -= t->used*unitbytes;
159: PetscMemcpy(ptr,t->u.array,t->used*unitbytes);
160: PetscFree(t);
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: return(0);
168: }
170: /*@C
171: PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer
173: Not Collective
175: Input Argument:
176: . seg - segmented buffer
178: Output Argument:
179: . contiguous - address of new array containing contiguous data, caller frees with PetscFree()
181: Level: developer
183: Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done
185: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace()
186: @*/
187: PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous)
188: {
189: PetscErrorCode ierr;
190: struct _PetscSegBufferLink *s;
191: void *contig;
194: s = seg->head;
196: PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);
197: PetscSegBufferExtractTo(seg,contig);
198: *(void**)contiguous = contig;
199: return(0);
200: }
202: /*@C
203: PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse
205: Not Collective
207: Input Arguments:
208: . seg - segmented buffer object
210: Output Arguments:
211: . contig - address of pointer to contiguous memory
213: Level: developer
215: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo()
216: @*/
217: PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig)
218: {
220: struct _PetscSegBufferLink *head;
223: head = seg->head;
224: if (PetscUnlikely(head->tail)) {
225: PetscSegBuffer newseg;
227: PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);
228: PetscSegBufferExtractTo(seg,newseg->head->u.array);
229: seg->head = newseg->head;
230: newseg->head = head;
231: PetscSegBufferDestroy(&newseg);
232: head = seg->head;
233: }
234: *(char**)contig = head->u.array;
235: head->used = 0;
236: return(0);
237: }
239: /*@C
240: PetscSegBufferGetSize - get currently used size of segmented buffer
242: Not Collective
244: Input Arguments:
245: . seg - segmented buffer object
247: Output Arguments:
248: . usedsize - number of used units
250: Level: developer
252: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet()
253: @*/
254: PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize)
255: {
258: *usedsize = seg->head->tailused + seg->head->used;
259: return(0);
260: }
262: /*@C
263: PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet()
265: Not Collective
267: Input Arguments:
268: + seg - segmented buffer object
269: - unused - number of unused units
271: Level: developer
273: .seealso: PetscSegBufferCreate(), PetscSegBufferGet()
274: @*/
275: PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)
276: {
277: struct _PetscSegBufferLink *head;
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: return(0);
284: }