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
9: { /* Dummy types to ensure alignment */
10: PetscReal dummy_real;
11: PetscInt dummy_int;
12: char array[1]; /* This array is over-allocated for the size of the link */
13: } u;
14: };
16: /* Segmented (extendable) array implementation */
17: struct _n_PetscSegBuffer {
18: struct _PetscSegBufferLink *head;
19: size_t unitbytes;
20: };
22: static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg, size_t count)
23: {
24: size_t alloc;
25: struct _PetscSegBufferLink *newlink, *s;
27: s = seg->head;
28: /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */
29: alloc = PetscMax(s->used + count, PetscMin(1000000 / seg->unitbytes + 1, s->alloc + s->tailused));
30: PetscMalloc(offsetof(struct _PetscSegBufferLink, u) + alloc * seg->unitbytes, &newlink);
31: PetscMemzero(newlink, offsetof(struct _PetscSegBufferLink, u));
33: newlink->tailused = s->used + s->tailused;
34: newlink->tail = s;
35: newlink->alloc = alloc;
36: seg->head = newlink;
37: return 0;
38: }
40: /*@C
41: PetscSegBufferCreate - create a segmented buffer
43: Not Collective
45: Input Parameters:
46: + unitbytes - number of bytes that each entry will contain
47: - expected - expected/typical number of entries
49: Output Parameter:
50: . seg - segmented buffer object
52: Level: developer
54: .seealso: `PetscSegBufferGet()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`, `PetscSegBufferDestroy()`
55: @*/
56: PetscErrorCode PetscSegBufferCreate(size_t unitbytes, size_t expected, PetscSegBuffer *seg)
57: {
58: struct _PetscSegBufferLink *head;
60: PetscNew(seg);
61: PetscMalloc(offsetof(struct _PetscSegBufferLink, u) + expected * unitbytes, &head);
62: PetscMemzero(head, offsetof(struct _PetscSegBufferLink, u));
64: head->alloc = expected;
65: (*seg)->unitbytes = unitbytes;
66: (*seg)->head = head;
67: return 0;
68: }
70: /*@C
71: PetscSegBufferGet - get new buffer space from a segmented buffer
73: Not Collective
75: Input Parameters:
76: + seg - address of segmented buffer
77: - count - number of entries needed
79: Output Parameter:
80: . buf - address of new buffer for contiguous data
82: Level: developer
84: .seealso: `PetscSegBufferCreate()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`, `PetscSegBufferDestroy()`
85: @*/
86: PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg, size_t count, void *buf)
87: {
88: struct _PetscSegBufferLink *s;
90: s = seg->head;
91: if (PetscUnlikely(s->used + count > s->alloc)) PetscSegBufferAlloc_Private(seg, count);
92: s = seg->head;
93: *(char **)buf = &s->u.array[s->used * seg->unitbytes];
94: s->used += count;
95: return 0;
96: }
98: /*@C
99: PetscSegBufferDestroy - destroy segmented buffer
101: Not Collective
103: Input Parameter:
104: . seg - address of segmented buffer object
106: Level: developer
108: .seealso: `PetscSegBufferCreate()`
109: @*/
110: PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg)
111: {
112: struct _PetscSegBufferLink *s;
114: if (!*seg) return 0;
115: for (s = (*seg)->head; s;) {
116: struct _PetscSegBufferLink *tail = s->tail;
117: PetscFree(s);
118: s = tail;
119: }
120: PetscFree(*seg);
121: return 0;
122: }
124: /*@C
125: PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer
127: Not Collective
129: Input Parameters:
130: + seg - segmented buffer
131: - contig - allocated buffer to hold contiguous data
133: Level: developer
135: .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractInPlace()`
136: @*/
137: PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg, void *contig)
138: {
139: size_t unitbytes;
140: struct _PetscSegBufferLink *s, *t;
141: char *ptr;
143: unitbytes = seg->unitbytes;
144: s = seg->head;
145: ptr = ((char *)contig) + s->tailused * unitbytes;
146: PetscMemcpy(ptr, s->u.array, s->used * unitbytes);
147: for (t = s->tail; t;) {
148: struct _PetscSegBufferLink *tail = t->tail;
149: ptr -= t->used * unitbytes;
150: PetscMemcpy(ptr, t->u.array, t->used * unitbytes);
151: PetscFree(t);
152: t = tail;
153: }
155: s->used = 0;
156: s->tailused = 0;
157: s->tail = NULL;
158: return 0;
159: }
161: /*@C
162: PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer
164: Not Collective
166: Input Parameter:
167: . seg - segmented buffer
169: Output Parameter:
170: . contiguous - address of new array containing contiguous data, caller frees with `PetscFree()`
172: Level: developer
174: Developer Note:
175: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done
177: .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`
178: @*/
179: PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg, void *contiguous)
180: {
181: struct _PetscSegBufferLink *s;
182: void *contig;
184: s = seg->head;
186: PetscMalloc((s->used + s->tailused) * seg->unitbytes, &contig);
187: PetscSegBufferExtractTo(seg, contig);
188: *(void **)contiguous = contig;
189: return 0;
190: }
192: /*@C
193: PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse
195: Not Collective
197: Input Parameter:
198: . seg - segmented buffer object
200: Output Parameter:
201: . contig - address of pointer to contiguous memory, may be NULL
203: Level: developer
205: .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`
206: @*/
207: PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg, void *contig)
208: {
209: struct _PetscSegBufferLink *head;
211: head = seg->head;
212: if (PetscUnlikely(head->tail)) {
213: PetscSegBuffer newseg;
215: PetscSegBufferCreate(seg->unitbytes, head->used + head->tailused, &newseg);
216: PetscSegBufferExtractTo(seg, newseg->head->u.array);
217: seg->head = newseg->head;
218: newseg->head = head;
219: PetscSegBufferDestroy(&newseg);
220: head = seg->head;
221: }
222: if (contig) *(char **)contig = head->u.array;
223: head->used = 0;
224: return 0;
225: }
227: /*@C
228: PetscSegBufferGetSize - get currently used size of segmented buffer
230: Not Collective
232: Input Parameter:
233: . seg - segmented buffer object
235: Output Parameter:
236: . usedsize - number of used units
238: Level: developer
240: .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferCreate()`, `PetscSegBufferGet()`
241: @*/
242: PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg, size_t *usedsize)
243: {
244: *usedsize = seg->head->tailused + seg->head->used;
245: return 0;
246: }
248: /*@C
249: PetscSegBufferUnuse - return some unused entries obtained with an overzealous `PetscSegBufferGet()`
251: Not Collective
253: Input Parameters:
254: + seg - segmented buffer object
255: - unused - number of unused units
257: Level: developer
259: .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`
260: @*/
261: PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg, size_t unused)
262: {
263: struct _PetscSegBufferLink *head;
265: head = seg->head;
267: head->used -= unused;
268: return 0;
269: }