Merge branch 'handle-cleanup-attr'

[smatch.git] / ptrlist.c

/*
 * ptrlist.c
 *
 * (C) Copyright Linus Torvalds 2003-2005
 */

///
// Pointer list manipulation
// -------------------------
//
// The data structure handled here is designed to hold pointers
// but two special cases need to be avoided or need special care:
// * NULL is used by {PREPARE,NEXT}_PTR_LIST() to indicate the end-of-list.
//   Thus, NULL can't be stored in lists using this API but is fine to
//   use with FOR_EACH_PTR() and its variants.
// * VOID is used to replace a removed pseudo 'usage'. Since phi-nodes
//   (OP_PHI) use a list to store their operands, a VOID in a phi-node
//   list must be ignored since it represents a removed operand. As
//   consequence, VOIDs must never be used as phi-node operand.
//   This is fine since phi-nodes make no sense with void values
//   but VOID is also used for invalid types and in case of errors.

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "ptrlist.h"
#include "allocate.h"
#include "compat.h"

__DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
__ALLOCATOR(struct ptr_list, "ptr list", ptrlist);

///
// get the size of a ptrlist
// @head: the head of the list
// @return: the size of the list given by @head.
int ptr_list_size(struct ptr_list *head)
{
        int nr = 0;

        if (head) {
                struct ptr_list *list = head;
                do {
                        nr += list->nr - list->rm;
                } while ((list = list->next) != head);
        }
        return nr;
}

///
// test if a list is empty
// @head: the head of the list
// @return: ``true`` if the list is empty, ``false`` otherwise.
bool ptr_list_empty(const struct ptr_list *head)
{
        const struct ptr_list *list = head;

        if (!head)
                return true;

        do {
                if (list->nr - list->rm)
                        return false;
        } while ((list = list->next) != head);

        return true;
}

///
// test is a list contains more than one element
// @head: the head of the list
// @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
bool ptr_list_multiple(const struct ptr_list *head)
{
        const struct ptr_list *list = head;
        int nr = 0;

        if (!head)
                return false;

        do {
                nr += list->nr - list->rm;
                if (nr > 1)
                        return true;
        } while ((list = list->next) != head);

        return false;
}

///
// get the first element of a ptrlist
// @head: the head of the list
// @return: the first element of the list or ``NULL`` if the list is empty
void *first_ptr_list(struct ptr_list *head)
{
        struct ptr_list *list = head;

        if (!head)
                return NULL;

        while (list->nr == 0) {
                list = list->next;
                if (list == head)
                        return NULL;
        }
        return PTR_ENTRY_NOTAG(list, 0);
}

///
// get the last element of a ptrlist
// @head: the head of the list
// @return: the last element of the list or ``NULL`` if the list is empty
void *last_ptr_list(struct ptr_list *head)
{
        struct ptr_list *list;

        if (!head)
                return NULL;
        list = head->prev;
        while (list->nr == 0) {
                if (list == head)
                        return NULL;
                list = list->prev;
        }
        return PTR_ENTRY_NOTAG(list, list->nr-1);
}

///
// get the nth element of a ptrlist
// @head: the head of the list
// @return: the nth element of the list or ``NULL`` if the list is too short.
void *ptr_list_nth_entry(struct ptr_list *list, unsigned int idx)
{
        struct ptr_list *head = list;

        if (!head)
                return NULL;

        do {
                unsigned int nr = list->nr;

                if (idx < nr)
                        return list->list[idx];
                else
                        idx -= nr;
        } while ((list = list->next) != head);
        return NULL;
}

///
// linearize the entries of a list
//
// @head: the list to be linearized
// @arr: a ``void*`` array to fill with @head's entries
// @max: the maximum number of entries to store into @arr
// @return: the number of entries in the list.
//
// Linearize the entries of a list up to a total of @max,
// and return the number of entries in the list.
//
// The array to linearize into (@arr) should really
// be ``void *x[]``, but we want to let people fill in any kind
// of pointer array, so let's just call it ``void **``.
int linearize_ptr_list(struct ptr_list *head, void **arr, int max)
{
        int nr = 0;
        if (head && max > 0) {
                struct ptr_list *list = head;

                do {
                        int i = list->nr;
                        nr += i;
                        if (max == 0)
                                continue;
                        if (i > max) 
                                i = max;
                        memcpy(arr, list->list, i*sizeof(void *));
                        arr += i;
                        max -= i;
                } while ((list = list->next) != head);
        }
        return nr;
}

///
// pack a ptrlist
//
// @listp: a pointer to the list to be packed.
//
// When we've walked the list and deleted entries,
// we may need to re-pack it so that we don't have
// any empty blocks left (empty blocks upset the
// walking code).
void pack_ptr_list(struct ptr_list **listp)
{
        struct ptr_list *head = *listp;

        if (head) {
                struct ptr_list *entry = head;
                do {
                        struct ptr_list *next;
restart:
                        next = entry->next;
                        if (!entry->nr) {
                                struct ptr_list *prev;
                                if (next == entry) {
                                        __free_ptrlist(entry);
                                        *listp = NULL;
                                        return;
                                }
                                prev = entry->prev;
                                prev->next = next;
                                next->prev = prev;
                                __free_ptrlist(entry);
                                if (entry == head) {
                                        *listp = next;
                                        head = next;
                                        entry = next;
                                        goto restart;
                                }
                        }
                        entry = next;
                } while (entry != head);
        }
}               

///
// split a ptrlist block
// @head: the ptrlist block to be split
//
// A new block is inserted just after @head and the entries
// at the half end of @head are moved to this new block.
// The goal being to create space inside @head for a new entry.
void split_ptr_list_head(struct ptr_list *head)
{
        int old = head->nr, nr = old / 2;
        struct ptr_list *newlist = __alloc_ptrlist(0);
        struct ptr_list *next = head->next;

        old -= nr;
        head->nr = old;
        newlist->next = next;
        next->prev = newlist;
        newlist->prev = head;
        head->next = newlist;
        newlist->nr = nr;
        memcpy(newlist->list, head->list + old, nr * sizeof(void *));
        memset(head->list + old, 0xf0, nr * sizeof(void *));
}

///
// add an entry to a ptrlist
// @listp: a pointer to the list
// @ptr: the entry to add to the list
// @return: the address where the new entry is stored.
//
// :note: code must not use this function and should use
//      :func:`add_ptr_list` instead.
void **__add_ptr_list(struct ptr_list **listp, void *ptr)
{
        struct ptr_list *list = *listp;
        struct ptr_list *last = NULL; /* gcc complains needlessly */
        void **ret;
        int nr;

        if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) {
                struct ptr_list *newlist = __alloc_ptrlist(0);
                if (!list) {
                        newlist->next = newlist;
                        newlist->prev = newlist;
                        *listp = newlist;
                } else {
                        newlist->prev = last;
                        newlist->next = list;
                        list->prev = newlist;
                        last->next = newlist;
                }
                last = newlist;
                nr = 0;
        }
        ret = last->list + nr;
        *ret = ptr;
        nr++;
        last->nr = nr;
        return ret;
}

///
// add a tagged entry to a ptrlist
// @listp: a pointer to the list
// @ptr: the entry to add to the list
// @tag: the tag to add to @ptr
// @return: the address where the new entry is stored.
//
// :note: code must not use this function and should use
//      :func:`add_ptr_list_tag` instead.
void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
{
        /* The low two bits are reserved for tags */
        assert((3 & (unsigned long)ptr) == 0);
        assert((~3 & tag) == 0);

        ptr = (void *)(tag | (unsigned long)ptr);

        return __add_ptr_list(listp, ptr);
}

///
// test if some entry is already present in a ptrlist
// @list: the head of the list
// @entry: the entry to test
// @return: ``true`` if the entry is already present, ``false`` otherwise.
bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry)
{
        const struct ptr_list *list = head;

        if (!head)
                return false;
        do {
                int nr = list->nr;
                int i;
                for (i = 0; i < nr; i++)
                        if (list->list[i] == entry)
                                return true;
        } while ((list = list->next) != head);
        return false;
}

///
// delete an entry from a ptrlist
// @list: a pointer to the list
// @entry: the item to be deleted
// @count: the minimum number of times @entry should be deleted or 0.
int delete_ptr_list_entry(struct ptr_list **list, void *entry, int count)
{
        void *ptr;

        FOR_EACH_PTR(*list, ptr) {
                if (ptr == entry) {
                        DELETE_CURRENT_PTR(ptr);
                        if (!--count)
                                goto out;
                }
        } END_FOR_EACH_PTR(ptr);
        assert(count <= 0);
out:
        pack_ptr_list(list);
        return count;
}

///
// replace an entry in a ptrlist
// @list: a pointer to the list
// @old_ptr: the entry to be replaced
// @new_ptr: the new entry
// @count: the minimum number of times @entry should be deleted or 0.
int replace_ptr_list_entry(struct ptr_list **list, void *old_ptr,
        void *new_ptr, int count)
{
        void *ptr;

        FOR_EACH_PTR(*list, ptr) {
                if (ptr==old_ptr) {
                        REPLACE_CURRENT_PTR(ptr, new_ptr);
                        if (!--count)
                                goto out;
                }
        }END_FOR_EACH_PTR(ptr);
        assert(count <= 0);
out:
        return count;
}

///
// remove the last entry of a ptrlist
// @head: a pointer to the list
// @return: the last element of the list or NULL if the list is empty.
//
// :note: this doesn't repack the list
void * undo_ptr_list_last(struct ptr_list **head)
{
        struct ptr_list *last, *first = *head;

        if (!first)
                return NULL;
        last = first;
        do {
                last = last->prev;
                if (last->nr) {
                        void *ptr;
                        int nr = --last->nr;
                        ptr = last->list[nr];
                        last->list[nr] = (void *)0xf1f1f1f1;
                        return ptr;
                }
        } while (last != first);
        return NULL;
}

///
// remove the last entry and repack the list
// @head: a pointer to the list
// @return: the last element of the list or NULL if the list is empty.
void * delete_ptr_list_last(struct ptr_list **head)
{
        void *ptr = NULL;
        struct ptr_list *last, *first = *head;

        if (!first)
                return NULL;
        last = first->prev;
        if (last->nr)
                ptr = last->list[--last->nr];
        if (last->nr <=0) {
                first->prev = last->prev;
                last->prev->next = first;
                if (last == first)
                        *head = NULL;
                __free_ptrlist(last);
        }
        return ptr;
}

///
// concat two ptrlists
// @a: the source list
// @b: a pointer to the destination list.
// The element of @a are added at the end of @b.
void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
{
        void *entry;
        FOR_EACH_PTR(a, entry) {
                add_ptr_list(b, entry);
        } END_FOR_EACH_PTR(entry);
}

///
// copy the elements of a list at the end of another list.
// @listp: a pointer to the destination list.
// @src: the head of the source list.
void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src)
{
        struct ptr_list *head, *tail;
        struct ptr_list *cur = src;
        int idx;

        if (!src)
                return;
        head = *listp;
        if (!head) {
                *listp = src;
                return;
        }

        tail = head->prev;
        idx = tail->nr;
        do {
                struct ptr_list *next;
                int nr = cur->nr;
                int i;
                for (i = 0; i < nr;) {
                        void *ptr = cur->list[i++];
                        if (!ptr)
                                continue;
                        if (idx >= LIST_NODE_NR) {
                                struct ptr_list *prev = tail;
                                tail = __alloc_ptrlist(0);
                                prev->next = tail;
                                tail->prev = prev;
                                prev->nr = idx;
                                idx = 0;
                        }
                        tail->list[idx++] = ptr;
                }

                next = cur->next;
                __free_ptrlist(cur);
                cur = next;
        } while (cur != src);

        tail->nr = idx;
        head->prev = tail;
        tail->next = head;
}

///
// free a ptrlist
// @listp: a pointer to the list
// Each blocks of the list are freed (but the entries
// themselves are not freed).
//
// :note: code must not use this function and should use
//      the macro :func:`free_ptr_list` instead.
void __free_ptr_list(struct ptr_list **listp)
{
        struct ptr_list *tmp, *list = *listp;

        if (!list)
                return;

        list->prev->next = NULL;
        while (list) {
                tmp = list;
                list = list->next;
                __free_ptrlist(tmp);
        }

        *listp = NULL;
}