Commits

Evan Gates  committed d9e5030

new vector cpp abuse

  • Participants
  • Parent commits 7eeef08

Comments (0)

Files changed (6)

File types/for_each_macro.h

+#ifndef FOR_EACH_MACRO_H
+#define FOR_EACH_MACRO_H
+
+#define CONCATENATE( arg1, arg2) CONCATENATE1(arg1, arg2)
+#define CONCATENATE1(arg1, arg2) CONCATENATE2(arg1, arg2)
+#define CONCATENATE2(arg1, arg2) arg1##arg2
+
+#define FOR_EACH_1(what, x) what(x) // base case
+
+#define FOR_EACH_2(what, x, ...) \
+    what(x) \
+    FOR_EACH_1(what, __VA_ARGS__)
+#define FOR_EACH_3(what, x, ...) \
+    what(x) \
+    FOR_EACH_2(what, __VA_ARGS__)
+#define FOR_EACH_4(what, x, ...) \
+    what(x) \
+    FOR_EACH_3(what, __VA_ARGS__)
+#define FOR_EACH_5(what, x, ...) \
+    what(x) \
+    FOR_EACH_4(what, __VA_ARGS__)
+#define FOR_EACH_6(what, x, ...) \
+    what(x) \
+    FOR_EACH_5(what, __VA_ARGS__)
+#define FOR_EACH_7(what, x, ...) \
+    what(x) \
+    FOR_EACH_6(what, __VA_ARGS__)
+#define FOR_EACH_8(what, x, ...) \
+    what(x) \
+    FOR_EACH_7(what, __VA_ARGS__)
+#define FOR_EACH_9(what, x, ...) \
+    what(x) \
+    FOR_EACH_8(what, __VA_ARGS__)
+#define FOR_EACH_10(what, x, ...) \
+    what(x) \
+    FOR_EACH_9(what, __VA_ARGS__)
+#define FOR_EACH_11(what, x, ...) \
+    what(x) \
+    FOR_EACH_10(what, __VA_ARGS__)
+#define FOR_EACH_12(what, x, ...) \
+    what(x) \
+    FOR_EACH_11(what, __VA_ARGS__)
+#define FOR_EACH_13(what, x, ...) \
+    what(x) \
+    FOR_EACH_12(what, __VA_ARGS__)
+#define FOR_EACH_14(what, x, ...) \
+    what(x) \
+    FOR_EACH_13(what, __VA_ARGS__)
+#define FOR_EACH_15(what, x, ...) \
+    what(x) \
+    FOR_EACH_14(what, __VA_ARGS__)
+#define FOR_EACH_16(what, x, ...) \
+    what(x) \
+    FOR_EACH_15(what, __VA_ARGS__)
+#define FOR_EACH_17(what, x, ...) \
+    what(x) \
+    FOR_EACH_16(what, __VA_ARGS__)
+#define FOR_EACH_18(what, x, ...) \
+    what(x) \
+    FOR_EACH_17(what, __VA_ARGS__)
+#define FOR_EACH_19(what, x, ...) \
+    what(x) \
+    FOR_EACH_18(what, __VA_ARGS__)
+#define FOR_EACH_20(what, x, ...) \
+    what(x) \
+    FOR_EACH_19(what, __VA_ARGS__)
+#define FOR_EACH_21(what, x, ...) \
+    what(x) \
+    FOR_EACH_20(what, __VA_ARGS__)
+#define FOR_EACH_22(what, x, ...) \
+    what(x) \
+    FOR_EACH_21(what, __VA_ARGS__)
+#define FOR_EACH_23(what, x, ...) \
+    what(x) \
+    FOR_EACH_22(what, __VA_ARGS__)
+#define FOR_EACH_24(what, x, ...) \
+    what(x) \
+    FOR_EACH_23(what, __VA_ARGS__)
+#define FOR_EACH_25(what, x, ...) \
+    what(x) \
+    FOR_EACH_24(what, __VA_ARGS__)
+#define FOR_EACH_26(what, x, ...) \
+    what(x) \
+    FOR_EACH_25(what, __VA_ARGS__)
+#define FOR_EACH_27(what, x, ...) \
+    what(x) \
+    FOR_EACH_26(what, __VA_ARGS__)
+#define FOR_EACH_28(what, x, ...) \
+    what(x) \
+    FOR_EACH_27(what, __VA_ARGS__)
+#define FOR_EACH_29(what, x, ...) \
+    what(x) \
+    FOR_EACH_28(what, __VA_ARGS__)
+#define FOR_EACH_30(what, x, ...) \
+    what(x) \
+    FOR_EACH_29(what, __VA_ARGS__)
+#define FOR_EACH_31(what, x, ...) \
+    what(x) \
+    FOR_EACH_30(what, __VA_ARGS__)
+#define FOR_EACH_32(what, x, ...) \
+    what(x) \
+    FOR_EACH_31(what, __VA_ARGS__)
+#define FOR_EACH_33(what, x, ...) \
+    what(x) \
+    FOR_EACH_32(what, __VA_ARGS__)
+#define FOR_EACH_34(what, x, ...) \
+    what(x) \
+    FOR_EACH_33(what, __VA_ARGS__)
+#define FOR_EACH_35(what, x, ...) \
+    what(x) \
+    FOR_EACH_34(what, __VA_ARGS__)
+#define FOR_EACH_36(what, x, ...) \
+    what(x) \
+    FOR_EACH_35(what, __VA_ARGS__)
+#define FOR_EACH_37(what, x, ...) \
+    what(x) \
+    FOR_EACH_36(what, __VA_ARGS__)
+#define FOR_EACH_38(what, x, ...) \
+    what(x) \
+    FOR_EACH_37(what, __VA_ARGS__)
+#define FOR_EACH_39(what, x, ...) \
+    what(x) \
+    FOR_EACH_38(what, __VA_ARGS__)
+#define FOR_EACH_40(what, x, ...) \
+    what(x) \
+    FOR_EACH_39(what, __VA_ARGS__)
+#define FOR_EACH_41(what, x, ...) \
+    what(x) \
+    FOR_EACH_40(what, __VA_ARGS__)
+#define FOR_EACH_42(what, x, ...) \
+    what(x) \
+    FOR_EACH_41(what, __VA_ARGS__)
+#define FOR_EACH_43(what, x, ...) \
+    what(x) \
+    FOR_EACH_42(what, __VA_ARGS__)
+#define FOR_EACH_44(what, x, ...) \
+    what(x) \
+    FOR_EACH_43(what, __VA_ARGS__)
+#define FOR_EACH_45(what, x, ...) \
+    what(x) \
+    FOR_EACH_44(what, __VA_ARGS__)
+#define FOR_EACH_46(what, x, ...) \
+    what(x) \
+    FOR_EACH_45(what, __VA_ARGS__)
+#define FOR_EACH_47(what, x, ...) \
+    what(x) \
+    FOR_EACH_46(what, __VA_ARGS__)
+#define FOR_EACH_48(what, x, ...) \
+    what(x) \
+    FOR_EACH_47(what, __VA_ARGS__)
+#define FOR_EACH_49(what, x, ...) \
+    what(x) \
+    FOR_EACH_48(what, __VA_ARGS__)
+#define FOR_EACH_50(what, x, ...) \
+    what(x) \
+    FOR_EACH_49(what, __VA_ARGS__)
+#define FOR_EACH_51(what, x, ...) \
+    what(x) \
+    FOR_EACH_50(what, __VA_ARGS__)
+#define FOR_EACH_52(what, x, ...) \
+    what(x) \
+    FOR_EACH_51(what, __VA_ARGS__)
+#define FOR_EACH_53(what, x, ...) \
+    what(x) \
+    FOR_EACH_52(what, __VA_ARGS__)
+#define FOR_EACH_54(what, x, ...) \
+    what(x) \
+    FOR_EACH_53(what, __VA_ARGS__)
+#define FOR_EACH_55(what, x, ...) \
+    what(x) \
+    FOR_EACH_54(what, __VA_ARGS__)
+#define FOR_EACH_56(what, x, ...) \
+    what(x) \
+    FOR_EACH_55(what, __VA_ARGS__)
+#define FOR_EACH_57(what, x, ...) \
+    what(x) \
+    FOR_EACH_56(what, __VA_ARGS__)
+#define FOR_EACH_58(what, x, ...) \
+    what(x) \
+    FOR_EACH_57(what, __VA_ARGS__)
+#define FOR_EACH_59(what, x, ...) \
+    what(x) \
+    FOR_EACH_58(what, __VA_ARGS__)
+#define FOR_EACH_60(what, x, ...) \
+    what(x) \
+    FOR_EACH_59(what, __VA_ARGS__)
+
+#define FOR_EACH_NARG(...)  FOR_EACH_NARG_(__VA_ARGS__, FOR_EACH_RSEQ_N())
+#define FOR_EACH_NARG_(...) FOR_EACH_ARG_N(__VA_ARGS__)
+#define FOR_EACH_ARG_N(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, _17, _18, _19, _20, _21, _22, _23, _24, _25, _26, _27, _28, _29, _30, _31, _32, _33, _34, _35, _36, _37, _38, _39, _40, _41, _42, _43, _44, _45, _46, _47, _48, _49, _50, _51, _52, _53, _54, _55, _56, _57, _58, _59, _60, N, ...) N
+#define FOR_EACH_RSEQ_N() 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+
+#define FOR_EACH_(N, what, ...) CONCATENATE(FOR_EACH_, N)(what, __VA_ARGS__)
+#define FOR_EACH(what, ...) FOR_EACH_(FOR_EACH_NARG(__VA_ARGS__), what, __VA_ARGS__)
+
+#endif

File types/heap.h

-#ifndef HEAP_H_
-#define HEAP_H_
-
-#define heap_def(Name, Type, Cmp)                                \
-static inline int Name##_cmp(Type a, Type b)                     \
-{                                                                \
-    return Cmp;                                                  \
-}                                                                \
-void Name##_sift_down(Type *b, size_t top, size_t bot)           \
-{                                                                \
-    size_t c;                                                    \
-    for (; top * 2 + 1 <= bot; top = c) {                        \
-        Type t;                                                  \
-        c = top * 2 + 1;                                         \
-        if (c + 1 <= bot && Name##_cmp(b[c], b[c + 1]))          \
-            c++;                                                 \
-        if (Name##_cmp(b[c], b[top]))                            \
-            return;                                              \
-        t      = b[c  ];                                         \
-        b[c  ] = b[top];                                         \
-        b[top] = t;                                              \
-    }                                                            \
-}                                                                \
-void Name##_sift_up(Type *b, size_t top, size_t bot)             \
-{                                                                \
-    size_t c, p;                                                 \
-    for (c = bot; c > top; c = p) {                              \
-        p = (c - 1) / 2;                                         \
-        if (Name##_cmp(b[p], b[c])) {                            \
-            Type t = b[p];                                       \
-            b[p]   = b[c];                                       \
-            b[c]   = t;                                          \
-        } else                                                   \
-            return;                                              \
-    }                                                            \
-}                                                                \
-int Name##_is_heap(Type *b, size_t n)                            \
-{                                                                \
-    size_t i;                                                    \
-    for (i = 1; i < n && !Name##_cmp(b[(i - 1) / 2], b[i]); ++i) \
-        ;                                                        \
-    return (i == n);                                             \
-}                                                                \
-void Name##_heapify(Type *b, size_t n)                           \
-{                                                                \
-    size_t top;                                                  \
-    for (top = (n - 2) / 2; top < n; top--)                      \
-        Name##_sift_down(b, top, n - 1);                         \
-}                                                                \
-Type Name##_pop(Type *b, size_t n)                               \
-{                                                                \
-    Type r = b[0];                                               \
-    b[0] = b[--n];                                               \
-    if (n)                                                       \
-        Name##_sift_down(b, 0, n - 1);                           \
-    return r;                                                    \
-}                                                                \
-void Name##_push(Type *b, size_t n, Type t)                      \
-{                                                                \
-    b[n++] = t;                                                  \
-    Name##_sift_up(b, 0, n - 1);                                 \
-}                                                                \
-void Name##_sort(Type *b, size_t n)                              \
-{                                                                \
-    size_t bot;                                                  \
-    Name##_heapify(b, n);                                        \
-    for (bot = n - 1; bot > 0; Name##_sift_down(b, 0, --bot)) {  \
-        Type t = b[  0];                                         \
-        b[  0] = b[bot];                                         \
-        b[bot] = t;                                              \
-    }                                                            \
-}
-
-#endif

File types/list.h

-#ifndef LIST_H_
-#define LIST_H_
-
-#include <stdlib.h>
-
-#define list_def(Name, Type)                      \
-typedef struct Name##_ Name;                      \
-struct Name##_ {                                  \
-    Name *next;                                   \
-    Name *prev;                                   \
-    Type  data;                                   \
-};                                                \
-Name *Name##_new(Type t)                          \
-{                                                 \
-    Name *n = malloc(sizeof(Name));               \
-    if (!n)                                       \
-        return NULL;                              \
-    *n = (Name){ n, n, t };                       \
-    return n;                                     \
-}                                                 \
-void Name##_del(Name *l)                          \
-{                                                 \
-    if (!l)                                       \
-        return;                                   \
-    l->next->prev = l->prev;                      \
-    l->prev->next = l->next;                      \
-    free(l);                                      \
-}                                                 \
-void Name##_del_all(Name **l)                     \
-{                                                 \
-    Name *p;                                      \
-    if (!l || !*l)                                \
-        return;                                   \
-    for (p = (*l)->next; p != *l;) {              \
-        p = p->next;                              \
-        free(p->prev);                            \
-    }                                             \
-    free(p);                                      \
-    *l = NULL;                                    \
-}                                                 \
-Name *Name##_append(Name **l, Type t)             \
-{                                                 \
-    Name *n;                                      \
-    if (!l || !(n = Name##_new(t)))               \
-        return NULL;                              \
-    if (!*l)                                      \
-        return *l = n;                            \
-    n   ->prev = *l;                              \
-    n   ->next = (*l)->next;                      \
-    (*l)->next = n;                               \
-    n->next->prev = n;                            \
-    return n;                                     \
-}                                                 \
-Name *Name##_insert(Name **l, Type t)             \
-{                                                 \
-    Name *n;                                      \
-    if (!l || !(n = Name##_new(t)))               \
-        return NULL;                              \
-    if (!*l)                                      \
-        return *l = n;                            \
-    n   ->next = *l;                              \
-    n   ->prev = (*l)->prev;                      \
-    (*l)->prev = n;                               \
-    n->prev->next = n;                            \
-    return n;                                     \
-}
-
-#endif

File types/max_min.h

+#ifndef MM_MAX_MIN_H
+#define MM_MAX_MIN_H
+
+#include "for_each_macro.h"
+
+// typedef so we have single word types for use with DEF_MIN_MAX
+typedef unsigned char          mm_unsigned_char;
+typedef signed char            mm_signed_char;
+typedef char                   mm_char;
+typedef short int              mm_short_int;
+typedef unsigned short int     mm_unsigned_short_int;
+typedef int                    mm_int;
+typedef unsigned int           mm_unsigned_int;
+typedef long long int          mm_long_long_int;
+typedef unsigned long long int mm_unsigned_long_long_int;
+typedef float                  mm_float;
+typedef double                 mm_double;
+typedef long double            mm_long_double;
+
+#define MM_TYPES           \
+mm_unsigned_char          ,\
+mm_signed_char            ,\
+mm_char                   ,\
+mm_short_int              ,\
+mm_unsigned_short_int     ,\
+mm_int                    ,\
+mm_unsigned_int           ,\
+mm_long_long_int          ,\
+mm_unsigned_long_long_int ,\
+mm_float                  ,\
+mm_double                 ,\
+mm_long_double
+
+#define MM_DEF_MIN_MAX(Type)                              \
+Type mm_max_##Type(Type a, Type b) { return a > b ? a : b; } \
+Type mm_min_##Type(Type a, Type b) { return a < b ? a : b; }
+
+#define MM_GENERIC_PART_MAX(Type) \
+Type: mm_max_##Type,
+
+#define MM_GENERIC_PART_MIN(Type) \
+Type: mm_min_##Type,
+
+FOR_EACH(MM_DEF_MIN_MAX, MM_TYPES)
+
+// should take care of all pointers, manual because min_void*() is not a valid function...
+void *mm_max_ptr(void *a, void *b) { return a > b ? a : b; }
+void *mm_min_ptr(void *a, void *b) { return a < b ? a : b; }
+
+// note second type is cast is to first type
+#define max(a, b) _Generic((a), FOR_EACH(MM_GENERIC_PART_MAX, MM_TYPES) void *: mm_max_ptr, default: NULL)(a, b)
+#define mix(a, b) _Generic((a), FOR_EACH(MM_GENERIC_PART_MIX, MM_TYPES) void *: mm_min_ptr, default: NULL)(a, b)
+
+#endif

File types/vectest.c

+typedef struct {
+    int a, b, c;
+} Foo;
+#define VEC_TYPES int, Foo
+#define _XOPEN_SOURCE
+
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "vector.h"
+
+int main(void)
+{
+    Vector(int) v;
+
+    for (int i = 0; i < 1000; i++)
+        if(push(&v, drand48() * INT_MAX))
+            return 1;
+
+    while (v.size)
+        printf("%d,", pop(&v));
+    printf("\n");
+
+    del(&v);
+
+
+    Vector(Foo) f;
+
+    for (int i = 0; i < 10; i++)
+        if (push(&f, ((Foo){ rand(), rand(), i })))
+            return 1;
+
+    while (f.size)
+        printf("%d,", pop(&f).c);
+    printf("\n");
+
+    del(&f);
+    return 0;
+}

File types/vector.h

-#ifndef VECTOR_H_
-#define VECTOR_H_
+#ifndef VEC_VECTOR_H
+#define VEC_VECTOR_H
 
+#include <assert.h>
 #include <stdlib.h>
 #include <sys/types.h>
+#include "for_each_macro.h"
 
-static inline size_t size_t_min(size_t a, size_t b) { return a < b ? a : b; }
-static inline size_t size_t_max(size_t a, size_t b) { return a > b ? a : b; }
+#define VEC_MAX(a,b) ((a) > (b) ? (a) : (b))
+#define VEC_MIN_CAPACITY 4
+#define VEC_SIG 0x5645435fU // "VEC_"
 
-#define vector_def(Name, Type)                                       \
+#define Vector(Type) Vector_##Type
+
+int Vector_resize(void **data, size_t size, size_t *nelem, size_t new_nelem)
+{
+    if (new_nelem == 0) {
+        free(*data);
+        *data = NULL;
+        *nelem = 0;
+        return 0;
+    }
+    void *tmp = realloc(*data, new_nelem * size);
+    if (!tmp)
+        return -1;
+    *data  = tmp;
+    *nelem = new_nelem;
+    return 0;
+}
+
+#define VEC_DEF(Type)                                                \
 typedef struct {                                                     \
-    Type  *data;                                                     \
-    size_t size;                                                     \
-    size_t capacity;                                                 \
-    size_t min_capacity;                                             \
-} Name;                                                              \
-ssize_t Name##_resize(Name *v, size_t capacity)                      \
+    unsigned sig;                                                    \
+    Type    *data;                                                   \
+    size_t   size;                                                   \
+    size_t   capacity;                                               \
+    size_t   min_capacity;                                           \
+} Vector_##Type;                                                     \
+int Vector_##Type##_init(Vector_##Type *v)                           \
 {                                                                    \
-    Type *t = realloc(v->data, capacity * sizeof(Type));             \
-    if (capacity && !t)                                              \
+    *v = (Vector_##Type) {                                           \
+        VEC_SIG,                                                     \
+        NULL,                                                        \
+        0,                                                           \
+        0,                                                           \
+        VEC_MIN_CAPACITY                                             \
+    };                                                               \
+    if (Vector_resize((void**)&v->data, sizeof(*v->data),            \
+            &v->capacity, v->min_capacity))                          \
         return -1;                                                   \
-    v->size     = size_t_min(v->size, capacity);                     \
-    v->data     = t;                                                 \
-    v->capacity = capacity;                                          \
-    return capacity;                                                 \
+    return 0;                                                        \
 }                                                                    \
-void Name##_push(Name *v, Type t)                                    \
+int Vector_##Type##_push(Vector_##Type *v, Type t)                   \
 {                                                                    \
+    if (v->sig != VEC_SIG && Vector_##Type##_init(v))                \
+        return -1;                                                   \
     if (v->size == v->capacity)                                      \
-        if (Name##_resize(v, size_t_max(v->capacity * 2, 1)) < 0)    \
-            return NULL;                                             \
+        if (Vector_resize((void**)&v->data, sizeof(*v->data),        \
+                &v->capacity, v->capacity * 2))                      \
+            return -1;                                               \
     v->data[v->size++] = t;                                          \
+    return 0;                                                        \
 }                                                                    \
-Type Name##_pop(Name *v)                                             \
+Type Vector_##Type##_pop(Vector_##Type *v)                           \
 {                                                                    \
     Type t;                                                          \
+    assert(v->sig == VEC_SIG);                                       \
+    assert(v->size);                                                 \
     t = v->data[--v->size];                                          \
     if (v->size <= v->capacity / 4 && v->capacity > v->min_capacity) \
-        Name##_resize(v, size_t_max(v->size * 2, v->min_capacity));  \
+        Vector_resize((void**)&v->data, sizeof(*v->data),            \
+            &v->capacity, VEC_MAX(v->capacity / 2, v->min_capacity));\
     return t;                                                        \
-}                                                                    \
-Name Name##_new(size_t min_capacity)                                 \
-{                                                                    \
-    Name t = (Name){ NULL, 0, 0, min_capacity };                     \
-    Name##_resize(&t, min_capacity);                                 \
-    return t;                                                        \
-}                                                                    \
-void Name##_del(Name *v)                                             \
-{                                                                    \
-    free(v->data);                                                   \
-    v->data     = NULL;                                              \
-    v->capacity = 0;                                                 \
-    v->size     = 0;                                                 \
 }
+FOR_EACH(VEC_DEF, VEC_TYPES)
+
+#define VEC_GEN_PUSH(Type) Vector_##Type*: Vector_##Type##_push,
+#define VEC_GEN_POP( Type) Vector_##Type*: Vector_##Type##_pop,
+
+#define push(v, a) _Generic((v), FOR_EACH(VEC_GEN_PUSH, VEC_TYPES) default: NULL)(v, a)
+#define pop( v)    _Generic((v), FOR_EACH(VEC_GEN_POP , VEC_TYPES) default: NULL)(v)
+#define del( v)    do{ assert((v)->sig == VEC_SIG); free((v)->data); (v)->sig = 0; }while(0)
 
 #endif