rg2c+@andrew.cmu.edu (Robert Nelson Gasch) (12/11/90)
I have a question concerning dynamically allocated data structures. An aquaintance told me this was possible, but did now know the deatils. In PASCAL, if you have 3 linked lists of different pointer types, you have to write 3 different Insert, search & delete routines; one for each pointer type. I was wondering if these routines can be generalized for any pointer type in C? This would mean that you could write each routine only once, which would then operate on all 3 pointer types. If this can be done, what are the details involved?? Thanx ---> Rob
gwyn@smoke.brl.mil (Doug Gwyn) (12/12/90)
In article <cbN7yBm00UhW45Cnh2@andrew.cmu.edu> rg2c+@andrew.cmu.edu (Robert Nelson Gasch) writes: >In PASCAL, if you have 3 linked lists of different pointer types, >you have to write 3 different Insert, search & delete routines; one >for each pointer type. I was wondering if these routines can be >generalized for any pointer type in C? Yes, the simplest scheme is to have a special "linkage" substructure as the first member of each type of node structure. By appropriate use of casts etc., common link-manipulation routines can be used for all the node types, in a portable ("strictly conforming") manner. Tom Plum's "Reliable Data Structures in C" contains examples. You might also contact Karen Murray <Karen@BRL.MIL> about obtaining the MUVES "Dq" package source code, which is a fairly elaborate implementation of the idea (complete with "lint" escapes).
david@doe.utoronto.ca (David Megginson) (12/12/90)
In article <cbN7yBm00UhW45Cnh2@andrew.cmu.edu> rg2c+@andrew.cmu.edu (Robert Nelson Gasch) writes: >I have a question concerning dynamically allocated data structures. An >aquaintance told me this was possible, but did now know the deatils. > >In PASCAL, if you have 3 linked lists of different pointer types, >you have to write 3 different Insert, search & delete routines; one >for each pointer type. I was wondering if these routines can be >generalized for any pointer type in C? This would mean that you >could write each routine only once, which would then operate on all >3 pointer types. If this can be done, what are the details involved?? > >Thanx ---> Rob One trick which I know is to define a generic structure or two to get at linked-list pointers. For example, struct list1 { struct list1 * next; }; struct list2 { struct list2 * next; struct list2 * prev; }; Now, you can write functions to deal with any arbitrary linked list of structures, as long as the links are always the first element of the structures. For example, you could have a linked list of these structures: struct record { struct record * next; char name[NAMEMAX]; char address[ADDRMAX]; int age; long salary; /* wishful thinking! */ }; and your linked-list functions would deal with lists of this structure as if it were (struct list1). This works fine for inserting or deleting in linked lists, or for freeing lists (free() knows how much memory to free). Enjoy! David Megginson -- //////////////////////////////////////////////////////////////////////// / David Megginson david@doe.utoronto.ca / / Centre for Medieval Studies meggin@vm.epas.utoronto.ca / ////////////////////////////////////////////////////////////////////////
aas@aase.nr.no (Gisle Aas) (12/13/90)
In article <14714@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: In article <cbN7yBm00UhW45Cnh2@andrew.cmu.edu> rg2c+@andrew.cmu.edu (Robert Nelson Gasch) writes: >In PASCAL, if you have 3 linked lists of different pointer types, >you have to write 3 different Insert, search & delete routines; one >for each pointer type. I was wondering if these routines can be >generalized for any pointer type in C? Yes, the simplest scheme is to have a special "linkage" substructure as the first member of each type of node structure. By appropriate use of casts etc., common link-manipulation routines can be used for all the node types, in a portable ("strictly conforming") manner. Or you could use the preprocessor. These macros operate on double linked lists. The idea should be simple to extend. #ifdef lint int _ZERO_; #else #define _ZERO_ 0 #endif #define STATEMENT(s) do {s} while (_ZERO_) /* don't use this macro directly */ #define _dl_insert(z,d,first,prev,next) \ if (first) { \ z->prev = d->prev; \ z->next = d; \ d->prev->next = z; \ d->prev = z; \ } else { \ first = z; \ z->next = z; \ z->prev = z; \ } /* insert the element z just before the element d which is a member of * the list starting with element first. */ #define dl_insert(z,d,first,prev,next) \ STATEMENT( \ _dl_insert(z,d,first,prev,next); \ if (d == first) \ first = z; \ ) #define dl_insert_first(z,first,prev,next) \ STATEMENT( \ _dl_insert(z,first,first,prev,next); \ first = z; \ ) #define dl_insert_last(z,first,prev,next) \ STATEMENT( \ _dl_insert(z,first,first,prev,next); \ ) #define dl_remove(z,first,prev,next) \ STATEMENT( \ z->next->prev = z->prev; \ z->prev->next = z->next; \ if (z == first) first = z->next; \ if (z == first) first = NULL; \ ) /*---- Example of use, not tested ----*/ struct node *list1 = NULL, *list2 = NULL; /* list heads */ struct node { sometype foo; ... struct node *next1, *prev1; struct node *next2, *prev2; } x = malloc(sizeof(node)); dl_insert_first(x,list1,prev1,next2); dl_insert_last(x,list2,prev2,next2); dl_remove(x,list2,prev2,next2); -- Gisle Aas | snail: Boks 114 Blindern, N-0314 Oslo, Norway Norsk Regnesentral | X.400: G=Gisle;S=Aas;O=nr;P=uninett;C=no voice: +47-2-453561 | inet: Gisle.Aas@nr.no
n025fc@tamuts.tamu.edu (Kevin Weller) (12/13/90)
In article <1990Dec12.002520.25210@doe.utoronto.ca> david@doe.utoronto.ca (David Megginson) writes: One trick which I know is to define a generic structure or two to get at linked-list pointers. For example, struct list1 { struct list1 * next; }; struct list2 { struct list2 * next; struct list2 * prev; }; Now, you can write functions to deal with any arbitrary linked list of structures, as long as the links are always the first element of the structures. .... David Megginson That's the way I do it. A whole subsection of my own C library is devoted to this (when it's "done," I hope to release this library as freeware, ISAM manager and all). I was assigned to write two programs in Pascal class, both doing the same thing, but one with an array and the other with a linked list. I wanted to write two sets of low-level procedures to handle the two different data structure types, then just plug in the right set of routines into one high-level program like I would do in C. Hah! I had to introduce one kludge after another due to Pascal's data typing rules until the low-level stuff was no longer very general. C, by comparison, has so many features supporting procedural abstraction that Pascal lacks, and I guess I've been spoiled. -- Kevin L. Weller /-------+--------------------\ internet: n025fc@tamuts.tamu.edu | aTm | GIG 'EM, AGGIES! | CIS: 73327,1447 \-------+--------------------/