1 #include <petscsys.h> 2 3 /* Segmented (extendable) array implementation */ 4 struct _n_PetscSegBuffer { 5 PetscInt unitbytes; 6 PetscInt alloc; 7 PetscInt used; 8 PetscInt tailused; 9 PetscSegBuffer tail; 10 union { /* Dummy types to ensure alignment */ 11 PetscReal dummy_real; 12 PetscInt dummy_int; 13 char array[1]; 14 } u; 15 }; 16 17 #undef __FUNCT__ 18 #define __FUNCT__ "PetscSegBufferAlloc_Private" 19 static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer *seg,PetscInt count) 20 { 21 PetscErrorCode ierr; 22 PetscSegBuffer newseg,s; 23 PetscInt alloc; 24 25 PetscFunctionBegin; 26 s = *seg; 27 /* Grow at least fast enough to hold next item, like Fibonacci otherwise (up to 1MB chunks) */ 28 alloc = PetscMax(s->used+count,PetscMin(1000000/s->unitbytes+1,s->alloc+s->tailused)); 29 ierr = PetscMalloc(offsetof(struct _n_PetscSegBuffer,u)+alloc*s->unitbytes,&newseg);CHKERRQ(ierr); 30 ierr = PetscMemzero(newseg,offsetof(struct _n_PetscSegBuffer,u));CHKERRQ(ierr); 31 32 newseg->unitbytes = s->unitbytes; 33 newseg->tailused = s->used + s->tailused; 34 newseg->tail = s; 35 newseg->alloc = alloc; 36 *seg = newseg; 37 PetscFunctionReturn(0); 38 } 39 40 #undef __FUNCT__ 41 #define __FUNCT__ "PetscSegBufferCreate" 42 /*@C 43 PetscSegBufferCreate - create segmented buffer 44 45 Not Collective 46 47 Input Arguments: 48 + unitbytes - number of bytes that each entry will contain 49 - expected - expected/typical number of entries 50 51 Output Argument: 52 . seg - segmented buffer object 53 54 Level: developer 55 56 .seealso: PetscSegBufferGet(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 57 @*/ 58 PetscErrorCode PetscSegBufferCreate(PetscInt unitbytes,PetscInt expected,PetscSegBuffer *seg) 59 { 60 PetscErrorCode ierr; 61 62 PetscFunctionBegin; 63 ierr = PetscMalloc(offsetof(struct _n_PetscSegBuffer,u)+expected*unitbytes,seg);CHKERRQ(ierr); 64 ierr = PetscMemzero(*seg,offsetof(struct _n_PetscSegBuffer,u));CHKERRQ(ierr); 65 66 (*seg)->unitbytes = unitbytes; 67 (*seg)->alloc = expected; 68 PetscFunctionReturn(0); 69 } 70 71 #undef __FUNCT__ 72 #define __FUNCT__ "PetscSegBufferGet" 73 /*@C 74 PetscSegBufferGet - get new buffer space from a segmented buffer 75 76 Not Collective 77 78 Input Arguments: 79 + seg - address of segmented buffer 80 - count - number of entries needed 81 82 Output Argument: 83 . buf - address of new buffer for contiguous data 84 85 Level: developer 86 87 .seealso: PetscSegBufferCreate(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace(), PetscSegBufferDestroy() 88 @*/ 89 PetscErrorCode PetscSegBufferGet(PetscSegBuffer *seg,PetscInt count,void *buf) 90 { 91 PetscErrorCode ierr; 92 PetscSegBuffer s; 93 94 PetscFunctionBegin; 95 s = *seg; 96 if (PetscUnlikely(s->used + count > s->alloc)) {ierr = PetscSegBufferAlloc_Private(seg,count);CHKERRQ(ierr);} 97 s = *seg; 98 *(char**)buf = &s->u.array[s->used*s->unitbytes]; 99 s->used += count; 100 PetscFunctionReturn(0); 101 } 102 103 #undef __FUNCT__ 104 #define __FUNCT__ "PetscSegBufferDestroy" 105 /*@C 106 PetscSegBufferDestroy - destroy segmented buffer 107 108 Not Collective 109 110 Input Arguments: 111 . seg - address of segmented buffer object 112 113 Level: developer 114 115 .seealso: PetscSegBufferCreate() 116 @*/ 117 PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) 118 { 119 PetscErrorCode ierr; 120 PetscSegBuffer s; 121 122 PetscFunctionBegin; 123 for (s=*seg; s;) { 124 PetscSegBuffer tail = s->tail; 125 ierr = PetscFree(s);CHKERRQ(ierr); 126 s = tail; 127 } 128 *seg = NULL; 129 PetscFunctionReturn(0); 130 } 131 132 #undef __FUNCT__ 133 #define __FUNCT__ "PetscSegBufferExtractTo" 134 /*@C 135 PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 136 137 Not Collective 138 139 Input Argument: 140 + seg - segmented buffer 141 - contig - allocated buffer to hold contiguous data 142 143 Level: developer 144 145 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 146 @*/ 147 PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer *seg,void *contig) 148 { 149 PetscErrorCode ierr; 150 PetscInt unitbytes; 151 PetscSegBuffer s,t; 152 char *ptr; 153 154 PetscFunctionBegin; 155 s = *seg; 156 157 unitbytes = s->unitbytes; 158 159 ptr = ((char*)contig) + s->tailused*unitbytes; 160 ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr); 161 for (t=s->tail; t;) { 162 PetscSegBuffer tail = t->tail; 163 ptr -= t->used*unitbytes; 164 ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr); 165 ierr = PetscFree(t);CHKERRQ(ierr); 166 t = tail; 167 } 168 if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 169 s->used = 0; 170 s->tailused = 0; 171 s->tail = NULL; 172 PetscFunctionReturn(0); 173 } 174 175 #undef __FUNCT__ 176 #define __FUNCT__ "PetscSegBufferExtractAlloc" 177 /*@C 178 PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 179 180 Not Collective 181 182 Input Argument: 183 . seg - segmented buffer 184 185 Output Argument: 186 . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 187 188 Level: developer 189 190 Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 191 192 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 193 @*/ 194 PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer *seg,void *contiguous) 195 { 196 PetscErrorCode ierr; 197 PetscSegBuffer s; 198 void *contig; 199 200 PetscFunctionBegin; 201 s = *seg; 202 203 ierr = PetscMalloc((s->used+s->tailused)*s->unitbytes,&contig);CHKERRQ(ierr); 204 ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr); 205 *(void**)contiguous = contig; 206 PetscFunctionReturn(0); 207 } 208 209 #undef __FUNCT__ 210 #define __FUNCT__ "PetscSegBufferExtractInPlace" 211 /*@C 212 PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 213 214 Collective 215 216 Input Arguments: 217 . seg - segmented buffer object 218 219 Output Arguments: 220 . contig - address of pointer to contiguous memory 221 222 Level: developer 223 224 .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 225 @*/ 226 PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer *seg,void *contig) 227 { 228 PetscErrorCode ierr; 229 230 PetscFunctionBegin; 231 if (!(*seg)->tail) { 232 *(char**)contig = (*seg)->u.array; 233 } else { 234 PetscSegBuffer s = *seg,newseg; 235 236 ierr = PetscSegBufferCreate(s->unitbytes,s->used+s->tailused,&newseg);CHKERRQ(ierr); 237 ierr = PetscSegBufferExtractTo(seg,newseg->u.array);CHKERRQ(ierr); 238 ierr = PetscSegBufferDestroy(seg);CHKERRQ(ierr); 239 *seg = newseg; 240 *(void**)contig = newseg->u.array; 241 } 242 PetscFunctionReturn(0); 243 } 244