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 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 Notes: 'seg' argument is a pointer so that implementation could reallocate, though this is not currently done 175 176 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()`, `PetscSegBufferDestroy()`, `PetscSegBufferExtractTo()`, `PetscSegBufferExtractInPlace()` 177 @*/ 178 PetscErrorCode PetscSegBufferExtractAlloc(PetscSegBuffer seg, void *contiguous) { 179 struct _PetscSegBufferLink *s; 180 void *contig; 181 182 PetscFunctionBegin; 183 s = seg->head; 184 185 PetscCall(PetscMalloc((s->used + s->tailused) * seg->unitbytes, &contig)); 186 PetscCall(PetscSegBufferExtractTo(seg, contig)); 187 *(void **)contiguous = contig; 188 PetscFunctionReturn(0); 189 } 190 191 /*@C 192 PetscSegBufferExtractInPlace - extract in-place contiguous representation of data and reset segmented buffer for reuse 193 194 Not Collective 195 196 Input Parameter: 197 . seg - segmented buffer object 198 199 Output Parameter: 200 . contig - address of pointer to contiguous memory, may be NULL 201 202 Level: developer 203 204 .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()` 205 @*/ 206 PetscErrorCode PetscSegBufferExtractInPlace(PetscSegBuffer seg, void *contig) { 207 struct _PetscSegBufferLink *head; 208 209 PetscFunctionBegin; 210 head = seg->head; 211 if (PetscUnlikely(head->tail)) { 212 PetscSegBuffer newseg; 213 214 PetscCall(PetscSegBufferCreate(seg->unitbytes, head->used + head->tailused, &newseg)); 215 PetscCall(PetscSegBufferExtractTo(seg, newseg->head->u.array)); 216 seg->head = newseg->head; 217 newseg->head = head; 218 PetscCall(PetscSegBufferDestroy(&newseg)); 219 head = seg->head; 220 } 221 if (contig) *(char **)contig = head->u.array; 222 head->used = 0; 223 PetscFunctionReturn(0); 224 } 225 226 /*@C 227 PetscSegBufferGetSize - get currently used size of segmented buffer 228 229 Not Collective 230 231 Input Parameter: 232 . seg - segmented buffer object 233 234 Output Parameter: 235 . usedsize - number of used units 236 237 Level: developer 238 239 .seealso: `PetscSegBufferExtractAlloc()`, `PetscSegBufferExtractTo()`, `PetscSegBufferCreate()`, `PetscSegBufferGet()` 240 @*/ 241 PetscErrorCode PetscSegBufferGetSize(PetscSegBuffer seg, size_t *usedsize) { 242 PetscFunctionBegin; 243 *usedsize = seg->head->tailused + seg->head->used; 244 PetscFunctionReturn(0); 245 } 246 247 /*@C 248 PetscSegBufferUnuse - return some unused entries obtained with an overzealous PetscSegBufferGet() 249 250 Not Collective 251 252 Input Parameters: 253 + seg - segmented buffer object 254 - unused - number of unused units 255 256 Level: developer 257 258 .seealso: `PetscSegBufferCreate()`, `PetscSegBufferGet()` 259 @*/ 260 PetscErrorCode PetscSegBufferUnuse(PetscSegBuffer seg, size_t unused) { 261 struct _PetscSegBufferLink *head; 262 263 PetscFunctionBegin; 264 head = seg->head; 265 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); 266 head->used -= unused; 267 PetscFunctionReturn(0); 268 } 269