Xref: utzoo comp.lang.c:7330 comp.software-eng:212 Path: utzoo!yunexus!geac!daveb From: daveb@geac.UUCP (David Collier-Brown) Newsgroups: comp.lang.c,comp.software-eng Subject: Writing upgradable data structures Summary: was Re: Timekeeping in ANSI C Message-ID: <2307@geac.UUCP> Date: 21 Feb 88 15:45:44 GMT Article-I.D.: geac.2307 Posted: Sun Feb 21 10:45:44 1988 References: <461@auvax.UUCP> <28700025@ccvaxa> <7159@brl-smoke.ARPA> <2527@haddock.ISC.COM> <594@acornrc.UUCP> <2079@bsu-cs.UUCP> Reply-To: daveb@geac.UUCP (David Collier-Brown) Organization: The G. Yac History Department Lines: 73 In article <2079@bsu-cs.UUCP> dhesi@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.