Format de la base de donnée

Pas mal de gens semblent s'intéresser à cette base de donnée, donc je vais détailler.

La base de donnée utilise deux concepts intéressants. D'une part, elle est binaire, et d'autre part, elle est lue grâce à des fichiers mappés.

L'immense avantage des fichiers mappés est que l'OS se charge de toutes les entrées sorties. Pour un solveur de type SAT, qui doit construire le problème, tous les paquets doivent être lus et mis dans le problème. On a donc beaucoup d'IO sur le disque.

Ici, mon système n'utilise que les dépendances d'un paquet (avec les conflits, les dépendances inverses, etc). Si le paquet A dépend de B et est en conflit avec C, je ne vois absolument pas pourquoi je dois mettre D, E et F dans le problème.

Pour illustrer par un cas réel, imaginez que vous souhaitiez installer OpenOffice.org. Vous avez vraiment besoin que votre solveur perde son temps à tester s'il doit installer Wormux ?

Donc, c'est un fichier mappé en mémoire, et ça accélère/simplifie grandement les choses. Il n'y à qu'à voir comment on récupère un paquet quand on connait son ID :

_Package *PackageSystemPrivate::package(int index)
{
// Trouver l'adresse du paquet
if (index >= *(int *)m_packages)
{
return 0;
}

// Début de la liste des paquets
uchar *pkg = m_packages;
pkg += 4;

// Paquet au bon index
pkg += (index * sizeof(_Package));

return (_Package *)pkg;
}

Seulement des pointeurs. Et ce qui est vraiment excellent, c'est que GCC sait très bien compiler et optimiser du code de ce genre. Ceci est compilé en ce code assembleur, uniquement :

movq 40(%rdi), %rdx
xorl %eax, %eax
cmpl %esi, (%rdx)
jle .L3
movslq %esi,%rax
leaq (%rax,%rax,4), %rax
leaq 4(%rdx,%rax,4), %rax
.L3:
rep
ret

9 instructions, en O(1), pour récupérer un paquet dans la BDD. Qui dit mieux ?

Même chose quand on a une chaîne :

const char *PackageSystemPrivate::string(uchar *map, int index)
{
// Si map == 0, on prend m_strings (c'est qu'on a été appelé d'ailleurs)
if (map == 0)
{
map = m_strings;
}

// Vérifier l'index
if (index >= *(int *)map)
{
return 0;
}

// Trouver la chaîne à l'index spécifié
uchar *str = map;
int count = *(int *)map; // count

str += 4; // Sauter count

// Index
str += (index * sizeof(_String));

// En fonction du pointeur, trouver l'adresse de la chaîne
const char *ptr = (const char *)map;
ptr += ((_String *)(str))->ptr; // Ajouter l'adresse du pointeur
ptr += 4; // Sauter le count
ptr += (count * sizeof(_String)); // Sauter la table des chaînes

return ptr;
}

Egalement en temps constant, très rapide. Ca s'utilise comme ça :

QString PackageSystemPrivate::packageName(int index)
{
_Package *pkg = package(index);

if (pkg == 0) return QString();

return QString(string(m_strings, pkg->name));
}

Pour la dépendance de Qt, c'est simplement qu'il est totalement idiot de ne pas l'utiliser alors qu'il marche si bien. Libpackage et Setup ne dépendent que de QtCore, mais bien. Par exemple, mon code utilise beaucoup de QHash, QList, QVector, QFile, QString, etc. Qt est vraiment très confortable, et permet de raccourcir le code.

Je n'ai pas de temps à perdre à coder mon propre Hash, ou ma propre liste. C'est une source de bugs potentielle. Je préfère me concentrer sur l'algo, pas sur le codage en dessous. Pour ça, Qt est excellent : il propose tous les trucs dont on a besoin, mais qui prennent pas mal de temps à coder. Utiliser QString::split() ou QString::section est un bonheur quand on a des trucs comme splitter "machin>=chose" pour récupérer le nom et la version.