list.h

Go to the documentation of this file.

// The MIT License (MIT)
// Copyright (c) 2017 Maksim Andrianov
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
#ifndef CDCONTAINERS_INCLUDE_CDCONTAINERS_LIST_H
#define CDCONTAINERS_INCLUDE_CDCONTAINERS_LIST_H

#include <cdcontainers/common.h>
#include <cdcontainers/status.h>

#include <assert.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdlib.h>

struct cdc_list_node {
  struct cdc_list_node *next;
  struct cdc_list_node *prev;
  void *data;
};

struct cdc_list {
  struct cdc_list_node *head;
  struct cdc_list_node *tail;
  size_t size;
  struct cdc_data_info *dinfo;
};

struct cdc_list_iter {
  struct cdc_list *container;
  struct cdc_list_node *current;
};

struct cdc_list_riter {
  struct cdc_list *container;
  struct cdc_list_node *current;
};

#define CDC_LIST_FOR_EACH(item, list) \
  for (cdc_list_node * (item) = (list->head); (item); (item) = (item)->next)

// Base
enum cdc_stat cdc_list_ctor(struct cdc_list **l, struct cdc_data_info *info);

enum cdc_stat cdc_list_ctorl(struct cdc_list **l, struct cdc_data_info *info,
                             ...);

enum cdc_stat cdc_list_ctorv(struct cdc_list **l, struct cdc_data_info *info,
                             va_list args);

void cdc_list_dtor(struct cdc_list *l);
// Element access
void *cdc_list_get(struct cdc_list *l, size_t index);

enum cdc_stat cdc_list_at(struct cdc_list *l, size_t index, void **elem);

static inline void *cdc_list_front(struct cdc_list *l)
{
  assert(l != NULL);
  assert(l->size > 0);

  return l->head->data;
}

static inline void *cdc_list_back(struct cdc_list *l)
{
  assert(l != NULL);
  assert(l->size > 0);

  return l->tail->data;
}
// Capacity
static inline size_t cdc_list_size(struct cdc_list *l)
{
  assert(l != NULL);

  return l->size;
}

static inline bool cdc_list_empty(struct cdc_list *l)
{
  assert(l != NULL);

  return l->size == 0;
}
// Modifiers
void cdc_list_set(struct cdc_list *l, size_t index, void *value);

enum cdc_stat cdc_list_push_back(struct cdc_list *l, void *value);

void cdc_list_pop_back(struct cdc_list *l);

enum cdc_stat cdc_list_push_front(struct cdc_list *l, void *value);

void cdc_list_pop_front(struct cdc_list *l);

enum cdc_stat cdc_list_insert(struct cdc_list *l, size_t index, void *value);

enum cdc_stat cdc_list_iinsert(struct cdc_list_iter *before, void *value);

void cdc_list_erase(struct cdc_list *l, size_t index);

void cdc_list_ierase(struct cdc_list_iter *pos);

void cdc_list_clear(struct cdc_list *l);

void cdc_list_swap(struct cdc_list *a, struct cdc_list *b);
// Operations
void cdc_list_splice(struct cdc_list_iter *position,
                     struct cdc_list_iter *first, struct cdc_list_iter *last);

void cdc_list_ssplice(struct cdc_list_iter *position,
                      struct cdc_list_iter *first);

void cdc_list_lsplice(struct cdc_list_iter *position, struct cdc_list *other);

void cdc_list_merge(struct cdc_list *l, struct cdc_list *other);

void cdc_list_cmerge(struct cdc_list *l, struct cdc_list *other,
                     cdc_binary_pred_fn_t compare);
void cdc_list_erase_if(struct cdc_list *l, cdc_unary_pred_fn_t pred);

void cdc_list_reverse(struct cdc_list *l);

void cdc_list_unique(struct cdc_list *l);

void cdc_list_punique(struct cdc_list *l, cdc_binary_pred_fn_t pred);

void cdc_list_sort(struct cdc_list *l);

void cdc_list_csort(struct cdc_list *l, cdc_binary_pred_fn_t compare);

void cdc_list_foreach(struct cdc_list *l, void (*cb)(void *));
// Iterators
static inline void cdc_list_begin(struct cdc_list *l, struct cdc_list_iter *it)
{
  assert(l != NULL);
  assert(it != NULL);

  it->container = l;
  it->current = l->head;
}

static inline void cdc_list_end(struct cdc_list *l, struct cdc_list_iter *it)
{
  assert(l != NULL);
  assert(it != NULL);

  it->container = l;
  it->current = NULL;
}

static inline void cdc_list_rbegin(struct cdc_list *l,
                                   struct cdc_list_riter *it)
{
  assert(l != NULL);
  assert(it != NULL);

  it->container = l;
  it->current = l->tail;
}

static inline void cdc_list_rend(struct cdc_list *l, struct cdc_list_riter *it)
{
  assert(l != NULL);
  assert(it != NULL);

  it->container = l;
  it->current = NULL;
}
// Iterators
static inline void cdc_list_iter_next(struct cdc_list_iter *it)
{
  assert(it != NULL);

  it->current = it->current->next;
}

static inline void cdc_list_iter_prev(struct cdc_list_iter *it)
{
  assert(it != NULL);

  it->current = it->current ? it->current->prev : it->container->tail;
}

static inline bool cdc_list_iter_has_next(struct cdc_list_iter *it)
{
  assert(it != NULL);

  return it->current->next != NULL;
}

static inline bool cdc_list_iter_has_prev(struct cdc_list_iter *it)
{
  assert(it != NULL);

  return it->current->prev != NULL;
}

static inline void *cdc_list_iter_data(struct cdc_list_iter *it)
{
  assert(it != NULL);

  return it->current->data;
}

static inline void cdc_list_iter_from(struct cdc_list_riter *rit,
                                      struct cdc_list_iter *it)
{
  assert(rit != NULL);
  assert(it != NULL);

  it->container = rit->container;
  it->current = rit->current ? rit->current->next : rit->container->head;
}

static inline bool cdc_list_iter_is_eq(struct cdc_list_iter *it1,
                                       struct cdc_list_iter *it2)
{
  assert(it1 != NULL);
  assert(it2 != NULL);

  return it1->container == it2->container && it1->current == it2->current;
}

static inline void cdc_list_riter_next(struct cdc_list_riter *it)
{
  assert(it != NULL);

  it->current = it->current->prev;
}

static inline void cdc_list_riter_prev(struct cdc_list_riter *it)
{
  assert(it != NULL);

  it->current = it->current ? it->current->next : it->container->head;
}

static inline bool cdc_list_riter_has_next(struct cdc_list_riter *it)
{
  assert(it != NULL);

  return it->current->prev != NULL;
}

static inline bool cdc_list_riter_has_prev(struct cdc_list_riter *it)
{
  assert(it != NULL);

  return it->current->next != NULL;
}

static inline void *cdc_list_riter_data(struct cdc_list_riter *it)
{
  assert(it != NULL);

  return it->current->data;
}

static inline void cdc_list_riter_from(struct cdc_list_iter *it,
                                       struct cdc_list_riter *rit)
{
  assert(it != NULL);
  assert(rit != NULL);

  rit->container = it->container;
  rit->current = it->current ? it->current->prev : it->container->tail;
}

static inline bool cdc_list_riter_is_eq(struct cdc_list_riter *rit1,
                                        struct cdc_list_riter *rit2)
{
  assert(rit1 != NULL);
  assert(rit2 != NULL);

  return rit1->container == rit2->container && rit1->current == rit2->current;
}
// Short names
#ifdef CDC_USE_SHORT_NAMES
typedef struct cdc_list list_t;
typedef struct cdc_list_iter list_iter_t;
typedef struct cdc_list_riter list_riter_t;

// Base
#define list_ctor(...) cdc_list_ctor(__VA_ARGS__)
#define list_ctorl(...) cdc_list_ctorl(__VA_ARGS__)
#define list_ctorv(...) cdc_list_ctorv(__VA_ARGS__)
#define list_dtor(...) cdc_list_dtor(__VA_ARGS__)

// Element access
#define list_at(...) cdc_list_at(__VA_ARGS__)
#define list_front(...) cdc_list_front(__VA_ARGS__)
#define list_back(...) cdc_list_back(__VA_ARGS__)

// Capacity
#define list_empty(...) cdc_list_empty(__VA_ARGS__)
#define list_size(...) cdc_list_size(__VA_ARGS__)

// Modifiers
#define list_insert(...) cdc_list_insert(__VA_ARGS__)
#define list_iinsert(...) cdc_list_iinsert(__VA_ARGS__)
#define list_erase(...) cdc_list_erase(__VA_ARGS__)
#define list_ierase(...) cdc_list_ierase(__VA_ARGS__)
#define list_clear(...) cdc_list_clear(__VA_ARGS__)
#define list_push_back(...) cdc_list_push_back(__VA_ARGS__)
#define list_pop_back(...) cdc_list_pop_back(__VA_ARGS__)
#define list_push_front(...) cdc_list_push_front(__VA_ARGS__)
#define list_pop_front(...) cdc_list_pop_back(__VA_ARGS__)
#define list_swap(...) cdc_list_swap(__VA_ARGS__)

// Operations
#define list_splice(...) cdc_list_splice(__VA_ARGS__)
#define list_ssplice(...) cdc_list_ssplice(__VA_ARGS__)
#define list_lsplice(...) cdc_list_lsplice(__VA_ARGS__)
#define list_merge(...) cdc_list_merge(__VA_ARGS__)
#define list_cmerge(...) cdc_list_cmerge(__VA_ARGS__)
#define list_erase_if(...) cdc_list_erase_if(__VA_ARGS__)
#define list_reverse(...) cdc_list_reverse(__VA_ARGS__)
#define list_unique(...) cdc_list_unique(__VA_ARGS__)
#define list_punique(...) cdc_list_punique(__VA_ARGS__)
#define list_sort(...) cdc_list_sort(__VA_ARGS__)
#define list_csort(...) cdc_list_csort(__VA_ARGS__)

#define list_foreach(...) cdc_list_foreach(__VA_ARGS__)

// Iterators
#define list_begin(...) cdc_list_begin(__VA_ARGS__)
#define list_end(...) cdc_list_end(__VA_ARGS__)
#define list_rbegin(...) cdc_list_rbegin(__VA_ARGS__)
#define list_rend(...) cdc_list_rend(__VA_ARGS__)

// Iterators
#define list_iter_next(...) cdc_list_iter_next(__VA_ARGS__)
#define list_iter_prev(...) cdc_list_iter_prev(__VA_ARGS__)
#define list_iter_has_next(...) cdc_list_iter_has_next(__VA_ARGS__)
#define list_iter_has_prev(...) cdc_list_iter_has_prev(__VA_ARGS__)
#define list_iter_data(...) cdc_list_iter_data(__VA_ARGS__)
#define list_riter_from(...) cdc_list_riter_from(__VA_ARGS__)
#define list_iter_is_eq(...) cdc_list_iter_is_eq(__VA_ARGS__)

#define list_riter_next(...) cdc_list_riter_next(__VA_ARGS__)
#define list_riter_prev(...) cdc_list_riter_prev(__VA_ARGS__)
#define list_riter_has_next(...) cdc_list_riter_has_next(__VA_ARGS__)
#define list_riter_has_prev(...) cdc_list_riter_has_prev(__VA_ARGS__)
#define list_riter_data(...) cdc_list_riter_data(__VA_ARGS__)
#define list_iter_from(...) cdc_list_iter_from(__VA_ARGS__)
#define list_riter_is_eq(...) cdc_list_riter_is_eq(__VA_ARGS__)
#endif

#endif  // CDCONTAINERS_INCLUDE_CDCONTAINERS_LIST_H