Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!panews.awdpa.ibm.com!rchland.ibm.com!seurer+
From: seurer+@rchland.ibm.com (Bill Seurer)
Newsgroups: comp.lang.modula2
Subject: Re: POINTER/LINKED LIST HELP?
Message-ID: <obxukFQ91EAf1E_24T@rchland.ibm.com>
Date: 1 Apr 91 21:54:25 GMT
References: <1991Mar30.151406.29367@kuhub.cc.ukans.edu> <5164@uniol.UUCP>,
	<1991Apr1.123810.29390@kuhub.cc.ukans.edu>
Organization: IBM Rochester, Mn
Lines: 219
In-Reply-To: <1991Apr1.123810.29390@kuhub.cc.ukans.edu>

Here it is.  It's not pretty, it throws type checking to the wind
(mostly), but it works (as far as I tested it)!

Some notes:
1) This will allow you to make lists of anything.  The lists need not be
all the same type.  This is EXTREMELY dangerous.
2) I didn't test it much.  I suspect that List.Delete is not fully
functional.  Whadaya expect for less than half an hour?
3) Some compilers might not like some of the typecasting that was done.

Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Output of the test program:

2147483647
0
42
-906
906
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
DEFINITION MODULE List;
(* "Generic" lists module *)

FROM SYSTEM IMPORT ADDRESS, BYTE;

TYPE
  T (*Opaque type*);
  Element (*Opaque type*);

CONST
  NilList = T(NIL);
  NilElement = Element(NIL);

PROCEDURE NewList(): T;
(* Create a new list *)

PROCEDURE Insert (list: T;
                  after: Element;
                  actualElement: ARRAY OF BYTE);
(* Add a new element to a list *)

PROCEDURE Delete (list: T;
                  element: Element);
(* Delete an element from a list *)

PROCEDURE First(list: T): Element;
(* Get the first element of a list *)

PROCEDURE Next(previous: Element): Element;
(* Get the next element of a list *)

PROCEDURE Data(of: Element): ADDRESS;
(* Get the (address of the) data of an element *)

END List.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
IMPLEMENTATION MODULE List;
(* "Generic" lists module *)

FROM SYSTEM IMPORT ADDRESS, BYTE, ADR;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

TYPE    
  T = POINTER TO ListRcd;
  Element = POINTER TO ElementRcd;

  ListRcd = RECORD
    first: Element;
  END (*ListRcd*);

  ElementRcd = RECORD
    next: Element;
    data: ADDRESS;
    dataSize: CARDINAL;
  END (*ElementRcd*);

  BytePtr = POINTER TO ARRAY[0..32767] OF BYTE;

PROCEDURE CopyBytes(from, to: BytePtr;
                    nbr: CARDINAL);
(* Ugly internal procedure to copy bytes from one address to another *)
VAR
  cnt: CARDINAL;
BEGIN
  FOR cnt := 0 TO nbr DO
    to^[cnt] := from^[cnt];
  END (*For*);
END CopyBytes;

PROCEDURE NewList(): T;
(* Create a new list *)
VAR
  newList: T;
BEGIN
  NEW(newList);
  newList^.first := NIL;
  RETURN newList;
END NewList;


PROCEDURE Insert (list: T;
                  after: Element;
                  element: ARRAY OF BYTE);
(* Add a new element to a list *)
VAR
  new: Element;
BEGIN
  NEW(new);
  new^.dataSize := HIGH(element)+1;
  ALLOCATE(new^.data, new^.dataSize);
  IF after = NIL THEN
    new^.next := list^.first;
    list^.first := new;
  ELSE
    new^.next := after^.next;
    after^.next := new;
  END (*Else*);
  CopyBytes(ADR(element), new^.data, new^.dataSize);
END Insert;

PROCEDURE Delete (list: T;
                  element: Element);
(* Delete an element from a list *)
VAR
  previous, current: Element;
BEGIN
  previous := list^.first;
  current := previous;
  LOOP
    IF current = NIL THEN
      EXIT (*Loop*);
    ELSIF current = element THEN
      IF current = list^.first THEN
        list^.first := list^.first^.next;
      ELSE
        previous^.next := current^.next;
      END (*Else*);
      DEALLOCATE(current^.data, current^.dataSize);
      DISPOSE(current);
      EXIT (*Loop*);
    ELSE
      previous := current;
      current := current^.next;
    END (*Else*);
  END (*While*);
  element := NIL;
END Delete;

PROCEDURE First(list: T): Element;
(* Get the first element of a list *)
BEGIN
  RETURN list^.first;
END First;

PROCEDURE Next(previous: Element): Element;
(* Get the next element of a list *)
BEGIN
  RETURN previous^.next;
END Next;

PROCEDURE Data(of: Element): ADDRESS;
(* Get the (address of the) data of an element *)
BEGIN
  RETURN of^.data;
END Data;

END List.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
MODULE tryList;

IMPORT List, InOut;

TYPE
  IntPtr = POINTER TO INTEGER;

VAR
  somelist: List.T;
  el: List.Element;
  int: IntPtr;

BEGIN
  somelist := List.NewList();
  List.Insert(somelist, List.NilElement, INTEGER(906));
  (* typecast to prevent SHORTINTs from being used *)
  List.Insert(somelist, List.NilElement, INTEGER(-906));
  List.Insert(somelist, List.NilElement, INTEGER(42));
  List.Insert(somelist, List.NilElement, INTEGER(0));
  List.Insert(somelist, List.NilElement, MAX(INTEGER));

  el := List.First(somelist);
  WHILE el <> List.NilElement DO
    int := IntPtr(List.Data(el));
    InOut.WriteInt(int^, 1);
    InOut.WriteLn;
    el := List.Next(el);
  END (*While*);

  LOOP
    el := List.First(somelist);
    IF el = List.NilElement THEN
      EXIT(*Loop*);
    END (*If*);
    List.Delete(somelist, el);
  END (*Loop*);
END tryList.

- Bill Seurer      IBM: seurer@rchland  Prodigy: CNSX71A
  Rochester, MN    Internet: seurer@rchland.vnet.ibm.com

This material contains code that is supplied for illustrative purposes
only.  IBM has not tested this code via its ordinary process and it is
not supported.  IBM provides the code AS IS and specifically DISCLAIMS
ALL WARRANTIES, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR PARTICULAR PURPOSE.  In no event will
IBM be responsible for any special, incidental or consequential damages,
even if advised of the possibility thereof.

If you think *I* wrote that...