-.\" See LICENSE.BSD for license
-.TH LIBSOLV 7 "May 2011"
-.SH NAME
+'\" t
+.\" Title: Libsolv
+.\" Author: [see the "Author" section]
+.\" Generator: DocBook XSL Stylesheets v1.78.0 <http://docbook.sf.net/>
+.\" Date: 09/20/2013
+.\" Manual: LIBSOLV
+.\" Source: libsolv
+.\" Language: English
+.\"
+.TH "LIBSOLV" "3" "09/20/2013" "libsolv" "LIBSOLV"
+.\" -----------------------------------------------------------------
+.\" * Define some portability stuff
+.\" -----------------------------------------------------------------
+.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.\" http://bugs.debian.org/507673
+.\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html
+.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.ie \n(.g .ds Aq \(aq
+.el .ds Aq '
+.\" -----------------------------------------------------------------
+.\" * set default formatting
+.\" -----------------------------------------------------------------
+.\" disable hyphenation
+.nh
+.\" disable justification (adjust text to left margin only)
+.ad l
+.\" -----------------------------------------------------------------
+.\" * MAIN CONTENT STARTS HERE *
+.\" -----------------------------------------------------------------
+.SH "NAME"
libsolv \- package dependency solver library using a satisfiability algorithm
-
-.SH HISTORY
-This project was started in May 2007 when the zypp folks decided to switch
-to a database to speed up installation. As I'm not a big fan of databases,
-I wondered if there would be really some merit of using one for solving,
-as package dependencies of all packages have to be read in anyway.
+.SH "DOCUMENTATION"
+.sp
+The libsolv documentation is split into multiple parts:
.PP
-Back in 2002 I researched that using a dictionary approach for storing
-dependencies can reduce the packages file to 1/3 of its size. Extending
-this idea a bit more, I decided to store all strings and relations
-as unique 32bit numbers. This has three big advantages:
-.IP - 2
-because of the unification, testing if two strings are equal is the same as
-testing the equality of two numbers, thus very fast
-.IP - 2
-much space is saved, as numbers don't take so much space as strings
-.IP - 2
-the internal memory representation doesn't take more space on a
-64bit system where a pointer is twice the size of a 32bit number
+\fBlibsolv\-history\fR
+.RS 4
+how the libsolv library came into existence
+.RE
.PP
-Thus the solv format was created, which stores a repository as a string
-dictionary, a relation dictionary and then all packages dependencies.
-Tests showed that reading and merging multiple solv repositories takes
-just some milliseconds.
-
-.SS
-Early solver experiments
-
-Having a new repository format was one big step, but the other area
-where libzypp needed improvement was the solver. Libzypp's solver was
-a port from the red carpet solver, which was written to update packages
-in an already installed system. Using it for the complete installation
-progress brought it to its limits. Also, the added extensions like
-support for weak dependencies and patches made it fragile and
-unpredictable.
+\fBlibsolv\-constantids\fR
+.RS 4
+fixed Ids for often used strings
+.RE
.PP
-As I wasn't very pleased with the way the solver worked, I looked at
-other solver algorithms. I checked smart, yum and apt, but could not
-find a convincing algorithm. My own experiments also were not very
-convincing, they worked fine for some problems but failed miserably
-for other corner cases.
-
-.SS
-Using SAT for solving
-
-SUSE's hack week at the end of June 2007 turned out to be a turning point
-for the solver. Googling for solver algorithms I stumbled over some note
-saying that some people are trying to use SAT algorithms to improve
-solving on debian. Looking at the SAT entry in wikipedia, it was easy
-to see that this indeed was the missing piece: sat algorithms are well
-researched and there are quite some open source implementations.
-I decided to look at the minisat code, as it is one of the fastest
-solvers while consisting of too many lines of code.
-Of course, directly using minisat would not work, as a package solver
-doesn't need to find just one correct solution, but it also has to
-optimize some metrics, i.e. keep as many packages installed as possible.
-Thus, I needed to write my own solver incorporation the ideas and
-algorithms used in minisat. This wasn't very hard, and at the end of
-the hack week the solver calculated the first right solutions.
-
-.SS
-Selling it to libzypp
-
-With those encouraging results I went to Klaus Kaempf, the system
-management architect here at SUSE. We spoke about how to convince the
-team to make libzypp switch to the new solver. Fortunately libzypp comes
-with a plethora of solver test cases, so we decided to make the solver pass
-most of the test cases first. Klaus wrote a "deptestomatic" implementation
-to check the test cases. Together with Stephan Kulow, responsible for the
-openSUSE distribution, we tweaked and extended the solver until most of
-the test cases looked good.
-Duncan Mac-Vicar Prett, the team lead of the YaST team, also joined
-development by creating ruby bindings for the solver. Later, Klaus
-improved the bindings and ported them to some other languages.
-
-.SS
-The attribute store
-
-The progress with the repository format and the solver attracted another
-hacker to the project: Michael Matz from the compiler team. He started
-with improving the repository parsers so that patches and content files
-also generate solvables. After that, he concentrated on storing all
-of the other metadata of the repositories that are not used for solving,
-like the package summaries and descriptions. In the end of October, a first
-version of this "attribute store" was checked in. Its design goals were:
-.IP - 2
-space efficient storage of attributes
-.IP - 2
-paging/on demand loading of data
-.IP - 2
-page compression
+\fBlibsolv\-bindings\fR
+.RS 4
+access libsolv from perl/python/ruby
+.RE
.PP
-The first version of the attribute store used a different format for
-storing information, we later merged this format with the solv file
-format.
-
-.SS
-libzypp integration
-
-Integrating the sat-solver into libzypp also started in October 2007 by
-Stefan Schubert and Michael Andres from the YaST team. The first
-versions supported both the old solver and the new one by using the
-old repository read functions and converting the old package data
-in-memory into a sat solver pool. Solvers could be switched with
-the environment variable ZYPP_SAT_SOLVER. The final decision to
-move to the new solver was made in January of 2008, first just by
-making the new solver the default one, later by completely throwing out
-the old solver code. This had the advantage that the internal solvable
-storage could also be done by using the solver pool, something Michael
-Matz already played with in a proof of concept implementation showing
-some drastic speed gains. The last traces of the old database code
-were removed in February.
-
-.SH AUTHOR
-Michael Schroeder <mls@suse.de>
+\fBlibsolv\-pool\fR
+.RS 4
+libsolv\(cqs pool object
+.RE
+.SH "POINTER VALIDITY"
+.sp
+Note that all pointers to objects that have an Id have only a limited validity period, with the exception of Repo pointers\&. There are only guaranteed to be valid until a new object of that type is added or an object of that type is removed\&. Thus pointers to Solvable objects are only valid until another solvable is created, because adding a Solvable may relocate the Pool\(cqs Solvable array\&. This is also true for Pool strings, you should use solv_strdup() to create a copy of the string if you want to use it at some later time\&. You should use the Ids in the code and not the pointers, except for short times where you know that the pointer is safe\&.
+.sp
+Note also that the data lookup functions or the dataiterator also return values with limited lifetime, this is especially true for data stored in the paged data segment of solv files\&. This is normally data that consists of big strings like package descriptions or is not often needed like package checksums\&. Thus looking up a description of a solvable and then looking up the description of a different solvable or even the checksum of the same solvable may invalidate the first result\&. (The dataiterator supports a dataiterator_strdup() function to create a safe copy\&.)
+.sp
+The language bindings already deal with pointer validity, so you do not have to worry about this issue when using the bindings\&.
+.SH "AUTHOR"
+.sp
+Michael Schroeder <mls@suse\&.de>
projects / platform / upstream / libsolv.git / blobdiff