fork download
copy 
  1. // Hidden header style array. (2.20)
  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_reserve(a, n) ((a) = _ar_reserve(a, n, sizeof *(a)))
  33. #define ar_resize(a, n, v) ((a) = _ar_resize(a, n, (__typeof__(*(a))[]){v}, sizeof *(a)))
  34. #define ar_free(a) (_ar_free(a), (a) = 0)
  35. #define ar_init(a) ((a) = _ar_init())
  36. #define ar_init_size(a, n, v) ((a) = _ar_init_size(n, (__typeof__(*(a))[]){v}, sizeof *(a)))
  37. #define ar_init_copy(a, b) ((a) = _ar_init_copy(b, sizeof *(a)))
  38. #define ar_at(a, i) (ar_at_p(a, i)[0])
  39. #define ar_at_c(a, i) (ar_at_c_p(a, i)[0])
  40. #define ar_at_p(a, i) ((__typeof__(*(a))*)_ar_at(a, i, sizeof *(a)))
  41. #define ar_at_c_p(a, i) ((const __typeof__(*(a))*)_ar_at_c(a, i, sizeof *(a)))
  42. #define ar_remove(a, i, n) _ar_remove(a, i, n, sizeof *(a))
  43. #define ar_insert(a, i, s, n) ((a) = _ar_insert(a, i, s, n, sizeof *(a)))
  44. #define ar_push(a, v) ((a) = _ar_push(a, (__typeof__(*(a))[]){v}, sizeof *(a)))
  45. #define ar_pop(a) _ar_pop(a, sizeof *(a))
  46. #define ar_clear(a) _ar_clear(a, sizeof *(a))
  47.  
  48. size_t _ar_size(const void *p);
  49. size_t _ar_capacity(const void *p);
  50. void *_ar_reserve(void *p, size_t capacity, size_t itemsize);
  51. void *_ar_resize(void *p, size_t size, const void *fill, size_t itemsize);
  52. void _ar_free(void *p);
  53. void *_ar_init(void);
  54. void *_ar_init_size(size_t size, const void *fill, size_t itemsize);
  55. void *_ar_init_copy(const void *p, size_t itemsize);
  56. const void *_ar_at_c(const void *p, ptrdiff_t i, size_t itemsize);
  57. void *_ar_at(void *p, ptrdiff_t i, size_t itemsize);
  58. void _ar_remove(void *p, size_t i, size_t n, size_t itemsize);
  59. void *_ar_insert(void *p, size_t i, const void *first, size_t n, size_t itemsize);
  60. void *_ar_push(void *p, const void *item, size_t itemsize);
  61. void _ar_pop(void *p, size_t itemsize);
  62. void _ar_clear(void *p, size_t itemsize);
  63.  
  64. // Implementation.
  65.  
  66. typedef struct {
  67.     size_t size, capacity;
  68. } _Header;
  69.  
  70. #define _PTR_TO_HDR(p) ((_Header*)((char*)p - sizeof(_Header)))
  71. #define _HDR_TO_PTR(p) ((void*)((char*)p + sizeof(_Header)))
  72.  
  73. size_t _ar_size(const void *p)
  74. {
  75.     assert(p != 0);
  76.     return _PTR_TO_HDR(p)->size;
  77. }
  78.  
  79. size_t _ar_capacity(const void *p)
  80. {
  81.     assert(p != 0);
  82.     return _PTR_TO_HDR(p)->capacity;
  83. }
  84.  
  85. void *_ar_reserve(void *p, size_t capacity, size_t itemsize)
  86. {
  87.     assert(p != 0);
  88.     _Header *self = _PTR_TO_HDR(p);
  89.  
  90.     if (capacity > self->capacity)
  91.     {
  92.         self = realloc(self, sizeof *self + capacity*itemsize);
  93.         assert(self != 0);
  94.         self->capacity = capacity;
  95.     }
  96.     return _HDR_TO_PTR(self);
  97. }
  98.  
  99. void *_ar_resize(void *p, size_t size, const void *fill, size_t itemsize)
  100. {
  101.     assert(p != 0);
  102.     p = _ar_reserve(p, size, itemsize);
  103.  
  104.     _Header *self = _PTR_TO_HDR(p);
  105.     size_t oldsize = self->size;
  106.     self->size = size;
  107.  
  108.     if (fill != 0 && size > oldsize)
  109.         memfill(_ar_at(p, oldsize, itemsize), size - oldsize, itemsize, fill);
  110.     return p;
  111. }
  112.  
  113. void _ar_free(void *p)
  114. {
  115.     if (p != 0)
  116.         free(_PTR_TO_HDR(p));
  117. }
  118.  
  119. void *_ar_init(void)
  120. {
  121.     _Header *self = malloc(sizeof *self);
  122.     assert(self != 0);
  123.     self->size = 0;
  124.     self->capacity = 0;
  125.     return _HDR_TO_PTR(self);
  126. }
  127.  
  128. void *_ar_init_size(size_t size, const void *fill, size_t itemsize)
  129. {
  130.     return _ar_resize(_ar_init(), size, fill, itemsize);
  131. }
  132.  
  133. void *_ar_init_copy(const void *p, size_t itemsize)
  134. {
  135.     return _ar_insert(_ar_init(), 0, p, _ar_size(p), itemsize);
  136. }
  137.  
  138. const void *_ar_at_c(const void *p, ptrdiff_t i, size_t itemsize)
  139. {
  140.     size_t size = _ar_size(p);
  141.     size_t j = (i < 0) ? i + size : (size_t)i;
  142.     assert(j < size);
  143.     return (const char*)p + j*itemsize;
  144. }
  145.  
  146. void *_ar_at(void *p, ptrdiff_t i, size_t itemsize)
  147. {
  148.     return (void*)_ar_at_c(p, i, itemsize);
  149. }
  150.  
  151. void _ar_remove(void *p, size_t i, size_t n, size_t itemsize)
  152. {
  153.     assert(p != 0);
  154.     _Header *self = _PTR_TO_HDR(p);
  155.  
  156.     size_t oldsize = self->size;
  157.     assert(oldsize >= i);
  158.  
  159.     if (n != 0)
  160.     {
  161.         size_t j;
  162.         if (__builtin_add_overflow(i, n, &j))
  163.             assert(0 && "integer overflow");
  164.         assert(oldsize >= j);
  165.  
  166.         if (oldsize > j)
  167.             memmove(_ar_at(p, i, itemsize), _ar_at(p, j, itemsize), (oldsize - j)*itemsize);
  168.         self->size = oldsize - n;
  169.     }
  170. }
  171.  
  172. void *_ar_insert(void *p, size_t i, const void *first, size_t n, size_t itemsize)
  173. {
  174.     assert(p != 0);
  175.     _Header *self = _PTR_TO_HDR(p);
  176.  
  177.     size_t oldsize = self->size;
  178.     assert(oldsize >= i);
  179.  
  180.     if (n != 0)
  181.     {
  182.         size_t newsize;
  183.         if (__builtin_add_overflow(oldsize, n, &newsize))
  184.             assert(0 && "integer overflow");
  185.  
  186.         if (newsize > self->capacity)
  187.         {
  188.             p = _ar_reserve(p, MAX(2*self->capacity, newsize), itemsize);
  189.             self = _PTR_TO_HDR(p);
  190.         }
  191.         self->size = newsize;
  192.         void *ip = _ar_at(p, i, itemsize);
  193.  
  194.         if (oldsize > i)
  195.             memmove(_ar_at(p, i + n, itemsize), ip, (oldsize - i)*itemsize);
  196.         memcpy(ip, first, n*itemsize);
  197.     }
  198.     return p;
  199. }
  200.  
  201. void *_ar_push(void *p, const void *item, size_t itemsize)
  202. {
  203.     return _ar_insert(p, _ar_size(p), item, 1, itemsize);
  204. }
  205.  
  206. void _ar_pop(void *p, size_t itemsize)
  207. {
  208.     _ar_remove(p, _ar_size(p)-1, 1, itemsize);
  209. }
  210.  
  211. void _ar_clear(void *p, size_t itemsize)
  212. {
  213.     _ar_resize(p, 0, 0, itemsize);
  214. }
  215.  
  216. // Main.
  217.  
  218. void ar_print(const int *p)
  219. {
  220.     printf("size/capacity: %zu/%zu [", ar_size(p), ar_capacity(p));
  221.     for (size_t i = 0; i < ar_size(p); i++)
  222.     {
  223.         printf(i ? ", %d" : "%d", p[i]);
  224.     }
  225.     puts("]");
  226. }
  227.  
  228. void test_init_free(void)
  229. {
  230.     // Init.
  231.  
  232.     int *p = 0;
  233.     ar_init(p);
  234.     assert(ar_size(p) == 0);
  235.     ar_free(p);
  236.     assert(p == 0);
  237.  
  238.     // Init size.
  239.  
  240.     ar_init_size(p, 3, 123);
  241.     assert(ar_size(p) == 3);
  242.     for (size_t i = 0; i < 3; i++)
  243.         assert(ar_at(p, i) == 123);
  244.  
  245.     // Init copy.
  246.  
  247.     int *q = 0;
  248.     ar_init_copy(q, p);
  249.     ar_free(p);
  250.     assert(p == 0);
  251.  
  252.     assert(ar_size(q) == 3);
  253.     for (size_t i = 0; i < 3; i++)
  254.         assert(ar_at(q, i) == 123);
  255.     ar_free(q);
  256.     assert(q == 0);
  257.  
  258.     printf("%s: Okay.\n", __func__);
  259. }
  260.  
  261. void test_push_pop(void)
  262. {
  263.     int *p = 0;
  264.     ar_init(p);
  265.  
  266.     // Push (back).
  267.  
  268.     for (int i = 0; i < 8; i++)
  269.     {
  270.         assert(ar_size(p) == i);
  271.         int cp2 = i ? 1<<(31 - __builtin_clz(2*i-1)) : 0;
  272.         assert(ar_capacity(p) == cp2);
  273.         ar_push(p, i);
  274.         assert(ar_at(p, -1) == i);
  275.     }
  276.  
  277.     // Pop (back).
  278.  
  279.     for (int i = 7; i >= 0; i--)
  280.     {
  281.         assert(ar_at(p, -1) == i);
  282.         ar_pop(p);
  283.     }
  284.     assert(ar_size(p) == 0);
  285.     ar_free(p);
  286.  
  287.     printf("%s: Okay.\n", __func__);
  288. }
  289.  
  290. void test_insert_remove(void)
  291. {
  292.     int *p = 0;
  293.     ar_init(p);
  294.  
  295.     // Insert even (bulk).
  296.  
  297.     ar_insert(p, 0, ((int[]){0, 2, 4}), 3);
  298.     assert(ar_size(p) == 3);
  299.     for (int i = 0; i < 3; i++)
  300.         assert(ar_at(p, i) == 2*i);
  301.  
  302.     // Insert odd (single).
  303.  
  304.     for (int i = 0; i < 3; i++)
  305.         ar_insert(p, 2*i+1, (int[]){2*i+1}, 1);
  306.     assert(ar_size(p) == 6);
  307.     for (int i = 0; i < 6; i++)
  308.         assert(ar_at(p, i) == i);
  309.  
  310.     // Remove even (single).
  311.  
  312.     for (int i = 2; i >= 0; i--)
  313.         ar_remove(p, 2*i, 1);
  314.     assert(ar_size(p) == 3);
  315.     for (int i = 0; i < 3; i++)
  316.         assert(ar_at(p, i) == 2*i+1);
  317.  
  318.     // Remove odd (bulk).
  319.  
  320.     ar_remove(p, 0, 3);
  321.     assert(ar_size(p) == 0);
  322.     ar_free(p);
  323.  
  324.     printf("%s: Okay.\n", __func__);
  325. }
  326.  
  327. int main(void)
  328. {
  329.     test_init_free();
  330.     test_push_pop();
  331.     test_insert_remove();
  332.  
  333.     int *p = 0;
  334.     ar_init(p);
  335.  
  336.     int n = 5;
  337.  
  338.     // Push/Pop (back).
  339.  
  340.     for (int i = 0; i < n; i++)
  341.     {
  342.         ar_push(p, i);
  343.         ar_print(p);
  344.     }
  345.     while (ar_size(p) != 0)
  346.     {
  347.         ar_pop(p);
  348.         ar_print(p);
  349.     }
  350.  
  351.     // Insert/Erase.
  352.  
  353.     for (int i = 0; i < n; i++)
  354.     {
  355.         ar_insert(p, i, ((int[]){i+1, i+1+n}), 2);
  356.         ar_print(p);
  357.     }
  358.     for (int i = n-1; i >= 0; i--)
  359.     {
  360.         ar_remove(p, i, 2);
  361.         ar_print(p);
  362.     }
  363.  
  364.     // Resize (fill).
  365.  
  366.     for (int i = 1; i < n; i++)
  367.     {
  368.         ar_clear(p);
  369.         ar_resize(p, i, -i);
  370.         ar_print(p);
  371.     }
  372.  
  373.     ar_free(p);
  374.     return 0;
  375. }
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.
size/capacity: 1/1 [0]
size/capacity: 2/2 [0, 1]
size/capacity: 3/4 [0, 1, 2]
size/capacity: 4/4 [0, 1, 2, 3]
size/capacity: 5/8 [0, 1, 2, 3, 4]
size/capacity: 4/8 [0, 1, 2, 3]
size/capacity: 3/8 [0, 1, 2]
size/capacity: 2/8 [0, 1]
size/capacity: 1/8 [0]
size/capacity: 0/8 []
size/capacity: 2/8 [1, 6]
size/capacity: 4/8 [1, 2, 7, 6]
size/capacity: 6/8 [1, 2, 3, 8, 7, 6]
size/capacity: 8/8 [1, 2, 3, 4, 9, 8, 7, 6]
size/capacity: 10/16 [1, 2, 3, 4, 5, 10, 9, 8, 7, 6]
size/capacity: 8/16 [1, 2, 3, 4, 9, 8, 7, 6]
size/capacity: 6/16 [1, 2, 3, 8, 7, 6]
size/capacity: 4/16 [1, 2, 7, 6]
size/capacity: 2/16 [1, 6]
size/capacity: 0/16 []
size/capacity: 1/16 [-1]
size/capacity: 2/16 [-2, -2]
size/capacity: 3/16 [-3, -3, -3]
size/capacity: 4/16 [-4, -4, -4, -4]
https://ideone.com/X7n1Az
language:
C (gcc 8.3)
created:
3 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!