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; 89371c9d4SSatish Balay union 99371c9d4SSatish Balay { /* Dummy types to ensure alignment */ 100f453b92SJed Brown PetscReal dummy_real; 110f453b92SJed Brown PetscInt dummy_int; 12137cf7b6SJed Brown char array[1]; /* This array is over-allocated for the size of the link */ 130f453b92SJed Brown } u; 140f453b92SJed Brown }; 150f453b92SJed Brown 16137cf7b6SJed Brown /* Segmented (extendable) array implementation */ 17137cf7b6SJed Brown struct _n_PetscSegBuffer { 18137cf7b6SJed Brown struct _PetscSegBufferLink *head; 1913e3f751SJed Brown size_t unitbytes; 20137cf7b6SJed Brown }; 21137cf7b6SJed Brown 229371c9d4SSatish Balay static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg, size_t count) { 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 41*811af0c4SBarry Smith PetscSegBufferCreate - create a 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 54db781477SPatrick Sanan .seealso: `PetscSegBufferGet()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`, `PetscSegBufferDestroy()` 550f453b92SJed Brown @*/ 569371c9d4SSatish Balay PetscErrorCode PetscSegBufferCreate(size_t unitbytes, size_t expected, PetscSegBuffer *seg) { 57137cf7b6SJed Brown struct _PetscSegBufferLink *head; 580f453b92SJed Brown 590f453b92SJed Brown PetscFunctionBegin; 609566063dSJacob Faibussowitsch PetscCall(PetscNew(seg)); 619566063dSJacob Faibussowitsch PetscCall(PetscMalloc(offsetof(struct _PetscSegBufferLink, u) + expected * unitbytes, &head)); 629566063dSJacob Faibussowitsch PetscCall(PetscMemzero(head, offsetof(struct _PetscSegBufferLink, u))); 630f453b92SJed Brown 64137cf7b6SJed Brown head->alloc = expected; 650f453b92SJed Brown (*seg)->unitbytes = unitbytes; 66137cf7b6SJed Brown (*seg)->head = head; 670f453b92SJed Brown PetscFunctionReturn(0); 680f453b92SJed Brown } 690f453b92SJed Brown 700f453b92SJed Brown /*@C 710f453b92SJed Brown PetscSegBufferGet - get new buffer space from a segmented buffer 720f453b92SJed Brown 730f453b92SJed Brown Not Collective 740f453b92SJed Brown 754165533cSJose E. Roman Input Parameters: 760f453b92SJed Brown + seg - address of segmented buffer 770f453b92SJed Brown - count - number of entries needed 780f453b92SJed Brown 794165533cSJose E. Roman Output Parameter: 800f453b92SJed Brown . buf - address of new buffer for contiguous data 810f453b92SJed Brown 820f453b92SJed Brown Level: developer 830f453b92SJed Brown 84db781477SPatrick Sanan .seealso: `PetscSegBufferCreate()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`, `PetscSegBufferDestroy()` 850f453b92SJed Brown @*/ 869371c9d4SSatish Balay PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg, size_t count, void *buf) { 87137cf7b6SJed Brown struct _PetscSegBufferLink *s; 880f453b92SJed Brown 890f453b92SJed Brown PetscFunctionBegin; 90137cf7b6SJed Brown s = seg->head; 919566063dSJacob Faibussowitsch if (PetscUnlikely(s->used + count > s->alloc)) PetscCall(PetscSegBufferAlloc_Private(seg, count)); 92137cf7b6SJed Brown s = seg->head; 93137cf7b6SJed Brown *(char **)buf = &s->u.array[s->used * seg->unitbytes]; 940f453b92SJed Brown s->used += count; 950f453b92SJed Brown PetscFunctionReturn(0); 960f453b92SJed Brown } 970f453b92SJed Brown 980f453b92SJed Brown /*@C 990f453b92SJed Brown PetscSegBufferDestroy - destroy segmented buffer 1000f453b92SJed Brown 1010f453b92SJed Brown Not Collective 1020f453b92SJed Brown 1034165533cSJose E. Roman Input Parameter: 1040f453b92SJed Brown . seg - address of segmented buffer object 1050f453b92SJed Brown 1060f453b92SJed Brown Level: developer 1070f453b92SJed Brown 108db781477SPatrick Sanan .seealso: `PetscSegBufferCreate()` 1090f453b92SJed Brown @*/ 1109371c9d4SSatish Balay PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) { 111137cf7b6SJed Brown struct _PetscSegBufferLink *s; 1120f453b92SJed Brown 1130f453b92SJed Brown PetscFunctionBegin; 1145d7c30b2SJed Brown if (!*seg) PetscFunctionReturn(0); 115137cf7b6SJed Brown for (s = (*seg)->head; s;) { 116137cf7b6SJed Brown struct _PetscSegBufferLink *tail = s->tail; 1179566063dSJacob Faibussowitsch PetscCall(PetscFree(s)); 1180f453b92SJed Brown s = tail; 1190f453b92SJed Brown } 1209566063dSJacob Faibussowitsch PetscCall(PetscFree(*seg)); 1210f453b92SJed Brown PetscFunctionReturn(0); 1220f453b92SJed Brown } 1230f453b92SJed Brown 1240f453b92SJed Brown /*@C 12547452e7bSJed Brown PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 12647452e7bSJed Brown 12747452e7bSJed Brown Not Collective 12847452e7bSJed Brown 1294165533cSJose E. Roman Input Parameters: 13047452e7bSJed Brown + seg - segmented buffer 13147452e7bSJed Brown - contig - allocated buffer to hold contiguous data 13247452e7bSJed Brown 13347452e7bSJed Brown Level: developer 13447452e7bSJed Brown 135db781477SPatrick Sanan .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractInPlace()` 13647452e7bSJed Brown @*/ 1379371c9d4SSatish Balay PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg, void *contig) { 13813e3f751SJed Brown size_t unitbytes; 139137cf7b6SJed Brown struct _PetscSegBufferLink *s, *t; 14047452e7bSJed Brown char *ptr; 14147452e7bSJed Brown 14247452e7bSJed Brown PetscFunctionBegin; 143137cf7b6SJed Brown unitbytes = seg->unitbytes; 144137cf7b6SJed Brown s = seg->head; 14547452e7bSJed Brown ptr = ((char *)contig) + s->tailused * unitbytes; 1469566063dSJacob Faibussowitsch PetscCall(PetscMemcpy(ptr, s->u.array, s->used * unitbytes)); 14747452e7bSJed Brown for (t = s->tail; t;) { 148137cf7b6SJed Brown struct _PetscSegBufferLink *tail = t->tail; 14947452e7bSJed Brown ptr -= t->used * unitbytes; 1509566063dSJacob Faibussowitsch PetscCall(PetscMemcpy(ptr, t->u.array, t->used * unitbytes)); 1519566063dSJacob Faibussowitsch PetscCall(PetscFree(t)); 15247452e7bSJed Brown t = tail; 15347452e7bSJed Brown } 15408401ef6SPierre Jolivet PetscCheck(ptr == contig, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Tail count does not match"); 15547452e7bSJed Brown s->used = 0; 15647452e7bSJed Brown s->tailused = 0; 15747452e7bSJed Brown s->tail = NULL; 15847452e7bSJed Brown PetscFunctionReturn(0); 15947452e7bSJed Brown } 16047452e7bSJed Brown 16147452e7bSJed Brown /*@C 16247452e7bSJed Brown PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 1630f453b92SJed Brown 1640f453b92SJed Brown Not Collective 1650f453b92SJed Brown 1664165533cSJose E. Roman Input Parameter: 1670f453b92SJed Brown . seg - segmented buffer 1680f453b92SJed Brown 1694165533cSJose E. Roman Output Parameter: 170*811af0c4SBarry Smith . contiguous - address of new array containing contiguous data, caller frees with `PetscFree()` 1710f453b92SJed Brown 1720f453b92SJed Brown Level: developer 1730f453b92SJed Brown 174*811af0c4SBarry Smith Developer Note: 175*811af0c4SBarry Smith 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 17647452e7bSJed Brown 177db781477SPatrick Sanan .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()` 1780f453b92SJed Brown @*/ 1799371c9d4SSatish Balay PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg, void *contiguous) { 180137cf7b6SJed Brown struct _PetscSegBufferLink *s; 18147452e7bSJed Brown void *contig; 1820f453b92SJed Brown 1830f453b92SJed Brown PetscFunctionBegin; 184137cf7b6SJed Brown s = seg->head; 1850f453b92SJed Brown 1869566063dSJacob Faibussowitsch PetscCall(PetscMalloc((s->used + s->tailused) * seg->unitbytes, &contig)); 1879566063dSJacob Faibussowitsch PetscCall(PetscSegBufferExtractTo(seg, contig)); 18847452e7bSJed Brown *(void **)contiguous = contig; 18947452e7bSJed Brown PetscFunctionReturn(0); 1900f453b92SJed Brown } 19147452e7bSJed Brown 19247452e7bSJed Brown /*@C 19347452e7bSJed Brown PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 19447452e7bSJed Brown 19501d09641SJed Brown Not Collective 19647452e7bSJed Brown 1974165533cSJose E. Roman Input Parameter: 19847452e7bSJed Brown . seg - segmented buffer object 19947452e7bSJed Brown 2004165533cSJose E. Roman Output Parameter: 201d2b3fd65SBarry Smith . contig - address of pointer to contiguous memory, may be NULL 20247452e7bSJed Brown 20347452e7bSJed Brown Level: developer 20447452e7bSJed Brown 205db781477SPatrick Sanan .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()` 20647452e7bSJed Brown @*/ 2079371c9d4SSatish Balay PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg, void *contig) { 208137cf7b6SJed Brown struct _PetscSegBufferLink *head; 20947452e7bSJed Brown 21047452e7bSJed Brown PetscFunctionBegin; 211137cf7b6SJed Brown head = seg->head; 212137cf7b6SJed Brown if (PetscUnlikely(head->tail)) { 213137cf7b6SJed Brown PetscSegBuffer newseg; 21447452e7bSJed Brown 2159566063dSJacob Faibussowitsch PetscCall(PetscSegBufferCreate(seg->unitbytes, head->used + head->tailused, &newseg)); 2169566063dSJacob Faibussowitsch PetscCall(PetscSegBufferExtractTo(seg, newseg->head->u.array)); 217137cf7b6SJed Brown seg->head = newseg->head; 218137cf7b6SJed Brown newseg->head = head; 2199566063dSJacob Faibussowitsch PetscCall(PetscSegBufferDestroy(&newseg)); 220137cf7b6SJed Brown head = seg->head; 22147452e7bSJed Brown } 222d2b3fd65SBarry Smith if (contig) *(char **)contig = head->u.array; 223137cf7b6SJed Brown head->used = 0; 2240f453b92SJed Brown PetscFunctionReturn(0); 2250f453b92SJed Brown } 22601d09641SJed Brown 22701d09641SJed Brown /*@C 22801d09641SJed Brown PetscSegBufferGetSize - get currently used size of segmented buffer 22901d09641SJed Brown 23001d09641SJed Brown Not Collective 23101d09641SJed Brown 2324165533cSJose E. Roman Input Parameter: 23301d09641SJed Brown . seg - segmented buffer object 23401d09641SJed Brown 2354165533cSJose E. Roman Output Parameter: 23601d09641SJed Brown . usedsize - number of used units 23701d09641SJed Brown 23801d09641SJed Brown Level: developer 23901d09641SJed Brown 240db781477SPatrick Sanan .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferCreate()`, `PetscSegBufferGet()` 24101d09641SJed Brown @*/ 2429371c9d4SSatish Balay PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg, size_t *usedsize) { 24301d09641SJed Brown PetscFunctionBegin; 244137cf7b6SJed Brown *usedsize = seg->head->tailused + seg->head->used; 24501d09641SJed Brown PetscFunctionReturn(0); 24601d09641SJed Brown } 24701d09641SJed Brown 24801d09641SJed Brown /*@C 249*811af0c4SBarry Smith PetscSegBufferUnuse - return some unused entries obtained with an overzealous `PetscSegBufferGet()` 25001d09641SJed Brown 25101d09641SJed Brown Not Collective 25201d09641SJed Brown 2534165533cSJose E. Roman Input Parameters: 25401d09641SJed Brown + seg - segmented buffer object 25501d09641SJed Brown - unused - number of unused units 25601d09641SJed Brown 25701d09641SJed Brown Level: developer 25801d09641SJed Brown 259db781477SPatrick Sanan .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()` 26001d09641SJed Brown @*/ 2619371c9d4SSatish Balay PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg, size_t unused) { 262137cf7b6SJed Brown struct _PetscSegBufferLink *head; 26301d09641SJed Brown 26401d09641SJed Brown PetscFunctionBegin; 265137cf7b6SJed Brown head = seg->head; 26608401ef6SPierre Jolivet PetscCheck(head->used >= unused, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Attempt to return more unused entries (%zu) than previously gotten (%zu)", unused, head->used); 267137cf7b6SJed Brown head->used -= unused; 26801d09641SJed Brown PetscFunctionReturn(0); 26901d09641SJed Brown } 270