Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. // Copyright (c) 2015 Evan Teran
  2. // Copyright (c) 2020 Magomed Kostoev
  3. //
  4. // You may use, distribute and modify this code under the terms of the MIT license.
  5. //
  6. // You should have received a copy of the MIT license with this file. If not, please visit
  7. // https://opensource.org/licenses/MIT for full license details.
  8.  
  9. // cvec.h - std::vector (ish) implementation in C. Based on https://github.com/eteran/c-vector/.
  10. //
  11. // Unlike a real std::vector this one is implemented as a fat array, so metadata is placed inside
  12. // an allocated buffer itself.
  13. //
  14. // Configuration (definitions):
  15. // CVEC_TYPE:    Type of the vector's elements, after instantiation these functions will be visible
  16. //               as cvec_<CVEC_TYPE>_funcname, so no stars and subscripting marks allowed - named
  17. //               types only
  18. // CVEC_INST:    Instantiate the functions if defined
  19. // CVEC_LOGG:    Multiply capacity by CVEC_LOGG each expansion if defined (should be >= 1)
  20. // CVEC_ASSERT:  Replacement for assert from <assert.h>
  21. // CVEC_MALLOC:  Replacement for malloc from <stdlib.h>
  22. // CVEC_REALLOC: Replacement for realloc from <stdlib.h>
  23. // CVEC_FREE:    Replacement for free from <stdlib.h>
  24. // CVEC_OOBH:    Out-of-bounds handler (gets __func__, vector data address and index of overflow)
  25. // CVEC_OOBVAL:  Default value to return on out of bounds access
  26. //
  27. // Minimal definitions for declaration: CVEC_TYPE
  28. // Minimal definitions for instantiation: CVEC_TYPE, CVEC_INST, CVEC_OOBVAL if the type object
  29. // can't be represented by 0 value.
  30. //
  31. // WARNING: All used definitions will be undefined on header exit.
  32. //
  33. // Dependencies:
  34. // <stddef.h> or another source of size_t and ptrdiff_t
  35. // <stdint.h> or another source of SIZE_MAX
  36. // <stdlib.h> or another source of malloc, calloc and realloc
  37. // <assert.h> or another source of assert
  38.  
  39. //
  40. // Input macros
  41. //
  42.  
  43. #ifndef CVEC_LOGG
  44. #   define CVEC_LOGG 1.5
  45. #endif
  46. #ifndef CVEC_ASSERT
  47. #   define CVEC_ASSERT(x) assert(x)
  48. #endif
  49. #ifndef CVEC_MALLOC
  50. #   define CVEC_MALLOC(size) malloc(size)
  51. #endif
  52. #ifndef CVEC_REALLOC
  53. #   define CVEC_REALLOC(ptr, size) realloc(ptr, size)
  54. #endif
  55. #ifndef CVEC_FREE
  56. #   define CVEC_FREE(size) free(size)
  57. #endif
  58. #ifndef CVEC_OOBH
  59. #   define CVEC_OOBH(funcname, vec, index)
  60. #endif
  61. #ifndef CVEC_OOBVAL
  62. #   define CVEC_OOBVAL { 0 }
  63. #endif
  64.  
  65. //
  66. // Internal macros
  67. //
  68.  
  69. #define CVEC_CONCAT2_IMPL(x, y) cvec_ ## x ## _ ## y
  70. #define CVEC_CONCAT2(x, y) CVEC_CONCAT2_IMPL(x, y)
  71.  
  72. /// Creates method name according to CVEC_TYPE
  73. #define CVEC_FUN(name) CVEC_CONCAT2(CVEC_TYPE, name)
  74.  
  75. #define cvec_x_new CVEC_FUN(new)
  76. #define cvec_x_capacity CVEC_FUN(capacity)
  77. #define cvec_x_size CVEC_FUN(size)
  78. #define cvec_x_empty CVEC_FUN(empty)
  79. #define cvec_x_pop_back CVEC_FUN(pop_back)
  80. #define cvec_x_erase CVEC_FUN(erase)
  81. #define cvec_x_free CVEC_FUN(free)
  82. #define cvec_x_begin CVEC_FUN(begin)
  83. #define cvec_x_cbegin CVEC_FUN(cbegin)
  84. #define cvec_x_end CVEC_FUN(end)
  85. #define cvec_x_cend CVEC_FUN(cend)
  86. #define cvec_x_push_back CVEC_FUN(push_back)
  87. #define cvec_x_at CVEC_FUN(at)
  88. #define cvec_x_reserve CVEC_FUN(reserve)
  89. #define cvec_x_shrink_to_fit CVEC_FUN(shrink_to_fit)
  90. #define cvec_x_assign_fill CVEC_FUN(assign_fill)
  91. #define cvec_x_assign_range CVEC_FUN(assign_range)
  92. #define cvec_x_assign_other CVEC_FUN(assign_other)
  93. #define cvec_x_data CVEC_FUN(data)
  94. #define cvec_x_resize CVEC_FUN(resize)
  95. #define cvec_x_resize_v CVEC_FUN(resize_v)
  96. #define cvec_x_clear CVEC_FUN(clear)
  97. #define cvec_x_front CVEC_FUN(front)
  98. #define cvec_x_front_p CVEC_FUN(front_p)
  99. #define cvec_x_back CVEC_FUN(back)
  100. #define cvec_x_back_p CVEC_FUN(back_p)
  101. #define cvec_x_max_size CVEC_FUN(max_size)
  102. #define cvec_x_insert CVEC_FUN(insert)
  103. #define cvec_x_insert_it CVEC_FUN(insert_it)
  104.  
  105. #define cvec_x_grow CVEC_FUN(grow)
  106. #define cvec_x_set_capacity CVEC_FUN(set_capacity)
  107. #define cvec_x_set_size CVEC_FUN(set_size)
  108.  
  109. //
  110. // External declarations
  111. //
  112.  
  113. /// Allocates new vector of specified capacity.
  114. CVEC_TYPE *cvec_x_new(size_t count);
  115.  
  116. /// Gets the current capacity of the vector.
  117. size_t cvec_x_capacity(CVEC_TYPE **vec);
  118.  
  119. /// Gets the current size of the vector.
  120. size_t cvec_x_size(CVEC_TYPE **vec);
  121.  
  122. /// Returns non-zero if the vector is empty.
  123. int cvec_x_empty(CVEC_TYPE **vec);
  124.  
  125. /// Removes the last element from the vector.
  126. void cvec_x_pop_back(CVEC_TYPE **vec);
  127.  
  128. /// Removes the element at index i from the vector.
  129. void cvec_x_erase(CVEC_TYPE **vec, size_t i);
  130.  
  131. /// Frees all memory associated with the vector.
  132. void cvec_x_free(CVEC_TYPE **vec);
  133.  
  134. /// Returns an iterator to first element of the vector.
  135. CVEC_TYPE *cvec_x_begin(CVEC_TYPE **vec);
  136.  
  137. /// Returns a const iterator to first element of the vector
  138. const CVEC_TYPE *cvec_x_cbegin(CVEC_TYPE **vec);
  139.  
  140. /// Returns an iterator to one past the last element of the vector.
  141. CVEC_TYPE *cvec_x_end(CVEC_TYPE **vec);
  142.  
  143. /// Returns a const iterator to one past the last element of the vector.
  144. const CVEC_TYPE *cvec_x_cend(CVEC_TYPE **vec);
  145.  
  146. /// Adds an element to the end of the vector.
  147. void cvec_x_push_back(CVEC_TYPE **vec, CVEC_TYPE value);
  148.  
  149. /// Gets element with bounds checking. On out of bounds calls CVEC_OOBH and returns CVEC_OOBVAL.
  150. CVEC_TYPE cvec_x_at(CVEC_TYPE **vec, size_t i);
  151.  
  152. /// Increases the capacity of the vector to a value that's equal to new_cap.
  153. void cvec_x_reserve(CVEC_TYPE **vec, size_t new_cap);
  154.  
  155. /// Requests the removal of unused capacity.
  156. void cvec_x_shrink_to_fit(CVEC_TYPE **vec);
  157.  
  158. /// Replaces the contents with count copies of value value.
  159. void cvec_x_assign_fill(CVEC_TYPE **vec, size_t count, CVEC_TYPE value);
  160.  
  161. /// Replaces the contents with data from range [first, last).
  162. void cvec_x_assign_range(CVEC_TYPE **vec, CVEC_TYPE *first, CVEC_TYPE *last);
  163.  
  164. /// Replaces the contents with contetns of other.
  165. void cvec_x_assign_other(CVEC_TYPE **vec, CVEC_TYPE **other);
  166.  
  167. /// Gives direct access to buffer.
  168. CVEC_TYPE *cvec_x_data(CVEC_TYPE **vec);
  169.  
  170. /// Resizes the container to contain count elements.
  171. void cvec_x_resize(CVEC_TYPE **vec, size_t new_size);
  172.  
  173. /// Resizes the container to contain count elements, initializes new elements by value.
  174. void cvec_x_resize_v(CVEC_TYPE **vec, size_t new_size, CVEC_TYPE value);
  175.  
  176. /// Erases all elements from the container.
  177. void cvec_x_clear(CVEC_TYPE **vec);
  178.  
  179. /// Returns the first element of the vector.
  180. CVEC_TYPE cvec_x_front(CVEC_TYPE **vec);
  181.  
  182. /// Returns a pointer to the first element of the vector.
  183. CVEC_TYPE *cvec_x_front_p(CVEC_TYPE **vec);
  184.  
  185. /// Returns the last element of the vector.
  186. CVEC_TYPE cvec_x_back(CVEC_TYPE **vec);
  187.  
  188. /// Returns a pointer to the last element of the vector.
  189. CVEC_TYPE *cvec_x_back_p(CVEC_TYPE **vec);
  190.  
  191. /// Returns maximal size of the vector.
  192. size_t cvec_x_max_size(CVEC_TYPE **vec);
  193.  
  194. /// Inserts a value into vector by index.
  195. CVEC_TYPE *cvec_x_insert(CVEC_TYPE **vec, size_t index, CVEC_TYPE value);
  196.  
  197. /// Inserts a value into vector by iterator (pointer in vector).
  198. CVEC_TYPE *cvec_x_insert_it(CVEC_TYPE **vec, CVEC_TYPE *it, CVEC_TYPE value);
  199.  
  200. //
  201. // Function definitions
  202. //
  203.  
  204. #ifdef CVEC_INST
  205.  
  206. /// Ensures that the vector is at least <count> elements big.
  207. static void cvec_x_grow(CVEC_TYPE **vec, size_t count);
  208.  
  209. /// Sets the capacity variable of the vector.
  210. static void cvec_x_set_capacity(CVEC_TYPE **vec, size_t size);
  211.  
  212. /// Sets the size variable of the vector.
  213. static void cvec_x_set_size(CVEC_TYPE **vec, size_t size);
  214.  
  215. //
  216. // Public functions
  217. //
  218.  
  219. CVEC_TYPE *cvec_x_new(size_t count) {
  220.     const size_t cv_sz = count * sizeof(CVEC_TYPE) + sizeof(size_t) * 2;
  221.     size_t *cv_p = CVEC_MALLOC(cv_sz);
  222.     CVEC_ASSERT(cv_p);
  223.     CVEC_TYPE *vec = (void *)(&cv_p[2]);
  224.     cvec_x_set_capacity(&vec, count);
  225.     cvec_x_set_size(&vec, 0);
  226.     return vec;
  227. }
  228.  
  229. size_t cvec_x_capacity(CVEC_TYPE **vec) {
  230.     CVEC_ASSERT(vec);
  231.     return *vec ? ((size_t *)*vec)[-1] : (size_t)0;
  232. }
  233.  
  234. size_t cvec_x_size(CVEC_TYPE **vec) {
  235.     CVEC_ASSERT(vec);
  236.     return *vec ? ((size_t *)*vec)[-2] : (size_t)0;
  237. }
  238.  
  239. int cvec_x_empty(CVEC_TYPE **vec) {
  240.     return cvec_x_size(vec) == 0;
  241. }
  242.  
  243. void cvec_x_pop_back(CVEC_TYPE **vec) {
  244.     cvec_x_set_size(vec, cvec_x_size(vec) - 1);
  245. }
  246.  
  247. void cvec_x_erase(CVEC_TYPE **vec, size_t i) {
  248.     CVEC_ASSERT(vec);
  249.     if (*vec) {
  250.         const size_t cv_sz = cvec_x_size(vec);
  251.         if (i < cv_sz) {
  252.             cvec_x_set_size(vec, cv_sz - 1);
  253.             for (size_t cv_x = i; cv_x < (cv_sz - 1); ++cv_x) {
  254.                 (*vec)[cv_x] = (*vec)[cv_x + 1];
  255.             }
  256.         }
  257.     }
  258. }
  259.  
  260. void cvec_x_free(CVEC_TYPE **vec) {
  261.     CVEC_ASSERT(vec);
  262.     if (*vec) {
  263.         size_t *p1 = &((size_t *)*vec)[-2];
  264.         CVEC_FREE(p1);
  265.     }
  266. }
  267.  
  268. CVEC_TYPE *cvec_x_begin(CVEC_TYPE **vec) {
  269.     CVEC_ASSERT(vec);
  270.     return *vec;
  271. }
  272.  
  273. const CVEC_TYPE *cvec_x_cbegin(CVEC_TYPE **vec) {
  274.     return cvec_x_begin(vec);
  275. }
  276.  
  277. CVEC_TYPE *cvec_x_end(CVEC_TYPE **vec) {
  278.     CVEC_ASSERT(vec);
  279.     return *vec ? &((*vec)[cvec_x_size(vec)]) : NULL;
  280. }
  281.  
  282. const CVEC_TYPE *cvec_x_cend(CVEC_TYPE **vec) {
  283.     return cvec_x_end(vec);
  284. }
  285.  
  286. void cvec_x_push_back(CVEC_TYPE **vec, CVEC_TYPE value) {
  287.     CVEC_ASSERT(vec);
  288.     size_t cv_cap = cvec_x_capacity(vec);
  289.     if (cv_cap <= cvec_x_size(vec)) {
  290.         cvec_x_grow(vec, cv_cap * CVEC_LOGG + 1);
  291.     }
  292.     (*vec)[cvec_x_size(vec)] = value;
  293.     cvec_x_set_size(vec, cvec_x_size(vec) + 1);
  294. }
  295.  
  296. CVEC_TYPE cvec_x_at(CVEC_TYPE **vec, size_t i) {
  297.     CVEC_ASSERT(vec);
  298.     if (i >= cvec_x_size(vec) || i < 0) {
  299.         CVEC_OOBH(__func__, vec, i);
  300.         CVEC_TYPE ret = CVEC_OOBVAL;
  301.         return ret;
  302.     }
  303.     return (*vec)[i];
  304. }
  305.  
  306. void cvec_x_reserve(CVEC_TYPE **vec, size_t new_cap) {
  307.     if (new_cap <= cvec_x_capacity(vec)) {
  308.         return;
  309.     }
  310.     cvec_x_grow(vec, new_cap);
  311. }
  312.  
  313. void cvec_x_shrink_to_fit(CVEC_TYPE **vec) {
  314.     if (cvec_x_capacity(vec) > cvec_x_size(vec)) {
  315.         cvec_x_grow(vec, cvec_x_size(vec));
  316.     }
  317. }
  318.  
  319. void cvec_x_assign_fill(CVEC_TYPE **vec, size_t count, CVEC_TYPE value) {
  320.     CVEC_ASSERT(vec);
  321.     cvec_x_reserve(vec, count);
  322.     cvec_x_set_size(vec, count); // If the buffer was bigger than new_cap, set size ourselves
  323.     for (size_t i = 0; i < count; i++) {
  324.         (*vec)[i] = value;
  325.     }
  326. }
  327.  
  328. void cvec_x_assign_range(CVEC_TYPE **vec, CVEC_TYPE *first, CVEC_TYPE *last) {
  329.     CVEC_ASSERT(vec);
  330.     size_t new_size = ((ptrdiff_t)(last - first)) / sizeof(*first);
  331.     cvec_x_reserve(vec, new_size);
  332.     cvec_x_set_size(vec, new_size);
  333.     size_t i = 0;
  334.     for (CVEC_TYPE *it = first; it < last; it++, i++) {
  335.         (*vec)[i] = *it;
  336.     }
  337. }
  338.  
  339. void cvec_x_assign_other(CVEC_TYPE **vec, CVEC_TYPE **other) {
  340.     cvec_x_assign_range(vec, cvec_x_begin(other), cvec_x_end(other));
  341. }
  342.  
  343. CVEC_TYPE *cvec_x_data(CVEC_TYPE **vec) {
  344.     CVEC_ASSERT(vec);
  345.     return (*vec);
  346. }
  347.  
  348. void cvec_x_resize(CVEC_TYPE **vec, size_t count) {
  349.     CVEC_TYPE value = { 0 };
  350.     cvec_x_resize_v(vec, count, value);
  351. }
  352.  
  353. void cvec_x_resize_v(CVEC_TYPE **vec, size_t count, CVEC_TYPE value) {
  354.     CVEC_ASSERT(vec);
  355.     size_t old_size = cvec_x_size(vec);
  356.     cvec_x_set_size(vec, count);
  357.     if (cvec_x_capacity(vec) < count) {
  358.         cvec_x_reserve(vec, count);
  359.         for (CVEC_TYPE *it = (*vec) + old_size; it < cvec_x_end(vec); it++) {
  360.             *it = value;
  361.         }
  362.     }
  363. }
  364.  
  365. void cvec_x_clear(CVEC_TYPE **vec) {
  366.     cvec_x_set_size(vec, 0);
  367. }
  368.  
  369. CVEC_TYPE cvec_x_front(CVEC_TYPE **vec) {
  370.     CVEC_ASSERT(vec);
  371.     return (*vec)[0];
  372. }
  373.  
  374. CVEC_TYPE *cvec_x_front_p(CVEC_TYPE **vec) {
  375.     CVEC_ASSERT(vec);
  376.     return (*vec);
  377. }
  378.  
  379. CVEC_TYPE cvec_x_back(CVEC_TYPE **vec) {
  380.     return cvec_x_end(vec)[-1];
  381. }
  382.  
  383. CVEC_TYPE *cvec_x_back_p(CVEC_TYPE **vec) {
  384.     return cvec_x_end(vec) - 1;
  385. }
  386.  
  387. size_t cvec_x_max_size(CVEC_TYPE **vec) {
  388.     return SIZE_MAX / sizeof(**vec);
  389. }
  390.  
  391. CVEC_TYPE *cvec_x_insert(CVEC_TYPE **vec, size_t index, CVEC_TYPE value) {
  392.     CVEC_ASSERT(vec);
  393.     if (index > cvec_x_size(vec) || index < 0) {
  394.         return NULL; // TODO: What?
  395.     }
  396.     size_t new_size = cvec_x_size(vec) + 1;
  397.     cvec_x_reserve(vec, new_size);
  398.     cvec_x_set_size(vec, new_size);
  399.     CVEC_TYPE *ret = *vec + index;
  400.     for (CVEC_TYPE *it = cvec_x_back_p(vec); it > ret; it--) {
  401.         *it = it[-1];
  402.     }
  403.     *ret = value;
  404.     return ret;
  405. }
  406.  
  407. CVEC_TYPE *cvec_x_insert_it(CVEC_TYPE **vec, CVEC_TYPE *it, CVEC_TYPE value) {
  408.     CVEC_ASSERT(vec);
  409.     size_t index = (it - *vec) / sizeof(**vec);
  410.     return cvec_x_insert(vec, index, value);
  411. }
  412.  
  413. //
  414. // Private functions
  415. //
  416.  
  417. static void cvec_x_set_capacity(CVEC_TYPE **vec, size_t size) {
  418.     CVEC_ASSERT(vec);
  419.     if (*vec) {
  420.         ((size_t *)*vec)[-1] = size;
  421.     }
  422. }
  423.  
  424. static void cvec_x_set_size(CVEC_TYPE **vec, size_t size) {
  425.     CVEC_ASSERT(vec);
  426.     if (*vec) {
  427.         ((size_t *)*vec)[-2] = size;
  428.     }
  429. }
  430.  
  431. static void cvec_x_grow(CVEC_TYPE **vec, size_t count) {
  432.     CVEC_ASSERT(vec);
  433.     const size_t cv_sz = count * sizeof(**vec) + sizeof(size_t) * 2;
  434.     size_t *cv_p1 = &((size_t *)*vec)[-2];
  435.     size_t *cv_p2 = CVEC_REALLOC(cv_p1, (cv_sz));
  436.     CVEC_ASSERT(cv_p2);
  437.     *vec = (void *)(&cv_p2[2]);
  438.     cvec_x_set_capacity(vec, count);
  439. }
  440.  
  441. #endif
  442.  
  443. #undef CVEC_TYPE
  444.  
  445. #ifdef CVEC_INST
  446. #   undef CVEC_INST
  447. #   ifdef CVEC_LOGG
  448. #       undef CVEC_LOGG
  449. #   endif
  450. #   ifdef CVEC_OOBH
  451. #       undef CVEC_OOBH
  452. #   endif
  453. #   ifdef CVEC_OOBVAL
  454. #       undef CVEC_OOBVAL
  455. #   endif
  456. #   undef CVEC_ASSERT
  457. #   undef CVEC_MALLOC
  458. #   undef CVEC_REALLOC
  459. #   undef CVEC_FREE
  460. #endif
  461.  
  462. #undef CVEC_CONCAT2_IMPL
  463. #undef CVEC_CONCAT2
  464.  
  465. #undef CVEC_FUN
  466.  
  467. #undef cvec_x_new
  468. #undef cvec_x_capacity
  469. #undef cvec_x_size
  470. #undef cvec_x_empty
  471. #undef cvec_x_pop_back
  472. #undef cvec_x_erase
  473. #undef cvec_x_free
  474. #undef cvec_x_begin
  475. #undef cvec_x_cbegin
  476. #undef cvec_x_end
  477. #undef cvec_x_cend
  478. #undef cvec_x_push_back
  479. #undef cvec_x_at
  480. #undef cvec_x_reserve
  481. #undef cvec_x_shrink_to_fit
  482. #undef cvec_x_assign_fill
  483. #undef cvec_x_assign_range
  484. #undef cvec_x_assign_other
  485. #undef cvec_x_data
  486. #undef cvec_x_resize
  487. #undef cvec_x_resize_v
  488. #undef cvec_x_clear
  489. #undef cvec_x_front
  490. #undef cvec_x_front_p
  491. #undef cvec_x_back
  492. #undef cvec_x_back_p
  493. #undef cvec_x_max_size
  494. #undef cvec_x_insert
  495. #undef cvec_x_insert_it
  496. #undef cvec_x_grow
  497. #undef cvec_x_set_capacity
  498. #undef cvec_x_set_size
  499.