Last active
October 5, 2020 21:31
-
-
Save RobertDurfee/3b2222a01f025f9bc42bd52054dc3725 to your computer and use it in GitHub Desktop.
A simple, generic implementation of an array with amortized O(1) append in C.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef LIST_H | |
| #define LIST_H | |
| #include <stdlib.h> // size_t, malloc, realloc, free | |
| #include <stdint.h> // uint32_t | |
| #include <stdio.h> // printf | |
| #include <stdbool.h> // bool | |
| #define TOKENPASTE(X, Y) X ## Y | |
| #define INDENT(DEPTH) printf("%*c", DEPTH * 2, ' ') | |
| #define LIST_CONS(LIST) TOKENPASTE(LIST, Cons) | |
| #define LIST_NEXT(LIST) TOKENPASTE(LIST, Next) | |
| #define LIST_AT(LIST) TOKENPASTE(LIST, At) | |
| #define LIST_EQUALS(LIST) TOKENPASTE(LIST, Equals) | |
| #define LIST_DEBUG(LIST) TOKENPASTE(LIST, Debug) | |
| #define LIST_DES(LIST) TOKENPASTE(LIST, Des) | |
| #define LIST_GEN_DECL(LIST, ELEM) \ | |
| \ | |
| struct LIST { \ | |
| ELEM *elems; \ | |
| size_t capacity; \ | |
| size_t len; \ | |
| }; \ | |
| \ | |
| struct LIST *LIST_CONS(LIST)(struct LIST *list, size_t capacity); \ | |
| \ | |
| ELEM *LIST_NEXT(LIST)(struct LIST *list); \ | |
| \ | |
| ELEM *LIST_AT(LIST)(struct LIST *list, size_t i); \ | |
| \ | |
| bool LIST_EQUALS(LIST)(const struct LIST *a, const struct LIST *b); \ | |
| \ | |
| void LIST_DEBUG(LIST)(const struct LIST *list, uint32_t depth); \ | |
| \ | |
| struct LIST *LIST_DES(LIST)(struct LIST *list); | |
| #define LIST_GEN_DEF(LIST, ELEM, ELEM_EQUALS, ELEM_DEBUG, ELEM_DES) \ | |
| \ | |
| struct LIST *LIST_CONS(LIST)(struct LIST *list, size_t capacity) { \ | |
| list->elems = (ELEM *)malloc(capacity * sizeof(ELEM)); \ | |
| list->capacity = capacity; \ | |
| list->len = 0; \ | |
| return list; \ | |
| } \ | |
| \ | |
| ELEM *LIST_NEXT(LIST)(struct LIST *list) { \ | |
| if (list->len == list->capacity) { \ | |
| list->capacity *= 2; \ | |
| list->elems = (ELEM *)realloc(list->elems, list->capacity * sizeof(ELEM)); \ | |
| } \ | |
| return &list->elems[list->len]; \ | |
| } \ | |
| \ | |
| ELEM *LIST_AT(LIST)(struct LIST *list, size_t i) { \ | |
| return &list->elems[i]; \ | |
| } \ | |
| \ | |
| bool LIST_EQUALS(LIST)(const struct LIST *a, const struct LIST *b) { \ | |
| size_t i; \ | |
| if (a->len != b->len) { \ | |
| return false; \ | |
| } \ | |
| for (i = 0; i < a->len; i++) { \ | |
| if (!ELEM_EQUALS(&a->elems[i], &b->elems[i])) { \ | |
| return false; \ | |
| } \ | |
| } \ | |
| return true; \ | |
| } \ | |
| \ | |
| void LIST_DEBUG(LIST)(const struct LIST *list, uint32_t depth) { \ | |
| size_t i; \ | |
| printf(#LIST " {\n"); \ | |
| INDENT(depth); printf(" elems: [\n"); \ | |
| for (i = 0; i < list->len; i++) { \ | |
| INDENT(depth); ELEM_DEBUG(&list->elems[i], depth + 1); printf(",\n"); \ | |
| } \ | |
| INDENT(depth); printf(" ],\n"); \ | |
| INDENT(depth); printf(" capacity: %lu,\n", list->capacity); \ | |
| INDENT(depth); printf(" len: %lu,\n", list->len); \ | |
| INDENT(depth); printf("}"); \ | |
| } \ | |
| \ | |
| struct LIST *LIST_DES(LIST)(struct LIST *list) { \ | |
| size_t i; \ | |
| for (i = 0; i < list->len; i++) { \ | |
| ELEM_DES(&list->elems[i]); \ | |
| } \ | |
| free(list->elems); \ | |
| list->capacity = 0; \ | |
| list->len = 0; \ | |
| return list; \ | |
| } | |
| #endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment