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