Actual source code: segbuffer.c
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: size_t alloc;
24: struct _PetscSegBufferLink *newlink,*s;
26: s = seg->head;
27: /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */
28: alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused));
29: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);
30: PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));
32: newlink->tailused = s->used + s->tailused;
33: newlink->tail = s;
34: newlink->alloc = alloc;
35: seg->head = newlink;
36: return 0;
37: }
39: /*@C
40: PetscSegBufferCreate - create segmented buffer
42: Not Collective
44: Input Parameters:
45: + unitbytes - number of bytes that each entry will contain
46: - expected - expected/typical number of entries
48: Output Parameter:
49: . seg - segmented buffer object
51: Level: developer
53: .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
54: @*/
55: PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg)
56: {
57: struct _PetscSegBufferLink *head;
59: PetscNew(seg);
60: PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);
61: PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));
63: head->alloc = expected;
64: (*seg)->unitbytes = unitbytes;
65: (*seg)->head = head;
66: return 0;
67: }
69: /*@C
70: PetscSegBufferGet - get new buffer space from a segmented buffer
72: Not Collective
74: Input Parameters:
75: + seg - address of segmented buffer
76: - count - number of entries needed
78: Output Parameter:
79: . buf - address of new buffer for contiguous data
81: Level: developer
83: .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy()
84: @*/
85: PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf)
86: {
87: struct _PetscSegBufferLink *s;
89: s = seg->head;
90: if (PetscUnlikely(s->used + count > s->alloc)) PetscSegBufferAlloc_Private(seg,count);
91: s = seg->head;
92: *(char**)buf = &s->u.array[s->used*seg->unitbytes];
93: s->used += count;
94: return 0;
95: }
97: /*@C
98: PetscSegBufferDestroy - destroy segmented buffer
100: Not Collective
102: Input Parameter:
103: . seg - address of segmented buffer object
105: Level: developer
107: .seealso: PetscSegBufferCreate()
108: @*/
109: PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg)
110: {
111: struct _PetscSegBufferLink *s;
113: if (!*seg) return 0;
114: for (s=(*seg)->head; s;) {
115: struct _PetscSegBufferLink *tail = s->tail;
116: PetscFree(s);
117: s = tail;
118: }
119: PetscFree(*seg);
120: return 0;
121: }
123: /*@C
124: PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer
126: Not Collective
128: Input Parameters:
129: + seg - segmented buffer
130: - contig - allocated buffer to hold contiguous data
132: Level: developer
134: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace()
135: @*/
136: PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig)
137: {
138: size_t unitbytes;
139: struct _PetscSegBufferLink *s,*t;
140: char *ptr;
142: unitbytes = seg->unitbytes;
143: s = seg->head;
144: ptr = ((char*)contig) + s->tailused*unitbytes;
145: PetscMemcpy(ptr,s->u.array,s->used*unitbytes);
146: for (t=s->tail; t;) {
147: struct _PetscSegBufferLink *tail = t->tail;
148: ptr -= t->used*unitbytes;
149: PetscMemcpy(ptr,t->u.array,t->used*unitbytes);
150: PetscFree(t);
151: t = tail;
152: }
154: s->used = 0;
155: s->tailused = 0;
156: s->tail = NULL;
157: return 0;
158: }
160: /*@C
161: PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer
163: Not Collective
165: Input Parameter:
166: . seg - segmented buffer
168: Output Parameter:
169: . contiguous - address of new array containing contiguous data, caller frees with PetscFree()
171: Level: developer
173: Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done
175: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace()
176: @*/
177: PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous)
178: {
179: struct _PetscSegBufferLink *s;
180: void *contig;
182: s = seg->head;
184: PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);
185: PetscSegBufferExtractTo(seg,contig);
186: *(void**)contiguous = contig;
187: return 0;
188: }
190: /*@C
191: PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse
193: Not Collective
195: Input Parameter:
196: . seg - segmented buffer object
198: Output Parameter:
199: . contig - address of pointer to contiguous memory
201: Level: developer
203: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo()
204: @*/
205: PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig)
206: {
207: struct _PetscSegBufferLink *head;
209: head = seg->head;
210: if (PetscUnlikely(head->tail)) {
211: PetscSegBuffer newseg;
213: PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);
214: PetscSegBufferExtractTo(seg,newseg->head->u.array);
215: seg->head = newseg->head;
216: newseg->head = head;
217: PetscSegBufferDestroy(&newseg);
218: head = seg->head;
219: }
220: *(char**)contig = head->u.array;
221: head->used = 0;
222: return 0;
223: }
225: /*@C
226: PetscSegBufferGetSize - get currently used size of segmented buffer
228: Not Collective
230: Input Parameter:
231: . seg - segmented buffer object
233: Output Parameter:
234: . usedsize - number of used units
236: Level: developer
238: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet()
239: @*/
240: PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize)
241: {
242: *usedsize = seg->head->tailused + seg->head->used;
243: return 0;
244: }
246: /*@C
247: PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet()
249: Not Collective
251: Input Parameters:
252: + seg - segmented buffer object
253: - unused - number of unused units
255: Level: developer
257: .seealso: PetscSegBufferCreate(), PetscSegBufferGet()
258: @*/
259: PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)
260: {
261: struct _PetscSegBufferLink *head;
263: head = seg->head;
265: head->used -= unused;
266: return 0;
267: }