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 if (!*seg) PetscFunctionReturn(0); 130 for (s=(*seg)->head; s;) { 131 struct _PetscSegBufferLink *tail = s->tail; 132 ierr = PetscFree(s);CHKERRQ(ierr); 133 s = tail; 134 } 135 ierr = PetscFree(*seg);CHKERRQ(ierr); 136 PetscFunctionReturn(0); 137 } 138 139 #undef __FUNCT__ 140 #define __FUNCT__ "PetscSegBufferExtractTo" 141 /*@C 142 PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 143 144 Not Collective 145 146 Input Argument: 147 + seg - segmented buffer 148 - contig - allocated buffer to hold contiguous data 149 150 Level: developer 151 152 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractAlloc(), PetscSegBufferExtractInPlace() 153 @*/ 154 PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg,void *contig) 155 { 156 PetscErrorCode ierr; 157 size_t unitbytes; 158 struct _PetscSegBufferLink *s,*t; 159 char *ptr; 160 161 PetscFunctionBegin; 162 unitbytes = seg->unitbytes; 163 s = seg->head; 164 ptr = ((char*)contig) + s->tailused*unitbytes; 165 ierr = PetscMemcpy(ptr,s->u.array,s->used*unitbytes);CHKERRQ(ierr); 166 for (t=s->tail; t;) { 167 struct _PetscSegBufferLink *tail = t->tail; 168 ptr -= t->used*unitbytes; 169 ierr = PetscMemcpy(ptr,t->u.array,t->used*unitbytes);CHKERRQ(ierr); 170 ierr = PetscFree(t);CHKERRQ(ierr); 171 t = tail; 172 } 173 if (ptr != contig) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_PLIB,"Tail count does not match"); 174 s->used = 0; 175 s->tailused = 0; 176 s->tail = NULL; 177 PetscFunctionReturn(0); 178 } 179 180 #undef __FUNCT__ 181 #define __FUNCT__ "PetscSegBufferExtractAlloc" 182 /*@C 183 PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 184 185 Not Collective 186 187 Input Argument: 188 . seg - segmented buffer 189 190 Output Argument: 191 . contiguous - address of new array containing contiguous data, caller frees with PetscFree() 192 193 Level: developer 194 195 Developer Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 196 197 .seealso: PetscSegBufferCreate(), PetscSegBufferGet(), PetscSegBufferDestroy(), PetscSegBufferExtractTo(), PetscSegBufferExtractInPlace() 198 @*/ 199 PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg,void *contiguous) 200 { 201 PetscErrorCode ierr; 202 struct _PetscSegBufferLink *s; 203 void *contig; 204 205 PetscFunctionBegin; 206 s = seg->head; 207 208 ierr = PetscMalloc((s->used+s->tailused)*seg->unitbytes,&contig);CHKERRQ(ierr); 209 ierr = PetscSegBufferExtractTo(seg,contig);CHKERRQ(ierr); 210 *(void**)contiguous = contig; 211 PetscFunctionReturn(0); 212 } 213 214 #undef __FUNCT__ 215 #define __FUNCT__ "PetscSegBufferExtractInPlace" 216 /*@C 217 PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 218 219 Not Collective 220 221 Input Arguments: 222 . seg - segmented buffer object 223 224 Output Arguments: 225 . contig - address of pointer to contiguous memory 226 227 Level: developer 228 229 .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo() 230 @*/ 231 PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg,void *contig) 232 { 233 PetscErrorCode ierr; 234 struct _PetscSegBufferLink *head; 235 236 PetscFunctionBegin; 237 head = seg->head; 238 if (PetscUnlikely(head->tail)) { 239 PetscSegBuffer newseg; 240 241 ierr = PetscSegBufferCreate(seg->unitbytes,head->used+head->tailused,&newseg);CHKERRQ(ierr); 242 ierr = PetscSegBufferExtractTo(seg,newseg->head->u.array);CHKERRQ(ierr); 243 seg->head = newseg->head; 244 newseg->head = head; 245 ierr = PetscSegBufferDestroy(&newseg);CHKERRQ(ierr); 246 head = seg->head; 247 } 248 *(char**)contig = head->u.array; 249 head->used = 0; 250 PetscFunctionReturn(0); 251 } 252 253 #undef __FUNCT__ 254 #define __FUNCT__ "PetscSegBufferGetSize" 255 /*@C 256 PetscSegBufferGetSize - get currently used size of segmented buffer 257 258 Not Collective 259 260 Input Arguments: 261 . seg - segmented buffer object 262 263 Output Arguments: 264 . usedsize - number of used units 265 266 Level: developer 267 268 .seealso: PetscSegBufferExtractAlloc(), PetscSegBufferExtractTo(), PetscSegBufferCreate(), PetscSegBufferGet() 269 @*/ 270 PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg,size_t *usedsize) 271 { 272 273 PetscFunctionBegin; 274 *usedsize = seg->head->tailused + seg->head->used; 275 PetscFunctionReturn(0); 276 } 277 278 #undef __FUNCT__ 279 #define __FUNCT__ "PetscSegBufferUnuse" 280 /*@C 281 PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 282 283 Not Collective 284 285 Input Arguments: 286 + seg - segmented buffer object 287 - unused - number of unused units 288 289 Level: developer 290 291 .seealso: PetscSegBufferCreate(), PetscSegBufferGet() 292 @*/ 293 PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg,size_t unused) 294 { 295 struct _PetscSegBufferLink *head; 296 297 PetscFunctionBegin; 298 head = seg->head; 299 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); 300 head->used -= unused; 301 PetscFunctionReturn(0); 302 } 303