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 { 230f453b92SJed Brown PetscErrorCode ierr; 2413e3f751SJed Brown size_t alloc; 25137cf7b6SJed Brown struct _PetscSegBufferLink *newlink,*s; 260f453b92SJed Brown 270f453b92SJed Brown PetscFunctionBegin; 28137cf7b6SJed Brown s = seg->head; 290f453b92SJed Brown /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */ 30137cf7b6SJed Brown alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused)); 31137cf7b6SJed Brown ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);CHKERRQ(ierr); 32137cf7b6SJed Brown ierr = PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr); 330f453b92SJed Brown 34137cf7b6SJed Brown newlink->tailused = s->used + s->tailused; 35137cf7b6SJed Brown newlink->tail = s; 36137cf7b6SJed Brown newlink->alloc = alloc; 37137cf7b6SJed Brown seg->head = newlink; 380f453b92SJed Brown PetscFunctionReturn(0); 390f453b92SJed Brown } 400f453b92SJed Brown 410f453b92SJed Brown /*@C 420f453b92SJed Brown PetscSegBufferCreate - create segmented buffer 430f453b92SJed Brown 440f453b92SJed Brown Not Collective 450f453b92SJed Brown 464165533cSJose E. Roman Input Parameters: 470f453b92SJed Brown + unitbytes - number of bytes that each entry will contain 480f453b92SJed Brown - expected - expected/typical number of entries 490f453b92SJed Brown 504165533cSJose E. Roman Output Parameter: 510f453b92SJed Brown . seg - segmented buffer object 520f453b92SJed Brown 530f453b92SJed Brown Level: developer 540f453b92SJed Brown 5547452e7bSJed Brown .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 560f453b92SJed Brown @*/ 5713e3f751SJed Brown PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg) 580f453b92SJed Brown { 590f453b92SJed Brown PetscErrorCode ierr; 60137cf7b6SJed Brown struct _PetscSegBufferLink *head; 610f453b92SJed Brown 620f453b92SJed Brown PetscFunctionBegin; 6395dccacaSBarry Smith ierr = PetscNew(seg);CHKERRQ(ierr); 64137cf7b6SJed Brown ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);CHKERRQ(ierr); 65137cf7b6SJed Brown ierr = PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr); 660f453b92SJed Brown 67137cf7b6SJed Brown head->alloc = expected; 680f453b92SJed Brown (*seg)->unitbytes = unitbytes; 69137cf7b6SJed Brown (*seg)->head = head; 700f453b92SJed Brown PetscFunctionReturn(0); 710f453b92SJed Brown } 720f453b92SJed Brown 730f453b92SJed Brown /*@C 740f453b92SJed Brown PetscSegBufferGet - get new buffer space from a segmented buffer 750f453b92SJed Brown 760f453b92SJed Brown Not Collective 770f453b92SJed Brown 784165533cSJose E. Roman Input Parameters: 790f453b92SJed Brown + seg - address of segmented buffer 800f453b92SJed Brown - count - number of entries needed 810f453b92SJed Brown 824165533cSJose E. Roman Output Parameter: 830f453b92SJed Brown . buf - address of new buffer for contiguous data 840f453b92SJed Brown 850f453b92SJed Brown Level: developer 860f453b92SJed Brown 8747452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 880f453b92SJed Brown @*/ 8913e3f751SJed Brown PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf) 900f453b92SJed Brown { 910f453b92SJed Brown PetscErrorCode ierr; 92137cf7b6SJed Brown struct _PetscSegBufferLink *s; 930f453b92SJed Brown 940f453b92SJed Brown PetscFunctionBegin; 95137cf7b6SJed Brown s = seg->head; 960f453b92SJed Brown if (PetscUnlikely(s->used + count > s->alloc)) {ierr = PetscSegBufferAlloc_Private(seg,count);CHKERRQ(ierr);} 97137cf7b6SJed Brown s = seg->head; 98137cf7b6SJed Brown *(char**)buf = &s->u.array[s->used*seg->unitbytes]; 990f453b92SJed Brown s->used += count; 1000f453b92SJed Brown PetscFunctionReturn(0); 1010f453b92SJed Brown } 1020f453b92SJed Brown 1030f453b92SJed Brown /*@C 1040f453b92SJed Brown PetscSegBufferDestroy - destroy segmented buffer 1050f453b92SJed Brown 1060f453b92SJed Brown Not Collective 1070f453b92SJed Brown 1084165533cSJose E. Roman Input Parameter: 1090f453b92SJed Brown . seg - address of segmented buffer object 1100f453b92SJed Brown 1110f453b92SJed Brown Level: developer 1120f453b92SJed Brown 1130f453b92SJed Brown .seealso: PetscSegBufferCreate() 1140f453b92SJed Brown @*/ 1150f453b92SJed Brown PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) 1160f453b92SJed Brown { 1170f453b92SJed Brown PetscErrorCode ierr; 118137cf7b6SJed Brown struct _PetscSegBufferLink *s; 1190f453b92SJed Brown 1200f453b92SJed Brown PetscFunctionBegin; 1215d7c30b2SJed Brown if (!*seg) PetscFunctionReturn(0); 122137cf7b6SJed Brown for (s=(*seg)->head; s;) { 123137cf7b6SJed Brown struct _PetscSegBufferLink *tail = s->tail; 1240f453b92SJed Brown ierr = PetscFree(s);CHKERRQ(ierr); 1250f453b92SJed Brown s = tail; 1260f453b92SJed Brown } 127137cf7b6SJed Brown ierr = PetscFree(*seg);CHKERRQ(ierr); 1280f453b92SJed Brown PetscFunctionReturn(0); 1290f453b92SJed Brown } 1300f453b92SJed Brown 1310f453b92SJed Brown /*@C 13247452e7bSJed Brown PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 13347452e7bSJed Brown 13447452e7bSJed Brown Not Collective 13547452e7bSJed Brown 1364165533cSJose E. Roman Input Parameters: 13747452e7bSJed Brown + seg - segmented buffer 13847452e7bSJed Brown - contig - allocated buffer to hold contiguous data 13947452e7bSJed Brown 14047452e7bSJed Brown Level: developer 14147452e7bSJed Brown 14247452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 14347452e7bSJed Brown @*/ 144137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig) 14547452e7bSJed Brown { 14647452e7bSJed Brown PetscErrorCode ierr; 14713e3f751SJed Brown size_t unitbytes; 148137cf7b6SJed Brown struct _PetscSegBufferLink *s,*t; 14947452e7bSJed Brown char *ptr; 15047452e7bSJed Brown 15147452e7bSJed Brown PetscFunctionBegin; 152137cf7b6SJed Brown unitbytes = seg->unitbytes; 153137cf7b6SJed Brown s = seg->head; 15447452e7bSJed Brown ptr = ((char*)contig) + s->tailused*unitbytes; 15547452e7bSJed Brown ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr); 15647452e7bSJed Brown for (t=s->tail; t;) { 157137cf7b6SJed Brown struct _PetscSegBufferLink *tail = t->tail; 15847452e7bSJed Brown ptr -= t->used*unitbytes; 15947452e7bSJed Brown ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr); 16047452e7bSJed Brown ierr = PetscFree(t);CHKERRQ(ierr); 16147452e7bSJed Brown t = tail; 16247452e7bSJed Brown } 163*2c71b3e2SJacob Faibussowitsch PetscCheckFalse(ptr != contig,PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 16447452e7bSJed Brown s->used = 0; 16547452e7bSJed Brown s->tailused = 0; 16647452e7bSJed Brown s->tail = NULL; 16747452e7bSJed Brown PetscFunctionReturn(0); 16847452e7bSJed Brown } 16947452e7bSJed Brown 17047452e7bSJed Brown /*@C 17147452e7bSJed Brown PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 1720f453b92SJed Brown 1730f453b92SJed Brown Not Collective 1740f453b92SJed Brown 1754165533cSJose E. Roman Input Parameter: 1760f453b92SJed Brown . seg - segmented buffer 1770f453b92SJed Brown 1784165533cSJose E. Roman Output Parameter: 1790f453b92SJed Brown . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 1800f453b92SJed Brown 1810f453b92SJed Brown Level: developer 1820f453b92SJed Brown 18347452e7bSJed Brown Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 18447452e7bSJed Brown 18547452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 1860f453b92SJed Brown @*/ 187137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous) 1880f453b92SJed Brown { 1890f453b92SJed Brown PetscErrorCode ierr; 190137cf7b6SJed Brown struct _PetscSegBufferLink *s; 19147452e7bSJed Brown void *contig; 1920f453b92SJed Brown 1930f453b92SJed Brown PetscFunctionBegin; 194137cf7b6SJed Brown s = seg->head; 1950f453b92SJed Brown 196137cf7b6SJed Brown ierr = PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);CHKERRQ(ierr); 19747452e7bSJed Brown ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr); 19847452e7bSJed Brown *(void**)contiguous = contig; 19947452e7bSJed Brown PetscFunctionReturn(0); 2000f453b92SJed Brown } 20147452e7bSJed Brown 20247452e7bSJed Brown /*@C 20347452e7bSJed Brown PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 20447452e7bSJed Brown 20501d09641SJed Brown Not Collective 20647452e7bSJed Brown 2074165533cSJose E. Roman Input Parameter: 20847452e7bSJed Brown . seg - segmented buffer object 20947452e7bSJed Brown 2104165533cSJose E. Roman Output Parameter: 21147452e7bSJed Brown . contig - address of pointer to contiguous memory 21247452e7bSJed Brown 21347452e7bSJed Brown Level: developer 21447452e7bSJed Brown 21547452e7bSJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 21647452e7bSJed Brown @*/ 217137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig) 21847452e7bSJed Brown { 21947452e7bSJed Brown PetscErrorCode ierr; 220137cf7b6SJed Brown struct _PetscSegBufferLink *head; 22147452e7bSJed Brown 22247452e7bSJed Brown PetscFunctionBegin; 223137cf7b6SJed Brown head = seg->head; 224137cf7b6SJed Brown if (PetscUnlikely(head->tail)) { 225137cf7b6SJed Brown PetscSegBuffer newseg; 22647452e7bSJed Brown 227137cf7b6SJed Brown ierr = PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);CHKERRQ(ierr); 228137cf7b6SJed Brown ierr = PetscSegBufferExtractTo(seg,newseg->head->u.array);CHKERRQ(ierr); 229137cf7b6SJed Brown seg->head = newseg->head; 230137cf7b6SJed Brown newseg->head = head; 231137cf7b6SJed Brown ierr = PetscSegBufferDestroy(&newseg);CHKERRQ(ierr); 232137cf7b6SJed Brown head = seg->head; 23347452e7bSJed Brown } 234137cf7b6SJed Brown *(char**)contig = head->u.array; 235137cf7b6SJed Brown head->used = 0; 2360f453b92SJed Brown PetscFunctionReturn(0); 2370f453b92SJed Brown } 23801d09641SJed Brown 23901d09641SJed Brown /*@C 24001d09641SJed Brown PetscSegBufferGetSize - get currently used size of segmented buffer 24101d09641SJed Brown 24201d09641SJed Brown Not Collective 24301d09641SJed Brown 2444165533cSJose E. Roman Input Parameter: 24501d09641SJed Brown . seg - segmented buffer object 24601d09641SJed Brown 2474165533cSJose E. Roman Output Parameter: 24801d09641SJed Brown . usedsize - number of used units 24901d09641SJed Brown 25001d09641SJed Brown Level: developer 25101d09641SJed Brown 25201d09641SJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet() 25301d09641SJed Brown @*/ 25413e3f751SJed Brown PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize) 25501d09641SJed Brown { 25601d09641SJed Brown 25701d09641SJed Brown PetscFunctionBegin; 258137cf7b6SJed Brown *usedsize = seg->head->tailused + seg->head->used; 25901d09641SJed Brown PetscFunctionReturn(0); 26001d09641SJed Brown } 26101d09641SJed Brown 26201d09641SJed Brown /*@C 26301d09641SJed Brown PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 26401d09641SJed Brown 26501d09641SJed Brown Not Collective 26601d09641SJed Brown 2674165533cSJose E. Roman Input Parameters: 26801d09641SJed Brown + seg - segmented buffer object 26901d09641SJed Brown - unused - number of unused units 27001d09641SJed Brown 27101d09641SJed Brown Level: developer 27201d09641SJed Brown 27301d09641SJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet() 27401d09641SJed Brown @*/ 27513e3f751SJed Brown PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused) 27601d09641SJed Brown { 277137cf7b6SJed Brown struct _PetscSegBufferLink *head; 27801d09641SJed Brown 27901d09641SJed Brown PetscFunctionBegin; 280137cf7b6SJed Brown head = seg->head; 281*2c71b3e2SJacob 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); 282137cf7b6SJed Brown head->used -= unused; 28301d09641SJed Brown PetscFunctionReturn(0); 28401d09641SJed Brown } 285