10f453b92SJed Brown #include <petscsys.h> 20f453b92SJed Brown 3137cf7b6SJed Brown struct _PetscSegBufferLink { 4137cf7b6SJed Brown struct _PetscSegBufferLink *tail; 513e3f751SJed Brown size_t alloc; 613e3f751SJed Brown size_t used; 713e3f751SJed Brown size_t tailused; 80f453b92SJed Brown union { /* Dummy types to ensure alignment */ 90f453b92SJed Brown PetscReal dummy_real; 100f453b92SJed Brown PetscInt dummy_int; 11137cf7b6SJed Brown char array[1]; /* This array is over-allocated for the size of the link */ 120f453b92SJed Brown } u; 130f453b92SJed Brown }; 140f453b92SJed Brown 15137cf7b6SJed Brown /* Segmented (extendable) array implementation */ 16137cf7b6SJed Brown struct _n_PetscSegBuffer { 17137cf7b6SJed Brown struct _PetscSegBufferLink *head; 1813e3f751SJed Brown size_t unitbytes; 19137cf7b6SJed Brown }; 20137cf7b6SJed Brown 2113e3f751SJed Brown static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count) 220f453b92SJed Brown { 2313e3f751SJed Brown size_t alloc; 24137cf7b6SJed Brown struct _PetscSegBufferLink *newlink,*s; 250f453b92SJed Brown 260f453b92SJed Brown PetscFunctionBegin; 27137cf7b6SJed Brown s = seg->head; 280f453b92SJed Brown /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */ 29137cf7b6SJed Brown alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused)); 309566063dSJacob Faibussowitsch PetscCall(PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink)); 319566063dSJacob Faibussowitsch PetscCall(PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u))); 320f453b92SJed Brown 33137cf7b6SJed Brown newlink->tailused = s->used + s->tailused; 34137cf7b6SJed Brown newlink->tail = s; 35137cf7b6SJed Brown newlink->alloc = alloc; 36137cf7b6SJed Brown seg->head = newlink; 370f453b92SJed Brown PetscFunctionReturn(0); 380f453b92SJed Brown } 390f453b92SJed Brown 400f453b92SJed Brown /*@C 410f453b92SJed Brown PetscSegBufferCreate - create segmented buffer 420f453b92SJed Brown 430f453b92SJed Brown Not Collective 440f453b92SJed Brown 454165533cSJose E. Roman Input Parameters: 460f453b92SJed Brown + unitbytes - number of bytes that each entry will contain 470f453b92SJed Brown - expected - expected/typical number of entries 480f453b92SJed Brown 494165533cSJose E. Roman Output Parameter: 500f453b92SJed Brown . seg - segmented buffer object 510f453b92SJed Brown 520f453b92SJed Brown Level: developer 530f453b92SJed Brown 5447452e7bSJed Brown .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 550f453b92SJed Brown @*/ 5613e3f751SJed Brown PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg) 570f453b92SJed Brown { 58137cf7b6SJed Brown struct _PetscSegBufferLink *head; 590f453b92SJed Brown 600f453b92SJed Brown PetscFunctionBegin; 619566063dSJacob Faibussowitsch PetscCall(PetscNew(seg)); 629566063dSJacob Faibussowitsch PetscCall(PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head)); 639566063dSJacob Faibussowitsch PetscCall(PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u))); 640f453b92SJed Brown 65137cf7b6SJed Brown head->alloc = expected; 660f453b92SJed Brown (*seg)->unitbytes = unitbytes; 67137cf7b6SJed Brown (*seg)->head = head; 680f453b92SJed Brown PetscFunctionReturn(0); 690f453b92SJed Brown } 700f453b92SJed Brown 710f453b92SJed Brown /*@C 720f453b92SJed Brown PetscSegBufferGet - get new buffer space from a segmented buffer 730f453b92SJed Brown 740f453b92SJed Brown Not Collective 750f453b92SJed Brown 764165533cSJose E. Roman Input Parameters: 770f453b92SJed Brown + seg - address of segmented buffer 780f453b92SJed Brown - count - number of entries needed 790f453b92SJed Brown 804165533cSJose E. Roman Output Parameter: 810f453b92SJed Brown . buf - address of new buffer for contiguous data 820f453b92SJed Brown 830f453b92SJed Brown Level: developer 840f453b92SJed Brown 8547452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 860f453b92SJed Brown @*/ 8713e3f751SJed Brown PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf) 880f453b92SJed Brown { 89137cf7b6SJed Brown struct _PetscSegBufferLink *s; 900f453b92SJed Brown 910f453b92SJed Brown PetscFunctionBegin; 92137cf7b6SJed Brown s = seg->head; 939566063dSJacob Faibussowitsch if (PetscUnlikely(s->used + count > s->alloc)) PetscCall(PetscSegBufferAlloc_Private(seg,count)); 94137cf7b6SJed Brown s = seg->head; 95137cf7b6SJed Brown *(char**)buf = &s->u.array[s->used*seg->unitbytes]; 960f453b92SJed Brown s->used += count; 970f453b92SJed Brown PetscFunctionReturn(0); 980f453b92SJed Brown } 990f453b92SJed Brown 1000f453b92SJed Brown /*@C 1010f453b92SJed Brown PetscSegBufferDestroy - destroy segmented buffer 1020f453b92SJed Brown 1030f453b92SJed Brown Not Collective 1040f453b92SJed Brown 1054165533cSJose E. Roman Input Parameter: 1060f453b92SJed Brown . seg - address of segmented buffer object 1070f453b92SJed Brown 1080f453b92SJed Brown Level: developer 1090f453b92SJed Brown 1100f453b92SJed Brown .seealso: PetscSegBufferCreate() 1110f453b92SJed Brown @*/ 1120f453b92SJed Brown PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) 1130f453b92SJed Brown { 114137cf7b6SJed Brown struct _PetscSegBufferLink *s; 1150f453b92SJed Brown 1160f453b92SJed Brown PetscFunctionBegin; 1175d7c30b2SJed Brown if (!*seg) PetscFunctionReturn(0); 118137cf7b6SJed Brown for (s=(*seg)->head; s;) { 119137cf7b6SJed Brown struct _PetscSegBufferLink *tail = s->tail; 1209566063dSJacob Faibussowitsch PetscCall(PetscFree(s)); 1210f453b92SJed Brown s = tail; 1220f453b92SJed Brown } 1239566063dSJacob Faibussowitsch PetscCall(PetscFree(*seg)); 1240f453b92SJed Brown PetscFunctionReturn(0); 1250f453b92SJed Brown } 1260f453b92SJed Brown 1270f453b92SJed Brown /*@C 12847452e7bSJed Brown PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 12947452e7bSJed Brown 13047452e7bSJed Brown Not Collective 13147452e7bSJed Brown 1324165533cSJose E. Roman Input Parameters: 13347452e7bSJed Brown + seg - segmented buffer 13447452e7bSJed Brown - contig - allocated buffer to hold contiguous data 13547452e7bSJed Brown 13647452e7bSJed Brown Level: developer 13747452e7bSJed Brown 13847452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 13947452e7bSJed Brown @*/ 140137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig) 14147452e7bSJed Brown { 14213e3f751SJed Brown size_t unitbytes; 143137cf7b6SJed Brown struct _PetscSegBufferLink *s,*t; 14447452e7bSJed Brown char *ptr; 14547452e7bSJed Brown 14647452e7bSJed Brown PetscFunctionBegin; 147137cf7b6SJed Brown unitbytes = seg->unitbytes; 148137cf7b6SJed Brown s = seg->head; 14947452e7bSJed Brown ptr = ((char*)contig) + s->tailused*unitbytes; 1509566063dSJacob Faibussowitsch PetscCall(PetscMemcpy(ptr,s->u.array,s->used*unitbytes)); 15147452e7bSJed Brown for (t=s->tail; t;) { 152137cf7b6SJed Brown struct _PetscSegBufferLink *tail = t->tail; 15347452e7bSJed Brown ptr -= t->used*unitbytes; 1549566063dSJacob Faibussowitsch PetscCall(PetscMemcpy(ptr,t->u.array,t->used*unitbytes)); 1559566063dSJacob Faibussowitsch PetscCall(PetscFree(t)); 15647452e7bSJed Brown t = tail; 15747452e7bSJed Brown } 1582c71b3e2SJacob Faibussowitsch PetscCheckFalse(ptr != contig,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 15947452e7bSJed Brown s->used = 0; 16047452e7bSJed Brown s->tailused = 0; 16147452e7bSJed Brown s->tail = NULL; 16247452e7bSJed Brown PetscFunctionReturn(0); 16347452e7bSJed Brown } 16447452e7bSJed Brown 16547452e7bSJed Brown /*@C 16647452e7bSJed Brown PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 1670f453b92SJed Brown 1680f453b92SJed Brown Not Collective 1690f453b92SJed Brown 1704165533cSJose E. Roman Input Parameter: 1710f453b92SJed Brown . seg - segmented buffer 1720f453b92SJed Brown 1734165533cSJose E. Roman Output Parameter: 1740f453b92SJed Brown . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 1750f453b92SJed Brown 1760f453b92SJed Brown Level: developer 1770f453b92SJed Brown 17847452e7bSJed Brown Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 17947452e7bSJed Brown 18047452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 1810f453b92SJed Brown @*/ 182137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous) 1830f453b92SJed Brown { 184137cf7b6SJed Brown struct _PetscSegBufferLink *s; 18547452e7bSJed Brown void *contig; 1860f453b92SJed Brown 1870f453b92SJed Brown PetscFunctionBegin; 188137cf7b6SJed Brown s = seg->head; 1890f453b92SJed Brown 1909566063dSJacob Faibussowitsch PetscCall(PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig)); 1919566063dSJacob Faibussowitsch PetscCall(PetscSegBufferExtractTo(seg,contig)); 19247452e7bSJed Brown *(void**)contiguous = contig; 19347452e7bSJed Brown PetscFunctionReturn(0); 1940f453b92SJed Brown } 19547452e7bSJed Brown 19647452e7bSJed Brown /*@C 19747452e7bSJed Brown PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 19847452e7bSJed Brown 19901d09641SJed Brown Not Collective 20047452e7bSJed Brown 2014165533cSJose E. Roman Input Parameter: 20247452e7bSJed Brown . seg - segmented buffer object 20347452e7bSJed Brown 2044165533cSJose E. Roman Output Parameter: 205*d2b3fd65SBarry Smith . contig - address of pointer to contiguous memory, may be NULL 20647452e7bSJed Brown 20747452e7bSJed Brown Level: developer 20847452e7bSJed Brown 20947452e7bSJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 21047452e7bSJed Brown @*/ 211137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig) 21247452e7bSJed Brown { 213137cf7b6SJed Brown struct _PetscSegBufferLink *head; 21447452e7bSJed Brown 21547452e7bSJed Brown PetscFunctionBegin; 216137cf7b6SJed Brown head = seg->head; 217137cf7b6SJed Brown if (PetscUnlikely(head->tail)) { 218137cf7b6SJed Brown PetscSegBuffer newseg; 21947452e7bSJed Brown 2209566063dSJacob Faibussowitsch PetscCall(PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg)); 2219566063dSJacob Faibussowitsch PetscCall(PetscSegBufferExtractTo(seg,newseg->head->u.array)); 222137cf7b6SJed Brown seg->head = newseg->head; 223137cf7b6SJed Brown newseg->head = head; 2249566063dSJacob Faibussowitsch PetscCall(PetscSegBufferDestroy(&newseg)); 225137cf7b6SJed Brown head = seg->head; 22647452e7bSJed Brown } 227*d2b3fd65SBarry Smith if (contig) *(char**)contig = head->u.array; 228137cf7b6SJed Brown head->used = 0; 2290f453b92SJed Brown PetscFunctionReturn(0); 2300f453b92SJed Brown } 23101d09641SJed Brown 23201d09641SJed Brown /*@C 23301d09641SJed Brown PetscSegBufferGetSize - get currently used size of segmented buffer 23401d09641SJed Brown 23501d09641SJed Brown Not Collective 23601d09641SJed Brown 2374165533cSJose E. Roman Input Parameter: 23801d09641SJed Brown . seg - segmented buffer object 23901d09641SJed Brown 2404165533cSJose E. Roman Output Parameter: 24101d09641SJed Brown . usedsize - number of used units 24201d09641SJed Brown 24301d09641SJed Brown Level: developer 24401d09641SJed Brown 24501d09641SJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet() 24601d09641SJed Brown @*/ 24713e3f751SJed Brown PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize) 24801d09641SJed Brown { 24901d09641SJed Brown PetscFunctionBegin; 250137cf7b6SJed Brown *usedsize = seg->head->tailused + seg->head->used; 25101d09641SJed Brown PetscFunctionReturn(0); 25201d09641SJed Brown } 25301d09641SJed Brown 25401d09641SJed Brown /*@C 25501d09641SJed Brown PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 25601d09641SJed Brown 25701d09641SJed Brown Not Collective 25801d09641SJed Brown 2594165533cSJose E. Roman Input Parameters: 26001d09641SJed Brown + seg - segmented buffer object 26101d09641SJed Brown - unused - number of unused units 26201d09641SJed Brown 26301d09641SJed Brown Level: developer 26401d09641SJed Brown 26501d09641SJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet() 26601d09641SJed Brown @*/ 26713e3f751SJed Brown PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused) 26801d09641SJed Brown { 269137cf7b6SJed Brown struct _PetscSegBufferLink *head; 27001d09641SJed Brown 27101d09641SJed Brown PetscFunctionBegin; 272137cf7b6SJed Brown head = seg->head; 2732c71b3e2SJacob Faibussowitsch PetscCheckFalse(head->used < unused,PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Attempt to return more unused entries (%zu) than previously gotten (%zu)",unused,head->used); 274137cf7b6SJed Brown head->used -= unused; 27501d09641SJed Brown PetscFunctionReturn(0); 27601d09641SJed Brown } 277