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: }