/** A generic linked list * * Linked lists a used for several data structures in the code. * * @author Steffen Vogel * @copyright 2017, Institute for Automation of Complex Power Systems, EONERC * @license GNU General Public License (version 3) * * VILLASnode * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . *********************************************************************************/ #include #include #include #include /* Compare functions */ static int cmp_lookup(const void *a, const void *b) { const struct { char *name; } *obj = a; return strcmp(obj->name, b); } static int cmp_contains(const void *a, const void *b) { return a == b ? 0 : 1; } static int cmp_sort(const void *a, const void *b, void *thunk) { cmp_cb_t cmp = (cmp_cb_t) thunk; return cmp(*(void **) a, *(void **) b); } int list_init(struct list *l) { assert(l->state == STATE_DESTROYED); pthread_mutex_init(&l->lock, NULL); l->length = 0; l->capacity = 0; l->array = NULL; l->state = STATE_INITIALIZED; return 0; } int list_destroy(struct list *l, dtor_cb_t destructor, bool release) { pthread_mutex_lock(&l->lock); assert(l->state != STATE_DESTROYED); for (size_t i = 0; i < list_length(l); i++) { void *e = list_at(l, i); if (destructor) destructor(e); if (release) free(e); } free(l->array); l->length = -1; l->capacity = 0; l->array = NULL; l->state = STATE_DESTROYED; pthread_mutex_unlock(&l->lock); pthread_mutex_destroy(&l->lock); return 0; } void list_push(struct list *l, void *p) { pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); /* Resize array if out of capacity */ if (l->length >= l->capacity) { l->capacity += LIST_CHUNKSIZE; l->array = realloc(l->array, l->capacity * sizeof(void *)); } l->array[l->length] = p; l->length++; pthread_mutex_unlock(&l->lock); } void list_remove(struct list *l, void *p) { int removed = 0; pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); for (size_t i = 0; i < list_length(l); i++) { if (list_at(l, i) == p) removed++; else l->array[i - removed] = list_at(l, i); } l->length -= removed; pthread_mutex_unlock(&l->lock); } void * list_lookup(struct list *l, const char *name) { return list_search(l, cmp_lookup, (void *) name); } ssize_t list_lookup_index(struct list *l, const char *name) { void *ptr = list_lookup(l, name); if (!ptr) return -1; return list_index(l, ptr); } int list_contains(struct list *l, void *p) { return list_count(l, cmp_contains, p); } int list_count(struct list *l, cmp_cb_t cmp, void *ctx) { int c = 0; void *e; pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); for (size_t i = 0; i < list_length(l); i++) { e = list_at(l, i); if (cmp(e, ctx) == 0) c++; } pthread_mutex_unlock(&l->lock); return c; } void * list_search(struct list *l, cmp_cb_t cmp, void *ctx) { void *e; pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); for (size_t i = 0; i < list_length(l); i++) { e = list_at(l, i); if (cmp(e, ctx) == 0) goto out; } e = NULL; /* not found */ out: pthread_mutex_unlock(&l->lock); return e; } void list_sort(struct list *l, cmp_cb_t cmp) { pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); qsort_r(l->array, l->length, sizeof(void *), cmp_sort, (void *) cmp); pthread_mutex_unlock(&l->lock); } int list_set(struct list *l, int index, void *value) { if (index >= l->length) return -1; l->array[index] = value; return 0; } ssize_t list_index(struct list *l, void *p) { void *e; ssize_t f; pthread_mutex_lock(&l->lock); assert(l->state == STATE_INITIALIZED); for (size_t i = 0; i < list_length(l); i++) { e = list_at(l, i); if (e == p) { f = i; goto found; } } f = -1; found: pthread_mutex_unlock(&l->lock); return f; }