-# Order-preserving minimal perfect hash function generator
-
-Build order-preserving minimal perfect hash functions.
-
-[](https://codecov.io/gh/julian-klode/triehash)
-[](https://travis-ci.org/julian-klode/triehash)
-
-## Performance
-
-Performance was evaluated against other hash functions. As an input set, the
-fields of Debian Packages and Sources files was used, and each hash function
-was run 1,000,000 times for each word. The byte count of the words were then
-summed up and divided by the total number of nanoseconds each function ran, so
-all speeds below are given in bytes per nanosecond, AKA gigabyte per second.
-
-arch/function|jak-x230 (amd64)|backup (amd64)|asachi.d.o (arm64)|asachi.d.o (armel)|asachi.d.o (armhf)|plummer.d.o (ppc64el)|eller.d.o (mipsel)
--------------|----------------|--------------|------------------|------------------|------------------|---------------------|------------------
-Trie | 2.4 | 1.9 | 1.2 | 0.9 | 0.8 | 2.0 | 0.2
-Trie (*) | 2.2 | 1.7 | 0.8 | 0.7 | 0.7 | 1.8 | 0.2
-re2c | 1.7 | 1.3 | 0.9 | 0.9 | 0.7 | 1.6 | 0.2
-re2c (*) | 1.2 | 0.9 | 0.6 | 0.6 | 0.5 | 1.1 | 0.1
-gperf (*) | 0.7 | 0.5 | 0.2 | 0.2 | 0.2 | 0.5 | 0.1
-gperf | 1.3 | 0.9 | 0.3 | 0.3 | 0.2 | 0.4 | 0.1
-djb (*) | 0.7 | 0.5 | 0.3 | 0.3 | 0.3 | 0.5 | 0.1
-djb (**) | 1.0 | 0.7 | 0.4 | 0.5 | 0.5 | 0.6 | 0.2
-djb | 0.9 | 0.7 | 0.5 | 0.5 | 0.5 | 0.7 | 0.2
-apt (*) | 1.2 | 0.9 | 0.7 | 0.7 | 0.7 | 1.1 | 0.2
-apt (**) | 2.3 | 1.7 | 0.7 | 0.9 | 0.8 | 1.9 | 0.2
-
-And transposed:
-
-function/arch |Trie |Trie (*) |re2c |re2c (*) |gperf (*)|gperf |djb (*) |djb (**) |djb |apt (*) |apt (**)
----------------------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------
-jak-x230 (amd64) | 2.4| 2.2| 1.7| 1.2| 0.7| 1.3| 0.7| 1.0| 0.9| 1.2| 2.3
-backup (amd64) | 1.9| 1.7| 1.3| 0.9| 0.5| 0.9| 0.5| 0.7| 0.7| 0.9| 1.7
-asachi.d.o (arm64) | 1.2| 0.8| 0.9| 0.6| 0.2| 0.3| 0.3| 0.4| 0.5| 0.7| 0.7
-asachi.d.o (armel) | 0.9| 0.7| 0.9| 0.6| 0.2| 0.3| 0.3| 0.5| 0.5| 0.7| 0.9
-asachi.d.o (armhf) | 0.8| 0.7| 0.7| 0.5| 0.2| 0.2| 0.3| 0.5| 0.5| 0.7| 0.8
-plummer.d.o (ppc64el)| 2.0| 1.8| 1.6| 1.1| 0.5| 0.4| 0.5| 0.6| 0.7| 1.1| 1.9
-eller.d.o (mipsel) | 0.2| 0.2| 0.2| 0.1| 0.1| 0.1| 0.1| 0.2| 0.2| 0.2| 0.2
-
-
-Legend:
-
-* The (*) variants are case-insensitive, (**) are more optimised versions
- of the (*) versions.
-* DJB (*) is a DJB Hash with naive lowercase conversion, DJB (**) just ORs one
- bit into each value to get alphabetical characters to be lowercase
-* APT (*) is the AlphaHash function from APT which hashes the last 8 bytes in a
- word in a case-insensitive manner. APT (**) is the same function unrolled.
-* All hosts except the x230 are Debian porterboxes. The x230 has a Core i5-3320M,
- barriere has an Opteron 23xx.
-
-Notes:
-
-* The overhead is larger than needed on some platforms due to gcc inserting
- unneeded zero extend instructions, see:
- https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77729
+APT
+===
+
+apt is the main commandline package manager for Debian and its derivatives.
+It provides commandline tools for searching and managing as well as querying
+information about packages as well as low-level access to all features
+provided by the libapt-pkg and libapt-inst libraries which higher-level
+package managers can depend upon.
+
+Included tools are:
+
+* apt-get for retrieval of packages and information about them
+ from authenticated sources and for installation, upgrade and
+ removal of packages together with their dependencies
+* apt-cache for querying available information about installed
+ as well as installable packages
+* apt-cdrom to use removable media as a source for packages
+* apt-config as an interface to the configuration settings
+* apt-key as an interface to manage authentication keys
+* apt-extracttemplates to be used by debconf to prompt for configuration
+ questions before installation.
+* apt-ftparchive creates Packages and other index files
+ needed to publish an archive of debian packages
+* apt-sortpkgs is a Packages/Sources file normalizer.
+
+The libraries libapt-pkg and libapt-inst are also maintained as part of this project,
+alongside various additional binaries like the acquire-methods used by them.
+Bindings for Python ([python-apt](https://tracker.debian.org/pkg/python-apt)) and
+Perl ([libapt-pkg-perl](https://tracker.debian.org/pkg/libapt-pkg-perl)) are available as separated projects.
+
+Discussion happens mostly on [the mailinglist](mailto:deity@lists.debian.org) ([archive](https://lists.debian.org/deity/)) and on [IRC](irc://irc.oftc.net/debian-apt).
+Our bugtracker as well as a general overview can be found at the [Debian Tracker page](https://tracker.debian.org/pkg/apt).
+
+
+Contributing
+------------
+APT is maintained in git, the official repository being located at
+`git://anonscm.debian.org/apt/apt.git` ([webgit](https://anonscm.debian.org/git/apt/apt.git)),
+but also available at other locations like [GitHub](https://github.com/Debian/apt).
+
+The default branch is `master`, other branches targeted at different
+derivatives and releases being used as needed. Various topic branches in
+different stages of completion might be branched of from those, which you
+are encouraged to do as well.
+
+### Coding
+
+APT uses cmake. To start building, you need to run
+
+ cmake <path to source directory>
+
+from a build directory. For example, if you want to build in the source tree,
+run:
+
+ cmake .
+
+Then you can use make as you normally would (pass -j <count> to perform <count>
+jobs in parallel).
+
+You can also use the Ninja generator of cmake, to do that pass
+ -G Ninja
+to the cmake invocation, and then use ninja instead of make.
+
+The source code uses in most parts a relatively uncommon indent convention,
+namely 3 spaces with 8 space tab (see [doc/style.txt](https://anonscm.debian.org/git/apt/apt.git/tree/doc/style.txt) for more on this).
+Adhering to it avoids unnecessary code-churn destroying history (aka: `git blame`)
+and you are therefore encouraged to write patches in this style.
+Your editor can surely help you with this, for vim the settings would be
+`setlocal shiftwidth=3 noexpandtab tabstop=8`
+(the later two are the default configuration and could therefore be omitted).
+
+### Translations
+
+While we welcome contributions here, we highly encourage you to contact the [Debian Internationalization (i18n) team](https://wiki.debian.org/Teams/I18n).
+Various language teams have formed which can help you creating, maintaining
+and improving a translation, while we could only do a basic syntax check of the
+file format…
+
+Further more, Translating APT is split into two independent parts:
+The program translation, meaning the messages printed by the tools,
+as well as the manpages and other documentation shipped with APT.
+
+### Bug triage
+
+Software tools like APT which are used by thousands of users every
+day have a steady flow of incoming bugreports. Not all of them are really
+bugs in APT: It can be packaging bugs like failing maintainer scripts a
+user reports against apt, because apt was the command he executed leading
+to this failure or various wishlist items for new features. Given enough time
+also the occasional duplicate enters the system.
+Our bugtracker is therefore full with open bugreports which are waiting for you! ;)
+
+Testing
+-------
+
+### Manual execution
+
+When you make changes and want to run them manually, you can just do so. CMake
+automatically inserts an rpath so the binaries find the correct libraries.
+
+Note that you have to invoke CMake with the right install prefix set (e.g.
+`-DCMAKE_INSTALL_PREFIX=/usr`) to have your build find and use the right files
+by default or alternatively set the locations at runtime via an `APT_CONFIG`
+configuration file.
+
+### Integration tests
+
+There is an extensive integration testsuite available which can be run via:
+
+ $ ./test/integration/run-tests
+
+Each test can also be run individually as well. The tests are very noisy by
+default, especially so while running all of them it might be beneficial to
+enabling quiet (`-q`) or very quiet (`-qq`) mode. The tests can also be run in
+parallel via `-j X` where `X` is the number of jobs to run.
+
+While these tests are not executed at package build-time as they require
+additional dependencies, the repository contains the configuration needed to
+run them on [Travis CI](https://travis-ci.org/) and
+[Shippable](https://shippable.com/) as well as via autopkgtests e.g. on
+[Debian Continuous Integration](https://ci.debian.net/packages/a/apt/).
+
+A testcase here is a shellscript embedded in a framework creating an environment in which
+apt tools can be used naturally without root-rights to test every aspect of its behavior
+itself as well as in conjunction with dpkg and other tools while working with packages.
+
+
+### Unit tests
+
+These tests are gtest-dev based, executed by ctest, reside in `./test/libapt`
+and can be run with `make test`. They are executed at package build-time, but
+not by `make`. CTest by default does not show the output of tests, even if they
+failed, so to see more details you can also run them with `ctest --verbose`.
+
+Debugging
+---------
+
+APT does many things, so there is no central debug mode which could be
+activated. It uses instead various config-options to activate debug output
+in certain areas. The following describes some common scenarios and generally
+useful options, but is in no way exhaustive.
+
+Note that you should *NEVER* use these settings as root to avoid accidents.
+Simulation mode (`-s`) is usually sufficient to help you run apt as a non-root user.
+
+### Using different state files
+
+If a dependency solver bug is reported, but can't be reproduced by the
+triager easily, it is beneficial to ask the reporter for the
+`/var/lib/dpkg/status` file, which includes the packages installed on the
+system and in which version. Such a file can then be used via the option
+`dir::state::status`. Beware of different architecture settings!
+Bugreports usually include this information in the template. Assuming you
+already have the `Packages` files for the architecture (see `sources.list`
+manpage for the `arch=` option) you can change to a different architecture
+with a config file like:
+
+ APT::Architecture "arch1";
+ #clear APT::Architectures;
+ APT:: Architectures { "arch1"; "arch2"; }
+
+If a certain mirror state is needed, see if you can reproduce it with [snapshot.debian.org](http://snapshot.debian.org/).
+Your sources.list file (`dir::etc::sourcelist`) has to be correctly mention the repository,
+but if it does, you can use different downloaded archive state files via `dir::state::lists`.
+
+In case manually vs. automatically installed matters, you can ask the reporter for
+the `/var/lib/apt/extended_states` file and use it with `dir::state::extended_states`.
+
+### Dependency resolution
+
+APT works in its internal resolver in two stages: First all packages are visited
+and marked for installation, keep back or removal. Option `Debug::pkgDepCache::Marker`
+shows this. This also decides which packages are to be installed to satisfy dependencies,
+which can be seen by `Debug::pkgDepCache::AutoInstall`. After this is done, we might
+be in a situation in which two packages want to be installed, but only on of them can be.
+It is the job of the pkgProblemResolver to decide which of two packages 'wins' and can
+therefore decide what has to happen. You can see the contenders as well as their fight and
+the resulting resolution with `Debug::pkgProblemResolver`.
+
+### Downloading files
+
+Various binaries (called 'methods') are tasked with downloading files. The Acquire system
+talks to them via simple text protocol. Depending on which side you want to see, either
+`Debug::pkgAcquire::Worker` or `Debug::Acquire::http` (or similar) will show the messages.
+
+The integration tests use a simple self-built webserver which also logs. If you find that
+the http(s) methods do not behave like they should be try to implement this behavior in the
+webserver for simpler and more controlled testing.
+
+### Installation order
+
+Dependencies are solved, packages downloaded: Everything read for the installation!
+The last step in the chain is often forgotten, but still very important:
+Packages have to be installed in a particular order so that their dependencies are
+satisfied, but at the same time you don't want to install very important and optional
+packages at the same time if possible, so that a broken optional package does not
+block the correct installation of very important packages. Which option to use depends on
+if you are interested in the topology sorting (`Debug::pkgOrderList`), the dependency-aware
+cycle and unconfigured prevention (`Debug::pkgPackageManager`) or the actual calls
+to dpkg (`Debug::pkgDpkgPm`).
projects / apt.git / blobdiff