fork download
copy 
  1. /**
  2.  * @file array.002.c
  3.  * @ingroup experimental
  4.  * Dynamic array using hidden header.
  5.  * @date 08/13/2026
  6.  */
  7.  
  8. #include <assert.h>
  9. #include <stddef.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <stdio.h>
  13.  
  14. //
  15. // Utility.
  16. //
  17.  
  18. #define REF_T(T, ...) \
  19.     ((T[]){__VA_ARGS__})
  20.  
  21. #define DEREF_T(T, p) \
  22.     (((T *)(void *)(p))[0])
  23.  
  24. #define MAX(a, b) \
  25. ({ __auto_type _x = (a); __auto_type _y = (b); \
  26.    (_y > _x) ? _y : _x; })
  27.  
  28. void *memfill(void *base, size_t n, size_t size, const void *fill)
  29. {
  30.     if (n*size != 0)
  31.     {
  32.         memmove(base, fill, size);
  33.         size_t i = 1;
  34.         for (; i <= n/2; i *= 2)
  35.             memcpy((char *)base + i*size, base, i*size);
  36.         memcpy((char *)base + i*size, base, (n-i)*size);
  37.     }
  38.     return base;
  39. }
  40.  
  41. //
  42. // Array.
  43. //
  44.  
  45. #define ar_size(a) _ar_size(a)
  46. #define ar_itemsize(a) _ar_itemsize(a)
  47. #define ar_capacity(a) _ar_capacity(a)
  48. #define ar_putitem(a) _ar_putitem(a)
  49. #define ar_set_putitem(a, f) _ar_set_putitem(a, f)
  50. #define ar_at(a, i) (((__typeof__(*(a)) *)_ar_at(a, i))[0])
  51. #define ar_at_c(a, i) (((const __typeof__(*(a)) *)_ar_at_c(a, i))[0])
  52. #define ar_reserve(a, n) ((a) = _ar_reserve(a, n))
  53. #define ar_resize(a, n, v) ((a) = _ar_resize(a, n, (__typeof__(*(a))[]){v}))
  54. #define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, n))
  55. #define ar_remove(a, i, n) _ar_remove(a, i, n)
  56. #define ar_push(a, v) ((a) = _ar_push(a, (__typeof__(*(a))[]){v}))
  57. #define ar_pop(a) _ar_pop(a)
  58. #define ar_clear(a) _ar_clear(a)
  59. #define ar_free(a) (_ar_free(a), (a) = 0)
  60. #define ar_init(a, n) ((a) = _ar_init(sizeof *(a), n))
  61. #define ar_init_size(a, n, v) ((a) = _ar_init_size(sizeof *(a), n, (__typeof__(*(a))[]){v}))
  62. #define ar_init_copy(a, b, n) ((a) = (__typeof__(*(b)) *)_ar_init_copy(b, n))
  63. #define ar_print(a) _ar_print(a, stdout)
  64. #define ar_println(a) _ar_println(a, stdout)
  65.  
  66. // ..
  67.  
  68. #define _BASE_TO_SELF(p) ((_Header *)((char *)p - offsetof(_Header, _base)))
  69. #define _SELF_TO_BASE(p) ((void *)(((_Header *)p)->_base))
  70.  
  71. typedef struct {
  72.     size_t size;
  73.     size_t itemsize;
  74.     size_t capacity;
  75.     void (*putitem)(const void *item, FILE *stream);
  76.     _Alignas(max_align_t) char _base[];
  77. } _Header;
  78.  
  79. size_t _ar_size(const void *base)
  80. {
  81.     assert(base != 0);
  82.     return _BASE_TO_SELF(base)->size;
  83. }
  84.  
  85. size_t _ar_itemsize(const void *base)
  86. {
  87.     assert(base != 0);
  88.     return _BASE_TO_SELF(base)->itemsize;
  89. }
  90.  
  91. size_t _ar_capacity(const void *base)
  92. {
  93.     assert(base != 0);
  94.     return _BASE_TO_SELF(base)->capacity;
  95. }
  96.  
  97. void (*_ar_putitem(const void *base))(const void *, FILE *)
  98. {
  99.     assert(base != 0);
  100.     return _BASE_TO_SELF(base)->putitem;
  101. }
  102.  
  103. void _ar_set_putitem(void *base, void (*putitem)(const void *, FILE *))
  104. {
  105.     assert(base != 0);
  106.     _BASE_TO_SELF(base)->putitem = putitem;
  107. }
  108.  
  109. const void *_ar_at_c(const void *base, ptrdiff_t i)
  110. {
  111.     assert(base != 0);
  112.     const _Header *self = _BASE_TO_SELF(base);
  113.  
  114.     size_t size = self->size;
  115.     if (i < 0) i += size;
  116.     assert((size_t)i < size);
  117.     return (const char *)base + i*self->itemsize;
  118. }
  119.  
  120. void *_ar_at(void *base, ptrdiff_t i)
  121. {
  122.     return (void *)_ar_at_c(base, i);
  123. }
  124.  
  125. void *_ar_reserve(void *base, size_t capacity)
  126. {
  127.     // Ensure array has enough memory for capacity items.
  128.  
  129.     assert(base != 0);
  130.     _Header *self = _BASE_TO_SELF(base);
  131.  
  132.     if (capacity > self->capacity)
  133.     {
  134.         self = realloc(self, sizeof *self + capacity*self->itemsize);
  135.         assert(self != 0);
  136.         self->capacity = capacity;
  137.     }
  138.     return _SELF_TO_BASE(self);
  139. }
  140.  
  141. void *_ar_resize(void *base, size_t size, const void *fill)
  142. {
  143.     // Change array size and initialize newly revealed items to specified fill
  144.     // value. If fill is not provided, items are not initialized.
  145.  
  146.     assert(base != 0);
  147.     base = _ar_reserve(base, size);
  148.  
  149.     _Header *self = _BASE_TO_SELF(base);
  150.     size_t oldsize = self->size;
  151.     self->size = size;
  152.  
  153.     if (fill != 0 && size > oldsize)
  154.         memfill(_ar_at(base, oldsize), size - oldsize, self->itemsize, fill);
  155.     return base;
  156. }
  157.  
  158. void *_ar_insert(void *base, size_t i, const void *first, size_t n)
  159. {
  160.     // Insert n items starting at first into array before position i.
  161.  
  162.     assert(base != 0);
  163.     _Header *self = _BASE_TO_SELF(base);
  164.  
  165.     size_t oldsize = self->size;
  166.     assert(oldsize >= i);
  167.  
  168.     if (n != 0)
  169.     {
  170.         size_t size;
  171.         if (__builtin_add_overflow(oldsize, n, &size))
  172.             assert(0 && "integer overflow");
  173.  
  174.         if (size > self->capacity)
  175.         {
  176.             base = _ar_reserve(base, MAX(2*self->capacity, size));
  177.             self = _BASE_TO_SELF(base);
  178.         }
  179.         self->size = size;
  180.         void *ip = _ar_at(base, i);
  181.  
  182.         if (oldsize > i)
  183.             memmove(_ar_at(base, i + n), ip, (oldsize - i)*self->itemsize);
  184.         memcpy(ip, first, n*self->itemsize);
  185.     }
  186.     return base;
  187. }
  188.  
  189. void _ar_remove(void *base, size_t i, size_t n)
  190. {
  191.     // Remove n items from array starting at position i.
  192.  
  193.     assert(base != 0);
  194.     _Header *self = _BASE_TO_SELF(base);
  195.  
  196.     size_t oldsize = self->size;
  197.     assert(oldsize >= i);
  198.  
  199.     if (n != 0)
  200.     {
  201.         size_t j;
  202.         if (__builtin_add_overflow(i, n, &j))
  203.             assert(0 && "integer overflow");
  204.         assert(oldsize >= j);
  205.  
  206.         if (oldsize > j)
  207.             memmove(_ar_at(base, i), _ar_at(base, j), (oldsize - j)*self->itemsize);
  208.         self->size = oldsize - n;
  209.     }
  210. }
  211.  
  212. void *_ar_push(void *base, const void *item)
  213. {
  214.     return _ar_insert(base, _ar_size(base), item, 1);
  215. }
  216.  
  217. void _ar_pop(void *base)
  218. {
  219.     _ar_remove(base, _ar_size(base)-1, 1);
  220. }
  221.  
  222. void _ar_clear(void *base)
  223. {
  224.     _ar_resize(base, 0, 0);
  225. }
  226.  
  227. void _ar_free(void *base)
  228. {
  229.     if (base != 0)
  230.         free(_BASE_TO_SELF(base));
  231. }
  232.  
  233. void *_ar_init(size_t itemsize, size_t capacity)
  234. {
  235.     // Create array with enough memory for capacity items.
  236.  
  237.     _Header *self = malloc(sizeof *self + capacity*itemsize);
  238.     assert(self != 0);
  239.     self->size = 0;
  240.     self->itemsize = itemsize;
  241.     self->capacity = capacity;
  242.     self->putitem = 0;
  243.     return _SELF_TO_BASE(self);
  244. }
  245.  
  246. void *_ar_init_size(size_t itemsize, size_t size, const void *fill)
  247. {
  248.     // Create with size items and initialize with specified fill value.
  249.  
  250.     return _ar_resize(_ar_init(itemsize, size), size, fill);
  251. }
  252.  
  253. void *_ar_init_copy(const void *other_base, size_t capacity)
  254. {
  255.     // Create copy of an array with at least capacity items reserved.
  256.  
  257.     assert(other_base != 0);
  258.     const _Header *other = _BASE_TO_SELF(other_base);
  259.  
  260.     void *base = _ar_init(other->itemsize, MAX(other->size, capacity));
  261.     return _ar_insert(base, 0, other_base, other->size);
  262. }
  263.  
  264. void _ar_print(const void *base, FILE *stream)
  265. {
  266.     assert(base != 0);
  267.     const _Header *self = _BASE_TO_SELF(base);
  268.  
  269.     void (*putitem)(const void *, FILE *) = self->putitem;
  270.     assert(putitem != 0);
  271.  
  272.     size_t n = self->size;
  273.  
  274.     fputc('{', stream);
  275.     if (n != 0)
  276.     {
  277.         for (size_t i = 0;;)
  278.         {
  279.             putitem(_ar_at_c(base, i), stream);
  280.             if (++i == n) break;
  281.             fputs(", ", stream);
  282.         }
  283.     }
  284.     fputc('}', stream);
  285. }
  286.  
  287. void _ar_println(const void *base, FILE *stream)
  288. {
  289.     _ar_print(base, stream); fputc('\n', stream);
  290. }
  291.  
  292. //
  293. // Main.
  294. //
  295.  
  296. void test_init_free(void)
  297. {
  298.     printf("<%s>\n", __func__);
  299.  
  300.     // Init.
  301.  
  302.     int *a = 0;
  303.     ar_init(a, 0);
  304.     assert(ar_size(a) == 0);
  305.     assert(ar_itemsize(a) == sizeof(*a));
  306.     assert(ar_capacity(a) == 0);
  307.  
  308.     ar_free(a);
  309.     assert(a == 0);
  310.  
  311.     // Init (capacity).
  312.  
  313.     ar_init(a, 8);
  314.     assert(ar_size(a) == 0);
  315.     assert(ar_itemsize(a) == sizeof(*a));
  316.     assert(ar_capacity(a) == 8);
  317.  
  318.     ar_free(a);
  319.     assert(a == 0);
  320.  
  321.     // Init size.
  322.  
  323.     ar_init_size(a, 3, 123);
  324.     assert(ar_size(a) == 3);
  325.     assert(ar_itemsize(a) == sizeof(*a));
  326.     assert(ar_capacity(a) == 3);
  327.  
  328.     for (size_t i = 0; i < 3; i++)
  329.         assert(ar_at(a, i) == 123);
  330.  
  331.     // Init copy.
  332.  
  333.     int *b = 0;
  334.     ar_init_copy(b, a, 0);
  335.  
  336.     ar_free(a);
  337.     assert(a == 0);
  338.  
  339.     assert(ar_size(b) == 3);
  340.     assert(ar_itemsize(b) == sizeof(*b));
  341.     assert(ar_capacity(b) == 3);
  342.  
  343.     for (size_t i = 0; i < 3; i++)
  344.         assert(ar_at(b, i) == 123);
  345.  
  346.     // Init copy (capacity).
  347.  
  348.     ar_init_copy(a, b, 8);
  349.  
  350.     ar_free(b);
  351.     assert(b == 0);
  352.  
  353.     assert(ar_size(a) == 3);
  354.     assert(ar_itemsize(a) == sizeof(*a));
  355.     assert(ar_capacity(a) == 8);
  356.  
  357.     for (size_t i = 0; i < 3; i++)
  358.         assert(ar_at(a, i) == 123);
  359.     ar_free(a);
  360.     assert(a == 0);
  361.  
  362.     puts("..Okay");
  363. }
  364.  
  365. void test_push_pop(void)
  366. {
  367.     printf("<%s>\n", __func__);
  368.  
  369.     int *a = 0;
  370.     ar_init(a, 0);
  371.  
  372.     // Push (back).
  373.  
  374.     for (int i = 0; i < 8; i++)
  375.     {
  376.         ar_push(a, i);
  377.         assert(ar_size(a) == (size_t)i+1);
  378.         assert(ar_at(a, -1) == i);
  379.     }
  380.  
  381.     // Pop (back).
  382.  
  383.     for (int i = 8-1; i >= 0; i--)
  384.     {
  385.         assert(ar_at(a, -1) == i);
  386.         ar_pop(a);
  387.         assert(ar_size(a) == (size_t)i);
  388.     }
  389.  
  390.     ar_free(a);
  391.  
  392.     puts("..Okay");
  393. }
  394.  
  395. void test_insert_remove(void)
  396. {
  397.     printf("<%s>\n", __func__);
  398.  
  399.     int *a = 0;
  400.     ar_init(a, 0);
  401.  
  402.     // Insert even (bulk).
  403.  
  404.     ar_insert(a, 0, REF_T(int, 0, 2, 4), 3);
  405.     assert(ar_size(a) == 3);
  406.     for (int i = 0; i < 3; i++)
  407.         assert(ar_at(a, i) == 2*i);
  408.  
  409.     // Insert odd (single).
  410.  
  411.     for (int i = 0; i < 3; i++)
  412.         ar_insert(a, 2*i+1, REF_T(int, 2*i+1), 1);
  413.     assert(ar_size(a) == 6);
  414.     for (int i = 0; i < 6; i++)
  415.         assert(ar_at(a, i) == i);
  416.  
  417.     // Remove even (single).
  418.  
  419.     for (int i = 2; i >= 0; i--)
  420.         ar_remove(a, 2*i, 1);
  421.     assert(ar_size(a) == 3);
  422.     for (int i = 0; i < 3; i++)
  423.         assert(ar_at(a, i) == 2*i+1);
  424.  
  425.     // Remove odd (bulk).
  426.  
  427.     ar_remove(a, 0, 3);
  428.     assert(ar_size(a) == 0);
  429.     ar_free(a);
  430.  
  431.     puts("..Okay");
  432. }
  433.  
  434. void test_resize(void)
  435. {
  436.     printf("<%s>\n", __func__);
  437.  
  438.     int *a = 0;
  439.     ar_init(a, 0);
  440.  
  441.     // Resize (with clear).
  442.  
  443.     for (int i = 0; i < 3; i++)
  444.     {
  445.         int n = i+1;
  446.         ar_resize(a, n, i);
  447.         assert(ar_size(a) == (size_t)n);
  448.         for (int j = 0; j < n; j++)
  449.             assert(ar_at(a, j) == i);
  450.         ar_clear(a);
  451.         assert(ar_size(a) == 0);
  452.     }
  453.  
  454.     // Resize (without clear).
  455.  
  456.     for (int i = 0; i < 3; i++)
  457.     {
  458.         int n = i+1;
  459.         ar_resize(a, n, i);
  460.         assert(ar_size(a) == (size_t)n);
  461.         for (int j = 0; j < n; j++)
  462.             assert(ar_at(a, j) == j);
  463.     }
  464.  
  465.     ar_free(a);
  466.  
  467.     puts("..Okay");
  468. }
  469.  
  470. // ..
  471.  
  472. void putitem_ar(const void *item, FILE *stream)
  473. {
  474.     _ar_print(*(const void **)item, stream);
  475. }
  476.  
  477. void putitem_int(const void *item, FILE *stream)
  478. {
  479.     fprintf(stream, "%d", *(const int *)item);
  480. }
  481.  
  482. int *iota(int n, int start, int step)
  483. {
  484.     int *a = 0;
  485.     ar_init(a, MAX(n, 0));
  486.     ar_set_putitem(a, putitem_int);
  487.     for (int i = 0; i < n; i++)
  488.         ar_push(a, start + i*step);
  489.     return a;
  490. }
  491.  
  492. void show_push_pop(void)
  493. {
  494.     printf("<%s>\n", __func__);
  495.  
  496.     int *a = 0;
  497.     ar_init(a, 0);
  498.     ar_set_putitem(a, putitem_int);
  499.  
  500.     int n = 4;
  501.  
  502.     for (int i = 0; i < n; i++)
  503.     {
  504.         ar_push(a, i);
  505.         ar_println(a);
  506.     }
  507.  
  508.     while (ar_size(a) != 0)
  509.     {
  510.         ar_pop(a);
  511.         ar_println(a);
  512.     }
  513.  
  514.     ar_free(a);
  515. }
  516.  
  517. void show_insert_remove(void)
  518. {
  519.     printf("<%s>\n", __func__);
  520.  
  521.     int *a = 0;
  522.     ar_init(a, 0);
  523.     ar_set_putitem(a, putitem_int);
  524.  
  525.     int n = 4;
  526.  
  527.     for (int i = 0; i < n; i++)
  528.     {
  529.         ar_insert(a, i, REF_T(int, i+1, i+1+n), 2);
  530.         ar_println(a);
  531.     }
  532.  
  533.     for (int i = n-1; i >= 0; i--)
  534.     {
  535.         ar_remove(a, i, 2);
  536.         ar_println(a);
  537.     }
  538.  
  539.     ar_free(a);
  540. }
  541.  
  542. void show_resize(void)
  543. {
  544.     printf("<%s>\n", __func__);
  545.  
  546.     int *a = 0;
  547.     ar_init(a, 0);
  548.     ar_set_putitem(a, putitem_int);
  549.  
  550.     int n = 4;
  551.  
  552.     for (int i = 1; i <= n; i++)
  553.     {
  554.         ar_resize(a, i, -i);
  555.         ar_println(a);
  556.         ar_clear(a);
  557.     }
  558.  
  559.     for (int i = 1; i <= n; i++)
  560.     {
  561.         ar_resize(a, i, -i);
  562.         ar_println(a);
  563.     }
  564.  
  565.     ar_free(a);
  566. }
  567.  
  568. void show_array_of_array(void)
  569. {
  570.     printf("<%s>\n", __func__);
  571.  
  572.     int **a = 0;
  573.     ar_init(a, 0);
  574.     ar_set_putitem(a, putitem_ar);
  575.  
  576.     int n = 4;
  577.  
  578.     for (int i = 0; i < n; i++)
  579.     {
  580.         int count = i+1;
  581.         int start = i*(i+1)/2+1;
  582.         ar_push(a, iota(count, start, 1));
  583.         ar_println(a);
  584.     }
  585.  
  586.     for (size_t i = 0; i < ar_size(a); i++)
  587.         ar_free(a[i]);
  588.     ar_free(a);
  589. }
  590.  
  591. int main(void)
  592. {
  593.     test_init_free();
  594.     test_push_pop();
  595.     test_insert_remove();
  596.     test_resize();
  597.  
  598.     show_push_pop();
  599.     show_insert_remove();
  600.     show_resize();
  601.     show_array_of_array();
  602.     return 0;
  603. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
<test_init_free>
..Okay
<test_push_pop>
..Okay
<test_insert_remove>
..Okay
<test_resize>
..Okay
<show_push_pop>
{0}
{0, 1}
{0, 1, 2}
{0, 1, 2, 3}
{0, 1, 2}
{0, 1}
{0}
{}
<show_insert_remove>
{1, 5}
{1, 2, 6, 5}
{1, 2, 3, 7, 6, 5}
{1, 2, 3, 4, 8, 7, 6, 5}
{1, 2, 3, 7, 6, 5}
{1, 2, 6, 5}
{1, 5}
{}
<show_resize>
{-1}
{-2, -2}
{-3, -3, -3}
{-4, -4, -4, -4}
{-1}
{-1, -2}
{-1, -2, -3}
{-1, -2, -3, -4}
<show_array_of_array>
{{1}}
{{1}, {2, 3}}
{{1}, {2, 3}, {4, 5, 6}}
{{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}}
https://ideone.com/1kGxT7
language:
C (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!