10f453b92SJed Brown #include <petscsys.h> 20f453b92SJed Brown 3137cf7b6SJed Brown struct _PetscSegBufferLink { 4137cf7b6SJed Brown struct _PetscSegBufferLink *tail; 5*13e3f751SJed Brown size_t alloc; 6*13e3f751SJed Brown size_t used; 7*13e3f751SJed 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; 18*13e3f751SJed Brown size_t unitbytes; 19137cf7b6SJed Brown }; 20137cf7b6SJed Brown 210f453b92SJed Brown #undef __FUNCT__ 220f453b92SJed Brown #define __FUNCT__ "PetscSegBufferAlloc_Private" 23*13e3f751SJed Brown static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count) 240f453b92SJed Brown { 250f453b92SJed Brown PetscErrorCode ierr; 26*13e3f751SJed Brown size_t alloc; 27137cf7b6SJed Brown struct _PetscSegBufferLink *newlink,*s; 280f453b92SJed Brown 290f453b92SJed Brown PetscFunctionBegin; 30137cf7b6SJed Brown s = seg->head; 310f453b92SJed Brown /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */ 32137cf7b6SJed Brown alloc = PetscMax(s->used+count,PetscMin(1000000/seg->unitbytes+1,s->alloc+s->tailused)); 33137cf7b6SJed Brown ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+alloc*seg->unitbytes,&newlink);CHKERRQ(ierr); 34137cf7b6SJed Brown ierr = PetscMemzero(newlink,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr); 350f453b92SJed Brown 36137cf7b6SJed Brown newlink->tailused = s->used + s->tailused; 37137cf7b6SJed Brown newlink->tail = s; 38137cf7b6SJed Brown newlink->alloc = alloc; 39137cf7b6SJed Brown seg->head = newlink; 400f453b92SJed Brown PetscFunctionReturn(0); 410f453b92SJed Brown } 420f453b92SJed Brown 430f453b92SJed Brown #undef __FUNCT__ 440f453b92SJed Brown #define __FUNCT__ "PetscSegBufferCreate" 450f453b92SJed Brown /*@C 460f453b92SJed Brown PetscSegBufferCreate - create segmented buffer 470f453b92SJed Brown 480f453b92SJed Brown Not Collective 490f453b92SJed Brown 500f453b92SJed Brown Input Arguments: 510f453b92SJed Brown + unitbytes - number of bytes that each entry will contain 520f453b92SJed Brown - expected - expected/typical number of entries 530f453b92SJed Brown 540f453b92SJed Brown Output Argument: 550f453b92SJed Brown . seg - segmented buffer object 560f453b92SJed Brown 570f453b92SJed Brown Level: developer 580f453b92SJed Brown 5947452e7bSJed Brown .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 600f453b92SJed Brown @*/ 61*13e3f751SJed Brown PetscErrorCode PetscSegBufferCreate(size_t unitbytes,size_t expected,PetscSegBuffer *seg) 620f453b92SJed Brown { 630f453b92SJed Brown PetscErrorCode ierr; 64137cf7b6SJed Brown struct _PetscSegBufferLink *head; 650f453b92SJed Brown 660f453b92SJed Brown PetscFunctionBegin; 67137cf7b6SJed Brown ierr = PetscMalloc(sizeof(struct _n_PetscSegBuffer),seg);CHKERRQ(ierr); 68137cf7b6SJed Brown ierr = PetscMalloc(offsetof(struct _PetscSegBufferLink,u)+expected*unitbytes,&head);CHKERRQ(ierr); 69137cf7b6SJed Brown ierr = PetscMemzero(head,offsetof(struct _PetscSegBufferLink,u));CHKERRQ(ierr); 700f453b92SJed Brown 71137cf7b6SJed Brown head->alloc = expected; 720f453b92SJed Brown (*seg)->unitbytes = unitbytes; 73137cf7b6SJed Brown (*seg)->head = head; 740f453b92SJed Brown PetscFunctionReturn(0); 750f453b92SJed Brown } 760f453b92SJed Brown 770f453b92SJed Brown #undef __FUNCT__ 780f453b92SJed Brown #define __FUNCT__ "PetscSegBufferGet" 790f453b92SJed Brown /*@C 800f453b92SJed Brown PetscSegBufferGet - get new buffer space from a segmented buffer 810f453b92SJed Brown 820f453b92SJed Brown Not Collective 830f453b92SJed Brown 840f453b92SJed Brown Input Arguments: 850f453b92SJed Brown + seg - address of segmented buffer 860f453b92SJed Brown - count - number of entries needed 870f453b92SJed Brown 880f453b92SJed Brown Output Argument: 890f453b92SJed Brown . buf - address of new buffer for contiguous data 900f453b92SJed Brown 910f453b92SJed Brown Level: developer 920f453b92SJed Brown 9347452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 940f453b92SJed Brown @*/ 95*13e3f751SJed Brown PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg,size_t count,void *buf) 960f453b92SJed Brown { 970f453b92SJed Brown PetscErrorCode ierr; 98137cf7b6SJed Brown struct _PetscSegBufferLink *s; 990f453b92SJed Brown 1000f453b92SJed Brown PetscFunctionBegin; 101137cf7b6SJed Brown s = seg->head; 1020f453b92SJed Brown if (PetscUnlikely(s->used + count > s->alloc)) {ierr = PetscSegBufferAlloc_Private(seg,count);CHKERRQ(ierr);} 103137cf7b6SJed Brown s = seg->head; 104137cf7b6SJed Brown *(char**)buf = &s->u.array[s->used*seg->unitbytes]; 1050f453b92SJed Brown s->used += count; 1060f453b92SJed Brown PetscFunctionReturn(0); 1070f453b92SJed Brown } 1080f453b92SJed Brown 1090f453b92SJed Brown #undef __FUNCT__ 1100f453b92SJed Brown #define __FUNCT__ "PetscSegBufferDestroy" 1110f453b92SJed Brown /*@C 1120f453b92SJed Brown PetscSegBufferDestroy - destroy segmented buffer 1130f453b92SJed Brown 1140f453b92SJed Brown Not Collective 1150f453b92SJed Brown 1160f453b92SJed Brown Input Arguments: 1170f453b92SJed Brown . seg - address of segmented buffer object 1180f453b92SJed Brown 1190f453b92SJed Brown Level: developer 1200f453b92SJed Brown 1210f453b92SJed Brown .seealso: PetscSegBufferCreate() 1220f453b92SJed Brown @*/ 1230f453b92SJed Brown PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) 1240f453b92SJed Brown { 1250f453b92SJed Brown PetscErrorCode ierr; 126137cf7b6SJed Brown struct _PetscSegBufferLink *s; 1270f453b92SJed Brown 1280f453b92SJed Brown PetscFunctionBegin; 129137cf7b6SJed Brown for (s=(*seg)->head; s;) { 130137cf7b6SJed Brown struct _PetscSegBufferLink *tail = s->tail; 1310f453b92SJed Brown ierr = PetscFree(s);CHKERRQ(ierr); 1320f453b92SJed Brown s = tail; 1330f453b92SJed Brown } 134137cf7b6SJed Brown ierr = PetscFree(*seg);CHKERRQ(ierr); 1350f453b92SJed Brown PetscFunctionReturn(0); 1360f453b92SJed Brown } 1370f453b92SJed Brown 1380f453b92SJed Brown #undef __FUNCT__ 13947452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractTo" 1400f453b92SJed Brown /*@C 14147452e7bSJed Brown PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 14247452e7bSJed Brown 14347452e7bSJed Brown Not Collective 14447452e7bSJed Brown 14547452e7bSJed Brown Input Argument: 14647452e7bSJed Brown + seg - segmented buffer 14747452e7bSJed Brown - contig - allocated buffer to hold contiguous data 14847452e7bSJed Brown 14947452e7bSJed Brown Level: developer 15047452e7bSJed Brown 15147452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 15247452e7bSJed Brown @*/ 153137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig) 15447452e7bSJed Brown { 15547452e7bSJed Brown PetscErrorCode ierr; 156*13e3f751SJed Brown size_t unitbytes; 157137cf7b6SJed Brown struct _PetscSegBufferLink *s,*t; 15847452e7bSJed Brown char *ptr; 15947452e7bSJed Brown 16047452e7bSJed Brown PetscFunctionBegin; 161137cf7b6SJed Brown unitbytes = seg->unitbytes; 162137cf7b6SJed Brown s = seg->head; 16347452e7bSJed Brown ptr = ((char*)contig) + s->tailused*unitbytes; 16447452e7bSJed Brown ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr); 16547452e7bSJed Brown for (t=s->tail; t;) { 166137cf7b6SJed Brown struct _PetscSegBufferLink *tail = t->tail; 16747452e7bSJed Brown ptr -= t->used*unitbytes; 16847452e7bSJed Brown ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr); 16947452e7bSJed Brown ierr = PetscFree(t);CHKERRQ(ierr); 17047452e7bSJed Brown t = tail; 17147452e7bSJed Brown } 17247452e7bSJed Brown if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 17347452e7bSJed Brown s->used = 0; 17447452e7bSJed Brown s->tailused = 0; 17547452e7bSJed Brown s->tail = NULL; 17647452e7bSJed Brown PetscFunctionReturn(0); 17747452e7bSJed Brown } 17847452e7bSJed Brown 17947452e7bSJed Brown #undef __FUNCT__ 18047452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractAlloc" 18147452e7bSJed Brown /*@C 18247452e7bSJed Brown PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 1830f453b92SJed Brown 1840f453b92SJed Brown Not Collective 1850f453b92SJed Brown 1860f453b92SJed Brown Input Argument: 1870f453b92SJed Brown . seg - segmented buffer 1880f453b92SJed Brown 1890f453b92SJed Brown Output Argument: 1900f453b92SJed Brown . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 1910f453b92SJed Brown 1920f453b92SJed Brown Level: developer 1930f453b92SJed Brown 19447452e7bSJed Brown Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 19547452e7bSJed Brown 19647452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 1970f453b92SJed Brown @*/ 198137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous) 1990f453b92SJed Brown { 2000f453b92SJed Brown PetscErrorCode ierr; 201137cf7b6SJed Brown struct _PetscSegBufferLink *s; 20247452e7bSJed Brown void *contig; 2030f453b92SJed Brown 2040f453b92SJed Brown PetscFunctionBegin; 205137cf7b6SJed Brown s = seg->head; 2060f453b92SJed Brown 207137cf7b6SJed Brown ierr = PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);CHKERRQ(ierr); 20847452e7bSJed Brown ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr); 20947452e7bSJed Brown *(void**)contiguous = contig; 21047452e7bSJed Brown PetscFunctionReturn(0); 2110f453b92SJed Brown } 21247452e7bSJed Brown 21347452e7bSJed Brown #undef __FUNCT__ 21447452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractInPlace" 21547452e7bSJed Brown /*@C 21647452e7bSJed Brown PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 21747452e7bSJed Brown 21801d09641SJed Brown Not Collective 21947452e7bSJed Brown 22047452e7bSJed Brown Input Arguments: 22147452e7bSJed Brown . seg - segmented buffer object 22247452e7bSJed Brown 22347452e7bSJed Brown Output Arguments: 22447452e7bSJed Brown . contig - address of pointer to contiguous memory 22547452e7bSJed Brown 22647452e7bSJed Brown Level: developer 22747452e7bSJed Brown 22847452e7bSJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 22947452e7bSJed Brown @*/ 230137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig) 23147452e7bSJed Brown { 23247452e7bSJed Brown PetscErrorCode ierr; 233137cf7b6SJed Brown struct _PetscSegBufferLink *head; 23447452e7bSJed Brown 23547452e7bSJed Brown PetscFunctionBegin; 236137cf7b6SJed Brown head = seg->head; 237137cf7b6SJed Brown if (PetscUnlikely(head->tail)) { 238137cf7b6SJed Brown PetscSegBuffer newseg; 23947452e7bSJed Brown 240137cf7b6SJed Brown ierr = PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);CHKERRQ(ierr); 241137cf7b6SJed Brown ierr = PetscSegBufferExtractTo(seg,newseg->head->u.array);CHKERRQ(ierr); 242137cf7b6SJed Brown seg->head = newseg->head; 243137cf7b6SJed Brown newseg->head = head; 244137cf7b6SJed Brown ierr = PetscSegBufferDestroy(&newseg);CHKERRQ(ierr); 245137cf7b6SJed Brown head = seg->head; 24647452e7bSJed Brown } 247137cf7b6SJed Brown *(char**)contig = head->u.array; 248137cf7b6SJed Brown head->used = 0; 2490f453b92SJed Brown PetscFunctionReturn(0); 2500f453b92SJed Brown } 25101d09641SJed Brown 25201d09641SJed Brown #undef __FUNCT__ 25301d09641SJed Brown #define __FUNCT__ "PetscSegBufferGetSize" 25401d09641SJed Brown /*@C 25501d09641SJed Brown PetscSegBufferGetSize - get currently used size of segmented buffer 25601d09641SJed Brown 25701d09641SJed Brown Not Collective 25801d09641SJed Brown 25901d09641SJed Brown Input Arguments: 26001d09641SJed Brown . seg - segmented buffer object 26101d09641SJed Brown 26201d09641SJed Brown Output Arguments: 26301d09641SJed Brown . usedsize - number of used units 26401d09641SJed Brown 26501d09641SJed Brown Level: developer 26601d09641SJed Brown 26701d09641SJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet() 26801d09641SJed Brown @*/ 269*13e3f751SJed Brown PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize) 27001d09641SJed Brown { 27101d09641SJed Brown 27201d09641SJed Brown PetscFunctionBegin; 273137cf7b6SJed Brown *usedsize = seg->head->tailused + seg->head->used; 27401d09641SJed Brown PetscFunctionReturn(0); 27501d09641SJed Brown } 27601d09641SJed Brown 27701d09641SJed Brown #undef __FUNCT__ 27801d09641SJed Brown #define __FUNCT__ "PetscSegBufferUnuse" 27901d09641SJed Brown /*@C 28001d09641SJed Brown PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 28101d09641SJed Brown 28201d09641SJed Brown Not Collective 28301d09641SJed Brown 28401d09641SJed Brown Input Arguments: 28501d09641SJed Brown + seg - segmented buffer object 28601d09641SJed Brown - unused - number of unused units 28701d09641SJed Brown 28801d09641SJed Brown Level: developer 28901d09641SJed Brown 29001d09641SJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet() 29101d09641SJed Brown @*/ 292*13e3f751SJed Brown PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused) 29301d09641SJed Brown { 294137cf7b6SJed Brown struct _PetscSegBufferLink *head; 29501d09641SJed Brown 29601d09641SJed Brown PetscFunctionBegin; 297137cf7b6SJed Brown head = seg->head; 298137cf7b6SJed Brown 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); 299137cf7b6SJed Brown head->used -= unused; 30001d09641SJed Brown PetscFunctionReturn(0); 30101d09641SJed Brown } 302