klist.h

   1 #ifndef _LH3_KLIST_H
   2 #define _LH3_KLIST_H
   3
   4 #include <stdlib.h>
   5
   6 #define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f)                                               \
   7         typedef struct {                                                                                                        \
   8                 size_t cnt, n, max;                                                                                             \
   9                 kmptype_t **buf;                                                                                                \
  10         } kmp_##name##_t;                                                                                                       \
  11         static inline kmp_##name##_t *kmp_init_##name() {                                       \
  12                 return calloc(1, sizeof(kmp_##name##_t));                                               \
  13         }                                                                                                                                       \
  14         static inline void kmp_destroy_##name(kmp_##name##_t *mp) {                     \
  15                 size_t k;                                                                                                               \
  16                 for (k = 0; k < mp->n; ++k) {                                                                   \
  17                         kmpfree_f(mp->buf[k]); free(mp->buf[k]);                                        \
  18                 }                                                                                                                               \
  19                 free(mp->buf); free(mp);                                                                                \
  20         }                                                                                                                                       \
  21         static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) {         \
  22                 ++mp->cnt;                                                                                                              \
  23                 if (mp->n == 0) return calloc(1, sizeof(kmptype_t));                    \
  24                 return mp->buf[--mp->n];                                                                                \
  25         }                                                                                                                                       \
  26         static inline void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \
  27                 --mp->cnt;                                                                                                              \
  28                 if (mp->n == mp->max) {                                                                                 \
  29                         mp->max = mp->max? mp->max<<1 : 16;                                                     \
  30                         mp->buf = realloc(mp->buf, sizeof(void*) * mp->max);            \
  31                 }                                                                                                                               \
  32                 mp->buf[mp->n++] = p;                                                                                   \
  33         }
  34
  35 #define kmempool_t(name) kmp_##name##_t
  36 #define kmp_init(name) kmp_init_##name()
  37 #define kmp_destroy(name, mp) kmp_destroy_##name(mp)
  38 #define kmp_alloc(name, mp) kmp_alloc_##name(mp)
  39 #define kmp_free(name, mp, p) kmp_free_##name(mp, p)
  40
  41 #define KLIST_INIT(name, kltype_t, kmpfree_t)                                                   \
  42         struct __kl1_##name {                                                                                           \
  43                 kltype_t data;                                                                                                  \
  44                 struct __kl1_##name *next;                                                                              \
  45         };                                                                                                                                      \
  46         typedef struct __kl1_##name kl1_##name;                                                         \
  47         KMEMPOOL_INIT(name, kl1_##name, kmpfree_t)                                                      \
  48         typedef struct {                                                                                                        \
  49                 kl1_##name *head, *tail;                                                                                \
  50                 kmp_##name##_t *mp;                                                                                             \
  51                 size_t size;                                                                                                    \
  52         } kl_##name##_t;                                                                                                        \
  53         static inline kl_##name##_t *kl_init_##name() {                                         \
  54                 kl_##name##_t *kl = calloc(1, sizeof(kl_##name##_t));                   \
  55                 kl->mp = kmp_init(name);                                                                                \
  56                 kl->head = kl->tail = kmp_alloc(name, kl->mp);                                  \
  57                 kl->head->next = 0;                                                                                             \
  58                 return kl;                                                                                                              \
  59         }                                                                                                                                       \
  60         static inline void kl_destroy_##name(kl_##name##_t *kl) {                       \
  61                 kl1_##name *p;                                                                                                  \
  62                 for (p = kl->head; p != kl->tail; p = p->next)                                  \
  63                         kmp_free(name, kl->mp, p);                                                                      \
  64                 kmp_free(name, kl->mp, p);                                                                              \
  65                 kmp_destroy(name, kl->mp);                                                                              \
  66                 free(kl);                                                                                                               \
  67         }                                                                                                                                       \
  68         static inline kltype_t *kl_pushp_##name(kl_##name##_t *kl) {            \
  69                 kl1_##name *q, *p = kmp_alloc(name, kl->mp);                                    \
  70                 q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p;    \
  71                 ++kl->size;                                                                                                             \
  72                 return &q->data;                                                                                                \
  73         }                                                                                                                                       \
  74         static inline int kl_shift_##name(kl_##name##_t *kl, kltype_t *d) { \
  75                 kl1_##name *p;                                                                                                  \
  76                 if (kl->head->next == 0) return -1;                                                             \
  77                 --kl->size;                                                                                                             \
  78                 p = kl->head; kl->head = kl->head->next;                                                \
  79                 if (d) *d = p->data;                                                                                    \
  80                 kmp_free(name, kl->mp, p);                                                                              \
  81                 return 0;                                                                                                               \
  82         }
  83
  84 #define kliter_t(name) kl1_##name
  85 #define klist_t(name) kl_##name##_t
  86 #define kl_val(iter) ((iter)->data)
  87 #define kl_next(iter) ((iter)->next)
  88 #define kl_begin(kl) ((kl)->head)
  89 #define kl_end(kl) ((kl)->tail)
  90
  91 #define kl_init(name) kl_init_##name()
  92 #define kl_destroy(name, kl) kl_destroy_##name(kl)
  93 #define kl_pushp(name, kl) kl_pushp_##name(kl)
  94 #define kl_shift(name, kl, d) kl_shift_##name(kl, d)
  95
  96 #endif