[Linux-diag-devel] dlist patch
Brought to you by:
hegdevasant,
mananth
From: Eric B. <bo...@ga...> - 2003-07-11 16:50:37
|
Dan mentioned a need for some linked list organization in libsysfs so I crafted a lightweight double linked list implementation. I integrated it into sysutil-0.1.1 and have so far only plugged it in to replace the children list in the device structure. I'm considering refactoring most or all of the lists with it so the linked list navigation code can be consolidated rather than scattered and replicated thoughout. But before I go revamping everything, I figured I'd just put it in one isolated place to give people a taste of what it would look like. See the include/dlist.h for basic documentation and lib/dlist_test.c for a simple minded example. You create a list using dlist_new, navigate using dlist_next and dlist_prev, and it supports perlish dlist_push, dlist_pop, dlist_shift, dlist_unshift semantics. These apparently excess features are implemented using inlines and macros so we should be getting readability improvements with minimal overhead. It does have two typedefs. If someone will explain the reasoning behind the anti typedef prejudice to my satisfaction we can switch those to the longer uglier struct blah model. :) Will add sorting support if desired. Here's the patch: ---CUT--- diff -ruN ../sysutils-0.1.1/cmd/systool.c ./cmd/systool.c --- ../sysutils-0.1.1/cmd/systool.c Mon Jul 7 16:17:27 2003 +++ ./cmd/systool.c Fri Jul 11 10:27:53 2003 @@ -311,8 +311,8 @@ root->bus_id) == 0)) { show_root_device(root, level); } - cur = root->children; - while (cur != NULL) { + dlist_start(root->children); + while ((cur = dlist_next(root->children))) { show_device_tree(cur, (level+6)); cur = cur->next; } diff -ruN ../sysutils-0.1.1/include/dlist.h ./include/dlist.h --- ../sysutils-0.1.1/include/dlist.h Wed Dec 31 18:00:00 1969 +++ ./include/dlist.h Fri Jul 11 10:28:37 2003 @@ -0,0 +1,109 @@ +/* + * dlist.h + * + * Copyright (C) 2003 Eric J Bohm + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ +#ifndef _DLIST_H_ +#define _DLIST_H_ + +/* Double linked list header. + +* navigate your list with DLIST_PREV and DLIST_NEXT. These are macros +* so function call overhead is minimized. + +* Supports perl style push, pop, shift, unshift list semantics. + +* You allocate the data and give dlist the pointer. If your data is +* complex set the dlist->del_func to a an appropriate delete using +* dlist_new_with_delete. Your delete function must match +(void * )(del(void *) +*Otherwise dlist will just use free. + +* NOTE: The small amount of pain involved in doing that allows us to +* avoid copy in copy out semantics. + +* Dlist uses an internal mark pointer to keep track of where you are +* in the list. + +* insert and delete take a directional parameter. Where direction +* corresponds to the direction in which you want the list to go. +* true direction corresponded to progressing forward in the last +* false to regressing in the list. +* so a dlist_insert(yourlist,item,1) will insert it after the mark +* so a dlist_insert(yourlist,item,0) will insert it before the mark +* any insert will move the mark to the new node regardless of the direction. + +* Just use the dlist_(insert|delete)_(before|after) macros if you do not want +* to think about it. + +*/ +#include <malloc.h> +typedef struct dl_node { + struct dl_node *prev; + struct dl_node *next; + void *data; +} DL_node; + +typedef struct dlist { + DL_node *marker; + unsigned long count; + size_t data_size; + void (*del_func)(void *); + DL_node headnode; + DL_node *head; +} Dlist; + +Dlist *dlist_new(size_t datasize); +Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*)); +void *_dlist_mark_move(Dlist *list,int direction); +void *DLIST_NEXT(Dlist *); +void *dlist_mark(Dlist *); +void dlist_start(Dlist *); +void dlist_end(Dlist *); + +void *dlist_insert(Dlist *,void *,int) ; + +void dlist_delete(Dlist *,int); + +void dlist_push(Dlist *,void *); + +void dlist_unshift(Dlist *,void *); + +void *dlist_pop(Dlist *); + +void *dlist_shift(Dlist *); + +void dlist_destroy(Dlist *); + + +/* + * _dlist_remove is for internal use only + * _dlist_mark_move is for internal use only + */ +void *_dlist_remove(Dlist *,DL_node *,int ); + +#define dlist_prev(A) _dlist_mark_move((A),0) +#define dlist_next(A) _dlist_mark_move((A),1) + +#define dlist_insert_before(A,B) dlist_insert((A),(B),0) +#define dlist_insert_after(A,B) dlist_insert((A),(B),1) + +#define dlist_delete_before(A) dlist_delete((A),0) +#define dlist_delete_after(A) dlist_delete((A),1) + +#endif /* _DLIST_H_ */ diff -ruN ../sysutils-0.1.1/include/libsysfs.h ./include/libsysfs.h --- ../sysutils-0.1.1/include/libsysfs.h Mon Jul 7 16:30:01 2003 +++ ./include/libsysfs.h Fri Jul 11 10:15:59 2003 @@ -24,7 +24,7 @@ #define _LIBSYSFS_H_ #include <sys/types.h> - +#include "dlist.h" /* * Generic #defines go here.. */ @@ -80,7 +80,7 @@ struct sysfs_driver *driver; struct sysfs_directory *directory; struct sysfs_device *parent; - struct sysfs_device *children; + struct dlist *children; }; struct sysfs_bus { diff -ruN ../sysutils-0.1.1/lib/Makefile ./lib/Makefile --- ../sysutils-0.1.1/lib/Makefile Mon Jul 7 16:17:27 2003 +++ ./lib/Makefile Fri Jul 11 10:12:27 2003 @@ -6,12 +6,13 @@ H_INCLUDE=../include LIB_INCLUDE=. OBJS=sysfs_bus.o sysfs_class.o sysfs_device.o sysfs_dir.o sysfs_driver.o \ - sysfs_utils.o + sysfs_utils.o dlist.o # Install directory # Options CFLAGS=-O2 -Wall -ansi -g +CLFLAGS=-O2 -Wall -g # sysfs library LIBSYSFS=libsysfs.a @@ -40,5 +41,12 @@ sysfs_utils.o: sysfs_utils.c $(CC) -I$(H_INCLUDE) -I$(LIB_INCLUDE) $(CFLAGS) -c sysfs_utils.c + +dlist.o: dlist.c $(H_INCLUDE)/dlist.h + $(CC) -I$(H_INCLUDE) -I$(LIB_INCLUDE) $(CLFLAGS) -c dlist.c + +dlist_test: dlist.o $(H_INCLUDE)/dlist.h dlist_test.c + $(CC) -I$(H_INCLUDE) -I$(LIB_INCLUDE) $(CLFLAGS) dlist.o dlist_test.c -o dlist_test + clean: - $(RM) *.o *~ core $(LIBSYSFS) + $(RM) *.o *~ core $(LIBSYSFS) dlist_test diff -ruN ../sysutils-0.1.1/lib/dlist.c ./lib/dlist.c --- ../sysutils-0.1.1/lib/dlist.c Wed Dec 31 18:00:00 1969 +++ ./lib/dlist.c Fri Jul 11 10:30:38 2003 @@ -0,0 +1,309 @@ +/* + * dlist.c + * + * Copyright (C) 2003 Eric J Bohm + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021110307 USA + * + */ + + +/* Double linked list implementation. + + * You allocate the data and give dlist the pointer. + * If your data is complex set the dlist->del_func to a an appropriate + * delete function. Otherwise dlist will just use free. + +*/ +#include "dlist.h" + +/* + * Return pointer to node at marker. + * else null if no nodes. + */ + +inline void *dlist_mark(Dlist *list) +{ + if(list->marker!=NULL) + return(list->marker->data); + else + return(NULL); + + +} + +/* + * Set marker to start. + */ + +inline void dlist_start(Dlist *list) +{ + list->marker=list->head; +} + +/* + * Set marker to end. + */ + +inline void dlist_end(Dlist *list) +{ + list->marker=list->head; +} + +/* internal use function + * quickie inline to consolidate the marker movement logic + * in one place + * + * when direction true it moves marker after + * when direction false it moves marker before. + * return pointer to data at new marker + * if nowhere to move the marker in desired direction return null + */ +inline void *_dlist_mark_move(Dlist *list,int direction) +{ + if(direction) + { + if( list->marker->next!=NULL) + list->marker=list->marker->next; + else + return(NULL); + } + else + { + if( list->marker->prev!=NULL) + list->marker=list->marker->prev; + else + return(NULL); + } + if(list->marker!=list->head) + return(list->marker->data); + else + return(NULL); +} + +/* + * Create new linked list to store nodes of datasize. + * return null if list cannot be created. + */ +Dlist *dlist_new(size_t datasize) +{ + Dlist *list=NULL; + if((list=malloc(sizeof(Dlist)))) + { + list->marker=NULL; + list->count=0L; + list->data_size=datasize; + list->del_func=free; + list->head=&(list->headnode); + list->head->prev=NULL; + list->head->next=NULL; + list->head->data=NULL; + } + return(list); +} + +/* + * Create new linked list to store nodes of datasize set list + * data node delete function to the passed in del_func + * return null if list cannot be created. + */ +Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*)) +{ + Dlist *list=NULL; + list=dlist_new(datasize); + if(list!=NULL) + list->del_func=del_func; + return(list); +} + + +/* + * remove marker node from list + * call data_delete function on data if registered. + * otherwise call free. + * when direction true it moves marker after + * when direction false it moves marker before. + * free marker node + * return nothing. + */ + +void dlist_delete(Dlist *list,int direction) +{ + if((list->marker != list->head)&&(list->marker!=NULL)) + { + DL_node *corpse; + corpse=list->marker; + _dlist_mark_move(list,direction); + if(list->head->next==corpse) + list->head->next=corpse->next; + if(list->head->prev==corpse) + list->head->prev=corpse->prev; + if(corpse->prev!=NULL) //should be impossible + corpse->prev->next=corpse->next; + if(corpse->next!=NULL) //should be impossible + corpse->next->prev=corpse->prev; + list->del_func(corpse->data); + list->count--; + free(corpse); + } +} + +/* + * Insert node containing data at marker. + * If direction true it inserts after. + * If direction false it inserts before. + * move marker to inserted node + * return pointer to inserted node + */ +void *dlist_insert(Dlist *list,void *data,int direction) +{ + DL_node *new_node=NULL; + if(list==NULL || data==NULL) + return(NULL); + if(list->marker==NULL) //in case the marker ends up unset + list->marker=list->head; + if((new_node=malloc(sizeof(DL_node)))) + { + new_node->data=data; + new_node->prev=NULL; + new_node->next=NULL; + list->count++; + if(list->head->next==NULL) //no l + { + list->head->next=list->head->prev=list->marker=new_node; + new_node->prev=list->head; + new_node->next=list->head; + } + else if(direction) + { + new_node->next=list->marker->next; + new_node->prev=list->marker; + list->marker->next=new_node; + if(list->head->prev==list->marker) + list->head->prev=new_node; + list->marker=new_node; + } + else + { + new_node->prev=list->marker->prev; + new_node->next=list->marker; + list->marker->prev=new_node; + if(list->head->next==list->marker) + list->head->next=new_node; + list->marker=new_node; + } + } + else + { + return(NULL); + } + return(list->marker->data); +} + +/* + * Remove DL_node from list without deallocating data. + * if marker == killme . + * when direction true it moves marker after + * when direction false it moves marker before. + * to previous if there is no next. + */ +void *_dlist_remove(Dlist *list,DL_node *killme,int direction) +{ + if(killme!=NULL) + { + void *killer_data=killme->data; + // take care of head and marker pointers. + if(list->marker==killme) + _dlist_mark_move(list,direction); + if(killme ==list->head->next) + list->head->next=killme->next; + if(killme==list->head->prev) + list->head->prev=killme->prev; + // remove from list + if(killme->prev !=NULL) + killme->prev->next=killme->next; + if(killme->next !=NULL) + killme->next->prev=killme->prev; + list->count--; + free(killme); + return(killer_data); + } + else + return (NULL); +} + + +/* + * Insert node containing data after end. + */ +void dlist_push(Dlist *list,void *data) +{ + list->marker=list->head->prev; + dlist_insert(list,data,1); +} + +/* + * Insert node containing data at start. + */ + +void dlist_unshift(Dlist *list,void *data) + +{ + list->marker=list->head->next; + dlist_insert(list,data,0); +} + + +/* + * Remove end node from list. + * Return pointer to data in removed node. + * Null if no nodes. + */ + +void *dlist_pop(Dlist *list) +{ + return(_dlist_remove(list,list->head->prev,0)); +} + +/* + * Remove start node from list. + * Return pointer to data in removed node. + * Null if no nodes. + */ + +void *dlist_shift(Dlist *list) +{ + return(_dlist_remove(list,list->head->next,1)); +} + + +/* + * destroy the list freeing all memory + */ + + +void dlist_destroy(Dlist *list) +{ + if(list !=NULL) + { + dlist_start(list); + while(dlist_next(list)) + { + dlist_delete(list,1); + } + free(list); + } +} + diff -ruN ../sysutils-0.1.1/lib/dlist_test.c ./lib/dlist_test.c --- ../sysutils-0.1.1/lib/dlist_test.c Wed Dec 31 18:00:00 1969 +++ ./lib/dlist_test.c Fri Jul 11 10:30:09 2003 @@ -0,0 +1,217 @@ +/* + * dlist_test.c + * + * Copyright (C) 2003 Eric J Bohm + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ + + +/* Double linked list implementation tester. + */ +#include "dlist.h" +#include <stdio.h> +#include <string.h> +// create some dlists put nodes in and out +// use dump +// try list with del_func and without +// use insert, unshift, push +// use pop push mark +// use prev next + +typedef struct simple { + char label[80]; + int number; +} Simple; + + +typedef struct complex { + int cnumber; + Simple *sthing; +} Complex; + +void simple_dump(Dlist *); +void simple_dump_rev(Dlist *); +void complex_dump(Dlist *); +void complex_del(void *); + +int main (int argc,char *argv[]) +{ + Dlist *list; + Simple *s1,*s2,*s3,*stemp; + Complex *c1,*c2,*c3; + while(1) + { + if((s1=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s1->number=1; + strcpy(s1->label,"one"); + if((s2=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s2->number=2; + strcpy(s2->label,"two"); + if((s3=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s3->number=3; + strcpy(s3->label,"three"); + if((list=dlist_new(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR dlist_new fail\n"); + return(2); + } + + dlist_push(list,s1); + dlist_push(list,s2); + dlist_push(list,s3); + printf("count is %ld\n",list->count); + simple_dump(list); + simple_dump_rev(list); + stemp=dlist_pop(list); + printf("popped %s\n",stemp->label); + simple_dump(list); + printf("pushed\n"); + dlist_push(list,s3); + simple_dump(list); + stemp=dlist_shift(list); + printf("shifted %s\n",stemp->label); + simple_dump(list); + printf("unshifted\n"); + dlist_unshift(list,stemp); + simple_dump(list); + dlist_destroy(list); + + if((s1=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s1->number=1; + strcpy(s1->label,"one"); + if((c1=malloc(sizeof(Complex)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + c1->cnumber=1; + c1->sthing=s1; + if((s2=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s2->number=2; + strcpy(s2->label,"two"); + if((c2=malloc(sizeof(Complex)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + c2->cnumber=2; + c2->sthing=s2; + if((s3=malloc(sizeof(Simple)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + s3->number=3; + strcpy(s3->label,"three"); + if((c3=malloc(sizeof(Complex)))==NULL) + { + fprintf(stderr,"ERR malloc fail\n"); + return(1); + } + c3->cnumber=3; + c3->sthing=s3; + if((list=dlist_new_with_delete(sizeof(Complex),complex_del))==NULL) + { + fprintf(stderr,"ERR dlist_new fail\n"); + return(2); + } + dlist_start(list); + if(dlist_insert_before(list,c1)==NULL) + { + fprintf(stderr,"ERR dlist_insert fail\n"); + return(2); + } + printf("inserted before\n"); + if(dlist_insert_before(list,c2)==NULL) + { + fprintf(stderr,"ERR dlist_insert fail\n"); + return(2); + } + printf("inserted before\n"); + if(dlist_insert_before(list,c3)==NULL) + { + fprintf(stderr,"ERR dlist_insert fail\n"); + return(2); + } + printf("inserted before\n"); + complex_dump(list); + dlist_destroy(list); + } + return(0); +} + +void simple_dump (Dlist *list) +{ + Simple *thisone; + dlist_start(list); + printf("count %ld \n",list->count); + while((thisone=dlist_next(list))) + { + printf("label %s number %d \n",thisone->label,thisone->number); + } + +} +void simple_dump_rev (Dlist *list) +{ + Simple *thisone; + dlist_end(list); + printf("rev count %ld \n",list->count); + while((thisone=dlist_prev(list))) + { + printf("label %s number %d \n",thisone->label,thisone->number); + } +} + +void complex_dump (Dlist *list) +{ + Complex *thisone; + dlist_start(list); + printf("count %ld \n",list->count); + while((thisone=dlist_next(list))) + { + printf("cnumber %d label %s number %d \n",thisone->cnumber,thisone->sthing->label,thisone->sthing->number); + } + +} + +void complex_del (void *item) +{ + Complex *corpse=item; + printf("freeing complex\n"); + free(corpse->sthing); + free(corpse); +} diff -ruN ../sysutils-0.1.1/lib/sysfs_device.c ./lib/sysfs_device.c --- ../sysutils-0.1.1/lib/sysfs_device.c Mon Jul 7 16:28:55 2003 +++ ./lib/sysfs_device.c Fri Jul 11 10:24:30 2003 @@ -22,7 +22,7 @@ */ #include "libsysfs.h" #include "sysfs.h" - +void sysfs_del_device(void *dev); /** * sysfs_close_device: closes and cleans up a device * @dev = device to clean up @@ -58,7 +58,6 @@ new->parent = NULL; new->children = NULL; } - return new; } @@ -135,7 +134,11 @@ if ((strlen(dev->name) > 0) && *p == '\n') *p = '\0'; } - + dev->children=dlist_new_with_delete(sizeof(struct sysfs_device),sysfs_del_device); + if (dev->children == NULL) { + dprintf(stderr, "Error allocating device children at %s\n", path); + return NULL; + } return dev; } @@ -147,19 +150,17 @@ void sysfs_close_device_tree(struct sysfs_device *devroot) { if (devroot != NULL) { - if (devroot->children != NULL) { - struct sysfs_device *child = NULL, *next = NULL; - - for (child = devroot->children; child != NULL; - child = next) { - next = child->next; - sysfs_close_device_tree(child); - } - } - sysfs_close_device(devroot); + dlist_destroy(devroot->children); + sysfs_close_device(devroot); } } +void sysfs_del_device(void *dev) +{ + sysfs_close_device_tree((struct sysfs_device*) dev); +} + +/* EJB once dlist accepted this function will be redundant*/ /** * add_device_child_to_parent: adds child device to parent * @parent: parent device. @@ -168,11 +169,7 @@ static void add_device_child_to_parent(struct sysfs_device *parent, struct sysfs_device *child) { - if (parent != NULL && child != NULL) { - child->next = parent->children; - parent->children = child; - child->parent = parent; - } + dlist_unshift(parent->children,child); } /** @@ -205,6 +202,7 @@ sysfs_close_device_tree(rootdev); return NULL; } + /* EJB once dlist accepted this becomes a dlist_unshift call*/ add_device_child_to_parent(rootdev, new); cur = cur->next; } |