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 9 { /* Dummy types to ensure alignment */ 10 PetscReal dummy_real; 11 PetscInt dummy_int; 12 char array[1]; /* This array is over-allocated for the size of the link */ 13 } u; 14 }; 15 16 /* Segmented (extendable) array implementation */ 17 struct _n_PetscSegBuffer { 18 struct _PetscSegBufferLink *head; 19 size_t unitbytes; 20 }; 21 22 static PetscErrorCode PetscSegBufferAlloc_Private(PetscSegBuffer seg, size_t count) 23 { 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 PetscCall(PetscMalloc(offsetof(struct _PetscSegBufferLink, u) + alloc * seg->unitbytes, &newlink)); 32 PetscCall(PetscMemzero(newlink, offsetof(struct _PetscSegBufferLink, u))); 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 a 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 struct _PetscSegBufferLink *head; 60 61 PetscFunctionBegin; 62 PetscCall(PetscNew(seg)); 63 PetscCall(PetscMalloc(offsetof(struct _PetscSegBufferLink, u) + expected * unitbytes, &head)); 64 PetscCall(PetscMemzero(head, offsetof(struct _PetscSegBufferLink, u))); 65 66 head->alloc = expected; 67 (*seg)->unitbytes = unitbytes; 68 (*seg)->head = head; 69 PetscFunctionReturn(0); 70 } 71 72 /*@C 73 PetscSegBufferGet - get new buffer space from a segmented buffer 74 75 Not Collective 76 77 Input Parameters: 78 + seg - address of segmented buffer 79 - count - number of entries needed 80 81 Output Parameter: 82 . buf - address of new buffer for contiguous data 83 84 Level: developer 85 86 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()`, `PetscSegBufferDestroy()` 87 @*/ 88 PetscErrorCode PetscSegBufferGet(PetscSegBuffer seg, size_t count, void *buf) 89 { 90 struct _PetscSegBufferLink *s; 91 92 PetscFunctionBegin; 93 s = seg->head; 94 if (PetscUnlikely(s->used + count > s->alloc)) PetscCall(PetscSegBufferAlloc_Private(seg, count)); 95 s = seg->head; 96 *(char **)buf = &s->u.array[s->used * seg->unitbytes]; 97 s->used += count; 98 PetscFunctionReturn(0); 99 } 100 101 /*@C 102 PetscSegBufferDestroy - destroy segmented buffer 103 104 Not Collective 105 106 Input Parameter: 107 . seg - address of segmented buffer object 108 109 Level: developer 110 111 .seealso: `PetscSegBufferCreate()` 112 @*/ 113 PetscErrorCode PetscSegBufferDestroy(PetscSegBuffer *seg) 114 { 115 struct _PetscSegBufferLink *s; 116 117 PetscFunctionBegin; 118 if (!*seg) PetscFunctionReturn(0); 119 for (s = (*seg)->head; s;) { 120 struct _PetscSegBufferLink *tail = s->tail; 121 PetscCall(PetscFree(s)); 122 s = tail; 123 } 124 PetscCall(PetscFree(*seg)); 125 PetscFunctionReturn(0); 126 } 127 128 /*@C 129 PetscSegBufferExtractTo - extract contiguous data to provided buffer and reset segmented buffer 130 131 Not Collective 132 133 Input Parameters: 134 + seg - segmented buffer 135 - contig - allocated buffer to hold contiguous data 136 137 Level: developer 138 139 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractInPlace()` 140 @*/ 141 PetscErrorCode PetscSegBufferExtractTo(PetscSegBuffer seg, void *contig) 142 { 143 size_t unitbytes; 144 struct _PetscSegBufferLink *s, *t; 145 char *ptr; 146 147 PetscFunctionBegin; 148 unitbytes = seg->unitbytes; 149 s = seg->head; 150 ptr = ((char *)contig) + s->tailused * unitbytes; 151 PetscCall(PetscMemcpy(ptr, s->u.array, s->used * unitbytes)); 152 for (t = s->tail; t;) { 153 struct _PetscSegBufferLink *tail = t->tail; 154 ptr -= t->used * unitbytes; 155 PetscCall(PetscMemcpy(ptr, t->u.array, t->used * unitbytes)); 156 PetscCall(PetscFree(t)); 157 t = tail; 158 } 159 PetscCheck(ptr == contig, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Tail count does not match"); 160 s->used = 0; 161 s->tailused = 0; 162 s->tail = NULL; 163 PetscFunctionReturn(0); 164 } 165 166 /*@C 167 PetscSegBufferExtractAlloc - extract contiguous data to new allocation and reset segmented buffer 168 169 Not Collective 170 171 Input Parameter: 172 . seg - segmented buffer 173 174 Output Parameter: 175 . contiguous - address of new array containing contiguous data, caller frees with `PetscFree()` 176 177 Level: developer 178 179 Developer Note: 180 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 181 182 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()` 183 @*/ 184 PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg, void *contiguous) 185 { 186 struct _PetscSegBufferLink *s; 187 void *contig; 188 189 PetscFunctionBegin; 190 s = seg->head; 191 192 PetscCall(PetscMalloc((s->used + s->tailused) * seg->unitbytes, &contig)); 193 PetscCall(PetscSegBufferExtractTo(seg, contig)); 194 *(void **)contiguous = contig; 195 PetscFunctionReturn(0); 196 } 197 198 /*@C 199 PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 200 201 Not Collective 202 203 Input Parameter: 204 . seg - segmented buffer object 205 206 Output Parameter: 207 . contig - address of pointer to contiguous memory, may be NULL 208 209 Level: developer 210 211 .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()` 212 @*/ 213 PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg, void *contig) 214 { 215 struct _PetscSegBufferLink *head; 216 217 PetscFunctionBegin; 218 head = seg->head; 219 if (PetscUnlikely(head->tail)) { 220 PetscSegBuffer newseg; 221 222 PetscCall(PetscSegBufferCreate(seg->unitbytes, head->used + head->tailused, &newseg)); 223 PetscCall(PetscSegBufferExtractTo(seg, newseg->head->u.array)); 224 seg->head = newseg->head; 225 newseg->head = head; 226 PetscCall(PetscSegBufferDestroy(&newseg)); 227 head = seg->head; 228 } 229 if (contig) *(char **)contig = head->u.array; 230 head->used = 0; 231 PetscFunctionReturn(0); 232 } 233 234 /*@C 235 PetscSegBufferGetSize - get currently used size of segmented buffer 236 237 Not Collective 238 239 Input Parameter: 240 . seg - segmented buffer object 241 242 Output Parameter: 243 . usedsize - number of used units 244 245 Level: developer 246 247 .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferCreate()`, `PetscSegBufferGet()` 248 @*/ 249 PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg, size_t *usedsize) 250 { 251 PetscFunctionBegin; 252 *usedsize = seg->head->tailused + seg->head->used; 253 PetscFunctionReturn(0); 254 } 255 256 /*@C 257 PetscSegBufferUnuse - return some unused entries obtained with an overzealous `PetscSegBufferGet()` 258 259 Not Collective 260 261 Input Parameters: 262 + seg - segmented buffer object 263 - unused - number of unused units 264 265 Level: developer 266 267 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()` 268 @*/ 269 PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg, size_t unused) 270 { 271 struct _PetscSegBufferLink *head; 272 273 PetscFunctionBegin; 274 head = seg->head; 275 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); 276 head->used -= unused; 277 PetscFunctionReturn(0); 278 } 279