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