Writing upgradable data structures

[David Collier-Brown]

In article <2079 at bsu-cs.UUCP> dhesi at bsu-cs.UUCP (Rahul Dhesi) writes:
>Sooner than you can say "UNIX is a Trademark of ...", 47000 AD will be
>here.  The greatest mistake a designer can make is to assume that a
>certain date and time will never come.  Such short-sightedness has
>caused problems over and over again, yet we see it again and again.
>
>The right way to do it is as follows:
[ example of linked list elided]

  The idea of a infinitely-extendable date is one solution, and is
particularly applicable to things like dates, which should be
monotonically increasing. (But a library system would *freak* at
the late starting date).

  A more general solution predates Unix, and has therefore been
forgotten by many members of the Unix community: version-numbered
structures.

  Let us consider a date structure as follows:
	struct date_t {
		int	v;
		unsigned d;
	} foo = { 0, 32766};
  This describes a range of dates and times, encoded into a single
unsigned value (which should be insufficient for anything but the
execution of a single filter). Let us assume that this is the date
format of our machine.
  As soon as 47000 AD comes around (or whatever date breaks the
date/time system), the library containing the date routines is
replaced [note 1] with one which checks the version number, "v".  If
it is non-zero, the structure is trashed [note 2] and replaced by
one with the following form:
	struct date_t {
		int	v;
		unsigned long d;
	} foo = { 1, 32766};
  The new code changes the structure to type "1", and then
continues. This can happen over and over again, and allow the data
structure to grow or shrink, as necessary.

  The disadvantages are as follows:

	1) You have to make version-number checks in your library
	   routines, and fault to updating code if they fail
	2) You can't have "structure constants", because they would
	   be the wrong size (you have to stick with c initializers)
	3) You can't take sizeof(struct time_t) unless you build the
	   version stuff into the compiler (vstruct time_t, for
	   example). The size changes on you, so you have to keep a
	   dope-vector.
	4) You CAN'T use a severely type-checked language like
	   Pascal because it knows that you don't want variable
	   sized structures. (Its hard in Ada[note 3] too. Source:
	   Paul Stachour).

  This technique is used in the ARPAnet and on Multics.  Ritchie and
Thompson didn't include it in Unix and C, probably for the good
reason that it approached overkill. (:-))
  Some days, though, you have to kill something repeatedly.  Dates
are a good example.

--dave c-b
[note 1] Dynamic linking is needed: I assume we'll have it by then:
	I had it in the late '70s.
[note 2] Probably by being realloc'd. Malloc usually has a
	dope-vector available for this.
[note 3] Ada is a trademark of the Gods of War (Ada Joint Program
	Office).
-- 
 David Collier-Brown.                 {mnetor yunexus utgpu}!geac!daveb
 Geac Computers International Inc.,   |  Computer Science loses its
 350 Steelcase Road,Markham, Ontario, |  memory (if not its mind) 
 CANADA, L3R 1B3 (416) 475-0525 x3279 |  every 6 months.