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