fork download
copy 
  1. // Hidden header style array. (3.00)
  2.  
  3. #include <assert.h>
  4. #include <stddef.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <stdio.h>
  8.  
  9. // Utility.
  10.  
  11. #define MAX(a, b) \
  12. ({ __auto_type _x = (a); __auto_type _y = (b); \
  13.    (_y > _x) ? _y : _x; })
  14.  
  15. void *memfill(void *base, size_t n, size_t size, const void *fill)
  16. {
  17.     if (n != 0 && size != 0)
  18.     {
  19.         memmove(base, fill, size);
  20.         size_t i = 1;
  21.         for (; i <= n/2; i *= 2)
  22.             memcpy((char*)base + i*size, base, i*size);
  23.         memcpy((char*)base + i*size, base, (n-i)*size);
  24.     }
  25.     return base;
  26. }
  27.  
  28. // Interface.
  29.  
  30. #define ar_size(a) _ar_size(a)
  31. #define ar_capacity(a) _ar_capacity(a)
  32. #define ar_itemsize(a) _ar_itemsize(a)
  33. #define ar_putitem(a) _ar_putitem(a)
  34. #define ar_set_putitem(a, f) _ar_set_putitem(a, f)
  35. #define ar_reserve(a, n) ((a) = _ar_reserve(a, n))
  36. #define ar_resize(a, n, v) ((a) = _ar_resize(a, n, (__typeof__(*(a))[]){v}))
  37. #define ar_free(a) (_ar_free(a), (a) = 0)
  38. #define ar_init(a) ((a) = _ar_init(sizeof *(a)))
  39. #define ar_init_size(a, n, v) ((a) = _ar_init_size(n, (__typeof__(*(a))[]){v}, sizeof *(a)))
  40. #define ar_init_copy(a, b) ((a) = (__typeof__(*(b))*)_ar_init_copy(b, sizeof *(a)))
  41. #define ar_at(a, i) (((__typeof__(*(a))*)_ar_at(a, i))[0])
  42. #define ar_at_c(a, i) (((const __typeof__(*(a))*)_ar_at_c(a, i))[0])
  43. #define ar_remove(a, i, n) _ar_remove(a, i, n)
  44. #define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, n))
  45. #define ar_push(a, v) ((a) = _ar_push(a, (__typeof__(*(a))[]){v}))
  46. #define ar_pop(a) _ar_pop(a)
  47. #define ar_clear(a) _ar_clear(a)
  48. #define ar_print(a) _ar_print(a, stdout)
  49. #define ar_println(a) _ar_println(a, stdout)
  50.  
  51. size_t _ar_size(const void *p);
  52. size_t _ar_capacity(const void *p);
  53. size_t _ar_itemsize(const void *p);
  54. void (*_ar_putitem(const void *p))(const void *, FILE *);
  55. void _ar_set_putitem(void *p, void (*putitem)(const void *, FILE *));
  56. void *_ar_reserve(void *p, size_t capacity);
  57. void *_ar_resize(void *p, size_t size, const void *fill);
  58. void _ar_free(void *p);
  59. void *_ar_init(size_t itemsize);
  60. void *_ar_init_size(size_t size, const void *fill, size_t itemsize);
  61. void *_ar_init_copy(const void *p, size_t itemsize);
  62. const void *_ar_at_c(const void *p, ptrdiff_t i);
  63. void *_ar_at(void *p, ptrdiff_t i);
  64. void _ar_remove(void *p, size_t i, size_t n);
  65. void *_ar_insert(void *p, size_t i, const void *first, size_t n);
  66. void *_ar_push(void *p, const void *item);
  67. void _ar_pop(void *p);
  68. void _ar_clear(void *p);
  69. void _ar_print(const void *p, FILE *stream);
  70. void _ar_println(const void *p, FILE *stream);
  71.  
  72. // Implementation.
  73.  
  74. typedef struct {
  75.     size_t size;
  76.     size_t capacity;
  77.     size_t itemsize;
  78.     void (*putitem)(const void *item, FILE *stream);
  79. } _Header;
  80.  
  81. #define _PTR_TO_HDR(p) ((_Header*)((char*)p - sizeof(_Header)))
  82. #define _HDR_TO_PTR(p) ((void*)((char*)p + sizeof(_Header)))
  83.  
  84. size_t _ar_size(const void *p)
  85. {
  86.     assert(p != 0);
  87.     return _PTR_TO_HDR(p)->size;
  88. }
  89.  
  90. size_t _ar_capacity(const void *p)
  91. {
  92.     assert(p != 0);
  93.     return _PTR_TO_HDR(p)->capacity;
  94. }
  95.  
  96. size_t _ar_itemsize(const void *p)
  97. {
  98.     assert(p != 0);
  99.     return _PTR_TO_HDR(p)->itemsize;
  100. }
  101.  
  102. void (*_ar_putitem(const void *p))(const void *, FILE *)
  103. {
  104.     assert(p != 0);
  105.     return _PTR_TO_HDR(p)->putitem;
  106. }
  107.  
  108. void _ar_set_putitem(void *p, void (*putitem)(const void *, FILE *))
  109. {
  110.     assert(p != 0);
  111.     _PTR_TO_HDR(p)->putitem = putitem;
  112. }
  113.  
  114. void *_ar_reserve(void *p, size_t capacity)
  115. {
  116.     assert(p != 0);
  117.     _Header *self = _PTR_TO_HDR(p);
  118.  
  119.     if (capacity > self->capacity)
  120.     {
  121.         self = realloc(self, sizeof *self + capacity*self->itemsize);
  122.         assert(self != 0);
  123.         self->capacity = capacity;
  124.     }
  125.     return _HDR_TO_PTR(self);
  126. }
  127.  
  128. void *_ar_resize(void *p, size_t size, const void *fill)
  129. {
  130.     assert(p != 0);
  131.     p = _ar_reserve(p, size);
  132.  
  133.     _Header *self = _PTR_TO_HDR(p);
  134.     size_t oldsize = self->size;
  135.     self->size = size;
  136.  
  137.     if (fill != 0 && size > oldsize)
  138.         memfill(_ar_at(p, oldsize), size - oldsize, self->itemsize, fill);
  139.     return p;
  140. }
  141.  
  142. void _ar_free(void *p)
  143. {
  144.     if (p != 0)
  145.         free(_PTR_TO_HDR(p));
  146. }
  147.  
  148. void *_ar_init(size_t itemsize)
  149. {
  150.     _Header *self = malloc(sizeof *self);
  151.     assert(self != 0);
  152.     self->size = 0;
  153.     self->capacity = 0;
  154.     self->itemsize = itemsize;
  155.     self->putitem = 0;
  156.     return _HDR_TO_PTR(self);
  157. }
  158.  
  159. void *_ar_init_size(size_t size, const void *fill, size_t itemsize)
  160. {
  161.     return _ar_resize(_ar_init(itemsize), size, fill);
  162. }
  163.  
  164. void *_ar_init_copy(const void *p, size_t itemsize)
  165. {
  166.     assert(p != 0);
  167.     const _Header *other = _PTR_TO_HDR(p);
  168.  
  169.     assert(itemsize == other->itemsize);
  170.     return _ar_insert(_ar_init(itemsize), 0, p, other->size);
  171. }
  172.  
  173. const void *_ar_at_c(const void *p, ptrdiff_t i)
  174. {
  175.     assert(p != 0);
  176.     const _Header *self = _PTR_TO_HDR(p);
  177.  
  178.     size_t size = self->size;
  179.     size_t j = (i < 0) ? i + size : (size_t)i;
  180.     assert(j < size);
  181.     return (const char*)p + j*self->itemsize;
  182. }
  183.  
  184. void *_ar_at(void *p, ptrdiff_t i)
  185. {
  186.     return (void*)_ar_at_c(p, i);
  187. }
  188.  
  189. void _ar_remove(void *p, size_t i, size_t n)
  190. {
  191.     assert(p != 0);
  192.     _Header *self = _PTR_TO_HDR(p);
  193.  
  194.     size_t oldsize = self->size;
  195.     assert(oldsize >= i);
  196.  
  197.     if (n != 0)
  198.     {
  199.         size_t j;
  200.         if (__builtin_add_overflow(i, n, &j))
  201.             assert(0 && "integer overflow");
  202.         assert(oldsize >= j);
  203.  
  204.         if (oldsize > j)
  205.             memmove(_ar_at(p, i), _ar_at(p, j), (oldsize - j)*self->itemsize);
  206.         self->size = oldsize - n;
  207.     }
  208. }
  209.  
  210. void *_ar_insert(void *p, size_t i, const void *first, size_t n)
  211. {
  212.     assert(p != 0);
  213.     _Header *self = _PTR_TO_HDR(p);
  214.  
  215.     size_t oldsize = self->size;
  216.     assert(oldsize >= i);
  217.  
  218.     if (n != 0)
  219.     {
  220.         size_t size;
  221.         if (__builtin_add_overflow(oldsize, n, &size))
  222.             assert(0 && "integer overflow");
  223.  
  224.         if (size > self->capacity)
  225.         {
  226.             p = _ar_reserve(p, MAX(2*self->capacity, size));
  227.             self = _PTR_TO_HDR(p);
  228.         }
  229.         self->size = size;
  230.         void *ip = _ar_at(p, i);
  231.  
  232.         if (oldsize > i)
  233.             memmove(_ar_at(p, i + n), ip, (oldsize - i)*self->itemsize);
  234.         memcpy(ip, first, n*self->itemsize);
  235.     }
  236.     return p;
  237. }
  238.  
  239. void *_ar_push(void *p, const void *item)
  240. {
  241.     return _ar_insert(p, _ar_size(p), item, 1);
  242. }
  243.  
  244. void _ar_pop(void *p)
  245. {
  246.     _ar_remove(p, _ar_size(p)-1, 1);
  247. }
  248.  
  249. void _ar_clear(void *p)
  250. {
  251.     _ar_resize(p, 0, 0);
  252. }
  253.  
  254. void _ar_print(const void *p, FILE *stream)
  255. {
  256.     assert(p != 0);
  257.     const _Header *self = _PTR_TO_HDR(p);
  258.  
  259.     assert(self->putitem != 0);
  260.     size_t n = self->size;
  261.  
  262.     fputc('{', stream);
  263.     if (n != 0)
  264.     {
  265.         for (size_t i = 0;;)
  266.         {
  267.             self->putitem(_ar_at_c(p, i), stream);
  268.             if (++i == n) break;
  269.             fputs(", ", stream);
  270.         }
  271.     }
  272.     fputc('}', stream);
  273. }
  274.  
  275. void _ar_println(const void *p, FILE *stream)
  276. {
  277.     _ar_print(p, stream); fputc('\n', stream);
  278. }
  279.  
  280. // Putitem callback.
  281.  
  282. void putitem_ar(const void *item, FILE *stream)
  283. {
  284.     _ar_print(*(const void **)item, stream);
  285. }
  286.  
  287. void putitem_int(const void *item, FILE *stream)
  288. {
  289.     fprintf(stream, "%d", *(const int *)item);
  290. }
  291.  
  292. // Test.
  293.  
  294. void test_init_free(void)
  295. {
  296.     printf("<%s>\n", __func__);
  297.  
  298.     // Init.
  299.  
  300.     int *p = 0;
  301.     ar_init(p);
  302.     assert(ar_size(p) == 0);
  303.     ar_free(p);
  304.     assert(p == 0);
  305.  
  306.     // Init size.
  307.  
  308.     ar_init_size(p, 3, 123);
  309.     assert(ar_size(p) == 3);
  310.     for (size_t i = 0; i < 3; i++)
  311.         assert(ar_at(p, i) == 123);
  312.  
  313.     // Init copy.
  314.  
  315.     int *q = 0;
  316.     ar_init_copy(q, p);
  317.     ar_free(p);
  318.     assert(p == 0);
  319.  
  320.     assert(ar_size(q) == 3);
  321.     for (size_t i = 0; i < 3; i++)
  322.         assert(ar_at(q, i) == 123);
  323.     ar_free(q);
  324.     assert(q == 0);
  325.  
  326.     puts("..Okay");
  327. }
  328.  
  329. void test_push_pop(void)
  330. {
  331.     printf("<%s>\n", __func__);
  332.  
  333.     int *p = 0;
  334.     ar_init(p);
  335.  
  336.     // Push (back).
  337.  
  338.     for (int i = 0; i < 8; i++)
  339.     {
  340.         assert(ar_size(p) == i);
  341.         int cp2 = i ? 1<<(31 - __builtin_clz(2*i-1)) : 0;
  342.         assert(ar_capacity(p) == cp2);
  343.         ar_push(p, i);
  344.         assert(ar_at(p, -1) == i);
  345.     }
  346.  
  347.     // Pop (back).
  348.  
  349.     for (int i = 7; i >= 0; i--)
  350.     {
  351.         assert(ar_at(p, -1) == i);
  352.         ar_pop(p);
  353.     }
  354.     assert(ar_size(p) == 0);
  355.     ar_free(p);
  356.  
  357.     puts("..Okay");
  358. }
  359.  
  360. void test_insert_remove(void)
  361. {
  362.     printf("<%s>\n", __func__);
  363.  
  364.     int *p = 0;
  365.     ar_init(p);
  366.  
  367.     // Insert even (bulk).
  368.  
  369.     ar_insert(p, 0, ((int[]){0, 2, 4}), 3);
  370.     assert(ar_size(p) == 3);
  371.     for (int i = 0; i < 3; i++)
  372.         assert(ar_at(p, i) == 2*i);
  373.  
  374.     // Insert odd (single).
  375.  
  376.     for (int i = 0; i < 3; i++)
  377.         ar_insert(p, 2*i+1, (int[]){2*i+1}, 1);
  378.     assert(ar_size(p) == 6);
  379.     for (int i = 0; i < 6; i++)
  380.         assert(ar_at(p, i) == i);
  381.  
  382.     // Remove even (single).
  383.  
  384.     for (int i = 2; i >= 0; i--)
  385.         ar_remove(p, 2*i, 1);
  386.     assert(ar_size(p) == 3);
  387.     for (int i = 0; i < 3; i++)
  388.         assert(ar_at(p, i) == 2*i+1);
  389.  
  390.     // Remove odd (bulk).
  391.  
  392.     ar_remove(p, 0, 3);
  393.     assert(ar_size(p) == 0);
  394.     ar_free(p);
  395.  
  396.     puts("..Okay");
  397. }
  398.  
  399. // Show.
  400.  
  401. void show_push_pop(void)
  402. {
  403.     printf("<%s>\n", __func__);
  404.  
  405.     int *p = 0;
  406.     ar_init(p);
  407.     ar_set_putitem(p, putitem_int);
  408.  
  409.     int n = 4;
  410.  
  411.     for (int i = 0; i < n; i++)
  412.     {
  413.         ar_push(p, i);
  414.         ar_println(p);
  415.     }
  416.  
  417.     while (ar_size(p) != 0)
  418.     {
  419.         ar_pop(p);
  420.         ar_println(p);
  421.     }
  422.  
  423.     ar_free(p);
  424. }
  425.  
  426. void show_insert_remove(void)
  427. {
  428.     printf("<%s>\n", __func__);
  429.  
  430.     int *p = 0;
  431.     ar_init(p);
  432.     ar_set_putitem(p, putitem_int);
  433.  
  434.     int n = 4;
  435.  
  436.     for (int i = 0; i < n; i++)
  437.     {
  438.         ar_insert(p, i, ((int[]){i+1, i+1+n}), 2);
  439.         ar_println(p);
  440.     }
  441.  
  442.     for (int i = n-1; i >= 0; i--)
  443.     {
  444.         ar_remove(p, i, 2);
  445.         ar_println(p);
  446.     }
  447.  
  448.     ar_free(p);
  449. }
  450.  
  451. void show_resize(void)
  452. {
  453.     printf("<%s>\n", __func__);
  454.  
  455.     int *p = 0;
  456.     ar_init(p);
  457.     ar_set_putitem(p, putitem_int);
  458.  
  459.     int n = 5;
  460.  
  461.     for (int i = 1; i < n; i++)
  462.     {
  463.         ar_resize(p, i, -i);
  464.         ar_println(p);
  465.         ar_clear(p);
  466.     }
  467.  
  468.     ar_free(p);
  469. }
  470.  
  471. void show_array_of_array(void)
  472. {
  473.     printf("<%s>\n", __func__);
  474.  
  475.     int **p = 0;
  476.     ar_init(p);
  477.     ar_set_putitem(p, putitem_ar);
  478.  
  479.     int n = 4;
  480.     int v = 1;
  481.  
  482.     for (int i = 0; i < n; i++)
  483.     {
  484.         int *q = 0;
  485.         ar_init(q);
  486.         ar_set_putitem(q, putitem_int);
  487.         for (int j = 0; j < i+1; j++)
  488.             ar_push(q, v++);
  489.         ar_push(p, q);
  490.         ar_println(p);
  491.     }
  492.  
  493.     while (ar_size(p) != 0)
  494.     {
  495.         int *q = ar_at(p, -1);
  496.         ar_free(q);
  497.         ar_pop(p);
  498.     }
  499.  
  500.     ar_free(p);
  501. }
  502.  
  503. int main(void)
  504. {
  505.     test_init_free();
  506.     test_push_pop();
  507.     test_insert_remove();
  508.  
  509.     show_push_pop();
  510.     show_insert_remove();
  511.     show_resize();
  512.     show_array_of_array();
  513.     return 0;
  514. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
<test_init_free>
..Okay
<test_push_pop>
..Okay
<test_insert_remove>
..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}
<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/M3rypm
language:
C (gcc 8.3)
created:
7 hours 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!