Arraylist/array.h at main · code5717/Arraylist · GitHub

History

654 lines (552 loc) · 24.1 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

#pragma once

#include <stdbool.h>

#include <stddef.h>

#include <stdlib.h>

#include <string.h>

/* Optional debug mode.

* Define ARRAY_DEBUG to 1 before including this header (or via -DARRAY_DEBUG)

* to enable extra runtime assertions that catch misuse early during development.

* These checks are disabled by default for performance.

#ifndef ARRAY_DEBUG

#define ARRAY_DEBUG 0

#endif

#if ARRAY_DEBUG

#include <assert.h>

#define ARRAY_CHECK(cond) assert(cond)

#else

#define ARRAY_CHECK(cond) ((void)0)

#endif

* Arraylist

* ---------

* Header-only dynamic arrays, slices, and spans for C11/C17.

* Safety defaults (follow these to avoid most problems):

* - Prefer the checked APIs: array_try_push, array_reserve, array_try_*.

* - Always check the bool return value from mutating checked APIs.

* - array_reserve and array_try_push may update the Array(T) variable itself

* (they require a modifiable lvalue). Re-acquire pointers/Spans after growth.

* - Slice(T) stores indexes and survives realloc. Span(T) and raw pointers do not.

* - Use array_back_ptr for safe last-element access (returns NULL when empty).

* - array_push, array_at, array_end, slice_from_array_t, and span_make_t are

* unchecked compatibility APIs — only use them when preconditions are proven.

* - Define ARRAY_DEBUG=1 during development for extra runtime assertions.

* Ownership model:

* Array(T) is an owning pointer allocated by array_make and freed by

* array_free. Slice(T) is a non-owning range over an Array(T). Span(T) is

* an explicit temporary borrowed pointer view into current storage.

* Usage pattern:

* 1. Include this header.

* 2. Call generate_array_type(T) once before using Array(T), Slice(T), or Span(T).

* 3. Create arrays with array_make(T, capacity) — 8 is a good default.

* 4. Release owning arrays with array_free.

* Portability:

* The core API is strict C11/C17. Convenience macros that infer element

* types are enabled only when GNU/Clang typeof is available.

/* Public size type used for array counts and capacities. */

typedef size_t array_size_t;

/* Convenience macro for passing a properly typed NULL to checked APIs

* in strict C11 -pedantic mode (avoids dead-branch type errors with bare NULL).

* Preferred usage:

* array_try_get(array_null(int), 0, &val);

#define array_null(T) ((Array(T))0)

/* GNU/Clang typeof is convenient, but not part of strict ISO C. */

#if (defined(__GNUC__) || defined(__clang__)) && !defined(__STRICT_ANSI__)

#define ARRAY_HAS_TYPEOF 1

#else

#define ARRAY_HAS_TYPEOF 0

#endif

/* Token-pasting names used by generated concrete array/slice/span types. */

#define Slice(T) Slice_##T

#define Span(T) Span_##T

#define ArrayStruct(T) ArrayStruct_##T

#define Array(T) Array_##T

* Declare a range slice type for T.

* A Slice(T) stores offsets into an Array(T), not element pointers. It remains

* meaningful across reallocations of the backing array, as long as the current

* array still has enough elements for the range.

#define decl_slice(T) \

typedef struct \

{ \

array_size_t start; \

array_size_t count; \

} Slice(T)

* Declare a temporary raw pointer span type for T.

* A Span(T) is a borrowed pointer view. It must not be passed to array_free,

* and it becomes invalid when its backing storage is freed or reallocated.

#define decl_span(T) \

typedef struct \

{ \

array_size_t count; \

T *elements; \

} Span(T)

* Declare Array(T), ArrayStruct(T), Slice(T), and Span(T).

* The generated Array(T) is a pointer to a flexible-array-member struct:

* count and capacity live before the inline elements buffer. Generate the

* type before first use in a translation unit or public header.

#define generate_array_type(T) \

typedef struct \

{ \

array_size_t count; \

array_size_t capacity; \

T elements[]; \

} ArrayStruct(T); \

typedef ArrayStruct(T) *Array(T); \

decl_slice(T); \

decl_span(T)

/* Internal prefix shared by every generated ArrayStruct(T).

* We cast ArrayStruct(T)* to Array_Header* in the _impl functions to access

* count/capacity without knowing T. This relies on the common initial sequence

* of the two structs.

* In practice this has been safe and reliable across gcc/clang with LTO,

* UBSan, and strict aliasing warnings enabled. It is a deliberate trade-off

* for a small, header-only library.

* If you ever need to target extremely strict or unusual compilers, the

* internal implementation can be changed to use char* + memcpy for header access.

typedef struct

{

array_size_t count;

array_size_t capacity;

} Array_Header;

/* Internal layout helpers for generated flexible-array-member structs. */

#define array_header_bytes(arr) ((size_t)((char *)(arr)->elements - (char *)(arr)))

#define array_elem_size(arr) (sizeof((arr)->elements[0]))

/* Return true when a * b would overflow array_size_t; otherwise write *out. */

static inline bool array_size_mul_overflow(array_size_t a, array_size_t b, array_size_t *out)

{

if (a != 0 && b > (array_size_t)-1 / a)

{

return true;

}

*out = a * b;

return false;

}

/* Return true when a + b would overflow array_size_t; otherwise write *out. */

static inline bool array_size_add_overflow(array_size_t a, array_size_t b, array_size_t *out)

{

if (a > (array_size_t)-1 - b)

{

return true;

}

*out = a + b;

return false;

}

/* Locate the first element byte from an allocation block and header size. */

static inline char *array_elements_ptr(void *block, size_t header_bytes)

{

return (char *)block + header_bytes;

}

* Compute allocation size for a capacity.

* Returns false on size overflow. This keeps allocation and reallocation

* paths from silently wrapping byte counts.

static inline bool array_bytes_for_capacity(size_t header_bytes, size_t elem_size, array_size_t capacity,

size_t *out_bytes)

{

array_size_t elem_bytes = 0;

array_size_t total = 0;

if (array_size_mul_overflow(capacity, (array_size_t)elem_size, &elem_bytes))

{

return false;

}

if (array_size_add_overflow((array_size_t)header_bytes, elem_bytes, &total))

{

return false;

}

*out_bytes = (size_t)total;

return true;

}

* Growth policy used by array_reserve_impl.

* Capacity doubles until it reaches min_capacity. When doubling would overflow,

* it falls back to min_capacity so the later byte-size computation can perform

* the final overflow check in one place.

static inline array_size_t array_grow_capacity(array_size_t current, array_size_t min_capacity)

{

array_size_t new_capacity = current == 0 ? 1 : current;

while (new_capacity < min_capacity)

{

if (new_capacity > (array_size_t)-1 / 2)

{

return min_capacity;

}

new_capacity *= 2;

}

return new_capacity;

}

* Allocate a new array block with count == 0 and the requested capacity.

* Returns NULL on allocation failure or byte-size overflow.

static inline void *array_make_impl(size_t elem_size, size_t header_bytes, array_size_t capacity)

{

size_t total_bytes = 0;

void *block = NULL;

Array_Header *header = NULL;

if (!array_bytes_for_capacity(header_bytes, elem_size, capacity, &total_bytes))

{

return NULL;

}

block = malloc(total_bytes);

if (!block)

{

return NULL;

}

header = (Array_Header *)block;

header->count = 0;

header->capacity = capacity;

ARRAY_CHECK(header->count == 0);

ARRAY_CHECK(header->capacity == capacity);

return block;

}

* Ensure *block has at least min_capacity elements.

* On success, *block may change because realloc can move the allocation.

* On failure, the original allocation remains valid and *block is unchanged.

static inline bool array_reserve_impl(void **block, size_t elem_size, size_t header_bytes,

array_size_t min_capacity)

{

Array_Header *header = NULL;

array_size_t new_capacity = 0;

size_t total_bytes = 0;

void *new_block = NULL;

if (!block || !*block)

{

return false;

}

header = (Array_Header *)*block;

if (header->capacity >= min_capacity)

{

return true;

}

new_capacity = array_grow_capacity(header->capacity, min_capacity);

if (!array_bytes_for_capacity(header_bytes, elem_size, new_capacity, &total_bytes))

{

return false;

}

new_block = realloc(*block, total_bytes);

if (!new_block)

{

return false;

}

*block = new_block;

((Array_Header *)*block)->capacity = new_capacity;

ARRAY_CHECK(((Array_Header *)*block)->capacity >= min_capacity);

return true;

}

/* Return true when start/count name a valid half-open range in header. */

static inline bool array_slice_bounds_valid(const Array_Header *header, array_size_t start, array_size_t count)

{

array_size_t high = 0;

if (!header)

{

return false;

}

if (array_size_add_overflow(start, count, &high))

{

return false;

}

return high <= header->count;

}

* Build a checked range slice over [low, high).

* The output range is written only on success.

static inline bool array_try_slice_impl(void *block, array_size_t low, array_size_t high, array_size_t *out_start,

array_size_t *out_count)

{

Array_Header *header = NULL;

if (!block || !out_start || !out_count)

{

return false;

}

header = (Array_Header *)block;

if (low > high || high > header->count)

{

return false;

}

*out_start = low;

*out_count = high - low;

ARRAY_CHECK(*out_start + *out_count <= header->count);

return true;

}

* Materialize a temporary raw span from a valid range.

* The span's pointer is borrowed from block and is invalidated by free/realloc.

static inline bool array_try_span_impl(void *block, size_t elem_size, size_t header_bytes, array_size_t start,

array_size_t count, array_size_t *out_count, void **out_elements)

{

Array_Header *header = NULL;

char *base = NULL;

if (!block || !out_count || !out_elements)

{

return false;

}

header = (Array_Header *)block;

if (!array_slice_bounds_valid(header, start, count))

{

return false;

}

base = array_elements_ptr(block, header_bytes);

*out_count = count;

*out_elements = base + (start * elem_size);

return true;

}

/* Checked element access with an untyped output slot for macro NULL support. */

static inline bool array_try_at_impl(void *block, size_t elem_size, size_t header_bytes, array_size_t idx,

void **out_ptr)

{

Array_Header *header = NULL;

char *base = NULL;

if (!block || !out_ptr)

{

return false;

}

header = (Array_Header *)block;

if (idx >= header->count)

{

return false;

}

base = array_elements_ptr(block, header_bytes);

*out_ptr = base + (idx * elem_size);

return true;

}

/* Write a Slice(T)-layout struct without requiring the macro to dereference it. */

static inline bool array_try_slice_into_impl(void *block, array_size_t low, array_size_t high,

size_t start_offset, size_t count_offset, void *out_slice)

{

array_size_t start = 0;

array_size_t count = 0;

if (!out_slice || !array_try_slice_impl(block, low, high, &start, &count))

{

return false;

}

memcpy((char *)out_slice + start_offset, &start, sizeof(start));

memcpy((char *)out_slice + count_offset, &count, sizeof(count));

return true;

}

/* Checked range-relative element access with an untyped output slot. */

static inline bool array_try_slice_at_impl(void *block, size_t elem_size, size_t header_bytes, array_size_t start,

array_size_t count, array_size_t idx, void **out_ptr)

{

char *base = NULL;

if (!block || !out_ptr || idx >= count ||

!array_slice_bounds_valid((const Array_Header *)block, start, count))

{

return false;

}

base = array_elements_ptr(block, header_bytes);

*out_ptr = base + ((start + idx) * elem_size);

return true;

}

/* Write a Span(T)-layout struct without requiring the macro to dereference it. */

static inline bool array_try_span_into_impl(void *block, size_t elem_size, size_t header_bytes, array_size_t start,

array_size_t count, size_t count_offset, size_t elements_offset,

void *out_span)

{

void *elements = NULL;

if (!out_span || !array_try_span_impl(block, elem_size, header_bytes, start, count, &count, &elements))

{

return false;

}

memcpy((char *)out_span + count_offset, &count, sizeof(count));

memcpy((char *)out_span + elements_offset, &elements, sizeof(elements));

return true;

}

/* Copy an element value into an untyped output slot. */

static inline bool array_try_get_impl(void *block, size_t elem_size, size_t header_bytes, array_size_t idx,

void *out_value)

{

Array_Header *header = NULL;

char *base = NULL;

if (!block || !out_value)

{

return false;

}

header = (Array_Header *)block;

if (idx >= header->count)

{

return false;

}

base = array_elements_ptr(block, header_bytes);

memcpy(out_value, base + (idx * elem_size), elem_size);

return true;

}

* Checked element access.

* Preconditions:

* arr is either NULL or a valid Array(T).

* out_ptr is non-NULL when arr is non-NULL and idx is in range.

* On success, *out_ptr receives a pointer to the element stored inside arr.

* That pointer is invalidated if arr is reallocated or freed.

#define array_try_at(arr, idx, out_ptr) \

(((arr) == NULL) \

? false \

: array_try_at_impl((arr), array_elem_size(arr), array_header_bytes(arr), (idx), \

(void **)(out_ptr)))

* Allocate an Array(T) with count == 0 and capacity == size.

* Returns NULL on allocation failure or byte-size overflow.

#define array_make(T, size) \

((Array(T))array_make_impl(sizeof(T), offsetof(ArrayStruct(T), elements), (size)))

/* Free an owning Array(T). Passing NULL is valid, like free(NULL). */

#define array_free(arr) free(arr)

* Ensure arr has at least min_capacity slots.

* Preconditions:

* arr must be a modifiable Array(T) lvalue and must not be NULL.

* Returns false on allocation failure or size overflow. On failure, arr still

* points at the original allocation.

#define array_reserve(arr, min_capacity) \

((arr) == NULL ? false \

: array_reserve_impl((void **)&(arr), array_elem_size(arr), \

array_header_bytes(arr), (min_capacity)))

* Append value to arr with checked growth.

* Preconditions:

* arr must be a modifiable Array(T) lvalue. It may be NULL.

* value must be assignable to the array element type.

* Returns false if arr is NULL, count would overflow, or growth fails. The

* element assignment happens only after capacity has been reserved, so normal

* C assignment diagnostics report incompatible value types.

#define array_try_push(arr, value) \

(((arr) != NULL && (arr)->count != (array_size_t)-1 && \

array_reserve((arr), (arr)->count + 1)) \

? (((arr)->elements[(arr)->count] = (value)), ((arr)->count += 1), ARRAY_CHECK((arr)->count <= (arr)->capacity), true) \

: false)

/* Compatibility alias for array_try_push. */

#define array_try_push_lvalue(arr, value) array_try_push((arr), (value))

/* Compatibility push that intentionally discards allocation failure. */

#define array_push(arr, value) ((void)array_try_push(arr, value))

/* Unchecked element access. Requires arr != NULL and idx < arr->count. */

#define array_at(arr, idx) ((arr)->elements[(idx)])

* Checked typed range slice over [low, high).

* Preconditions:

* out_slice must be non-NULL. arr may be NULL, in which case false is

* returned.

* Returns false when bounds are invalid or the implementation rejects inputs.

* Slice(T) stores offsets, so it does not become dangling merely because arr is

* reallocated. Use array_try_span_t for a temporary pointer view.

#define array_try_slice_t(T, arr, low, high, out_slice) \

(((arr) == NULL) \

? false \

: array_try_slice_into_impl((arr), (low), (high), offsetof(Slice(T), start), \

offsetof(Slice(T), count), (void *)(out_slice)))

/* Unchecked typed range slice over [low, high). Requires valid bounds. */

#define slice_from_array_t(T, arr, low, high) \

((Slice(T)) \

{ \

.start = (array_size_t)(low), \

.count = (array_size_t)((high) - (low)), \

})

/* Checked element access through a range slice. */

#define array_try_slice_at_t(T, arr, slice, idx, out_ptr) \

((void)sizeof(T), \

((arr) == NULL \

? false \

: array_try_slice_at_impl((arr), array_elem_size(arr), array_header_bytes(arr), \

(slice).start, (slice).count, (idx), (void **)(out_ptr))))

/* Materialize a temporary raw span from an array and range slice. */

#define array_try_span_t(T, arr, slice, out_span) \

(((arr) == NULL) \

? false \

: array_try_span_into_impl((arr), sizeof(T), array_header_bytes(arr), (slice).start, \

(slice).count, offsetof(Span(T), count), \

offsetof(Span(T), elements), (void *)(out_span)))

/* Copy-based checked accessors. */

#define array_try_get(arr, idx, out_value) \

(((arr) == NULL) \

? false \

: array_try_get_impl((arr), array_elem_size(arr), array_header_bytes(arr), (idx), \

(void *)(out_value)))

#define array_try_set(arr, idx, value) \

(((arr) == NULL || (idx) >= (arr)->count) ? false \

: (((arr)->elements[(idx)] = (value)), true))

/* Return a pointer to the last element, or NULL when arr is NULL or empty. */

#define array_back_ptr(arr) \

((arr) && (arr)->count > 0 ? &(arr)->elements[(arr)->count - 1] : NULL)

/* Pointer to the first element. Requires arr != NULL. */

#define array_start(arr) ((arr)->elements)

/* Pointer to the last element. Requires arr != NULL and arr->count > 0. */

#define array_end(arr) ((arr)->elements + ((arr)->count - 1))

/* Explicit name for callers that want the unchecked contract visible. */

#define array_end_unchecked(arr) array_end(arr)

/* Count/capacity helpers. The unchecked variants require arr != NULL. */

#define array_length(arr) ((arr)->count)

#define array_is_empty(arr) ((arr)->count == 0)

/* Nullable-safe metadata helpers. */

#define array_length_or0(arr) ((arr) ? (arr)->count : 0)

#define array_is_empty_or_true(arr) ((arr) ? (arr)->count == 0 : true)

/* Strict-C iteration. Requires arr != NULL. */

#define array_for_each_t(T, arr, it) \

for (T *(it) = (arr)->elements; (it) < (arr)->elements + (arr)->count; ++(it))

/* Generic sequence helpers shared by arrays and spans. Require seq != NULL. */

#define seq_start(seq) ((seq)->elements)

#define seq_end(seq) ((seq)->elements + (seq)->count)

#define seq_length(seq) ((seq)->count)

/* Build a temporary non-owning span from an existing element pointer and count. */

#define span_make_t(T, start, count) ((Span(T)){.count = (count), .elements = (start)})

#if ARRAY_HAS_TYPEOF

/* GNU/Clang convenience helpers that infer the sequence element type. */

#define seq_elem_type(seq) typeof(*(seq)->elements)

#define for_each(seq, iter) \

for (seq_elem_type(seq) *(iter) = seq_start(seq); (iter) < seq_end(seq); (iter)++)

#define array_for_each(arr, el) for_each(arr, el)

/* Unchecked inferred-type range slice over [low, high). Requires valid bounds. */

#define slice_from_array(arr, low, high) \

((Slice(typeof(*(arr)->elements))){ \

.start = ((array_size_t)(low)), \

.count = ((array_size_t)((high) - (low))), \

})

#define span_make(start, count) ((Span(typeof(*(start)))){.count = (count), .elements = (start)})

#else

/* In strict ISO C mode, use array_for_each_t(T, arr, it) instead. */

#define array_for_each(arr, el) ARRAY_FOR_EACH_REQUIRES_TYPEOF_OR_USE_array_for_each_t

#endif

Arraylist/array.h at main · code5717/Arraylist · GitHub

Expand file tree

Breadcrumbs

array.h

Latest commit

History

Breadcrumbs

array.h

File metadata and controls