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