API tools faq
paste
chemoelectric

immutable vectors: my old implementation for Guile 2.0

chemoelectric
Mar 24th, 2026
454
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 76.83 KB | Source Code | 0 0
raw download clone embed print report
  1. /*
  2.  * Copyright (C) 2015 Khaled Hosny and Barry Schwartz
  3.  *
  4.  * This file is part of Sorts Mill Core Library.
  5.  *
  6.  * Sorts Mill Core Library is free software; you can redistribute it and/or modify
  7.  * it under the terms of the GNU General Public License as published by
  8.  * the Free Software Foundation; either version 3 of the License, or
  9.  * (at your option) any later version.
  10.  *
  11.  * Sorts Mill Core Library is distributed in the hope that it will be useful,
  12.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.  * GNU General Public License for more details.
  15.  *
  16.  * You should have received a copy of the GNU General Public License
  17.  * along with this program; if not, see <http://www.gnu.org/licenses/>.
  18.  */
  19.  
  20. #ifndef SORTSMILL_CORE_IMMUTABLE_VECTORS_H_
  21. #define SORTSMILL_CORE_IMMUTABLE_VECTORS_H_
  22.  
  23. #if CHECKING_IMMUTABLE_VECTOR_STRUCTURE__ && defined NDEBUG
  24. #error CHECKING_IMMUTABLE_VECTOR_STRUCTURE__ is incompatible with NDEBUG.
  25. #endif
  26.  
  27. #include <assert.h>
  28. #include <stdbool.h>
  29. #include <stdlib.h>
  30. #include <stdio.h>
  31. #include <stdint.h>
  32. #include <string.h>
  33. #include <sortsmill/core/attributes.h>
  34. #include <sortsmill/core/xgc.h>
  35.  
  36. #ifdef __cplusplus
  37. extern "C"
  38. {
  39. #endif
  40. #if 0
  41. }
  42. #endif
  43.  
  44. /*--------------------------------------------------------------------*/
  45.  
  46. /*
  47.  * The current implementation uses ordinary tries with tails (as
  48.  * opposed to, for instance, RRB-trees).
  49.  *
  50.  * Reference:
  51.  *
  52.  * @mastersthesis{lorange2014rrb,
  53.  *   author = {L'orange, Jean Niklas},
  54.  *   title  = {{Improving RRB-Tree Performance through Transience}},
  55.  *   school = {Norwegian University of Science and Technology},
  56.  *   year   = {2014},
  57.  *   month  = {June}}
  58.  *
  59.  * <http://hypirion.com/thesis>
  60.  */
  61.  
  62. /*
  63.  * NOTE: On account of how Boehm GC works, we cannot play optimization
  64.  * tricks such as using the least significant bit of a pointer as a
  65.  * flag. Do not be tempted, even if you are willing to assume all
  66.  * the structures pointed to have alignments on even addresses.
  67.  */
  68.  
  69. /*
  70.  * WARNING/NOTICE: The internals here are designed to match those of
  71.  * sortsmill/core/SATS/immutable_vectors.sats. Do not change the
  72.  * structure layout unless you know what you are doing.
  73.  */
  74.  
  75. /*--------------------------------------------------------------------*/
  76.  
  77. /* Returns the length of an immutable vector of any entry type. */
  78. inline size_t smcore_immutable_vector_length (void *ivect);
  79. inline size_t
  80. smcore_immutable_vector_length (void *ivect)
  81. {
  82.   typedef struct { size_t length; } ivect_t;
  83.   return (ivect == (void *) 0) ? 0 : (((ivect_t *) ivect)->length);
  84. }
  85.  
  86. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_T(MODIFIER, T, ENTRY_T, BITS)   \
  87.                                                                         \
  88.   typedef struct                                                        \
  89.   {                                                                     \
  90.     void *a[((size_t) 1) << (BITS)];                                    \
  91.   } T##__internal__;                                                    \
  92.                                                                         \
  93.   typedef struct                                                        \
  94.   {                                                                     \
  95.     ENTRY_T a[((size_t) 1) << (BITS)];                                  \
  96.   } T##__leaf__;                                                        \
  97.                                                                         \
  98.   typedef struct                                                        \
  99.   {                                                                     \
  100.     size_t length;                                                      \
  101.     unsigned char shift;                                                \
  102.     void *node;                                                         \
  103.     T##__leaf__ *tail;                                                  \
  104.   } T##__vector__;                                                      \
  105.                                                                         \
  106.   typedef T##__vector__ *T;                                             \
  107.                                                                         \
  108.   MODIFIER inline size_t T##__tail_length0__ (T);                       \
  109.   MODIFIER inline size_t                                                \
  110.   T##__tail_length0__ (T vec)                                           \
  111.   {                                                                     \
  112.     /* Return zero if the tail is full;  */                             \
  113.     /* otherwise return the tail length. */                             \
  114.     return vec->length & ((((size_t) 1) << (BITS)) - 1);                \
  115.   }                                                                     \
  116.                                                                         \
  117.   MODIFIER inline size_t T##__tail_length__ (T);                        \
  118.   MODIFIER inline size_t                                                \
  119.   T##__tail_length__ (T vec)                                            \
  120.   {                                                                     \
  121.     const size_t n = vec->length & ((((size_t) 1) << (BITS)) - 1);      \
  122.     return (n == 0) ? (((size_t) 1) << (BITS)) : n;                     \
  123.   }
  124. /*                                              */
  125. #if !CHECKING_IMMUTABLE_VECTOR_STRUCTURE__ /*   */
  126. /*                                              */
  127. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_T(MODIFIER, T, ENTRY_T, BITS)    \
  128.   MODIFIER size_t T##__tail_length0__ (T);                              \
  129.   MODIFIER size_t T##__tail_length__ (T);                               \
  130.   static inline void T##__check_structure__ (T vec)                     \
  131.   {                                                                     \
  132.     /* Do nothing. */                                                   \
  133.   }
  134. /*                                              */
  135. #else /* CHECKING_IMMUTABLE_VECTOR_STRUCTURE__  */
  136. /*                                              */
  137. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_T(MODIFIER, T, ENTRY_T, BITS)    \
  138.   MODIFIER size_t T##__tail_length0__ (T);                              \
  139.   MODIFIER size_t T##__tail_length__ (T);                               \
  140.   static void                                                           \
  141.   T##__check_fully_dense__ (void *p, size_t s)                          \
  142.   {                                                                     \
  143.     if (s != 0)                                                         \
  144.       {                                                                 \
  145.         T##__internal__ *const q = p;                                   \
  146.         /* Walk the tree. All entries should be non-NULL. */            \
  147.         for (size_t k = 0; k < (((size_t) 1) << (BITS)); k++)           \
  148.           {                                                             \
  149.             assert (q->a[k] != (void *) 0);                             \
  150.             T##__check_fully_dense__ (q->a[k], s - (BITS));             \
  151.           }                                                             \
  152.       }                                                                 \
  153.   }                                                                     \
  154.   static void                                                           \
  155.   T##__check_structure__ (T vec)                                        \
  156.   {                                                                     \
  157.     if (vec != NULL)                                                    \
  158.       {                                                                 \
  159.         assert (vec->length != 0);                                      \
  160.                                                                         \
  161.         const size_t mask = ((((size_t) 1) << (BITS)) - 1);             \
  162.         const size_t tail_length = T##__tail_length__ (vec);            \
  163.                                                                         \
  164.         /* Check the tail. */                                           \
  165.         assert (tail_length <= vec->length);                            \
  166.         assert (vec->tail != (T##__leaf__ *) 0);                        \
  167.                                                                         \
  168.         /* Check the trie. */                                           \
  169.         if (tail_length == vec->length)                                 \
  170.           assert (vec->node == (void *) 0);                             \
  171.         else                                                            \
  172.           {                                                             \
  173.             /* The last entry in the trie. */                           \
  174.             const size_t i = vec->length - tail_length - 1;             \
  175.                                                                         \
  176.             void *p = vec->node;                                        \
  177.             for (size_t s = vec->shift; s != 0; s -= (BITS))            \
  178.               {                                                         \
  179.                 const size_t index = (i >> s) & mask;                   \
  180.                 T##__internal__ *const q = p;                           \
  181.                 for (size_t k = 0; k < index; k++)                      \
  182.                   {                                                     \
  183.                     assert (q->a[k] != (void *) 0);                     \
  184.                     T##__check_fully_dense__ (q->a[k], s - (BITS));     \
  185.                   }                                                     \
  186.                 assert (q->a[index] != (void *) 0);                     \
  187.                 for (size_t k = index + 1; k <= mask; k++)              \
  188.                   assert (q->a[k] == (void *) 0);                       \
  189.                 p = q->a[index];                                        \
  190.               }                                                         \
  191.           }                                                             \
  192.       }                                                                 \
  193.   }
  194. /*                                              */
  195. #endif /* CHECKING_IMMUTABLE_VECTOR_STRUCTURE__ */
  196. /*                                              */
  197.  
  198. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_LENGTH(MODIFIER, NAME, T)       \
  199.   MODIFIER inline size_t NAME (T);                                      \
  200.   MODIFIER inline size_t                                                \
  201.   NAME (T vec)                                                          \
  202.   {                                                                     \
  203.     return (vec == (void *) 0) ? 0 : vec->length;                       \
  204.   }
  205. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_LENGTH(MODIFIER, NAME, T)        \
  206.   MODIFIER size_t NAME (T);
  207.  
  208. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_REF(MODIFIER, NAME, T, ENTRY_T, \
  209.                                             BITS)                       \
  210.   MODIFIER inline ENTRY_T NAME (T, size_t);                             \
  211.   MODIFIER inline ENTRY_T                                               \
  212.   NAME (T vec, size_t i)                                                \
  213.   {                                                                     \
  214.     assert (vec != (void *) 0 && i < vec->length);                      \
  215.     ENTRY_T value;                                                      \
  216.     const size_t tail_length = T##__tail_length__ (vec);                \
  217.     if (vec->length - tail_length <= i)                                 \
  218.       {                                                                 \
  219.         /* The desired entry is in the tail. */                         \
  220.         value = vec->tail->a[i - (vec->length - tail_length)];          \
  221.       }                                                                 \
  222.     else                                                                \
  223.       {                                                                 \
  224.         const size_t mask = (((size_t) 1) << (BITS)) - 1;               \
  225.         void *p = vec->node;                                            \
  226.         for (size_t s = vec->shift; s != 0; s -= (BITS))                \
  227.           {                                                             \
  228.             T##__internal__ *const q = p;                               \
  229.             p = q->a[(i >> s) & mask];                                  \
  230.           }                                                             \
  231.         value = ((T##__leaf__ *) p)->a[i & mask];                       \
  232.       }                                                                 \
  233.     return value;                                                       \
  234.   }
  235. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_REF(MODIFIER, NAME, T, ENTRY_T,  \
  236.                                            BITS)                        \
  237.   MODIFIER ENTRY_T NAME (T, size_t);
  238.  
  239. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_PTR(MODIFIER, NAME, T, ENTRY_T, \
  240.                                             BITS)                       \
  241.   MODIFIER inline const ENTRY_T *NAME (T, size_t);                      \
  242.   MODIFIER inline const ENTRY_T *                                       \
  243.   NAME (T vec, size_t i)                                                \
  244.   {                                                                     \
  245.     const ENTRY_T *ptr;                                                 \
  246.     if (vec != (void *) 0 && i < vec->length)                           \
  247.       {                                                                 \
  248.         const size_t tail_length = T##__tail_length__ (vec);            \
  249.         if (vec->length - tail_length <= i)                             \
  250.           {                                                             \
  251.             /* The desired entry is in the tail. */                     \
  252.             ptr = &vec->tail->a[i - (vec->length - tail_length)];       \
  253.           }                                                             \
  254.         else                                                            \
  255.           {                                                             \
  256.             const size_t mask = (((size_t) 1) << (BITS)) - 1;           \
  257.             void *p = vec->node;                                        \
  258.             for (size_t s = vec->shift; s != 0; s -= (BITS))            \
  259.               {                                                         \
  260.                 T##__internal__ *const q = p;                           \
  261.                 p = q->a[(i >> s) & mask];                              \
  262.               }                                                         \
  263.             ptr = &((T##__leaf__ *) p)->a[i & mask];                    \
  264.           }                                                             \
  265.       }                                                                 \
  266.     else                                                                \
  267.       ptr = (const ENTRY_T *) 0;                                        \
  268.     return ptr;                                                         \
  269.   }
  270. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_PTR(MODIFIER, NAME, T, ENTRY_T,  \
  271.                                            BITS)                        \
  272.   MODIFIER const ENTRY_T *NAME (T, size_t);
  273.  
  274. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_NEXT(MODIFIER, NAME, T, ENTRY_T, \
  275.                                              BITS)                      \
  276.   MODIFIER inline const ENTRY_T *NAME (T, size_t, const ENTRY_T *);     \
  277.   MODIFIER inline const ENTRY_T *                                       \
  278.   NAME (T vec, size_t i, const ENTRY_T *current)                        \
  279.   {                                                                     \
  280.     const ENTRY_T *next;                                                \
  281.     if (vec != (void *) 0 && i < vec->length - 1)                       \
  282.       {                                                                 \
  283.         i++;                                                            \
  284.         const size_t mask = (((size_t) 1) << (BITS)) - 1;               \
  285.         if ((i & mask) == 0)                                            \
  286.           {                                                             \
  287.             const size_t tail_length = T##__tail_length__ (vec);        \
  288.             if (vec->length - tail_length <= i)                         \
  289.               {                                                         \
  290.                 /* The desired entry is in the tail. */                 \
  291.                 next = &vec->tail->a[i - (vec->length - tail_length)];  \
  292.               }                                                         \
  293.             else                                                        \
  294.               {                                                         \
  295.                 void *p = vec->node;                                    \
  296.                 for (size_t s = vec->shift; s != 0; s -= (BITS))        \
  297.                   {                                                     \
  298.                     T##__internal__ *const q = p;                       \
  299.                     p = q->a[(i >> s) & mask];                          \
  300.                   }                                                     \
  301.                 next = &((T##__leaf__ *) p)->a[0];                      \
  302.               }                                                         \
  303.           }                                                             \
  304.         else                                                            \
  305.           next = current + 1;                                           \
  306.       }                                                                 \
  307.     else                                                                \
  308.       next = (const ENTRY_T *) 0;                                       \
  309.     return next;                                                        \
  310.   }
  311. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_NEXT(MODIFIER, NAME, T, ENTRY_T, \
  312.                                             BITS)                       \
  313.   MODIFIER const ENTRY_T *NAME (T, size_t, const ENTRY_T *);
  314.  
  315. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_PREV(MODIFIER, NAME, T, ENTRY_T, \
  316.                                              BITS)                      \
  317.   MODIFIER inline const ENTRY_T *NAME (T, size_t, const ENTRY_T *);     \
  318.   MODIFIER inline const ENTRY_T *                                       \
  319.   NAME (T vec, size_t i, const ENTRY_T *current)                        \
  320.   {                                                                     \
  321.     const ENTRY_T *prev;                                                \
  322.     if (vec == (void *) 0 || i == 0)                                    \
  323.       prev = (const ENTRY_T *) 0;                                       \
  324.     else                                                                \
  325.       {                                                                 \
  326.         const size_t mask = (((size_t) 1) << (BITS)) - 1;               \
  327.         if ((i & mask) == 0)                                            \
  328.           {                                                             \
  329.             i--;                                                        \
  330.             void *p = vec->node;                                        \
  331.             for (size_t s = vec->shift; s != 0; s -= (BITS))            \
  332.               {                                                         \
  333.                 T##__internal__ *const q = p;                           \
  334.                 p = q->a[(i >> s) & mask];                              \
  335.               }                                                         \
  336.             prev = &((T##__leaf__ *) p)->a[i & mask];                   \
  337.           }                                                             \
  338.         else                                                            \
  339.           prev = current - 1;                                           \
  340.       }                                                                 \
  341.     return prev;                                                        \
  342.   }
  343. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_PREV(MODIFIER, NAME, T, ENTRY_T, \
  344.                                             BITS)                       \
  345.   MODIFIER const ENTRY_T *NAME (T, size_t, const ENTRY_T *);
  346.  
  347. /* FIXME: Rewrite REFS to have tighter loops. */
  348. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_REFS(MODIFIER, NAME, T, \
  349.                                              ENTRY_T, BITS)     \
  350.   MODIFIER void NAME (T, size_t, size_t n, ENTRY_T x[n]);
  351. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_REFS(MODIFIER, NAME, T,          \
  352.                                             ENTRY_T, BITS,              \
  353.                                             IVECT_PTR, IVECT_NEXT)      \
  354.   MODIFIER void                                                         \
  355.   NAME (T vec, size_t i, size_t n, ENTRY_T x[n])                        \
  356.   {                                                                     \
  357.     assert ((vec == NULL) ? (i + n == 0) : (i + n <= vec->length));     \
  358.     const ENTRY_T *p = IVECT_PTR (vec, i);                              \
  359.     size_t k = 0;                                                       \
  360.     while (k < n)                                                       \
  361.       {                                                                 \
  362.         x[k] = *p;                                                      \
  363.         p = IVECT_NEXT (vec, i + k, p);                                 \
  364.         k++;                                                            \
  365.       }                                                                 \
  366.   }
  367.  
  368. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_SET(MODIFIER, NAME, T, ENTRY_T, \
  369.                                             BITS)                       \
  370.   MODIFIER T NAME (T, size_t, ENTRY_T);
  371. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_SET(MODIFIER, NAME, T, ENTRY_T,  \
  372.                                            BITS,                        \
  373.                                            POINTERS_MALLOC,             \
  374.                                            ENTRIES_MALLOC)              \
  375.   MODIFIER T                                                            \
  376.   NAME (T vec, size_t i, ENTRY_T x)                                     \
  377.   {                                                                     \
  378.     assert (vec != (void *) 0 && i < vec->length);                      \
  379.                                                                         \
  380.     /* Make a new root. */                                              \
  381.     T##__vector__ *const vec_ =                                         \
  382.       POINTERS_MALLOC (sizeof (T##__vector__));                         \
  383.     *vec_ = *vec;                                                       \
  384.     void **parent = &vec_->node;                                        \
  385.                                                                         \
  386.     const size_t tail_length = T##__tail_length__ (vec_);               \
  387.     if (vec_->length - tail_length <= i)                                \
  388.       {                                                                 \
  389.         /* The desired entry is in the tail. Make a new tail. */        \
  390.         T##__leaf__ *const entries =                                    \
  391.           ENTRIES_MALLOC (sizeof (T##__leaf__));                        \
  392.         *entries = *vec_->tail;                                         \
  393.         vec_->tail = entries;                                           \
  394.         entries->a[i - (vec_->length - tail_length)] = x;               \
  395.       }                                                                 \
  396.     else                                                                \
  397.       {                                                                 \
  398.         /* Make new internal nodes. */                                  \
  399.         void *p = vec_->node;                                           \
  400.         for (size_t s = vec_->shift; s != 0; s -= (BITS))               \
  401.           {                                                             \
  402.             T##__internal__ *const q =                                  \
  403.               POINTERS_MALLOC (sizeof (T##__internal__));               \
  404.             *q = *(T##__internal__ *) p;                                \
  405.             *parent = q;                                                \
  406.             parent = &q->a[(i >> s) & ((((size_t) 1) << (BITS)) - 1)];  \
  407.             p = *parent;                                                \
  408.           }                                                             \
  409.                                                                         \
  410.         /* Make a new leaf node. */                                     \
  411.         T##__leaf__ *const entries =                                    \
  412.           ENTRIES_MALLOC (sizeof (T##__leaf__));                        \
  413.         *entries = *(T##__leaf__ *) p;                                  \
  414.         entries->a[i & ((((size_t) 1) << (BITS)) - 1)] = x;             \
  415.         *parent = entries;                                              \
  416.       }                                                                 \
  417.                                                                         \
  418.     T##__check_structure__ (vec_);                                      \
  419.                                                                         \
  420.     return vec_;                                                        \
  421.   }
  422.  
  423. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_SETS(MODIFIER, NAME, T, \
  424.                                              ENTRY_T, BITS)     \
  425.   MODIFIER T NAME (T, size_t, size_t n, const ENTRY_T x[n]);
  426. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_SETS(MODIFIER, NAME, T, ENTRY_T, \
  427.                                             BITS,                       \
  428.                                             POINTERS_MALLOC,            \
  429.                                             ENTRIES_MALLOC)             \
  430.   MODIFIER T                                                            \
  431.   NAME (T vec, size_t i, size_t n, const ENTRY_T x[n])                  \
  432.   {                                                                     \
  433.     if (0 < n)                                                          \
  434.       {                                                                 \
  435.         assert (vec != (void *) 0);                                     \
  436.         assert (n <= vec->length);                                      \
  437.         assert (i <= vec->length - n);                                  \
  438.                                                                         \
  439.         const size_t end = i + n;                                       \
  440.         const ENTRY_T *chunk = x;                                       \
  441.         while (i != end)                                                \
  442.           {                                                             \
  443.             size_t j =                                                  \
  444.               ((i + (((size_t) 1) << (BITS))) / (((size_t) 1) << (BITS))) * \
  445.               (((size_t) 1) << (BITS));                                 \
  446.             if (end < j)                                                \
  447.               j = end;                                                  \
  448.                                                                         \
  449.             /* Make a new root. */                                      \
  450.             T##__vector__ *const vec_ =                                 \
  451.               POINTERS_MALLOC (sizeof (T##__vector__));                 \
  452.             *vec_ = *vec;                                               \
  453.             void **parent = &vec_->node;                                \
  454.                                                                         \
  455.             const size_t tail_length = T##__tail_length__ (vec_);       \
  456.             if (vec_->length - tail_length <= i)                        \
  457.               {                                                         \
  458.                 /* The desired entries are in the tail. */              \
  459.                 /* Make a new tail.                     */              \
  460.                 T##__leaf__ *const entries =                            \
  461.                   ENTRIES_MALLOC (sizeof (T##__leaf__));                \
  462.                 *entries = *vec_->tail;                                 \
  463.                 vec_->tail = entries;                                   \
  464.                 memcpy (&entries->a[i - (vec_->length - tail_length)],  \
  465.                         chunk, (j - i) * sizeof (ENTRY_T));             \
  466.               }                                                         \
  467.             else                                                        \
  468.               {                                                         \
  469.                 /* Make new internal nodes. */                          \
  470.                 void *p = vec_->node;                                   \
  471.                 for (size_t s = vec_->shift; s != 0; s -= (BITS))       \
  472.                   {                                                     \
  473.                     T##__internal__ *const q =                          \
  474.                       POINTERS_MALLOC (sizeof (T##__internal__));       \
  475.                     *q = *(T##__internal__ *) p;                        \
  476.                     *parent = q;                                        \
  477.                     parent =                                            \
  478.                       &q->a[(i >> s) & ((((size_t) 1) << (BITS)) - 1)]; \
  479.                     p = *parent;                                        \
  480.                   }                                                     \
  481.                                                                         \
  482.                 /* Make a new leaf node. */                             \
  483.                 T##__leaf__ *const entries =                            \
  484.                   ENTRIES_MALLOC (sizeof (T##__leaf__));                \
  485.                 *entries = *(T##__leaf__ *) p;                          \
  486.                 memcpy (&entries->a[i & ((((size_t) 1) << (BITS)) - 1)], \
  487.                         chunk, (j - i) * sizeof (ENTRY_T));             \
  488.                 *parent = entries;                                      \
  489.               }                                                         \
  490.                                                                         \
  491.             vec = vec_;                                                 \
  492.             chunk += j - i;                                             \
  493.             i = j;                                                      \
  494.           }                                                             \
  495.                                                                         \
  496.         T##__check_structure__ (vec);                                   \
  497.       }                                                                 \
  498.                                                                         \
  499.     return vec;                                                         \
  500.   }
  501.  
  502. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_PUSH(MODIFIER, NAME, T, \
  503.                                              ENTRY_T, BITS)     \
  504.   MODIFIER T NAME (T, ENTRY_T);
  505. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_PUSH(MODIFIER, NAME, T,          \
  506.                                             ENTRY_T, BITS,              \
  507.                                             POINTERS_MALLOC,            \
  508.                                             ENTRIES_MALLOC)             \
  509.   MODIFIER T                                                            \
  510.   NAME (T vec, ENTRY_T x)                                               \
  511.   {                                                                     \
  512.     /* Make a new root. */                                              \
  513.     T##__vector__ *const vec_ =                                         \
  514.       POINTERS_MALLOC (sizeof (T##__vector__));                         \
  515.                                                                         \
  516.     if (vec == (void *) 0)                                              \
  517.       {                                                                 \
  518.         /* Start a new vector. */                                       \
  519.                                                                         \
  520.         vec_->length = 1;                                               \
  521.         vec_->shift = 0;                                                \
  522.         T##__leaf__ *const entries =                                    \
  523.           ENTRIES_MALLOC (sizeof (T##__leaf__));                        \
  524.         vec_->tail = entries;                                           \
  525.         entries->a[0] = x;                                              \
  526.       }                                                                 \
  527.     else                                                                \
  528.       {                                                                 \
  529.         const size_t tail_length = T##__tail_length0__ (vec);           \
  530.                                                                         \
  531.         if (tail_length != 0)                                           \
  532.           {                                                             \
  533.             /* Extend the tail. */                                      \
  534.                                                                         \
  535.             vec_->length = vec->length + 1;                             \
  536.             vec_->shift = vec->shift;                                   \
  537.             vec_->node = vec->node;                                     \
  538.             T##__leaf__ *const entries =                                \
  539.               ENTRIES_MALLOC (sizeof (T##__leaf__));                    \
  540.             vec_->tail = entries;                                       \
  541.             *entries = *vec->tail;                                      \
  542.             entries->a[tail_length] = x;                                \
  543.           }                                                             \
  544.         else                                                            \
  545.           {                                                             \
  546.             /* The tail is full. Push it and start a new one. */        \
  547.                                                                         \
  548.             void **parent;                                              \
  549.                                                                         \
  550.             vec_->length = vec->length + 1;                             \
  551.                                                                         \
  552.             const size_t i = vec->length - (((size_t) 1) << (BITS));    \
  553.             if (i == 0)                                                 \
  554.               {                                                         \
  555.                 /* Start a new trie. */                                 \
  556.                 vec_->node = vec->tail;                                 \
  557.                 T##__leaf__ *const entries =                            \
  558.                   ENTRIES_MALLOC (sizeof (T##__leaf__));                \
  559.                 vec_->tail = entries;                                   \
  560.                 entries->a[0] = x;                                      \
  561.               }                                                         \
  562.             else                                                        \
  563.               {                                                         \
  564.                 if (i == (((size_t) 1) << (vec->shift + (BITS))))       \
  565.                   {                                                     \
  566.                     /* The trie is fully dense. Raise its height. */    \
  567.                     vec_->shift = vec->shift + (BITS);                  \
  568.                     T##__internal__ *const new_node =                   \
  569.                       POINTERS_MALLOC (sizeof (T##__internal__));       \
  570.                     new_node->a[0] = vec->node;                         \
  571.                     vec_->node = new_node;                              \
  572.                     parent = &new_node->a[1];                           \
  573.                   }                                                     \
  574.                 else                                                    \
  575.                   {                                                     \
  576.                     vec_->shift = vec->shift;                           \
  577.                     vec_->node = vec->node;                             \
  578.                     parent = &vec_->node;                               \
  579.                   }                                                     \
  580.                                                                         \
  581.                 /* Make new internal nodes. */                          \
  582.                 void *p = *parent;                                      \
  583.                 for (size_t s = vec->shift; s != 0; s -= (BITS))        \
  584.                   {                                                     \
  585.                     T##__internal__ *const q =                          \
  586.                       POINTERS_MALLOC (sizeof (T##__internal__));       \
  587.                     if (p != (void *) 0)                                \
  588.                       *q = *(T##__internal__ *) p;                      \
  589.                     *parent = q;                                        \
  590.                     parent =                                            \
  591.                       &q->a[(i >> s) & ((((size_t) 1) << (BITS)) - 1)]; \
  592.                     p = *parent;                                        \
  593.                   }                                                     \
  594.                                                                         \
  595.                 /* Push the tail. */                                    \
  596.                 *parent = vec->tail;                                    \
  597.                                                                         \
  598.                 /* Start a new tail. */                                 \
  599.                 T##__leaf__ *const entries =                            \
  600.                   ENTRIES_MALLOC (sizeof (T##__leaf__));                \
  601.                 vec_->tail = entries;                                   \
  602.                 entries->a[0] = x;                                      \
  603.               }                                                         \
  604.           }                                                             \
  605.       }                                                                 \
  606.                                                                         \
  607.     T##__check_structure__ (vec_);                                      \
  608.                                                                         \
  609.     return vec_;                                                        \
  610.   }
  611.  
  612. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_PUSHES(MODIFIER, NAME, T,       \
  613.                                                ENTRY_T, BITS)           \
  614.   MODIFIER T NAME (T, size_t n, const ENTRY_T x[n]);
  615. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_PUSHES(MODIFIER, NAME, T,        \
  616.                                               ENTRY_T, BITS,            \
  617.                                               POINTERS_MALLOC,          \
  618.                                               ENTRIES_MALLOC)           \
  619.   MODIFIER T                                                            \
  620.   NAME (T vec, size_t n, const ENTRY_T x[n])                            \
  621.   {                                                                     \
  622.     const ENTRY_T *chunk = x;                                           \
  623.     while (n != 0)                                                      \
  624.       {                                                                 \
  625.         const size_t chunk_size_max = (vec == (void *) 0) ?             \
  626.           (((size_t) 1) << (BITS)) :                                    \
  627.           ((((size_t) 1) << (BITS)) - T##__tail_length0__ (vec));       \
  628.         const size_t chunk_size =                                       \
  629.           (n < chunk_size_max) ? n : chunk_size_max;                    \
  630.                                                                         \
  631.         /* Make a new root. */                                          \
  632.         T##__vector__ *const vec_ =                                     \
  633.           POINTERS_MALLOC (sizeof (T##__vector__));                     \
  634.                                                                         \
  635.         size_t offset;                                                  \
  636.                                                                         \
  637.         if (vec == (void *) 0)                                          \
  638.           {                                                             \
  639.             /* Start a new vector. */                                   \
  640.                                                                         \
  641.             vec_->length = chunk_size;                                  \
  642.             vec_->shift = 0;                                            \
  643.             T##__leaf__ *const entries =                                \
  644.               ENTRIES_MALLOC (sizeof (T##__leaf__));                    \
  645.             vec_->tail = entries;                                       \
  646.             offset = 0;                                                 \
  647.           }                                                             \
  648.         else                                                            \
  649.           {                                                             \
  650.             const size_t tail_length = T##__tail_length0__ (vec);       \
  651.                                                                         \
  652.             if (tail_length != 0)                                       \
  653.               {                                                         \
  654.                 /* Extend the tail. */                                  \
  655.                                                                         \
  656.                 vec_->length = vec->length + chunk_size;                \
  657.                 vec_->shift = vec->shift;                               \
  658.                 vec_->node = vec->node;                                 \
  659.                 T##__leaf__ *const entries =                            \
  660.                   ENTRIES_MALLOC (sizeof (T##__leaf__));                \
  661.                 vec_->tail = entries;                                   \
  662.                 *entries = *vec->tail;                                  \
  663.                 offset = tail_length;                                   \
  664.               }                                                         \
  665.             else                                                        \
  666.               {                                                         \
  667.                 /* The tail is full. Push it and start a new one. */    \
  668.                                                                         \
  669.                 void **parent;                                          \
  670.                                                                         \
  671.                 vec_->length = vec->length + chunk_size;                \
  672.                                                                         \
  673.                 const size_t i =                                        \
  674.                   vec->length - (((size_t) 1) << (BITS));               \
  675.                 if (i == 0)                                             \
  676.                   {                                                     \
  677.                     /* Start a new trie. */                             \
  678.                     vec_->node = vec->tail;                             \
  679.                     T##__leaf__ *const entries =                        \
  680.                       ENTRIES_MALLOC (sizeof (T##__leaf__));            \
  681.                     vec_->tail = entries;                               \
  682.                     offset = 0;                                         \
  683.                   }                                                     \
  684.                 else                                                    \
  685.                   {                                                     \
  686.                     if (i == (((size_t) 1) << (vec->shift + (BITS))))   \
  687.                       {                                                 \
  688.                         /* The trie is fully dense. */                  \
  689.                         /* Raise its height.        */                  \
  690.                         vec_->shift = vec->shift + (BITS);              \
  691.                         T##__internal__ *const new_node =               \
  692.                           POINTERS_MALLOC (sizeof (T##__internal__));   \
  693.                         new_node->a[0] = vec->node;                     \
  694.                         vec_->node = new_node;                          \
  695.                         parent = &new_node->a[1];                       \
  696.                       }                                                 \
  697.                     else                                                \
  698.                       {                                                 \
  699.                         vec_->shift = vec->shift;                       \
  700.                         vec_->node = vec->node;                         \
  701.                         parent = &vec_->node;                           \
  702.                       }                                                 \
  703.                                                                         \
  704.                     /* Make new internal nodes. */                      \
  705.                     const size_t mask = ((((size_t) 1) << (BITS)) - 1); \
  706.                     void *p = *parent;                                  \
  707.                     for (size_t s = vec->shift; s != 0; s -= (BITS))    \
  708.                       {                                                 \
  709.                         T##__internal__ *const q =                      \
  710.                           POINTERS_MALLOC (sizeof (T##__internal__));   \
  711.                         if (p != (void *) 0)                            \
  712.                           *q = *(T##__internal__ *) p;                  \
  713.                         *parent = q;                                    \
  714.                         parent = &q->a[(i >> s) & mask];                \
  715.                         p = *parent;                                    \
  716.                       }                                                 \
  717.                                                                         \
  718.                     /* Push the tail. */                                \
  719.                     *parent = vec->tail;                                \
  720.                                                                         \
  721.                     /* Start a new tail. */                             \
  722.                     T##__leaf__ *const entries =                        \
  723.                       ENTRIES_MALLOC (sizeof (T##__leaf__));            \
  724.                     vec_->tail = entries;                               \
  725.                     offset = 0;                                         \
  726.                   }                                                     \
  727.               }                                                         \
  728.           }                                                             \
  729.                                                                         \
  730.         T##__leaf__ *const entries = vec_->tail;                        \
  731.         for (size_t i = 0; i < chunk_size; i++)                         \
  732.           entries->a[offset + i] = chunk[i];                            \
  733.                                                                         \
  734.         /* Get ready for the next chunk of new entries. */              \
  735.         vec = vec_;                                                     \
  736.         chunk += chunk_size;                                            \
  737.         n -= chunk_size;                                                \
  738.       }                                                                 \
  739.                                                                         \
  740.     T##__check_structure__ (vec);                                       \
  741.                                                                         \
  742.     return vec;                                                         \
  743.   }
  744.  
  745. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_POP(MODIFIER, NAME, T, BITS)    \
  746.   MODIFIER T NAME (T);
  747. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_POP(MODIFIER, NAME, T, BITS,     \
  748.                                            POINTERS_MALLOC,             \
  749.                                            ENTRIES_MALLOC,              \
  750.                                            COLLECT_ENTRIES)             \
  751.   MODIFIER T                                                            \
  752.   NAME (T vec)                                                          \
  753.   {                                                                     \
  754.     assert (vec != (void *) 0);                                         \
  755.                                                                         \
  756.     T##__vector__ *vec_;                                                \
  757.                                                                         \
  758.     if (vec->length == 1)                                               \
  759.       /* The new vector is empty; our representation for */             \
  760.       /* an empty vector is a NULL pointer.              */             \
  761.       vec_ = (T##__vector__ *) 0;                                       \
  762.     else                                                                \
  763.       {                                                                 \
  764.         /* Make a new root. */                                          \
  765.         vec_ = POINTERS_MALLOC (sizeof (T##__vector__));                \
  766.         *vec_ = *vec;                                                   \
  767.         vec_->length--;                                                 \
  768.                                                                         \
  769.         const size_t tail_length = T##__tail_length__ (vec);            \
  770.         if (tail_length == 1)                                           \
  771.           {                                                             \
  772.             /* We have to take the last block of the trie */            \
  773.             /* and make it a new tail.                    */            \
  774.                                                                         \
  775.             const size_t mask = ((((size_t) 1) << (BITS)) - 1);         \
  776.                                                                         \
  777.             const size_t i = vec_->length - (((size_t) 1) << (BITS));   \
  778.             if (i == 0)                                                 \
  779.               {                                                         \
  780.                 /* All entries now are in the tail; */                  \
  781.                 /* the trie is empty.               */                  \
  782.                 vec_->tail = vec_->node;                                \
  783.                 vec_->node = (void *) 0;                                \
  784.               }                                                         \
  785.             else if (i == (((size_t) 1) << vec_->shift))                \
  786.               {                                                         \
  787.                 /* Lower the height of the trie, yielding a */          \
  788.                 /* fully dense trie.                        */          \
  789.                 void *p = vec_->node;                                   \
  790.                 for (size_t s = vec_->shift; s != 0; s -= (BITS))       \
  791.                   {                                                     \
  792.                     T##__internal__ *const q = p;                       \
  793.                     p = q->a[(i >> s) & mask];                          \
  794.                   }                                                     \
  795.                 vec_->node = ((T##__internal__ *) vec_->node)->a[0];    \
  796.                 vec_->tail = p;                                         \
  797.                 vec_->shift -= (BITS);                                  \
  798.               }                                                         \
  799.             else                                                        \
  800.               {                                                         \
  801.                 /* `pruning' will be set true if we can prune  */       \
  802.                 /* a branch of the trie.                       */       \
  803.                 bool pruning = false;                                   \
  804.                                                                         \
  805.                 void **parent = &vec_->node;                            \
  806.                 void *p = *parent;                                      \
  807.                 for (size_t s = vec_->shift; s != 0; s -= (BITS))       \
  808.                   {                                                     \
  809.                     if (pruning)                                        \
  810.                       {                                                 \
  811.                         /* We have found the place at which      */     \
  812.                         /* to put a NULL (`parent'), but must    */     \
  813.                         /* continue searching for the new tail.  */     \
  814.                         /* And we know that all the indices from */     \
  815.                         /* now on are zero.                      */     \
  816.                         T##__internal__ *const q = p;                   \
  817.                         p = q->a[0];                                    \
  818.                       }                                                 \
  819.                     else                                                \
  820.                       {                                                 \
  821.                         /* Make a new internal node. */                 \
  822.                         T##__internal__ *const q =                      \
  823.                           POINTERS_MALLOC (sizeof (T##__internal__));   \
  824.                         *q = *(T##__internal__ *) p;                    \
  825.                         *parent = q;                                    \
  826.                         parent = &q->a[(i >> s) & mask];                \
  827.                         p = *parent;                                    \
  828.                         pruning = (i == ((i >> s) << s));               \
  829.                       }                                                 \
  830.                   }                                                     \
  831.                 *parent = (void *) 0;                                   \
  832.                 vec_->tail = p;                                         \
  833.               }                                                         \
  834.           }                                                             \
  835.         else if (COLLECT_ENTRIES)                                       \
  836.           {                                                             \
  837.             /* Clear the popped entry, so it can be collected */        \
  838.             /* as garbage if not referenced elsewhere.        */        \
  839.             T##__leaf__ *const entries =                                \
  840.               ENTRIES_MALLOC (sizeof (T##__leaf__));                    \
  841.             *entries = *vec_->tail;                                     \
  842.             vec_->tail = entries;                                       \
  843.             /* A fixed-length memset() that likely will be */           \
  844.             /* expanded inline by the compiler.            */           \
  845.             memset (&entries->a[tail_length - 1], 0,                    \
  846.                     sizeof entries->a[tail_length - 1]);                \
  847.           }                                                             \
  848.       }                                                                 \
  849.                                                                         \
  850.     T##__check_structure__ (vec_);                                      \
  851.                                                                         \
  852.     return vec_;                                                        \
  853.   }
  854.  
  855. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_POPS(MODIFIER, NAME, T, BITS)   \
  856.   MODIFIER T NAME (T, size_t);
  857. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_POPS(MODIFIER, NAME, T, BITS,    \
  858.                                             POINTERS_MALLOC,            \
  859.                                             ENTRIES_MALLOC,             \
  860.                                             COLLECT_ENTRIES)            \
  861.                                                                         \
  862.   static inline void                                                    \
  863.   NAME##__collect_entries__ (T##__vector__ *vec_,                       \
  864.                              size_t new_tail_length)                    \
  865.   {                                                                     \
  866.     /* If the popped entries are atomic, they can simply be ignored. */ \
  867.     if (COLLECT_ENTRIES)                                                \
  868.       {                                                                 \
  869.         /* Otherwise, clear the popped entries, so they can be       */ \
  870.         /* collected as garbage if not referenced elsewhere.         */ \
  871.         T##__leaf__ *const entries =                                    \
  872.           ENTRIES_MALLOC (sizeof (T##__leaf__));                        \
  873.         *entries = *vec_->tail;                                         \
  874.         memset (&entries->a[new_tail_length], 0,                        \
  875.                 ((((size_t) 1) << (BITS)) - new_tail_length)            \
  876.                 * sizeof entries->a[0]);                                \
  877.         vec_->tail = entries;                                           \
  878.       }                                                                 \
  879.   }                                                                     \
  880.                                                                         \
  881.   MODIFIER T                                                            \
  882.   NAME (T vec, size_t count)                                            \
  883.   {                                                                     \
  884.     assert ((vec == (void *) 0) ?                                       \
  885.             (count == 0) : (count <= vec->length));                     \
  886.                                                                         \
  887.     T##__vector__ *vec_;                                                \
  888.                                                                         \
  889.     if (count == 0)                                                     \
  890.       /* No change. */                                                  \
  891.       vec_ = (T##__vector__ *) vec;                                     \
  892.     else if (count == vec->length)                                      \
  893.       /* The new vector is empty; our representation for */             \
  894.       /* an empty vector is a NULL pointer.              */             \
  895.       vec_ = (T##__vector__ *) 0;                                       \
  896.     else                                                                \
  897.       {                                                                 \
  898.         /* Make a new root. */                                          \
  899.         vec_ = POINTERS_MALLOC (sizeof (T##__vector__));                \
  900.         *vec_ = *vec;                                                   \
  901.         vec_->length -= count;                                          \
  902.                                                                         \
  903.         const size_t tail_length = T##__tail_length__ (vec);            \
  904.         const size_t new_tail_length = T##__tail_length__ (vec_);       \
  905.         if (count < tail_length)                                        \
  906.           /* Merely shorten the tail. */                                \
  907.           NAME##__collect_entries__ (vec_, new_tail_length);            \
  908.         else                                                            \
  909.           {                                                             \
  910.             const size_t mask = (((size_t) 1) << (BITS)) - 1;           \
  911.             const size_t new_tail_offset =                              \
  912.               vec_->length - new_tail_length;                           \
  913.                                                                         \
  914.             /* Find the new tail. */                                    \
  915.             void *p = vec->node;                                        \
  916.             for (size_t s = vec->shift; s != 0; s -= (BITS))            \
  917.               {                                                         \
  918.                 T##__internal__ *const q = p;                           \
  919.                 p = q->a[(new_tail_offset >> s) & mask];                \
  920.               }                                                         \
  921.             vec_->tail = p;                                             \
  922.             NAME##__collect_entries__ (vec_, new_tail_length);          \
  923.                                                                         \
  924.             if (new_tail_offset == 0)                                   \
  925.               {                                                         \
  926.                 /* Delete the trie. We now have only a tail. */         \
  927.                 vec_->shift = 0;                                        \
  928.                 vec_->node = (void *) 0;                                \
  929.               }                                                         \
  930.             else                                                        \
  931.               {                                                         \
  932.                 /* The index of the last entry in the new trie. */      \
  933.                 const size_t i = new_tail_offset - 1;                   \
  934.                                                                         \
  935.                 /* Possibly reduce trie height. */                      \
  936.                 while (vec_->shift != 0                                 \
  937.                        && ((i >> vec_->shift) & mask) == 0)             \
  938.                   {                                                     \
  939.                     vec_->node =                                        \
  940.                       ((T##__internal__ *) vec_->node)->a[0];           \
  941.                     vec_->shift -= (BITS);                              \
  942.                   }                                                     \
  943.                                                                         \
  944.                 /* Make new internal nodes. */                          \
  945.                 void **parent = &vec_->node;                            \
  946.                 p = *parent;                                            \
  947.                 for (size_t s = vec_->shift; s != 0; s -= (BITS))       \
  948.                   {                                                     \
  949.                     T##__internal__ *const q =                          \
  950.                       POINTERS_MALLOC (sizeof (T##__internal__));       \
  951.                     const size_t index = (i >> s) & mask;               \
  952.                     for (size_t j = 0; j <= index; j++)                 \
  953.                       q->a[j] = ((T##__internal__ *) p)->a[j];          \
  954.                     *parent = q;                                        \
  955.                     parent = &q->a[index];                              \
  956.                     p = *parent;                                        \
  957.                   }                                                     \
  958.               }                                                         \
  959.           }                                                             \
  960.       }                                                                 \
  961.                                                                         \
  962.     T##__check_structure__ (vec_);                                      \
  963.                                                                         \
  964.     return vec_;                                                        \
  965.   }
  966.  
  967. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_SLICE(MODIFIER, NAME,   \
  968.                                               T, ENTRY_T, BITS) \
  969.   MODIFIER T NAME (T, size_t, size_t);
  970. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_SLICE(MODIFIER, NAME,            \
  971.                                              T, ENTRY_T, BITS,          \
  972.                                              REFS, PUSHES, POPS)        \
  973.   MODIFIER T                                                            \
  974.   NAME (T vec, size_t start, size_t end)                                \
  975.   {                                                                     \
  976.     assert (start <= end);                                              \
  977.                                                                         \
  978.     const size_t length =                                               \
  979.       (vec == (T##__vector__ *) 0) ? 0 : vec->length;                   \
  980.     assert (end <= length);                                             \
  981.                                                                         \
  982.     T vec_;                                                             \
  983.     if (start == 0)                                                     \
  984.       vec_ = POPS (vec, length - end);                                  \
  985.     else                                                                \
  986.       {                                                                 \
  987.         const size_t buffer_size = ((size_t) 1) << (BITS);              \
  988.         ENTRY_T buffer[buffer_size];                                    \
  989.                                                                         \
  990.         vec_ = (T) 0;                                                   \
  991.         size_t i = start;                                               \
  992.         while (i < end)                                                 \
  993.           {                                                             \
  994.             const size_t j = (end < i + buffer_size) ?                  \
  995.               end :                                                     \
  996.               ((i + buffer_size) & ~((((size_t) 1) << (BITS)) - 1));    \
  997.             REFS (vec, i, j - i, buffer);                               \
  998.             vec_ = PUSHES (vec_, j - i, buffer);                        \
  999.             i = j;                                                      \
  1000.           }                                                             \
  1001.       }                                                                 \
  1002.     return vec_;                                                        \
  1003.   }
  1004.  
  1005. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_APPEND(MODIFIER, NAME,          \
  1006.                                                T, ENTRY_T, BITS)        \
  1007.   MODIFIER T NAME (T, T);
  1008. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_APPEND(MODIFIER, NAME,           \
  1009.                                               T, ENTRY_T, BITS,         \
  1010.                                               REFS, PUSHES)             \
  1011.   MODIFIER T                                                            \
  1012.   NAME (T v1, T v2)                                                     \
  1013.   {                                                                     \
  1014.     const size_t buffer_size = ((size_t) 1) << (BITS);                  \
  1015.     ENTRY_T buffer[buffer_size];                                        \
  1016.                                                                         \
  1017.     if (v2 != (T##__vector__ *) 0)                                      \
  1018.       {                                                                 \
  1019.         const size_t end = v2->length;                                  \
  1020.         size_t i = 0;                                                   \
  1021.         while (i < end)                                                 \
  1022.           {                                                             \
  1023.             const size_t j =                                            \
  1024.               (end < i + buffer_size) ? end : (i + buffer_size);        \
  1025.             REFS (v2, i, j - i, buffer);                                \
  1026.             v1 = PUSHES (v1, j - i, buffer);                            \
  1027.             i = j;                                                      \
  1028.           }                                                             \
  1029.       }                                                                 \
  1030.     return v1;                                                          \
  1031.   }
  1032.  
  1033. /*--------------------------------------------------------------------*/
  1034.  
  1035. /*
  1036.  * Effort-savers that do a whole lot at once.
  1037.  */
  1038.  
  1039. #define DECLARE_SMCORE_IMMUTABLE_VECTOR_DATATYPE(MODIFIER, TNAME,       \
  1040.                                                  ENTRY_T, BITS)         \
  1041.   DECLARE_SMCORE_IMMUTABLE_VECTOR_T (MODIFIER, TNAME##_t, ENTRY_T,      \
  1042.                                      BITS);                             \
  1043.   DECLARE_SMCORE_IMMUTABLE_VECTOR_LENGTH (MODIFIER, TNAME##_length,     \
  1044.                                           TNAME##_t);                   \
  1045.   DECLARE_SMCORE_IMMUTABLE_VECTOR_REF (MODIFIER, TNAME##_ref,           \
  1046.                                        TNAME##_t, ENTRY_T, BITS);       \
  1047.   DECLARE_SMCORE_IMMUTABLE_VECTOR_PTR (MODIFIER, TNAME##_ptr,           \
  1048.                                        TNAME##_t, ENTRY_T, BITS);       \
  1049.   DECLARE_SMCORE_IMMUTABLE_VECTOR_NEXT (MODIFIER, TNAME##_next,         \
  1050.                                         TNAME##_t, ENTRY_T, BITS);      \
  1051.   DECLARE_SMCORE_IMMUTABLE_VECTOR_PREV (MODIFIER, TNAME##_prev,         \
  1052.                                         TNAME##_t, ENTRY_T, BITS);      \
  1053.   DECLARE_SMCORE_IMMUTABLE_VECTOR_REFS (MODIFIER, TNAME##_refs,         \
  1054.                                         TNAME##_t, ENTRY_T, BITS);      \
  1055.   DECLARE_SMCORE_IMMUTABLE_VECTOR_SET (MODIFIER, TNAME##_set,           \
  1056.                                        TNAME##_t, ENTRY_T, BITS);       \
  1057.   DECLARE_SMCORE_IMMUTABLE_VECTOR_SETS (MODIFIER, TNAME##_sets,         \
  1058.                                         TNAME##_t, ENTRY_T, BITS);      \
  1059.   DECLARE_SMCORE_IMMUTABLE_VECTOR_PUSH (MODIFIER, TNAME##_push,         \
  1060.                                         TNAME##_t, ENTRY_T, BITS);      \
  1061.   DECLARE_SMCORE_IMMUTABLE_VECTOR_PUSHES (MODIFIER, TNAME##_pushes,     \
  1062.                                           TNAME##_t, ENTRY_T, BITS);    \
  1063.   DECLARE_SMCORE_IMMUTABLE_VECTOR_POP (MODIFIER, TNAME##_pop,           \
  1064.                                        TNAME##_t, BITS);                \
  1065.   DECLARE_SMCORE_IMMUTABLE_VECTOR_POPS (MODIFIER, TNAME##_pops,         \
  1066.                                         TNAME##_t, BITS);               \
  1067.   DECLARE_SMCORE_IMMUTABLE_VECTOR_SLICE (MODIFIER, TNAME##_slice,       \
  1068.                                          TNAME##_t, ENTRY_T, BITS);     \
  1069.   DECLARE_SMCORE_IMMUTABLE_VECTOR_APPEND (MODIFIER, TNAME##_append,     \
  1070.                                           TNAME##_t, ENTRY_T, BITS)
  1071.  
  1072. /*
  1073.  * POINTERS_MALLOC() must zero out the memory it allocates. You may
  1074.  * use x_gc_malloc().
  1075.  *
  1076.  * ENTRIES_MALLOC() has no such requirement. You may use x_gc_malloc()
  1077.  * or, if the ENTRY_T type contains no pointers, x_gc_malloc_atomic().
  1078.  *
  1079.  * If ENTRY_T needs garbage collection you may also want to set
  1080.  * COLLECT_ENTRIES true.
  1081.  */
  1082. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_DATATYPE_GENERAL(MODIFIER,       \
  1083.                                                         TNAME,          \
  1084.                                                         ENTRY_T, BITS,  \
  1085.                                                         POINTERS_MALLOC, \
  1086.                                                         ENTRIES_MALLOC, \
  1087.                                                         COLLECT_ENTRIES) \
  1088.   DEFINE_SMCORE_IMMUTABLE_VECTOR_T (MODIFIER, TNAME##_t, ENTRY_T, BITS) \
  1089.   DEFINE_SMCORE_IMMUTABLE_VECTOR_LENGTH (MODIFIER, TNAME##_length,      \
  1090.                                          TNAME##_t);                    \
  1091.   DEFINE_SMCORE_IMMUTABLE_VECTOR_REF (MODIFIER, TNAME##_ref, TNAME##_t, \
  1092.                                       ENTRY_T, BITS);                   \
  1093.   DEFINE_SMCORE_IMMUTABLE_VECTOR_PTR (MODIFIER, TNAME##_ptr, TNAME##_t, \
  1094.                                       ENTRY_T, BITS);                   \
  1095.   DEFINE_SMCORE_IMMUTABLE_VECTOR_NEXT (MODIFIER, TNAME##_next,          \
  1096.                                        TNAME##_t, ENTRY_T, BITS);       \
  1097.   DEFINE_SMCORE_IMMUTABLE_VECTOR_PREV (MODIFIER, TNAME##_prev,          \
  1098.                                        TNAME##_t, ENTRY_T, BITS);       \
  1099.   DEFINE_SMCORE_IMMUTABLE_VECTOR_REFS(MODIFIER, TNAME##_refs,           \
  1100.                                       TNAME##_t, ENTRY_T, BITS,         \
  1101.                                       TNAME##_ptr, TNAME##_next);       \
  1102.   DEFINE_SMCORE_IMMUTABLE_VECTOR_SET (MODIFIER, TNAME##_set, TNAME##_t, \
  1103.                                       ENTRY_T, BITS,                    \
  1104.                                       POINTERS_MALLOC, ENTRIES_MALLOC); \
  1105.   DEFINE_SMCORE_IMMUTABLE_VECTOR_SETS (MODIFIER, TNAME##_sets,          \
  1106.                                        TNAME##_t, ENTRY_T, BITS,        \
  1107.                                        POINTERS_MALLOC,                 \
  1108.                                        ENTRIES_MALLOC);                 \
  1109.   DEFINE_SMCORE_IMMUTABLE_VECTOR_PUSH (MODIFIER, TNAME##_push,          \
  1110.                                        TNAME##_t, ENTRY_T, BITS,        \
  1111.                                        POINTERS_MALLOC,                 \
  1112.                                        ENTRIES_MALLOC);                 \
  1113.   DEFINE_SMCORE_IMMUTABLE_VECTOR_PUSHES (MODIFIER, TNAME##_pushes,      \
  1114.                                          TNAME##_t, ENTRY_T, BITS,      \
  1115.                                          POINTERS_MALLOC,               \
  1116.                                          ENTRIES_MALLOC);               \
  1117.   DEFINE_SMCORE_IMMUTABLE_VECTOR_POP (MODIFIER, TNAME##_pop,            \
  1118.                                       TNAME##_t, BITS,                  \
  1119.                                       POINTERS_MALLOC,                  \
  1120.                                       ENTRIES_MALLOC,                   \
  1121.                                       (COLLECT_ENTRIES));               \
  1122.   DEFINE_SMCORE_IMMUTABLE_VECTOR_POPS (MODIFIER, TNAME##_pops,          \
  1123.                                        TNAME##_t, BITS,                 \
  1124.                                        POINTERS_MALLOC,                 \
  1125.                                        ENTRIES_MALLOC,                  \
  1126.                                        (COLLECT_ENTRIES));              \
  1127.   DEFINE_SMCORE_IMMUTABLE_VECTOR_SLICE (MODIFIER, TNAME##_slice,        \
  1128.                                         TNAME##_t, ENTRY_T, BITS,       \
  1129.                                         TNAME##_refs, TNAME##_pushes,   \
  1130.                                         TNAME##_pops);                  \
  1131.   DEFINE_SMCORE_IMMUTABLE_VECTOR_APPEND (MODIFIER, TNAME##_append,      \
  1132.                                          TNAME##_t, ENTRY_T, BITS,      \
  1133.                                          TNAME##_refs, TNAME##_pushes)
  1134.  
  1135. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_DATATYPE(MODIFIER, TNAME,        \
  1136.                                                 ENTRY_T, BITS)          \
  1137.   DEFINE_SMCORE_IMMUTABLE_VECTOR_DATATYPE_GENERAL(MODIFIER, TNAME,      \
  1138.                                                   ENTRY_T, BITS,        \
  1139.                                                   x_gc_malloc,          \
  1140.                                                   x_gc_malloc,          \
  1141.                                                   true)
  1142.  
  1143. #define DEFINE_SMCORE_IMMUTABLE_VECTOR_DATATYPE_ATOMIC(MODIFIER, TNAME, \
  1144.                                                        ENTRY_T, BITS)   \
  1145.   DEFINE_SMCORE_IMMUTABLE_VECTOR_DATATYPE_GENERAL(MODIFIER, TNAME,      \
  1146.                                                   ENTRY_T, BITS,        \
  1147.                                                   x_gc_malloc,          \
  1148.                                                   x_gc_malloc_atomic,   \
  1149.                                                   false)
  1150.  
  1151. /*--------------------------------------------------------------------*/
  1152.  
  1153. #if 0
  1154. {
  1155. #endif
  1156. #ifdef __cplusplus
  1157. }
  1158. #endif
  1159.  
  1160. #endif /* SORTSMILL_CORE_IMMUTABLE_VECTORS_H_ */
  1161.  
Advertisement
Comments
  • User was banned
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!