<simpara
  >&config.OS.NAME; uses <application>dpkg</application> for package
  management. It maintains a set of loosely indexed text files in
  <filename>/var/lib/dpkg/</filename>. The whole thing is not well
  suited for our kind of query.
</simpara>

<formalpara>
  <title>Source: &config.PRE;/packages/deb/du.sh</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.PRE;/packages/deb/du.sh"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
<formalpara>
  <title>Output: &config.OUT;/packages/du</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.OUT;/packages/du"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>

<simpara
  >The first half of a simple example does a linear search trough
  <filename>/var/lib/dpkg/info/*.list</filename>:
</simpara>

<formalpara>
  <title>Source: &config.PRE;/packages/deb/simple.sh</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.PRE;/packages/deb/simple.sh"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
<formalpara>
  <title>Output: &config.OUT;/packages/simple</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.OUT;/packages/simple"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>

<simpara
  >To create the table shown in the
  <link linkend="index">abstract</link> a second query is required.
  This one does a linear search through one huge text file,
  <filename>/var/lib/dpkg/available</filename>.
</simpara>

<formalpara>
  <title>Source: &config.PRE;/packages/deb/avail.sh</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.PRE;/packages/deb/avail.sh"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
<formalpara>
  <title>Output: &config.OUT;/packages/deb/avail</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.OUT;/packages/deb/avail"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>

<simpara
  >But this is not the end of the story.
  A particularly absurd example is <application>perl</application>.
  A chain of symbolic links is not a problem in itself.
  But what shall we do if neither the links nor the final target
  are registered?
</simpara>

<formalpara>
  <title>Source: &config.PRE;/packages/deb/perl.sh</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.PRE;/packages/deb/perl.sh"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
<formalpara>
  <title>Output: &config.OUT;/packages/deb/perl</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.OUT;/packages/deb/perl"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>

<simpara>
  The solution to the puzzle is a hard link.
  <citerefentry>
    <refentrytitle>stat</refentrytitle>
    <manvolnum>2</manvolnum>
  </citerefentry> tells how many names refer to the same file.
  But to actually find these names the complete file system has
  to be searched, similar to <command>find -xdev -inum</command>.
  <footnote><simpara
    >Finding the mount point of the file system holding an
    arbitrary directory is tricky in itself. 
    Field <varname>st_dev</varname> of the <type>struct stat</type>
    returned by
    <citerefentry>
      <refentrytitle>stat</refentrytitle>
      <manvolnum>2</manvolnum>
    </citerefentry> unambiguously identifies a mounted file system.
    Repeatedly changing into the parent directory until its
    value of <varname>st_dev</varname> is different from that of
    the starting point should find the mount point.
  </simpara></footnote>
  In practice one can assume that this kind of hard link is
  located in the same directory. Not a guaranteed or fast solution,
  but manageable.
</simpara>

<formalpara>
  <title>Source: &config.PRE;/packages/deb/hard.sh</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.PRE;/packages/deb/hard.sh"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
<formalpara>
  <title>Output: &config.OUT;/packages/deb/hard</title>
  <para>
    <programlisting><inlinemediaobject><imageobject><imagedata
      format="linespecific"
      fileref="../../&config.OUT;/packages/deb/hard"
    /></imageobject></inlinemediaobject></programlisting>
  </para>
</formalpara>
