You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
183 lines
13 KiB
183 lines
13 KiB
/* This file is part of MIR project.
|
|
Copyright (C) 2018-2021 Vladimir Makarov <vmakarov.gcc@gmail.com>.
|
|
*/
|
|
|
|
/* Typed doubly linked lists. */
|
|
|
|
#ifndef MIR_DLIST_H
|
|
|
|
#define MIR_DLIST_H
|
|
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
|
|
#if !defined(DLIST_ENABLE_CHECKING) && !defined(NDEBUG)
|
|
#define DLIST_ENABLE_CHECKING
|
|
#endif
|
|
|
|
#ifndef DLIST_ENABLE_CHECKING
|
|
#define DLIST_ASSERT(EXPR, OP, T) ((void) (EXPR))
|
|
|
|
#else
|
|
static inline void dlist_assert_fail (const char* op, const char* var) {
|
|
fprintf (stderr, "wrong %s for %s", op, var);
|
|
assert (0);
|
|
}
|
|
|
|
#define DLIST_ASSERT(EXPR, OP, T) (void) ((EXPR) ? 0 : (dlist_assert_fail (OP, #T), 0))
|
|
|
|
#endif
|
|
|
|
#ifdef __GNUC__
|
|
#define MIR_DLIST_UNUSED __attribute__ ((unused))
|
|
#else
|
|
#define MIR_DLIST_UNUSED
|
|
#endif
|
|
|
|
#define DLIST(T) DLIST_##T
|
|
#define DLIST_OP(T, OP) DLIST_##T##_##OP
|
|
#define DLIST_OP_DEF(T, OP) MIR_DLIST_UNUSED DLIST_OP (T, OP)
|
|
#define DLIST_LINK(T) DLIST_LINK_##T
|
|
|
|
#define DLIST_LINK_T(T) \
|
|
typedef struct DLIST_LINK (T) { \
|
|
T prev, next; \
|
|
} DLIST_LINK (T)
|
|
|
|
#define DEF_DLIST_LINK(T) DLIST_LINK_T (T);
|
|
|
|
#define DEF_DLIST_TYPE(T) \
|
|
typedef struct DLIST (T) { \
|
|
T head, tail; \
|
|
} DLIST (T)
|
|
|
|
#define DEF_DLIST_CODE(T, LINK) \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, init) (DLIST (T) * list) { list->head = list->tail = NULL; } \
|
|
\
|
|
static inline T DLIST_OP_DEF (T, head) (DLIST (T) * list) { return list->head; } \
|
|
\
|
|
static inline T DLIST_OP_DEF (T, tail) (DLIST (T) * list) { return list->tail; } \
|
|
\
|
|
static inline T DLIST_OP_DEF (T, prev) (T elem) { return elem->LINK.prev; } \
|
|
static inline T DLIST_OP_DEF (T, next) (T elem) { return elem->LINK.next; } \
|
|
\
|
|
static inline T DLIST_OP_DEF (T, el) (DLIST (T) * list, int n) { \
|
|
T e; \
|
|
\
|
|
if (n >= 0) { \
|
|
for (e = list->head; e != NULL && n != 0; e = e->LINK.next, n--) \
|
|
; \
|
|
} else { \
|
|
for (e = list->tail; e != NULL && n != -1; e = e->LINK.prev, n++) \
|
|
; \
|
|
} \
|
|
return e; \
|
|
} \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, prepend) (DLIST (T) * list, T elem) { \
|
|
DLIST_ASSERT (list&& elem, "prepend", T); \
|
|
if (list->head == NULL) { \
|
|
DLIST_ASSERT (list->tail == NULL, "prepend", T); \
|
|
list->tail = elem; \
|
|
} else { \
|
|
DLIST_ASSERT (list->head->LINK.prev == NULL, "prepend", T); \
|
|
list->head->LINK.prev = elem; \
|
|
} \
|
|
elem->LINK.prev = NULL; \
|
|
elem->LINK.next = list->head; \
|
|
list->head = elem; \
|
|
} \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, append) (DLIST (T) * list, T elem) { \
|
|
DLIST_ASSERT (list&& elem, "append", T); \
|
|
if (list->tail == NULL) { \
|
|
DLIST_ASSERT (list->head == NULL, "append", T); \
|
|
list->head = elem; \
|
|
} else { \
|
|
DLIST_ASSERT (list->tail->LINK.next == NULL, "append", T); \
|
|
list->tail->LINK.next = elem; \
|
|
} \
|
|
elem->LINK.next = NULL; \
|
|
elem->LINK.prev = list->tail; \
|
|
list->tail = elem; \
|
|
} \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, insert_before) (DLIST (T) * list, T before, T elem) { \
|
|
DLIST_ASSERT (list&& before&& elem && list->tail, "insert_before", T); \
|
|
if (before->LINK.prev == NULL) { \
|
|
DLIST_ASSERT (list->head == before, "insert_before", T); \
|
|
before->LINK.prev = elem; \
|
|
elem->LINK.next = before; \
|
|
elem->LINK.prev = NULL; \
|
|
list->head = elem; \
|
|
} else { \
|
|
DLIST_ASSERT (list->head, "insert_before", T); \
|
|
before->LINK.prev->LINK.next = elem; \
|
|
elem->LINK.prev = before->LINK.prev; \
|
|
before->LINK.prev = elem; \
|
|
elem->LINK.next = before; \
|
|
} \
|
|
} \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, insert_after) (DLIST (T) * list, T after, T elem) { \
|
|
DLIST_ASSERT (list&& after&& elem && list->head, "insert_after", T); \
|
|
if (after->LINK.next == NULL) { \
|
|
DLIST_ASSERT (list->tail == after, "insert_after", T); \
|
|
after->LINK.next = elem; \
|
|
elem->LINK.prev = after; \
|
|
elem->LINK.next = NULL; \
|
|
list->tail = elem; \
|
|
} else { \
|
|
DLIST_ASSERT (list->tail, "insert_after", T); \
|
|
after->LINK.next->LINK.prev = elem; \
|
|
elem->LINK.next = after->LINK.next; \
|
|
after->LINK.next = elem; \
|
|
elem->LINK.prev = after; \
|
|
} \
|
|
} \
|
|
\
|
|
static inline void DLIST_OP_DEF (T, remove) (DLIST (T) * list, T elem) { \
|
|
DLIST_ASSERT (list&& elem, "remove", T); \
|
|
if (elem->LINK.prev != NULL) { \
|
|
elem->LINK.prev->LINK.next = elem->LINK.next; \
|
|
} else { \
|
|
DLIST_ASSERT (list->head == elem, "remove", T); \
|
|
list->head = elem->LINK.next; \
|
|
} \
|
|
if (elem->LINK.next != NULL) { \
|
|
elem->LINK.next->LINK.prev = elem->LINK.prev; \
|
|
} else { \
|
|
DLIST_ASSERT (list->tail == elem, "remove", T); \
|
|
list->tail = elem->LINK.prev; \
|
|
} \
|
|
elem->LINK.prev = elem->LINK.next = NULL; \
|
|
} \
|
|
\
|
|
static inline size_t DLIST_OP_DEF (T, length) (DLIST (T) * list) { \
|
|
size_t len = 0; \
|
|
T curr; \
|
|
\
|
|
for (curr = list->head; curr != NULL; curr = curr->LINK.next) len++; \
|
|
return len; \
|
|
}
|
|
|
|
#define DEF_DLIST(T, LINK) \
|
|
DEF_DLIST_TYPE (T); \
|
|
DEF_DLIST_CODE (T, LINK)
|
|
|
|
#define DLIST_INIT(T, L) (DLIST_OP (T, init) (&(L)))
|
|
#define DLIST_HEAD(T, L) (DLIST_OP (T, head) (&(L)))
|
|
#define DLIST_TAIL(T, L) (DLIST_OP (T, tail) (&(L)))
|
|
#define DLIST_PREV(T, E) (DLIST_OP (T, prev) (E))
|
|
#define DLIST_NEXT(T, E) (DLIST_OP (T, next) (E))
|
|
#define DLIST_EL(T, L, N) (DLIST_OP (T, el) (&(L), N))
|
|
#define DLIST_PREPEND(T, L, E) (DLIST_OP (T, prepend) (&(L), (E)))
|
|
#define DLIST_APPEND(T, L, E) (DLIST_OP (T, append) (&(L), (E)))
|
|
#define DLIST_INSERT_BEFORE(T, L, B, E) (DLIST_OP (T, insert_before) (&(L), (B), (E)))
|
|
#define DLIST_INSERT_AFTER(T, L, A, E) (DLIST_OP (T, insert_after) (&(L), (A), (E)))
|
|
#define DLIST_REMOVE(T, L, E) (DLIST_OP (T, remove) (&(L), (E)))
|
|
#define DLIST_LENGTH(T, L) (DLIST_OP (T, length) (&(L)))
|
|
|
|
#endif /* #ifndef MIR_DLIST_H */
|