- storage.h

- sort.o allocate.o compat-$(OS).o \

-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));

- if (!newlist)

- die("out of memory for symbol/statement lists");

- 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;

-}

-

-#define container(ptr, type, member) \

- (type *)((void *)(ptr) - offsetof(type, member))

-

-/* Silly type-safety check ;) */

-#define DECLARE_PTR_LIST(listname,type) struct listname { type *list[1]; }

-#define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0])

-#define TYPEOF(head) __typeof__(&(head)->list[0])

-#define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0]))

-

-#define LIST_NODE_NR (29)

-

-struct ptr_list {

- int nr;

- struct ptr_list *prev;

- struct ptr_list *next;

- void *list[LIST_NODE_NR];

-};

-

-#define ptr_list_empty(x) ((x) == NULL)

-

-void * delete_ptr_list_last(struct ptr_list **head);

-int delete_ptr_list_entry(struct ptr_list **, void *, int);

-int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);

-extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));

-

-extern void **__add_ptr_list(struct ptr_list **, void *, unsigned long tag);

-extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);

-extern void __free_ptr_list(struct ptr_list **);

-extern int ptr_list_size(struct ptr_list *);

-int linearize_ptr_list(struct ptr_list *, void **, int);

-

-/*

- * Hey, who said that you can't do overloading in C?

- *

- * You just have to be creative, and use some gcc

- * extensions..

- */

-#define add_ptr_list_tag(list,entry,tag) \

- (TYPEOF(*(list))) (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag)))

-#define add_ptr_list(list,entry) \

- add_ptr_list_tag(list,entry,0)

-#define free_ptr_list(list) \

- do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)

-#define PTR_ENTRY(h,i) (void *)(~3UL & (unsigned long)(h)->list[i])

-

-static inline void *first_ptr_list(struct ptr_list *list)

-{

- if (!list)

- return NULL;

- return PTR_ENTRY(list, 0);

-}

-

-static inline void *last_ptr_list(struct ptr_list *list)

-{

-

- if (!list)

- return NULL;

- list = list->prev;

- return PTR_ENTRY(list, list->nr-1);

-}

-

-#define DO_PREPARE(head, ptr, __head, __list, __nr) \

- do { \

- struct ptr_list *__head = (struct ptr_list *) (head); \

- struct ptr_list *__list = __head; \

- int __nr = 0; \

- CHECK_TYPE(head,ptr); \

- if (__head) ptr = PTR_ENTRY(__head, 0); \

- else ptr = NULL

-

-#define DO_NEXT(ptr, __head, __list, __nr) \

- if (ptr) { \

- if (++__nr < __list->nr) { \

- ptr = PTR_ENTRY(__list,__nr); \

- } else { \

- __list = __list->next; \

- ptr = NULL; \

- if (__list != __head) { \

- __nr = 0; \

- ptr = PTR_ENTRY(__list,0); \

- } \

- } \

- }

-

-#define DO_RESET(ptr, __head, __list, __nr) \

- do { \

- __nr = 0; \

- __list = __head; \

- if (__head) ptr = PTR_ENTRY(__head, 0); \

- } while (0)

-

-#define DO_FINISH(ptr, __head, __list, __nr) \

- (void)(__nr); /* Sanity-check nesting */ \

- } while (0)

-

-#define PREPARE_PTR_LIST(head, ptr) \

- DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define NEXT_PTR_LIST(ptr) \

- DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define RESET_PTR_LIST(ptr) \

- DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define FINISH_PTR_LIST(ptr) \

- DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define DO_FOR_EACH(head, ptr, __head, __list, __nr) do { \

- struct ptr_list *__head = (struct ptr_list *) (head); \

- struct ptr_list *__list = __head; \

- CHECK_TYPE(head,ptr); \

- if (__head) { \

- do { int __nr; \

- for (__nr = 0; __nr < __list->nr; __nr++) { \

- do { \

- ptr = PTR_ENTRY(__list,__nr); \

- do {

-

-#define DO_END_FOR_EACH(ptr, __head, __list, __nr) \

- } while (0); \

- } while (0); \

- } \

- } while ((__list = __list->next) != __head); \

- } \

-} while (0)

-

-#define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr) do { \

- struct ptr_list *__head = (struct ptr_list *) (head); \

- struct ptr_list *__list = __head; \

- CHECK_TYPE(head,ptr); \

- if (__head) { \

- do { int __nr; \

- __list = __list->prev; \

- __nr = __list->nr; \

- while (--__nr >= 0) { \

- do { \

- ptr = PTR_ENTRY(__list,__nr); \

- do {

-

-

-#define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \

- } while (0); \

- } while (0); \

- } \

- } while (__list != __head); \

- } \

-} while (0)

-

-#define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, __newlist, __newnr) do { \

- struct ptr_list *__newhead = __head; \

- struct ptr_list *__newlist = __list; \

- int __newnr = __nr; \

- new = ptr; \

- goto __inside##new; \

- if (1) { \

- do { \

- __newlist = __newlist->prev; \

- __newnr = __newlist->nr; \

- __inside##new: \

- while (--__newnr >= 0) { \

- do { \

- new = PTR_ENTRY(__newlist,__newnr); \

- do {

-

-#define RECURSE_PTR_REVERSE(ptr, new) \

- DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \

- new, __head##new, __list##new, __nr##new)

-

-#define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \

- ((__typeof__(&(ptr))) (__list->list + __nr))

-

-#define FOR_EACH_PTR(head, ptr) \

- DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define END_FOR_EACH_PTR(ptr) \

- DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define FOR_EACH_PTR_REVERSE(head, ptr) \

- DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define END_FOR_EACH_PTR_REVERSE(ptr) \

- DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define THIS_ADDRESS(ptr) \

- DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-extern void split_ptr_list_head(struct ptr_list *);

-

-#define DO_SPLIT(ptr, __head, __list, __nr) do { \

- split_ptr_list_head(__list); \

- if (__nr >= __list->nr) { \

- __nr -= __list->nr; \

- __list = __list->next; \

- }; \

-} while (0)

-

-#define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do { \

- void **__this, **__last; \

- if (__list->nr == LIST_NODE_NR) \

- DO_SPLIT(ptr, __head, __list, __nr); \

- __this = __list->list + __nr; \

- __last = __list->list + __list->nr - 1; \

- while (__last >= __this) { \

- __last[1] = __last[0]; \

- __last--; \

- } \

- *__this = (new); \

- __list->nr++; \

-} while (0)

-

-#define INSERT_CURRENT(new, ptr) \

- DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \

- void **__this = __list->list + __nr; \

- void **__last = __list->list + __list->nr - 1; \

- while (__this < __last) { \

- __this[0] = __this[1]; \

- __this++; \

- } \

- *__this = (void *)0xf0f0f0f0; \

- __list->nr--; __nr--; \

-} while (0)

-

-#define DELETE_CURRENT_PTR(ptr) \

- DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)

-

-#define REPLACE_CURRENT_PTR(ptr, new_ptr) \

- do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)

-

-extern void pack_ptr_list(struct ptr_list **);

-

-#define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))

-

-static inline void update_tag(void *p, unsigned long tag)

-{

- unsigned long *ptr = p;

- *ptr = tag | (~3UL & *ptr);

-}

-

-static inline void *tag_ptr(void *ptr, unsigned long tag)

-{

- return (void *)(tag | (unsigned long)ptr);

-}

-

-#define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))

-#define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)

-