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:   for (s=(*seg)->head; s;) {
130:     struct _PetscSegBufferLink *tail = s->tail;
131:     PetscFree(s);
132:     s = tail;
133:   }
134:   PetscFree(*seg);
135:   return(0);
136: }

140: /*@C
141:    PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer

143:    Not Collective

145:    Input Argument:
146: +  seg - segmented buffer
147: -  contig - allocated buffer to hold contiguous data

149:    Level: developer

151: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace()
152: @*/
153: PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig)
154: {
155:   PetscErrorCode             ierr;
156:   size_t                     unitbytes;
157:   struct _PetscSegBufferLink *s,*t;
158:   char                       *ptr;

161:   unitbytes = seg->unitbytes;
162:   s = seg->head;
163:   ptr  = ((char*)contig) + s->tailused*unitbytes;
164:   PetscMemcpy(ptr,s->u.array,s->used*unitbytes);
165:   for (t=s->tail; t;) {
166:     struct _PetscSegBufferLink *tail = t->tail;
167:     ptr -= t->used*unitbytes;
168:     PetscMemcpy(ptr,t->u.array,t->used*unitbytes);
169:     PetscFree(t);
170:     t    = tail;
171:   }
172:   if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match");
173:   s->used             = 0;
174:   s->tailused         = 0;
175:   s->tail             = NULL;
176:   return(0);
177: }

181: /*@C
182:    PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer

184:    Not Collective

186:    Input Argument:
187: .  seg - segmented buffer

189:    Output Argument:
190: .  contiguous - address of new array containing contiguous data, caller frees with PetscFree()

192:    Level: developer

194:    Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done

196: .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace()
197: @*/
198: PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous)
199: {
200:   PetscErrorCode             ierr;
201:   struct _PetscSegBufferLink *s;
202:   void                       *contig;

205:   s = seg->head;

207:   PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);
208:   PetscSegBufferExtractTo(seg,contig);
209:   *(void**)contiguous = contig;
210:   return(0);
211: }

215: /*@C
216:    PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse

218:    Not Collective

220:    Input Arguments:
221: .  seg - segmented buffer object

223:    Output Arguments:
224: .  contig - address of pointer to contiguous memory

226:    Level: developer

228: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo()
229: @*/
230: PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig)
231: {
233:   struct _PetscSegBufferLink *head;

236:   head = seg->head;
237:   if (PetscUnlikely(head->tail)) {
238:     PetscSegBuffer newseg;

240:     PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);
241:     PetscSegBufferExtractTo(seg,newseg->head->u.array);
242:     seg->head = newseg->head;
243:     newseg->head = head;
244:     PetscSegBufferDestroy(&newseg);
245:     head = seg->head;
246:   }
247:   *(char**)contig = head->u.array;
248:   head->used = 0;
249:   return(0);
250: }

254: /*@C
255:    PetscSegBufferGetSize - get currently used size of segmented buffer

257:    Not Collective

259:    Input Arguments:
260: .  seg - segmented buffer object

262:    Output Arguments:
263: .  usedsize - number of used units

265:    Level: developer

267: .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet()
268: @*/
269: PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize)
270: {

273:   *usedsize = seg->head->tailused + seg->head->used;
274:   return(0);
275: }

279: /*@C
280:    PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet()

282:    Not Collective

284:    Input Arguments:
285: +  seg - segmented buffer object
286: -  unused - number of unused units

288:    Level: developer

290: .seealso: PetscSegBufferCreate(), PetscSegBufferGet()
291: @*/
292: PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused)
293: {
294:   struct _PetscSegBufferLink *head;

297:   head = seg->head;
298:   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);
299:   head->used -= unused;
300:   return(0);
301: }