/* Neville's implementation of a linked list */ /* Search for XXX for incomplete areas */ #include #include #include "llist.h" /* Type of each node */ typedef struct llist_node { struct llist_node *prev; /* Points to previous node */ struct llist_node *next; /* Points to next node */ } llist_node_t; /* Type of the list */ typedef struct llist { llist_node_t *head; /* Points to first node */ llist_node_t *tail; /* Points to last node */ llist_node_t *current; /* Points to current selected node */ un_int node_size; /* Size of each node */ un_int elements; /* Total number of nodes */ void (*freefunc) (void *node); /* Function pointer to free a node */ void (*prnfunc) /* Function pointer to print nodes */ (void *node, int iscur); /* Node address, is it current (t/f) */ void *info; /* Info pointer for this list */ } llist_t; /*------------------------- Assistance functions ---------------------------*/ /**************************************************************************** * Wrapper for Malloc * Returns: whatever malloc returned ****************************************************************************/ static void *Malloc(size_t size) { void *ptr; ptr = calloc(1, size); if (ptr == NULL) { perror("calloc"); exit(-1); } return(ptr); } /*----------------------- List creation and removal ------------------------*/ /**************************************************************************** * Create a linked list * Returns: linked list structure ****************************************************************************/ extern LLIST ll_create(un_int size, void (*ffunc) (void *node)) { llist_t *thelist; if (size == 0) return(NULL); thelist = (llist_t*) Malloc(sizeof(llist_t)); thelist->node_size = size; thelist->freefunc = ffunc; return((void*) thelist); } /**************************************************************************** * Destroy a list * Returns: nothing ****************************************************************************/ extern void ll_destroy(LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *node; if (list == NULL) return; for (list->current = list->head; list->current != NULL; ) { node = list->current; list->current = list->current->next; if (list->freefunc != NULL) (*(list->freefunc)) (node + 1); free(node); } free(list); return; } /*-------------------------- List administration ---------------------------*/ /**************************************************************************** * Add a node to the beginning of list * Returns: address of local copy or NULL ****************************************************************************/ extern void *ll_addfirst(const LLIST inlist, void *element) { llist_t *list = (llist_t*) inlist; llist_node_t *node; char *retd; if (list == NULL) return(NULL); node = list->head; list->head = (llist_node_t*) Malloc(sizeof(llist_node_t) + list->node_size); retd = (char*) memcpy(list->head + 1, element, list->node_size); if (node != NULL) { node->prev = list->head; list->head->next = node; } else list->tail = list->head; list->elements++; return(node + 1); } /**************************************************************************** * Add a node to the end of list * Returns: address of local copy or NULL ****************************************************************************/ extern void *ll_addlast(const LLIST inlist, void *element) { llist_t *list = (llist_t*) inlist; llist_node_t *node; if (list == NULL) return(NULL); node = (llist_node_t*) Malloc(sizeof(llist_node_t) + list->node_size); if (list->tail == NULL) list->tail = list->head = node; else { node->prev = list->tail; list->tail->next = node; list->tail = node; } memcpy(node + 1, element, list->node_size); list->elements++; return(node + 1); } /**************************************************************************** * Add a node after the current node * Returns: pass or fail ****************************************************************************/ extern void *ll_addaftercur(const LLIST inlist, void *element) { llist_t *list = (llist_t*) inlist; llist_node_t *node; if (list == NULL) return(NULL); if (list->current == NULL) return(NULL); node = (llist_node_t*) Malloc(sizeof(llist_node_t) + list->node_size); node->next = list->current->next; node->prev = list->current; list->current->next = node; if (node->next != NULL) node->next->prev = node; else list->tail = node; memcpy(node + 1, element, list->node_size); list->elements++; return(node + 1); } /**************************************************************************** * Add a node before the current node * Returns: pass or fail ****************************************************************************/ extern void *ll_addbeforecur(const LLIST inlist, void *element) { llist_t *list = (llist_t*) inlist; llist_node_t *node; if (list == NULL) return(NULL); if (list->current == NULL) return(NULL); node = (llist_node_t*) Malloc(sizeof(llist_node_t) + list->node_size); node->next = list->current; node->prev = list->current->prev; list->current->prev = node; if (node->prev != NULL) node->prev->next = node; else list->head = node; memcpy(node + 1, element, list->node_size); list->elements++; return(node + 1); } /**************************************************************************** * Removes first node in list * Returns: pass or fail ****************************************************************************/ extern int ll_rmfirst(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *nextnode; if (list == NULL) return(LLIST_FAIL); if (list->head == NULL) return(LLIST_FAIL); nextnode = list->head->next; if (list->current == list->head) list->current = nextnode; if (list->tail == list->head) list->current = nextnode; if (list->freefunc != NULL) (*(list->freefunc)) (list->head + 1); free(list->head); list->head = nextnode; list->head->prev = NULL; list->elements--; return(LLIST_PASS); } /**************************************************************************** * Removes last node in list * Returns: pass or fail ****************************************************************************/ extern int ll_rmlast(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *prevnode; if (list == NULL) return(LLIST_FAIL); if (list->tail == NULL) return(LLIST_FAIL); prevnode = list->tail->prev; if (list->current == list->tail) list->current = prevnode; if (list->head == list->tail) list->head = NULL; if (list->freefunc != NULL) (*(list->freefunc)) (list->tail + 1); free(list->tail); list->elements--; /* Update list->tail */ list->tail = prevnode; list->tail->next = NULL; return(LLIST_PASS); } /**************************************************************************** * Removes last current node in list * Returns: pass or fail ****************************************************************************/ extern int ll_rmcurr(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *nextnode; llist_node_t *prevnode; if (list == NULL) return(LLIST_FAIL); if (list->current == NULL) return(LLIST_FAIL); nextnode = list->current->next; prevnode = list->current->prev; if (list->head == list->current) list->head = nextnode; if (list->tail == list->current) list->tail = list->current->prev; if (list->freefunc != NULL) (*(list->freefunc)) (list->current + 1); free(list->current); nextnode->prev = prevnode; prevnode->next = nextnode; return(LLIST_PASS); } /*-------------------------- Retrieve from list ----------------------------*/ /**************************************************************************** * Perform "pop" function when interfacing as a stack * Get the head node data and return pointer, remove place in list * Note: data is returned without being freed, must free manually * Returns: data pointer or NULL ****************************************************************************/ extern void *ll_pop(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *nextnode; void *data; if (list == NULL) return(NULL); if (list->head == NULL) return(NULL); data = list->head + 1; nextnode = list->head->next; if (list->current == list->head) list->current = nextnode; if (list->tail == list->head) list->tail = nextnode; free(list->head); list->head = nextnode; list->elements--; return(data); } /**************************************************************************** * Reset current pointer * Set current to NULL * Returns: pass or fail ****************************************************************************/ extern int ll_reset(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(LLIST_FAIL); list->current = NULL; return(LLIST_PASS); } /**************************************************************************** * Return next node * If current is reset, it will jump to head * Returns: node pointer or NULL ****************************************************************************/ extern void *ll_next(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(NULL); if (list->current == NULL) list->current = list->head; else list->current = list->current->next; if (list->current == NULL) return(NULL); return(list->current + 1); } /**************************************************************************** * Return previous node * If current is reset, it will jump to tail * Returns: node pointer or NULL ****************************************************************************/ extern void *ll_prev(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(NULL); if (list->current == NULL) list->current = list->tail; else list->current = list->current->prev; if (list->current == NULL) return(NULL); return(list->current + 1); } /**************************************************************************** * Returns number of elements currently in list * Returns: number of elements ****************************************************************************/ extern un_int ll_total(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(-1); return(list->elements); } /**************************************************************************** * Return element number for current * Returns: unsigned integer for current element ****************************************************************************/ extern un_int ll_curnum(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *curnode; un_int elmnt = 0; if (list == NULL) return(-1); if (list->current == NULL) return(-1); for (curnode = list->head; curnode != list->current; curnode = curnode->next, elmnt++) ; return(elmnt); } /**************************************************************************** * Return element number for supplied node * Warning: This could take quite a while for large lists * Returns: unsigned integer for current element ****************************************************************************/ extern un_int ll_nodenum(const LLIST inlist, const void *node) { llist_t *list = (llist_t*) inlist; llist_node_t *curnode; un_int elmnt = 0; if (list == NULL) return(-1); if (node == NULL) return(-1); for (curnode = list->head; (node != curnode + 1) || (curnode == NULL); curnode = curnode->next, elmnt++) ; if (curnode == NULL) return(-1); return(elmnt); } /**************************************************************************** * Return stated element * Warning: This could take quite a while for large lists * Returns: element corresponding to nodenum or NULL ****************************************************************************/ extern void *ll_getnode(const LLIST inlist, int nodenum) { llist_t *list = (llist_t*) inlist; llist_node_t *curnode; un_int elmnt = 0; if (list == NULL) return(NULL); for (curnode = list->head; (elmnt != nodenum) || (curnode == NULL); curnode = curnode->next, elmnt++) ; if (curnode == NULL) return(NULL); return(curnode + 1); } /**************************************************************************** * Return data of current segment * Returns: data pointer or NULL ****************************************************************************/ extern void *ll_data(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(NULL); if (list->current != NULL) return(list->current + 1); return(NULL); } /**************************************************************************** * Return first node * If current is reset, it will be set to the head * Returns: data pointer or NULL ****************************************************************************/ extern void *ll_head(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(NULL); if (list->head == NULL) return(NULL); if (list->current == NULL) list->current = list->head; return(list->head + 1); } /**************************************************************************** * Return last node * If current is reset, it will be set to tail * Returns: data pointer or NULL ****************************************************************************/ extern void *ll_tail(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(NULL); if (list->tail == NULL) return(NULL); if (list->current == NULL) list->current = list->tail; return(list->tail + 1); } /*-------------------------- List Info Functions ---------------------------*/ /**************************************************************************** * Information call * provided to hold a pointer to anything with this list (think title) * Set info pointer by calling with memory pointer, retrieve pointer by * calling with NULL * Returns: data pointer or NULL ****************************************************************************/ extern void *ll_info(const LLIST inlist, void *ptr) { llist_t *list = (llist_t*) inlist; if (ptr == NULL) return(list->info); list->info = ptr; return(list->info); } /*-------------------------- Printing Functions ----------------------------*/ /**************************************************************************** * Initialize printing functions * Returns: pass or fail ****************************************************************************/ extern int ll_prninit(const LLIST inlist, void (*infunc) (void *node, int iscur)) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(LLIST_FAIL); list->prnfunc = infunc; return(LLIST_PASS); } /**************************************************************************** * Call printing function for current node only * Note: could exit if prnfunc is NULL * Returns: pass or fail ****************************************************************************/ extern int ll_prncur(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(LLIST_FAIL); if (list->prnfunc == NULL) { fprintf(stderr, "call prninit function before attempting to print\n"); exit(0); } if (list->current == NULL) return(LLIST_FAIL); (*(list->prnfunc)) (list->current + 1, 1); return(LLIST_PASS); } /**************************************************************************** * Call printing function for node previous to current * Note: could exit if prnfunc is NULL * Returns: pass or fail ****************************************************************************/ extern int ll_prnprev(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(LLIST_FAIL); if (list->prnfunc == NULL) { fprintf(stderr, "call prninit function before attempting to print\n"); exit(0); } if (list->current == NULL) return(LLIST_FAIL); if (list->current->prev == NULL) return(LLIST_FAIL); (*(list->prnfunc)) (list->current->prev + 1, 0); return(LLIST_PASS); } /**************************************************************************** * Call printing function for node after current * Note: could exit if prnfunc is NULL * Returns: pass or fail ****************************************************************************/ extern int ll_prnnext(const LLIST inlist) { llist_t *list = (llist_t*) inlist; if (list == NULL) return(LLIST_FAIL); if (list->prnfunc == NULL) { fprintf(stderr, "call prninit function before attempting to print\n"); exit(0); } if (list->current == NULL) return(LLIST_FAIL); if (list->current->next == NULL) return(LLIST_FAIL); (*(list->prnfunc)) (list->current->next + 1, 0); return(LLIST_PASS); } /**************************************************************************** * Call printing function for every node in list * Note: could exit if prnfunc is NULL * Returns: pass or fail ****************************************************************************/ extern int ll_prnall(const LLIST inlist) { llist_t *list = (llist_t*) inlist; llist_node_t *node; if (list == NULL) return(LLIST_FAIL); if (list->prnfunc == NULL) { fprintf(stderr, "call prninit function before attempting to print\n"); exit(0); } node = list->head; while (node != NULL) { if (node == list->current) (*(list->prnfunc)) (node + 1, 1); else (*(list->prnfunc)) (node + 1, 0); node = node->next; } return(LLIST_PASS); } /* EOF */