| /* ply-list.c - linked list implementation |
| * |
| * Copyright (C) 2007 Red Hat, Inc. |
| * 2008 Charlie Brej <cbrej@cs.man.ac.uk> |
| * |
| * This program is free software; you can redistribute it and/or modify |
| * it under the terms of the GNU General Public License as published by |
| * the Free Software Foundation; either version 2, or (at your option) |
| * any later version. |
| * |
| * This program is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| * GNU General Public License for more details. |
| * |
| * You should have received a copy of the GNU General Public License |
| * along with this program; if not, write to the Free Software |
| * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA |
| * 02111-1307, USA. |
| * |
| * Written by: Charlie Brej <cbrej@cs.man.ac.uk> |
| * Ray Strode <rstrode@redhat.com> |
| */ |
| |
| #include "ply-list.h" |
| |
| #include <assert.h> |
| #include <errno.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| struct _ply_list |
| { |
| ply_list_node_t *first_node; |
| ply_list_node_t *last_node; |
| |
| int number_of_nodes; |
| }; |
| |
| struct _ply_list_node |
| { |
| void *data; |
| struct _ply_list_node *previous; |
| struct _ply_list_node *next; |
| }; |
| |
| ply_list_t * |
| ply_list_new (void) |
| { |
| ply_list_t *list; |
| |
| list = calloc (1, sizeof (ply_list_t)); |
| |
| list->first_node = NULL; |
| list->last_node = NULL; |
| list->number_of_nodes = 0; |
| |
| return list; |
| } |
| |
| void |
| ply_list_free (ply_list_t *list) |
| { |
| ply_list_remove_all_nodes (list); |
| free (list); |
| } |
| |
| static ply_list_node_t * |
| ply_list_node_new (void *data) |
| { |
| ply_list_node_t *node; |
| |
| node = calloc (1, sizeof (ply_list_node_t)); |
| node->data = data; |
| |
| return node; |
| } |
| |
| static void |
| ply_list_node_free (ply_list_node_t *node) |
| { |
| if (node == NULL) |
| return; |
| |
| assert ((node->previous == NULL) && (node->next == NULL)); |
| |
| free (node); |
| } |
| |
| int |
| ply_list_get_length (ply_list_t *list) |
| { |
| return list->number_of_nodes; |
| } |
| |
| ply_list_node_t * |
| ply_list_find_node (ply_list_t *list, |
| void *data) |
| { |
| ply_list_node_t *node; |
| |
| node = list->first_node; |
| while (node != NULL) |
| { |
| if (node->data == data) |
| break; |
| |
| node = node->next; |
| } |
| return node; |
| } |
| |
| static void |
| ply_list_insert_node (ply_list_t *list, |
| ply_list_node_t *node_before, |
| ply_list_node_t *new_node) |
| { |
| |
| if (new_node == NULL) |
| return; |
| |
| if (node_before == NULL) |
| { |
| if (list->first_node == NULL) |
| { |
| assert (list->last_node == NULL); |
| |
| list->first_node = new_node; |
| list->last_node = new_node; |
| } |
| else |
| { |
| list->first_node->previous = new_node; |
| new_node->next = list->first_node; |
| list->first_node = new_node; |
| } |
| } |
| else |
| { |
| new_node->next = node_before->next; |
| if (node_before->next != NULL) |
| node_before->next->previous = new_node; |
| node_before->next = new_node; |
| new_node->previous = node_before; |
| |
| if (node_before == list->last_node) |
| list->last_node = new_node; |
| } |
| |
| list->number_of_nodes++; |
| } |
| |
| ply_list_node_t * |
| ply_list_insert_data (ply_list_t *list, |
| void *data, |
| ply_list_node_t *node_before) |
| { |
| ply_list_node_t *node; |
| |
| node = ply_list_node_new (data); |
| |
| ply_list_insert_node (list, node_before, node); |
| |
| return node; |
| } |
| |
| ply_list_node_t * |
| ply_list_append_data (ply_list_t *list, |
| void *data) |
| { |
| return ply_list_insert_data (list, data, list->last_node); |
| } |
| |
| ply_list_node_t * |
| ply_list_prepend_data (ply_list_t *list, |
| void *data) |
| { |
| return ply_list_insert_data (list, data, NULL); |
| } |
| |
| void |
| ply_list_remove_data (ply_list_t *list, |
| void *data) |
| { |
| ply_list_node_t *node; |
| |
| if (data == NULL) |
| return; |
| |
| node = ply_list_find_node (list, data); |
| |
| if (node != NULL) |
| ply_list_remove_node (list, node); |
| } |
| |
| static void |
| ply_list_unlink_node (ply_list_t *list, |
| ply_list_node_t *node) |
| { |
| ply_list_node_t *node_before, *node_after; |
| |
| assert (list != NULL); |
| |
| if (node == NULL) |
| return; |
| |
| node_before = node->previous; |
| node_after = node->next; |
| |
| if (node_before != NULL) |
| node_before->next = node_after; |
| |
| if (node_after != NULL) |
| node_after->previous = node_before; |
| |
| if (list->first_node == node) |
| list->first_node = node_after; |
| |
| if (list->last_node == node) |
| list->last_node = node_before; |
| |
| node->previous = NULL; |
| node->next = NULL; |
| |
| list->number_of_nodes--; |
| assert (ply_list_find_node (list, node->data) != node); |
| } |
| |
| void |
| ply_list_remove_node (ply_list_t *list, |
| ply_list_node_t *node) |
| { |
| ply_list_unlink_node (list, node); |
| ply_list_node_free (node); |
| } |
| |
| void |
| ply_list_remove_all_nodes (ply_list_t *list) |
| { |
| ply_list_node_t *node; |
| |
| if (list == NULL) |
| return; |
| |
| node = list->first_node; |
| while (node != NULL) |
| { |
| ply_list_node_t *next_node; |
| next_node = node->next; |
| ply_list_remove_node (list, node); |
| node = next_node; |
| } |
| } |
| |
| ply_list_node_t * |
| ply_list_get_first_node (ply_list_t *list) |
| { |
| return list->first_node; |
| } |
| |
| ply_list_node_t * |
| ply_list_get_last_node (ply_list_t *list) |
| { |
| return list->last_node; |
| } |
| |
| ply_list_node_t * |
| ply_list_get_next_node (ply_list_t *list, |
| ply_list_node_t *node) |
| { |
| return node->next; |
| } |
| void ply_list_sort (ply_list_t *list, |
| ply_list_compare_func_t *compare) |
| { |
| ply_list_node_t *nodea; |
| ply_list_node_t *nodeb; |
| int clean; |
| do |
| { |
| clean=1; |
| nodea = ply_list_get_first_node (list); |
| if (!nodea) return; |
| nodeb = ply_list_get_next_node (list, nodea); |
| while (nodeb) |
| { |
| if ((compare)(ply_list_node_get_data(nodea), ply_list_node_get_data(nodeb))>0) |
| { |
| void* temp = ply_list_node_get_data(nodea); |
| ply_list_node_set_data(nodea, ply_list_node_get_data(nodeb)); |
| ply_list_node_set_data(nodeb, temp); |
| clean=0; |
| } |
| nodea = nodeb; |
| nodeb = ply_list_get_next_node (list, nodea); |
| } |
| } |
| while (!clean); |
| |
| } |
| |
| void * |
| ply_list_node_get_data (ply_list_node_t *node) |
| { |
| return node->data; |
| } |
| |
| void |
| ply_list_node_set_data (ply_list_node_t *node, void *data) |
| { |
| node->data = data; |
| return; |
| } |
| |
| #ifdef PLY_LIST_ENABLE_TEST |
| #include <stdio.h> |
| |
| int |
| main (int argc, |
| char **argv) |
| { |
| ply_list_t *list; |
| ply_list_node_t *node; |
| int i; |
| |
| list = ply_list_new (); |
| |
| ply_list_append_data (list, (void *) "foo"); |
| ply_list_append_data (list, (void *) "bar"); |
| ply_list_append_data (list, (void *) "baz"); |
| ply_list_prepend_data (list, (void *) "qux"); |
| ply_list_prepend_data (list, (void *) "quux"); |
| ply_list_remove_data (list, (void *) "baz"); |
| ply_list_remove_data (list, (void *) "foo"); |
| |
| node = ply_list_get_first_node (list); |
| i = 0; |
| while (node != NULL) |
| { |
| printf ("node '%d' has data '%s'\n", i, |
| (char *) ply_list_node_get_data (node)); |
| node = ply_list_get_next_node (list, node); |
| i++; |
| } |
| |
| ply_list_free (list); |
| return 0; |
| } |
| |
| #endif |
| /* vim: set ts=4 sw=4 expandtab autoindent cindent cino={.5s,(0: */ |