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