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 210f453b92SJed Brown #undef __FUNCT__ 220f453b92SJed Brown #define __FUNCT__ "PetscSegBufferAlloc_Private" 2313e3f751SJed Brown static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg,size_t count) 240f453b92SJed Brown { 250f453b92SJed Brown PetscErrorCode ierr; 2613e3f751SJed 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 @*/ 6113e3f751SJed 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; 67*95dccacaSBarry Smith ierr = PetscNew(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 @*/ 9513e3f751SJed 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; 1295d7c30b2SJed Brown if (!*seg) PetscFunctionReturn(0); 130137cf7b6SJed Brown for (s=(*seg)->head; s;) { 131137cf7b6SJed Brown struct _PetscSegBufferLink *tail = s->tail; 1320f453b92SJed Brown ierr = PetscFree(s);CHKERRQ(ierr); 1330f453b92SJed Brown s = tail; 1340f453b92SJed Brown } 135137cf7b6SJed Brown ierr = PetscFree(*seg);CHKERRQ(ierr); 1360f453b92SJed Brown PetscFunctionReturn(0); 1370f453b92SJed Brown } 1380f453b92SJed Brown 1390f453b92SJed Brown #undef __FUNCT__ 14047452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractTo" 1410f453b92SJed Brown /*@C 14247452e7bSJed Brown PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 14347452e7bSJed Brown 14447452e7bSJed Brown Not Collective 14547452e7bSJed Brown 14647452e7bSJed Brown Input Argument: 14747452e7bSJed Brown + seg - segmented buffer 14847452e7bSJed Brown - contig - allocated buffer to hold contiguous data 14947452e7bSJed Brown 15047452e7bSJed Brown Level: developer 15147452e7bSJed Brown 15247452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 15347452e7bSJed Brown @*/ 154137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig) 15547452e7bSJed Brown { 15647452e7bSJed Brown PetscErrorCode ierr; 15713e3f751SJed Brown size_t unitbytes; 158137cf7b6SJed Brown struct _PetscSegBufferLink *s,*t; 15947452e7bSJed Brown char *ptr; 16047452e7bSJed Brown 16147452e7bSJed Brown PetscFunctionBegin; 162137cf7b6SJed Brown unitbytes = seg->unitbytes; 163137cf7b6SJed Brown s = seg->head; 16447452e7bSJed Brown ptr = ((char*)contig) + s->tailused*unitbytes; 16547452e7bSJed Brown ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr); 16647452e7bSJed Brown for (t=s->tail; t;) { 167137cf7b6SJed Brown struct _PetscSegBufferLink *tail = t->tail; 16847452e7bSJed Brown ptr -= t->used*unitbytes; 16947452e7bSJed Brown ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr); 17047452e7bSJed Brown ierr = PetscFree(t);CHKERRQ(ierr); 17147452e7bSJed Brown t = tail; 17247452e7bSJed Brown } 17347452e7bSJed Brown if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 17447452e7bSJed Brown s->used = 0; 17547452e7bSJed Brown s->tailused = 0; 17647452e7bSJed Brown s->tail = NULL; 17747452e7bSJed Brown PetscFunctionReturn(0); 17847452e7bSJed Brown } 17947452e7bSJed Brown 18047452e7bSJed Brown #undef __FUNCT__ 18147452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractAlloc" 18247452e7bSJed Brown /*@C 18347452e7bSJed Brown PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 1840f453b92SJed Brown 1850f453b92SJed Brown Not Collective 1860f453b92SJed Brown 1870f453b92SJed Brown Input Argument: 1880f453b92SJed Brown . seg - segmented buffer 1890f453b92SJed Brown 1900f453b92SJed Brown Output Argument: 1910f453b92SJed Brown . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 1920f453b92SJed Brown 1930f453b92SJed Brown Level: developer 1940f453b92SJed Brown 19547452e7bSJed Brown Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 19647452e7bSJed Brown 19747452e7bSJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 1980f453b92SJed Brown @*/ 199137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous) 2000f453b92SJed Brown { 2010f453b92SJed Brown PetscErrorCode ierr; 202137cf7b6SJed Brown struct _PetscSegBufferLink *s; 20347452e7bSJed Brown void *contig; 2040f453b92SJed Brown 2050f453b92SJed Brown PetscFunctionBegin; 206137cf7b6SJed Brown s = seg->head; 2070f453b92SJed Brown 208137cf7b6SJed Brown ierr = PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);CHKERRQ(ierr); 20947452e7bSJed Brown ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr); 21047452e7bSJed Brown *(void**)contiguous = contig; 21147452e7bSJed Brown PetscFunctionReturn(0); 2120f453b92SJed Brown } 21347452e7bSJed Brown 21447452e7bSJed Brown #undef __FUNCT__ 21547452e7bSJed Brown #define __FUNCT__ "PetscSegBufferExtractInPlace" 21647452e7bSJed Brown /*@C 21747452e7bSJed Brown PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 21847452e7bSJed Brown 21901d09641SJed Brown Not Collective 22047452e7bSJed Brown 22147452e7bSJed Brown Input Arguments: 22247452e7bSJed Brown . seg - segmented buffer object 22347452e7bSJed Brown 22447452e7bSJed Brown Output Arguments: 22547452e7bSJed Brown . contig - address of pointer to contiguous memory 22647452e7bSJed Brown 22747452e7bSJed Brown Level: developer 22847452e7bSJed Brown 22947452e7bSJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 23047452e7bSJed Brown @*/ 231137cf7b6SJed Brown PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig) 23247452e7bSJed Brown { 23347452e7bSJed Brown PetscErrorCode ierr; 234137cf7b6SJed Brown struct _PetscSegBufferLink *head; 23547452e7bSJed Brown 23647452e7bSJed Brown PetscFunctionBegin; 237137cf7b6SJed Brown head = seg->head; 238137cf7b6SJed Brown if (PetscUnlikely(head->tail)) { 239137cf7b6SJed Brown PetscSegBuffer newseg; 24047452e7bSJed Brown 241137cf7b6SJed Brown ierr = PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);CHKERRQ(ierr); 242137cf7b6SJed Brown ierr = PetscSegBufferExtractTo(seg,newseg->head->u.array);CHKERRQ(ierr); 243137cf7b6SJed Brown seg->head = newseg->head; 244137cf7b6SJed Brown newseg->head = head; 245137cf7b6SJed Brown ierr = PetscSegBufferDestroy(&newseg);CHKERRQ(ierr); 246137cf7b6SJed Brown head = seg->head; 24747452e7bSJed Brown } 248137cf7b6SJed Brown *(char**)contig = head->u.array; 249137cf7b6SJed Brown head->used = 0; 2500f453b92SJed Brown PetscFunctionReturn(0); 2510f453b92SJed Brown } 25201d09641SJed Brown 25301d09641SJed Brown #undef __FUNCT__ 25401d09641SJed Brown #define __FUNCT__ "PetscSegBufferGetSize" 25501d09641SJed Brown /*@C 25601d09641SJed Brown PetscSegBufferGetSize - get currently used size of segmented buffer 25701d09641SJed Brown 25801d09641SJed Brown Not Collective 25901d09641SJed Brown 26001d09641SJed Brown Input Arguments: 26101d09641SJed Brown . seg - segmented buffer object 26201d09641SJed Brown 26301d09641SJed Brown Output Arguments: 26401d09641SJed Brown . usedsize - number of used units 26501d09641SJed Brown 26601d09641SJed Brown Level: developer 26701d09641SJed Brown 26801d09641SJed Brown .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet() 26901d09641SJed Brown @*/ 27013e3f751SJed Brown PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize) 27101d09641SJed Brown { 27201d09641SJed Brown 27301d09641SJed Brown PetscFunctionBegin; 274137cf7b6SJed Brown *usedsize = seg->head->tailused + seg->head->used; 27501d09641SJed Brown PetscFunctionReturn(0); 27601d09641SJed Brown } 27701d09641SJed Brown 27801d09641SJed Brown #undef __FUNCT__ 27901d09641SJed Brown #define __FUNCT__ "PetscSegBufferUnuse" 28001d09641SJed Brown /*@C 28101d09641SJed Brown PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 28201d09641SJed Brown 28301d09641SJed Brown Not Collective 28401d09641SJed Brown 28501d09641SJed Brown Input Arguments: 28601d09641SJed Brown + seg - segmented buffer object 28701d09641SJed Brown - unused - number of unused units 28801d09641SJed Brown 28901d09641SJed Brown Level: developer 29001d09641SJed Brown 29101d09641SJed Brown .seealso: PetscSegBufferCreate(), PetscSegBufferGet() 29201d09641SJed Brown @*/ 29313e3f751SJed Brown PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused) 29401d09641SJed Brown { 295137cf7b6SJed Brown struct _PetscSegBufferLink *head; 29601d09641SJed Brown 29701d09641SJed Brown PetscFunctionBegin; 298137cf7b6SJed Brown head = seg->head; 299137cf7b6SJed 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); 300137cf7b6SJed Brown head->used -= unused; 30101d09641SJed Brown PetscFunctionReturn(0); 30201d09641SJed Brown } 303