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