From: "Jesper Louis Andersen" <none@jlouis--mongers.org.lh.bsd-dk.dk> Date: Sat, 19 Mar 2005 08:53:14 +0100 To: devel@bsd-dk.dk Subject: Re: binære træer på FreeBSD
Quoting Claus Guttesen (cguttesen@yahoo.dk):
> Hej.
>
> Fandt et eksempel på brug af rb-træer på
> http://osmirrors.cerias.purdue.edu/pub/OpenBSD/src/usr.bin/du/du.c.
>
> Jeg har ud fra programmet lavet dette simple program:
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <sys/tree.h>
>
> struct blb_entry_stat {
> int active_sessions;
> int expired_sessions;
> };
>
Du mangler en del ting:
sys/tree.h kraever at du definerer en RB_ENTRY i din blb_entry. Denne
indeholder pointere til left og right child, hvis jeg husker rigtigt. Maaske
ogsaa en parent pointer i RB_TREE tilfaeldet (Der er nogle optimeringer
mulige hvis man har parent pointers). Dernaest mangler du at konstruere
prototyper for dit RB_TREE med RB_PROTOTYPE. Du mangler ogsaa at konstruere
selve funktionerne, der laver det haarde arbejde med RB_GENERATE. Du mangler
ogsaa at angive en sammenligningsfunktion for blb_entry.
Og hvorfor saa det? Jo, RB_* er makroer af den slemme slags, fordi C som
sprog ikke har nogensomhelst muligheder for at lave abstraktion. RB_ENTRY
ekspanderer som foer sagt til en struktur der kan benyttes til at linke
blb_entry's sammen med. RB_PROTOTYPE ekspanderer til prototypefunktionerne
for et RB_TREE og RB_GENERATE ekspanderer til egentlige funktioner. Det er
en af disse funktioner du mangler naar du forsoeger at oversaette.
Bemaerk at dit eksempel har foelgende du har overset:
* struct links_entry har en RB_ENTRY makro.
* links_cmp er en sammenligningsfunktion for struct links_entry *
* der kaldes RB_GENERATE(ltree, links_entry, entry, links_cmp);
Saa det er tilbage til arbejdsbordet/editoren med kodeeksemplet indtil du
lige har slaaet lidt mere paa det med din forhammer ;)
-- jlouis
This archive was generated by hypermail 2b30 : Wed 15 Nov 2006 - 18:25:13 CET