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