plist.c

Go to the documentation of this file.

#include "../stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "plist.h"

/*
 * A plist is a double-linked list of key-value pairs
 * It can be circular or not.
 */

/*
 * This is a node in a plist
 */
struct plist_node {
        void *pn_key;
        void *pn_value;
        struct plist_node *pn_next;
        struct plist_node *pn_prev;
};

/*
 * Adds a new entry into a plist.
 * if !*root it creates a node where prev and next point to itself
 * else, inserts itself in the list before *root
 * returns 1 on success, 0 on NOMEM failure.
 */
int
plist_add(void *k, void *v, plist_node_t **root)
{
        plist_node_t *n;

        if (!(n = malloc(sizeof (*n))))
                return 0;
        n->pn_key = k;
        n->pn_value = v;
        if (!*root) {
                n->pn_next = n;
                n->pn_prev = n;
                *root = n;
        } else {
                n->pn_prev = (*root)->pn_prev;
                n->pn_next = (*root);
                (*root)->pn_prev->pn_next = n;
                (*root)->pn_prev = n;
        }
        return 1;
}

/*
 * traverse list until cur == *root or cur == 0, freeing each node
 * (list could be either circular or not)
 * note that the key and value pointers are still valid.
 */
void
plist_clear(plist_node_t **root)
{
        plist_node_t *cur;
        plist_node_t *fr;

        cur = *root;
        while (cur) {
                fr = cur;
                cur = cur->pn_next;
                free(fr); fr = NULL;
                if (cur == *root) {
                        *root = NULL;
                        return;
                }
        }
}

/*
 * removes a node from a plist where the key pointer == k
 * if ov is not null, it will point to the old value from the removed node
 * This only removes the 1st occurance of k.
 * returns 1 on success, 0 if k was not in the list
 */
int
plist_remove(void *k, plist_node_t **rootp, void **ov)
{
        plist_node_t *cur;

        cur = *rootp;
        while (cur) {
                if (cur->pn_key == k) {
                        if (ov)
                                *ov = cur->pn_value;
                        cur->pn_prev->pn_next = cur->pn_next;
                        cur->pn_next->pn_prev = cur->pn_prev;
                        if (cur->pn_next == cur)
                                *rootp = NULL;
                        else if (*rootp == cur)
                                *rootp = cur->pn_next;
                        free(cur); cur = NULL;
                        return 1;
                }
                cur = cur->pn_next;
                if (cur == *rootp)
                        return 0;
        }
        return 0;
}

/*
 * finds k in plist.
 * if ov != 0, it will be set to the value pointer
 * returns 1 when the key is found, 0 if not found.
 */
int
plist_contains(void *k, plist_node_t *root, void **ov)
{
        plist_node_t *cur;

        cur = root;
        while (cur) {
                if (cur->pn_key == k) {
                        if (ov)
                                *ov = cur->pn_value;
                        return 1;
                }
                cur = cur->pn_next;
                if (cur == root)
                        return 0;
        }
        return 0;
}

/*
 * traverses the plist from start, until we get back to start or next==0
 * runs func with key, val, arg.
 * if func returns 0, stops traversing and returns 0
 * else returns 1 for success
 */
int
plist_walk(plist_node_t *start, int (*func)(const void *k, const void *v,
    void *arg), void *arg)
{
        plist_node_t *cur;
        int res;

        cur = start;
        while (cur) {
                if (!(res = func(cur->pn_key, cur->pn_value, arg)))
                        return res;
                cur = cur->pn_next;
                if (cur == start)
                        return 1;
        }
        return 1;
}