| /***************************************************************************** | |
| * list.c | |
| ***************************************************************************** | |
| * Copyright (C) 2001-2002 The Regents of the University of California. | |
| * Copyright (C) 2021 NVIDIA Corporation. | |
| * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). | |
| * Written by Chris Dunlap <cdunlap@llnl.gov>. | |
| * | |
| * This file is from LSD-Tools, the LLNL Software Development Toolbox. | |
| * | |
| * LSD-Tools 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 2 of the License, or (at your option) | |
| * any later version. | |
| * | |
| * In addition, as a special exception, the copyright holders give permission | |
| * to link the code of portions of this program with the OpenSSL library under | |
| * certain conditions as described in each individual source file, and | |
| * distribute linked combinations including the two. You must obey the GNU | |
| * General Public License in all respects for all of the code used other than | |
| * OpenSSL. If you modify file(s) with this exception, you may extend this | |
| * exception to your version of the file(s), but you are not obligated to do | |
| * so. If you do not wish to do so, delete this exception statement from your | |
| * version. If you delete this exception statement from all source files in | |
| * the program, then also delete it here. | |
| * | |
| * LSD-Tools 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 LSD-Tools; if not, write to the Free Software Foundation, Inc., | |
| * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. | |
| ***************************************************************************** | |
| * Refer to "list.h" for documentation on public functions. | |
| *****************************************************************************/ | |
| #include "config.h" | |
| #include <pthread.h> | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| #include "src/common/list.h" | |
| #include "src/common/log.h" | |
| #include "src/common/macros.h" | |
| #include "src/common/xassert.h" | |
| #include "src/common/xmalloc.h" | |
| /* | |
| ** Define slurm-specific aliases for use by plugins, see slurm_xlator.h | |
| ** for details. | |
| */ | |
| strong_alias(list_create, slurm_list_create); | |
| strong_alias(list_destroy, slurm_list_destroy); | |
| strong_alias(list_is_empty, slurm_list_is_empty); | |
| strong_alias(list_count, slurm_list_count); | |
| strong_alias(list_shallow_copy, slurm_list_shallow_copy); | |
| strong_alias(list_append, slurm_list_append); | |
| strong_alias(list_append_list, slurm_list_append_list); | |
| strong_alias(list_transfer, slurm_list_transfer); | |
| strong_alias(list_transfer_max, slurm_list_transfer_max); | |
| strong_alias(list_transfer_unique, slurm_list_transfer_unique); | |
| strong_alias(list_push, list_prepend); | |
| strong_alias(list_push, slurm_list_prepend); | |
| strong_alias(list_find_first, slurm_list_find_first); | |
| strong_alias(list_find_first_ro, slurm_list_find_first_ro); | |
| strong_alias(list_delete_all, slurm_list_delete_all); | |
| strong_alias(list_delete_first, slurm_list_delete_first); | |
| strong_alias(list_delete_ptr, slurm_list_delete_ptr); | |
| strong_alias(list_for_each, slurm_list_for_each); | |
| strong_alias(list_for_each_ro, slurm_list_for_each_ro); | |
| strong_alias(list_for_each_max, slurm_list_for_each_max); | |
| strong_alias(list_flush, slurm_list_flush); | |
| strong_alias(list_flush_max, slurm_list_flush_max); | |
| strong_alias(list_sort, slurm_list_sort); | |
| strong_alias(list_flip, slurm_list_flip); | |
| strong_alias(list_push, slurm_list_push); | |
| strong_alias(list_pop, slurm_list_pop); | |
| strong_alias(list_peek, slurm_list_peek); | |
| strong_alias(list_append, list_enqueue); | |
| strong_alias(list_append, slurm_list_enqueue); | |
| strong_alias(list_pop, list_dequeue); | |
| strong_alias(list_pop, slurm_list_dequeue); | |
| strong_alias(list_iterator_create, slurm_list_iterator_create); | |
| strong_alias(list_iterator_reset, slurm_list_iterator_reset); | |
| strong_alias(list_iterator_destroy, slurm_list_iterator_destroy); | |
| strong_alias(list_next, slurm_list_next); | |
| strong_alias(list_insert, slurm_list_insert); | |
| strong_alias(list_find, slurm_list_find); | |
| strong_alias(list_remove, slurm_list_remove); | |
| strong_alias(list_remove_first, slurm_list_remove_first); | |
| strong_alias(list_delete_item, slurm_list_delete_item); | |
| /*************** | |
| * Constants * | |
| ***************/ | |
| #define LIST_MAGIC 0xDEADBEEF | |
| #define LIST_ITR_MAGIC 0xDEADBEFF | |
| /**************** | |
| * Data Types * | |
| ****************/ | |
| typedef struct listNode { | |
| void *data; /* node's data */ | |
| struct listNode *next; /* next node in list */ | |
| } list_node_t; | |
| struct listIterator { | |
| unsigned int magic; /* sentinel for asserting validity */ | |
| list_t *list; /* the list being iterated */ | |
| list_node_t *pos; /* the next node to be iterated */ | |
| list_node_t **prev; /* addr of 'next' ptr to prv It node */ | |
| list_itr_t *iNext; /* iterator chain for list_destroy() */ | |
| }; | |
| struct xlist { | |
| unsigned int magic; /* sentinel for asserting validity */ | |
| int count; /* number of nodes in list */ | |
| list_node_t *head; /* head of the list */ | |
| list_node_t **tail; /* addr of last node's 'next' ptr */ | |
| list_itr_t *iNext; /* iterator chain for list_destroy() */ | |
| ListDelF fDel; /* function to delete node data */ | |
| pthread_rwlock_t mutex; /* mutex to protect access to list */ | |
| pthread_t tid; /* id of thread holding write lock */ | |
| list_node_t *free_nodes; /* head of unused nodes */ | |
| list_node_t *node_allocations; /* memory for additional nodes */ | |
| list_node_t nodes[]; /* THIS MUST BE THE LAST PART OF THE STRUCT */ | |
| }; | |
| /* | |
| * Fix as many list_node_t elements into a 4k page alongside the list as | |
| * possible. Leave at least 32 bytes off to account for xmalloc() and malloc() | |
| * overhead. | |
| */ | |
| static const int nodes_in_page = (4064 - sizeof(list_t)) / sizeof(list_node_t); | |
| /**************** | |
| * Macros | |
| ****************/ | |
| #define LIST_THREAD_LOCK_DEF pthread_t tid = pthread_self(); bool locked = false; | |
| #define LIST_THREAD_LOCK(l, write_lock) \ | |
| do { \ | |
| /* \ | |
| * If I am on the same thread and already locked, \ | |
| * don't lock again. \ | |
| */ \ | |
| if (!pthread_equal(l->tid, tid)) { \ | |
| if (write_lock) { \ | |
| slurm_rwlock_wrlock(&l->mutex); \ | |
| /* Only set tid under a write lock */ \ | |
| l->tid = tid; \ | |
| } else { \ | |
| slurm_rwlock_rdlock(&l->mutex); \ | |
| xassert(!l->tid); \ | |
| } \ | |
| locked = true; \ | |
| } else { \ | |
| debug3("%s: list lock already held by this thread", \ | |
| __func__); \ | |
| } \ | |
| } while (0) | |
| #define LIST_THREAD_UNLOCK(l, write_lock) \ | |
| do { \ | |
| if (locked) { \ | |
| /* Only clear tid under a write lock */ \ | |
| if (write_lock) \ | |
| l->tid = 0; \ | |
| slurm_rwlock_unlock(&l->mutex); \ | |
| } \ | |
| } while (0) | |
| /**************** | |
| * Prototypes * | |
| ****************/ | |
| static void _list_node_create(list_t *l, list_node_t **pp, void *x); | |
| static void *_list_node_destroy(list_t *l, list_node_t **pp); | |
| static void *_list_find_first_locked(list_t *l, ListFindF f, void *key); | |
| #ifndef NDEBUG | |
| static int _list_mutex_is_locked(pthread_rwlock_t *mutex); | |
| #endif | |
| /*************** | |
| * Functions * | |
| ***************/ | |
| extern list_t *list_create(ListDelF f) | |
| { | |
| list_t *l = xmalloc(sizeof(*l) + (nodes_in_page * sizeof(list_node_t))); | |
| l->magic = LIST_MAGIC; | |
| l->head = NULL; | |
| l->tail = &l->head; | |
| l->iNext = NULL; | |
| l->fDel = f; | |
| l->count = 0; | |
| slurm_rwlock_init(&l->mutex); | |
| l->node_allocations = NULL; | |
| l->free_nodes = &l->nodes[0]; | |
| for (int i = 0; i < (nodes_in_page - 1); i++) | |
| l->nodes[i].next = &l->nodes[i + 1]; | |
| return l; | |
| } | |
| extern void list_destroy(list_t *l) | |
| { | |
| list_itr_t *i, *iTmp; | |
| list_node_t *p, *pTmp; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| i = l->iNext; | |
| while (i) { | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| i->magic = ~LIST_ITR_MAGIC; | |
| iTmp = i->iNext; | |
| xfree(i); | |
| i = iTmp; | |
| } | |
| p = l->head; | |
| while (p) { | |
| if (p->data && l->fDel) | |
| l->fDel(p->data); | |
| p = p->next; | |
| } | |
| p = l->node_allocations; | |
| while (p) { | |
| pTmp = p->next; | |
| xfree(p); | |
| p = pTmp; | |
| } | |
| l->magic = ~LIST_MAGIC; | |
| slurm_rwlock_unlock(&l->mutex); | |
| slurm_rwlock_destroy(&l->mutex); | |
| xfree(l); | |
| } | |
| extern int list_is_empty(list_t *l) | |
| { | |
| int n; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_rdlock(&l->mutex); | |
| n = l->count; | |
| slurm_rwlock_unlock(&l->mutex); | |
| return (n == 0); | |
| } | |
| /* | |
| * Return the number of items in list [l]. | |
| * If [l] is NULL, return 0. | |
| */ | |
| extern int list_count(list_t *l) | |
| { | |
| int n; | |
| LIST_THREAD_LOCK_DEF; | |
| if (!l) | |
| return 0; | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, false); | |
| n = l->count; | |
| LIST_THREAD_UNLOCK(l, false); | |
| return n; | |
| } | |
| extern list_t *list_shallow_copy(list_t *l) | |
| { | |
| list_t *m = list_create(NULL); | |
| (void) list_append_list(m, l); | |
| return m; | |
| } | |
| extern void list_append(list_t *l, void *x) | |
| { | |
| LIST_THREAD_LOCK_DEF; | |
| xassert(l != NULL); | |
| xassert(x != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, true); | |
| _list_node_create(l, l->tail, x); | |
| LIST_THREAD_UNLOCK(l, true); | |
| } | |
| extern int list_append_list(list_t *l, list_t *sub) | |
| { | |
| int n = 0; | |
| list_node_t *p; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(l->fDel == NULL); | |
| xassert(sub != NULL); | |
| xassert(sub->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| slurm_rwlock_wrlock(&sub->mutex); | |
| p = sub->head; | |
| while (p) { | |
| _list_node_create(l, l->tail, p->data); | |
| n++; | |
| p = p->next; | |
| } | |
| slurm_rwlock_unlock(&sub->mutex); | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| /* | |
| * Pops off list [sub] to [l] with maximum number of entries. | |
| * Set max = 0 to transfer all entries. | |
| * Note: list [l] must have the same destroy function as list [sub]. | |
| * Note: list [sub] may be returned empty, but not destroyed. | |
| * Returns a count of the number of items added to list [l]. | |
| */ | |
| extern int list_transfer_max(list_t *l, list_t *sub, int max) | |
| { | |
| void *v; | |
| int n = 0; | |
| xassert(l); | |
| xassert(sub); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(sub->magic == LIST_MAGIC); | |
| xassert(l->fDel == sub->fDel); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| slurm_rwlock_wrlock(&sub->mutex); | |
| while ((!max || n <= max) && (v = _list_node_destroy(sub, &sub->head))) { | |
| _list_node_create(l, l->tail, v); | |
| n++; | |
| } | |
| slurm_rwlock_unlock(&sub->mutex); | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| extern int list_transfer_match(list_t *l, list_t *sub, ListFindF f, void *key) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| xassert(l); | |
| xassert(sub); | |
| xassert(l != sub); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(sub->magic == LIST_MAGIC); | |
| xassert(l->fDel == sub->fDel); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| slurm_rwlock_wrlock(&sub->mutex); | |
| pp = &l->head; | |
| while (*pp) { | |
| if (f((*pp)->data, key)) { | |
| if ((v = _list_node_destroy(l, pp))) | |
| n++; | |
| _list_node_create(sub, sub->tail, v); | |
| } else { | |
| pp = &(*pp)->next; | |
| } | |
| } | |
| slurm_rwlock_unlock(&sub->mutex); | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| /* | |
| * Pops off list [sub] to [l]. | |
| * Set max = 0 to transfer all entries. | |
| * Note: list [l] must have the same destroy function as list [sub]. | |
| * Note: list [sub] will be returned empty, but not destroyed. | |
| * Returns a count of the number of items added to list [l]. | |
| */ | |
| extern int list_transfer(list_t *l, list_t *sub) | |
| { | |
| return list_transfer_max(l, sub, 0); | |
| } | |
| /* | |
| * Pop off elements in list [sub] to [l], unless already in [l]. | |
| * Note: list [l] must have the same destroy function as list [sub]. | |
| * Note: list [l] could contain repeated elements, but those aren't removed. | |
| * Note: list [sub] will be returned with repeated elements or empty, | |
| * but never destroyed. | |
| * Returns a count of the number of items added to list [l]. | |
| */ | |
| extern int list_transfer_unique(list_t *l, ListFindF f, list_t *sub) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| xassert(l); | |
| xassert(f); | |
| xassert(sub); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(sub->magic == LIST_MAGIC); | |
| xassert(l->fDel == sub->fDel); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| slurm_rwlock_wrlock(&sub->mutex); | |
| pp = &sub->head; | |
| while (*pp) { | |
| v = (*pp)->data; | |
| /* Is this element already in destination list? */ | |
| if (!_list_find_first_locked(l, f, v)) { | |
| /* Not found: Transfer the element */ | |
| _list_node_create(l, l->tail, v); | |
| /* Destroy increases index */ | |
| _list_node_destroy(sub, pp); | |
| n++; | |
| } else | |
| /* Found: Just increase index */ | |
| pp = &(*pp)->next; | |
| } | |
| slurm_rwlock_unlock(&sub->mutex); | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| static void *_list_find_first_locked(list_t *l, ListFindF f, void *key) | |
| { | |
| for (list_node_t *p = l->head; p; p = p->next) { | |
| if (f(p->data, key)) | |
| return p->data; | |
| } | |
| return NULL; | |
| } | |
| static void *_list_find_first_lock(list_t *l, ListFindF f, void *key, | |
| bool write_lock) | |
| { | |
| void *v = NULL; | |
| LIST_THREAD_LOCK_DEF; | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, write_lock); | |
| v = _list_find_first_locked(l, f, key); | |
| LIST_THREAD_UNLOCK(l, write_lock); | |
| return v; | |
| } | |
| extern void *list_find_first(list_t *l, ListFindF f, void *key) | |
| { | |
| return _list_find_first_lock(l, f, key, true); | |
| } | |
| /* | |
| * Same as list_find_first, but use a rdlock instead of wrlock | |
| */ | |
| extern void *list_find_first_ro(list_t *l, ListFindF f, void *key) | |
| { | |
| return _list_find_first_lock(l, f, key, false); | |
| } | |
| extern void *list_remove_first(list_t *l, ListFindF f, void *key) | |
| { | |
| list_node_t **pp; | |
| void *v = NULL; | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(key != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| pp = &l->head; | |
| while (*pp) { | |
| if (f((*pp)->data, key)) { | |
| v = _list_node_destroy(l, pp); | |
| break; | |
| } else { | |
| pp = &(*pp)->next; | |
| } | |
| } | |
| slurm_rwlock_unlock(&l->mutex); | |
| return v; | |
| } | |
| extern int list_delete_all(list_t *l, ListFindF f, void *key) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| LIST_THREAD_LOCK_DEF | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, true); | |
| pp = &l->head; | |
| while (*pp) { | |
| if (f((*pp)->data, key)) { | |
| if ((v = _list_node_destroy(l, pp))) { | |
| if (l->fDel) | |
| l->fDel(v); | |
| n++; | |
| } | |
| } | |
| else { | |
| pp = &(*pp)->next; | |
| } | |
| } | |
| LIST_THREAD_UNLOCK(l, true); | |
| return n; | |
| } | |
| extern int list_delete_first(list_t *l, ListFindF f, void *key) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| pp = &l->head; | |
| while (*pp) { | |
| int rc = f((*pp)->data, key); | |
| if (rc > 0) { | |
| if ((v = _list_node_destroy(l, pp))) { | |
| if (l->fDel) | |
| l->fDel(v); | |
| } | |
| n = 1; | |
| break; | |
| } else if (rc < 0) { | |
| n = -1; | |
| break; | |
| } else { | |
| pp = &(*pp)->next; | |
| } | |
| } | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| extern int list_delete_ptr(list_t *l, void *key) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| LIST_THREAD_LOCK_DEF | |
| xassert(l); | |
| xassert(key); | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, true); | |
| pp = &l->head; | |
| while (*pp) { | |
| if ((*pp)->data == key) { | |
| if ((v = _list_node_destroy(l, pp))) { | |
| if (l->fDel) | |
| l->fDel(v); | |
| n = 1; | |
| break; | |
| } | |
| } else | |
| pp = &(*pp)->next; | |
| } | |
| LIST_THREAD_UNLOCK(l, true); | |
| return n; | |
| } | |
| extern int list_for_each(list_t *l, ListForF f, void *arg) | |
| { | |
| int max = -1; /* all values */ | |
| return list_for_each_max(l, &max, f, arg, 1, true); | |
| } | |
| extern int list_for_each_ro(list_t *l, ListForF f, void *arg) | |
| { | |
| int max = -1; /* all values */ | |
| return list_for_each_max(l, &max, f, arg, 1, false); | |
| } | |
| extern int list_for_each_nobreak(list_t *l, ListForF f, void *arg) | |
| { | |
| int max = -1; /* all values */ | |
| return list_for_each_max(l, &max, f, arg, 0, true); | |
| } | |
| extern int list_for_each_max(list_t *l, int *max, ListForF f, void *arg, | |
| int break_on_fail, int write_lock) | |
| { | |
| list_node_t *p; | |
| int n = 0; | |
| bool failed = false; | |
| LIST_THREAD_LOCK_DEF; | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| LIST_THREAD_LOCK(l, write_lock); | |
| for (p = l->head; (*max == -1 || n < *max) && p; p = p->next) { | |
| n++; | |
| if (f(p->data, arg) < 0) { | |
| failed = true; | |
| if (break_on_fail) | |
| break; | |
| } | |
| } | |
| *max = l->count - n; | |
| LIST_THREAD_UNLOCK(l, write_lock); | |
| if (failed) | |
| n = -n; | |
| return n; | |
| } | |
| extern int list_flush(list_t *l) | |
| { | |
| return list_flush_max(l, -1); | |
| } | |
| extern int list_flush_max(list_t *l, int max) | |
| { | |
| list_node_t **pp; | |
| void *v; | |
| int n = 0; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| pp = &l->head; | |
| for (int i = 0; (max < 0 || i < max) && *pp; i++) { | |
| if ((v = _list_node_destroy(l, pp))) { | |
| if (l->fDel) | |
| l->fDel(v); | |
| n++; | |
| } | |
| } | |
| slurm_rwlock_unlock(&l->mutex); | |
| return n; | |
| } | |
| extern void list_push(list_t *l, void *x) | |
| { | |
| xassert(l != NULL); | |
| xassert(x != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| _list_node_create(l, &l->head, x); | |
| slurm_rwlock_unlock(&l->mutex); | |
| } | |
| /* | |
| * Handle translation between ListCmpF and signature required by qsort. | |
| * glibc has this as __compar_fn_t, but that's non-standard so we define | |
| * our own instead. | |
| */ | |
| typedef int (*ConstListCmpF) (__const void *, __const void *); | |
| /* | |
| * This function uses the libC qsort(). | |
| */ | |
| extern void list_sort(list_t *l, ListCmpF f) | |
| { | |
| char **v; | |
| int n; | |
| int lsize; | |
| void *e; | |
| list_itr_t *i; | |
| xassert(l != NULL); | |
| xassert(f != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| if (l->count <= 1) { | |
| slurm_rwlock_unlock(&l->mutex); | |
| return; | |
| } | |
| lsize = l->count; | |
| v = xmalloc(lsize * sizeof(char *)); | |
| n = 0; | |
| while ((e = _list_node_destroy(l, &l->head))) { | |
| v[n] = e; | |
| ++n; | |
| } | |
| qsort(v, n, sizeof(char *), (ConstListCmpF)f); | |
| for (n = 0; n < lsize; n++) { | |
| _list_node_create(l, l->tail, v[n]); | |
| } | |
| xfree(v); | |
| /* Reset all iterators on the list to point | |
| * to the head of the list. | |
| */ | |
| for (i = l->iNext; i; i = i->iNext) { | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| i->pos = i->list->head; | |
| i->prev = &i->list->head; | |
| } | |
| slurm_rwlock_unlock(&l->mutex); | |
| } | |
| /* | |
| * list_flip - not called list_reverse due to collision with MariaDB | |
| */ | |
| extern void list_flip(list_t *l) | |
| { | |
| list_node_t *old_head, *prev = NULL, *curr, *next = NULL; | |
| list_itr_t *i; | |
| xassert(l); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| if (l->count <= 1) { | |
| slurm_rwlock_unlock(&l->mutex); | |
| return; | |
| } | |
| old_head = curr = l->head; | |
| while (curr) { | |
| next = curr->next; | |
| curr->next = prev; | |
| prev = curr; | |
| curr = next; | |
| } | |
| l->head = prev; | |
| l->tail = &old_head->next; | |
| /* | |
| * Reset all iterators on the list to point | |
| * to the head of the list. | |
| */ | |
| for (i = l->iNext; i; i = i->iNext) { | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| i->pos = i->list->head; | |
| i->prev = &i->list->head; | |
| } | |
| slurm_rwlock_unlock(&l->mutex); | |
| } | |
| extern void *list_pop(list_t *l) | |
| { | |
| void *v; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| v = _list_node_destroy(l, &l->head); | |
| slurm_rwlock_unlock(&l->mutex); | |
| return v; | |
| } | |
| extern void *list_peek(list_t *l) | |
| { | |
| void *v; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_rdlock(&l->mutex); | |
| v = (l->head) ? l->head->data : NULL; | |
| slurm_rwlock_unlock(&l->mutex); | |
| return v; | |
| } | |
| /* list_enqueue() is aliased to list_append() */ | |
| /* list_dequeue() is aliased to list_pop() */ | |
| extern list_itr_t *list_iterator_create(list_t *l) | |
| { | |
| list_itr_t *i = xmalloc(sizeof(*i)); | |
| xassert(l != NULL); | |
| i->magic = LIST_ITR_MAGIC; | |
| i->list = l; | |
| xassert(l->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&l->mutex); | |
| i->pos = l->head; | |
| i->prev = &l->head; | |
| i->iNext = l->iNext; | |
| l->iNext = i; | |
| slurm_rwlock_unlock(&l->mutex); | |
| return i; | |
| } | |
| extern void list_iterator_reset(list_itr_t *i) | |
| { | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| i->pos = i->list->head; | |
| i->prev = &i->list->head; | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| } | |
| extern void list_iterator_destroy(list_itr_t *i) | |
| { | |
| list_itr_t **pi; | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| for (pi = &i->list->iNext; *pi; pi = &(*pi)->iNext) { | |
| xassert((*pi)->magic == LIST_ITR_MAGIC); | |
| if (*pi == i) { | |
| *pi = (*pi)->iNext; | |
| break; | |
| } | |
| } | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| i->magic = ~LIST_ITR_MAGIC; | |
| xfree(i); | |
| } | |
| static void *_list_next_locked(list_itr_t *i) | |
| { | |
| list_node_t *p; | |
| if ((p = i->pos)) | |
| i->pos = p->next; | |
| if (*i->prev != p) | |
| i->prev = &(*i->prev)->next; | |
| return (p ? p->data : NULL); | |
| } | |
| extern void *list_next(list_itr_t *i) | |
| { | |
| void *rc; | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| rc = _list_next_locked(i); | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| return rc; | |
| } | |
| extern void *list_peek_next(list_itr_t *i) | |
| { | |
| list_node_t *p; | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_rdlock(&i->list->mutex); | |
| p = i->pos; | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| return (p ? p->data : NULL); | |
| } | |
| extern void list_insert(list_itr_t *i, void *x) | |
| { | |
| xassert(i != NULL); | |
| xassert(x != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| _list_node_create(i->list, i->prev, x); | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| } | |
| extern void *list_find(list_itr_t *i, ListFindF f, void *key) | |
| { | |
| void *v; | |
| xassert(i != NULL); | |
| xassert(f != NULL); | |
| xassert(key != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| while ((v = _list_next_locked(i)) && !f(v, key)) {;} | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| return v; | |
| } | |
| extern void *list_remove(list_itr_t *i) | |
| { | |
| void *v = NULL; | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| xassert(i->list->magic == LIST_MAGIC); | |
| slurm_rwlock_wrlock(&i->list->mutex); | |
| if (*i->prev != i->pos) | |
| v = _list_node_destroy(i->list, i->prev); | |
| slurm_rwlock_unlock(&i->list->mutex); | |
| return v; | |
| } | |
| extern int list_delete_item(list_itr_t *i) | |
| { | |
| void *v; | |
| xassert(i != NULL); | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| if ((v = list_remove(i))) { | |
| if (i->list->fDel) | |
| i->list->fDel(v); | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| /* | |
| * Inserts data pointed to by [x] into list [l] after [pp], | |
| * the address of the previous node's "next" ptr. | |
| * Returns a ptr to data [x], or NULL if insertion fails. | |
| * This routine assumes the list is already locked upon entry. | |
| */ | |
| static void _list_node_create(list_t *l, list_node_t **pp, void *x) | |
| { | |
| list_node_t *p; | |
| list_itr_t *i; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(_list_mutex_is_locked(&l->mutex)); | |
| xassert(pp != NULL); | |
| xassert(x != NULL); | |
| /* | |
| * Ran out of spare nodes. Allocate another page worth of nodes, | |
| * then link them together in the free_nodes list. | |
| */ | |
| if (!l->free_nodes) { | |
| list_node_t *ln = xcalloc(nodes_in_page, | |
| sizeof(list_node_t)); | |
| /* | |
| * Index 0 is used to link the node_allocations together, | |
| * and thus is unavailable for use as a list node. | |
| */ | |
| ln[0].next = l->node_allocations; | |
| l->node_allocations = &ln[0]; | |
| l->free_nodes = &ln[1]; | |
| for (int i = 1; i < (nodes_in_page - 1); i++) | |
| ln[i].next = &ln[i + 1]; | |
| } | |
| p = l->free_nodes; | |
| l->free_nodes = p->next; | |
| p->data = x; | |
| if (!(p->next = *pp)) | |
| l->tail = &p->next; | |
| *pp = p; | |
| l->count++; | |
| for (i = l->iNext; i; i = i->iNext) { | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| if (i->prev == pp) | |
| i->prev = &p->next; | |
| else if (i->pos == p->next) | |
| i->pos = p; | |
| xassert((i->pos == *i->prev) || | |
| ((*i->prev) && (i->pos == (*i->prev)->next))); | |
| } | |
| } | |
| /* | |
| * Removes the node pointed to by [*pp] from from list [l], | |
| * where [pp] is the address of the previous node's "next" ptr. | |
| * Returns the data ptr associated with list item being removed, | |
| * or NULL if [*pp] points to the NULL element. | |
| * This routine assumes the list is already locked upon entry. | |
| */ | |
| static void *_list_node_destroy(list_t *l, list_node_t **pp) | |
| { | |
| void *v; | |
| list_node_t *p; | |
| list_itr_t *i; | |
| xassert(l != NULL); | |
| xassert(l->magic == LIST_MAGIC); | |
| xassert(_list_mutex_is_locked(&l->mutex)); | |
| xassert(pp != NULL); | |
| if (!(p = *pp)) | |
| return NULL; | |
| v = p->data; | |
| if (!(*pp = p->next)) | |
| l->tail = pp; | |
| l->count--; | |
| for (i = l->iNext; i; i = i->iNext) { | |
| xassert(i->magic == LIST_ITR_MAGIC); | |
| if (i->pos == p) | |
| i->pos = p->next, i->prev = pp; | |
| else if (i->prev == &p->next) | |
| i->prev = pp; | |
| xassert((i->pos == *i->prev) || | |
| ((*i->prev) && (i->pos == (*i->prev)->next))); | |
| } | |
| /* push into free_nodes list */ | |
| p->next = l->free_nodes; | |
| l->free_nodes = p; | |
| return v; | |
| } | |
| #ifndef NDEBUG | |
| static int _list_mutex_is_locked(pthread_rwlock_t *mutex) | |
| { | |
| /* Returns true if the mutex is locked; o/w, returns false. | |
| */ | |
| int rc; | |
| xassert(mutex != NULL); | |
| rc = slurm_rwlock_trywrlock(mutex); | |
| return(rc == EBUSY ? 1 : 0); | |
| } | |
| #endif /* !NDEBUG */ |