cottrell@nbs-vms.ARPA (02/08/85)
/* As promised, a good reason for type punning. We start off with the definition of basic doubly linked circular lists: typedef struct link { /* list entry */ struct link *fwd; /* foreward pointer */ struct link *bwd; /* backward pointer */ } LINK, *LINKP; typedef struct head { /* list head */ LINK link; /* obvious */ int cnt; /* how many in list */ char id[3]; /* general use */ char lock; /* for test & set */ } HEAD, *HEADP; Now we define other objex such as buffers & channels: typedef struct buf { LINK link; /* to buffers */ .... /* more declarations */ char data[SIZE]; /* data goes here */ } BUF, *BUFP; typedef struct chan { /* com channel */ LINK link; /* to other channels */ .... /* other stuff */ HEAD rcvq; /* to buffers */ HEAD xmtq; /* to buffers */ .... /* other stuff */ LINK misc; /* to other channels */ .... /* chained for some reason */ } CHAN, *CHANP; Notice that the first two items of any struxure are forward & backward links! Now we create two funxions to manipulate links only. They are modeled after the vax instruxions INSQUE & REMQUE: LINKP remque(LINKP p); /* remove p from list */ { if (p) (p->fwd->bwd = p->bwd)->fwd = p->fwd; return(p); } LINKP insque(LINKP p,LINKP q); /* insert p after q */ { if (p) (((p->fwd = q->fwd)->bwd = p)->bwd = q)->fwd = p; return(p); } At the next level we have four funxions that insert & remove `objex' to/from the head/tail of the list: LINKP Get_Head(HEADP h); /* get from head of list h */ { if (!h || !h->cnt) return(0); /* null protect */ --h->cnt; /* one less */ return(remque(h->link.fwd); /* remove the head */ } LINKP Get_Tail(HEADP h); /* get from tail of list h */ { if (!h || !h->cnt) return(0); /* null protect */ --h->cnt; /* one less */ return(remque(h->link.bwd); /* remove the tail */ } LINKP Put_Head(HEADP h,LINKP p); /* put p to head of list h */ { if (!h) return(0); /* null protect */ ++h->cnt; /* one more */ return(insque(h->link.fwd,p); /* put to head */ } LINKP Put_Tail(HEADP h,LINKP p); /* put p to tail of list h */ { if (!h) return(0); /* null protect */ ++h->cnt; /* one more */ return(insque(h,p); /* put to tail */ } The Put funxions return a value so one can move an entire list by: while (Put_Tail(free,Get_head(list)); Note the lack of cast on h in Put_Tail. And for those of you who like out of bounds array refs, note that head->id[3] is available to use if the particular list is never locked via test and set. Now in the modules where we deal primarily with buffers, Get_Head is declared as BUFP Get_Head; where we deal with channels, CHANP Get_Head. And where widgets are used Get_Head is of type WIDGETP. And so on. Lint will go bonkers over this! I for one can do without all those extra casts cluttering up my code. Pretty soon programmers, like actors will be saying: "Break a leg!" */
Doug Gwyn (VLD/VMB) <gwyn@BRL-VLD.ARPA> (02/08/85)
Sigh. One can usually get away with punning different (struct XXX *)s because in a given implementation struct pointers probably all have a uniform representation. On the other hand, head->id[3] where the member id[] has only been declared of length 3 is illegal BECAUSE such usage may not work in general (for adjacent char arrays it usually does, but there is no guarantee of this in the language specification). If you happen to KNOW that you have e.g. a VAX, then of course you can cheat on the rules and get away with it. However, the same code may break miserably if run on some other machine (say, an S-1). To say that a MACHINE is non-portable just because its architecture is not that of a VAX strikes me as pretty silly. Lots of us have a variety of machines to cope with, and these VAX-specific tricks just get in the way. By the way, there are other ways to code linked lists while following the language rules. The example you gave is woefully short on error detection if a coding error is made and the wrong sort of structure is linked into a list.
guy@rlgvax.UUCP (Guy Harris) (02/09/85)
> Note the lack of cast on h in Put_Tail. Oh, JHFC, Gary, RTFM. K&R says that the coercion of 0 to a null pointer of the appropriate type is automatic in what amount to all situations where the compiler can figure this out. Stop talking about the lack of casts in statements like "if (!h)"; they never were required and never will be. > Now in the modules where we deal primarily with buffers, Get_Head is > declared as BUFP Get_Head; where we deal with channels, CHANP Get_Head. > And where widgets are used Get_Head is of type WIDGETP. And so on. > Lint will go bonkers over this! OK, where's the good reason (other than fingers tired of typing casts) for type punning? This whole thing can be expressed the same way with casts (if constantly typing casts get in your way, define some macros). ANSI Standard C would permit you to define Get_Head as returning "void *", in which case the casts wouldn't be necessary to silence "lint". The compiler would also know enough to generate correct code. I suspect with a language designed with type inheritance in mind, what you specify could be stated in a much more straightforward fashion (buffers, channels, widgets, etc. inherit the doubly-linked-list nature of lists), and be written in a type-safe fashion. I prefer to let the computer handle all the tedious details, like all correctness checks doable by computer, generation of optimal code, etc., which it can deal with better (given that machines, unlike humans, don't perform less poorly when bored, tired, etc.) than I can. Guy Harris {seismo,ihnp4,allegra}!rlgvax!guy
cottrell@nbs-vms.ARPA (02/12/85)
/* > > Note the lack of cast on h in Put_Tail. > > Oh, JHFC, Gary, RTFM. K&R says that the coercion of 0 to a null pointer > of the appropriate type is automatic in what amount to all situations where > the compiler can figure this out. Stop talking about the lack of casts > in statements like "if (!h)"; they never were required and never will be. Gotcha this time Guy! The omitted cast was in the funxion call to `insque'. Part of my message follows: ~ LINKP remque(LINKP p); /* remove p from list */ ~ { if (p) (p->fwd->bwd = p->bwd)->fwd = p->fwd; ~ return(p); ~ } ~ ~ LINKP insque(LINKP p,LINKP q); /* insert p after q */ ~ { if (p) (((p->fwd = q->fwd)->bwd = p)->bwd = q)->fwd = p; ~ return(p); ~ } ~ ~ LINKP Put_Head(HEADP h,LINKP p); /* put p to head of list h */ ~ { if (!h) return(0); /* null protect */ ~ ++h->cnt; /* one more */ ~ return(insque(h->link.fwd,p); /* put to head */ ~ } ~ ~ LINKP Put_Tail(HEADP h,LINKP p); /* put p to tail of list h */ ~ { if (!h) return(0); /* null protect */ ~ ++h->cnt; /* one more */ ~ return(insque(h,p); /* put to tail */ ~ } ~ ~ Note the lack of cast on h in Put_Tail. Admittedly this required you to muddle thru a lot of possibly boring code, but, he who lives by the nit dies by the pick. I have an idea what JHFC means, but what does RTFM mean? BTW, my name is not Gary, it's Jim. Okay, I figured it out. Better watch out, Guy, there is a pea-brain at Princeton who doesn't like "obscenity", even when it's encoded in asterisks. He sent a nastygram to our postmaster about my u-wiz message about `vm on a 680x0'. You know, the one that said: What the is this doing in unix-wizards? Hey, just kidding guys :-) */
bsa@ncoast.UUCP (Brandon Allbery) (02/26/85)
> Article <8125@brl-tgr.ARPA>, from cottrell@nbs-vms.ARPA +---------------- | /* | As promised, a good reason for type punning. We start off with the | definition of basic doubly linked circular lists: | Oh, for crying out loud! Someone give this person an Ada compiler, PLEASE! generic package LIST_PAK is ... package COM_LIST_PAK is new LIST_PAK(COM_RECORD); package STR_LIST_PAK is new LIST_PAK(STRING); ... (Ada hacks -- did I do that right? I haven't found an Ada compiler to play with yet.) --bsa -- Brandon Allbery, decvax!cwruecmp!ncoast!bsa, ncoast!bsa@case.csnet (etc.) 6504 Chestnut Road Independence, Ohio 44131 +1 216 524 1416 -- CIS 74106,1032 -=> Does the Doctor make house calls? <=-
bsa@ncoast.UUCP (Brandon Allbery) (02/26/85)
Since we're on the subject, I'm trying to write a program using my own
memory management routines. Basically, only two kinds of objects are
allocated: char[] and
struct _var
{
short v_type;
char *v_name;
char *v_value;
struct _var *v_next;
}
Now, my memory management is to sbrk() when needed, and to put freed
(struct _var)'s onto a free-list; freed strings are appended to char *'s
(v_value) on the free list, and the size of the string is kept in the
then-unused v_type field.
The problem is that I may conceivably use up all process memory (this is
a Xenix system, not vmunix) in strings on the freelist, stored in a
number of unremoveable struct _var's (string sizes near 32767 chars; the
most likely scenario is just ONE struct _var), and need a struct _var
for some reason. I would like to turn a string into a struct _var.
I've already set up a portability file; by using a set of macros
bsizeof() and word_size, I can get the sizes fairly portably. But I
don't know how to portably align the struct on whatever boundary it
needs.
Could people on various architectures (VAX/PDP-11, S-1, Honeywell, etc.)
please help me by sending me mail on the necessary alignment needed for
these structures? With a representative set of architectures, maybe I
could set up some kludgey form of alignof() or similar to make this
possible.
Thanks in advance,
Brandon (bsa@ncoast.UUCP)
--
Brandon Allbery, decvax!cwruecmp!ncoast!bsa, ncoast!bsa@case.csnet (etc.)
6504 Chestnut Road Independence, Ohio 44131 +1 216 524 1416 -- CIS 74106,1032
-=> Does the Doctor make house calls? <=-