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