diff options
author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-03-12 17:53:41 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-04-07 21:06:29 -0700 |
commit | 77ac63127dc8981264b31bcfaac825c62971bca2 (patch) | |
tree | 27cd8abb6be43358f0e45201687103dc242e6746 /ptrlist.c | |
parent | [PATCH] sparse: Makefile trivialities (diff) | |
download | sparse-77ac63127dc8981264b31bcfaac825c62971bca2.tar.gz sparse-77ac63127dc8981264b31bcfaac825c62971bca2.tar.bz2 sparse-77ac63127dc8981264b31bcfaac825c62971bca2.zip |
Move the ptrlist macros out of the sparse "lib.[ch]" files.
They rate their own "ptrlist" library status, since they are
definitely potentially useful outside of sparse.
Diffstat (limited to 'ptrlist.c')
-rw-r--r-- | ptrlist.c | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/ptrlist.c b/ptrlist.c new file mode 100644 index 0000000..065891c --- /dev/null +++ b/ptrlist.c @@ -0,0 +1,223 @@ +/* + * ptrlist.c + * + * Pointer list manipulation + * + * (C) Copyright Linus Torvalds 2003-2005 + */ +#include <stdlib.h> +#include <string.h> +#include <assert.h> + +#include "ptrlist.h" + +int ptr_list_size(struct ptr_list *head) +{ + int nr = 0; + + if (head) { + struct ptr_list *list = head; + do { + nr += list->nr; + } while ((list = list->next) != head); + } + return nr; +} + +/* + * Linearize the entries of a list up to a total of 'max', + * and return the nr of entries linearized. + * + * The array to linearize into (second argument) 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; + if (i > max) + i = max; + memcpy(arr, list->list, i*sizeof(void *)); + arr += i; + nr += i; + max -= i; + if (!max) + break; + } while ((list = list->next) != head); + } + return nr; +} + +/* + * 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) { + *listp = NULL; + return; + } + prev = entry->prev; + prev->next = next; + next->prev = prev; + free(entry); + if (entry == head) { + *listp = next; + head = next; + entry = next; + goto restart; + } + } + entry = next; + } while (entry != head); + } +} + +void split_ptr_list_head(struct ptr_list *head) +{ + int old = head->nr, nr = old / 2; + struct ptr_list *newlist = malloc(sizeof(*newlist)); + 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 *)); +} + +void **__add_ptr_list(struct ptr_list **listp, void *ptr, unsigned long tag) +{ + struct ptr_list *list = *listp; + struct ptr_list *last = NULL; /* gcc complains needlessly */ + void **ret; + int nr; + + /* The low two bits are reserved for tags */ + assert((3 & (unsigned long)ptr) == 0); + assert((~3 & tag) == 0); + ptr = (void *)(tag | (unsigned long)ptr); + + if (!list || (nr = (last = list->prev)->nr) >= LIST_NODE_NR) { + struct ptr_list *newlist = malloc(sizeof(*newlist)); + assert(newlist); + memset(newlist, 0, sizeof(*newlist)); + 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; +} + +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; +} + +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; +} + +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(last); + } + return ptr; +} + +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); +} + +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(tmp); + } + + *listp = NULL; +} |