From fe25182504257e2edc5135e8be196bb626bcc092 Mon Sep 17 00:00:00 2001 From: Michael Schroeder Date: Tue, 20 Dec 2011 14:23:59 +0100 Subject: [PATCH] fix memmove calls in repo_addid_dep, move hash version into separate function, fix SOLVABLE_FILEMARKER handling --- src/repo.c | 210 +++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 115 insertions(+), 95 deletions(-) diff --git a/src/repo.c b/src/repo.c index e85ea0a..c012572 100644 --- a/src/repo.c +++ b/src/repo.c @@ -302,6 +302,110 @@ repo_addid(Repo *repo, Offset olddeps, Id id) #define REPO_ADDID_DEP_HASHTHRES 64 #define REPO_ADDID_DEP_HASHMIN 128 +/* + * Optimization for packages with an excessive amount of provides/requires: + * if the number of deps exceed a threshold, we build a hash of the already + * seen ids. + */ +static Offset +repo_addid_dep_hash(Repo *repo, Offset olddeps, Id id, Id marker, int size) +{ + Id oid, *oidp; + int before; + Hashval h, hh; + Id hid; + + before = 0; + if (marker) + { + if (marker < 0) + { + marker = -marker; + before = 1; + } + if (marker == id) + marker = 0; + } + + /* maintain hash and lastmarkerpos */ + if (repo->lastidhash_idarraysize != repo->idarraysize || size * 2 > repo->lastidhash_mask || repo->lastmarker != marker) + { + if (size * 2 > repo->lastidhash_mask) + { + repo->lastidhash_mask = mkmask(size < REPO_ADDID_DEP_HASHMIN ? REPO_ADDID_DEP_HASHMIN : size); + repo->lastidhash = solv_realloc2(repo->lastidhash, repo->lastidhash_mask + 1, sizeof(Id)); + } + memset(repo->lastidhash, 0, (repo->lastidhash_mask + 1) * sizeof(Id)); + for (oidp = repo->idarraydata + olddeps; (oid = *oidp) != 0; oidp++) + { + h = oid & repo->lastidhash_mask; + hh = HASHCHAIN_START; + while (repo->lastidhash[h] != 0) + h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); + repo->lastidhash[h] = oid; + if (marker && oid == marker) + repo->lastmarkerpos = oidp - repo->idarraydata; + } + repo->lastmarker = marker; + repo->lastidhash_idarraysize = repo->idarraysize; + } + + /* check the hash! */ + h = id & repo->lastidhash_mask; + hh = HASHCHAIN_START; + while ((hid = repo->lastidhash[h]) != 0 && hid != id) + h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); + /* put new element in hash */ + if (!hid) + repo->lastidhash[h] = id; + if (marker && !before && !repo->lastmarkerpos) + { + /* we have to add the marker first */ + repo->lastmarkerpos = repo->idarraysize - 1; + olddeps = repo_addid(repo, olddeps, marker); + /* now put marker in hash */ + h = marker & repo->lastidhash_mask; + hh = HASHCHAIN_START; + while (repo->lastidhash[h] != 0) + h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); + repo->lastidhash[h] = marker; + repo->lastidhash_idarraysize = repo->idarraysize; + } + if (!hid) + { + if (marker && before && repo->lastmarkerpos) + { + /* need to add it before the marker */ + olddeps = repo_addid(repo, olddeps, id); /* dummy to make room */ + memmove(repo->idarraydata + repo->lastmarkerpos + 1, repo->idarraydata + repo->lastmarkerpos, (repo->idarraysize - repo->lastmarkerpos - 2) * sizeof(Id)); + repo->idarraydata[repo->lastmarkerpos++] = id; + } + else + { + /* just append it to the end */ + olddeps = repo_addid(repo, olddeps, id); + } + repo->lastidhash_idarraysize = repo->idarraysize; + return olddeps; + } + /* we already have it in the hash */ + if (!marker || before || marker == SOLVABLE_FILEMARKER) + return olddeps; + /* check if it is in the correct half */ + for (oidp = repo->idarraydata + repo->lastmarkerpos + 1; (oid = *oidp) != 0; oidp++) + if (oid == id) + return olddeps; + /* nope, copy it over */ + for (oidp = repo->idarraydata + olddeps; (oid = *oidp) != 0; oidp++) + if (oid == id) + break; + if (!oid) + return olddeps; /* should not happen */ + memmove(oidp, oidp + 1, (repo->idarraydata + repo->idarraysize - oidp - 2) * sizeof(Id)); + repo->idarraydata[repo->idarraysize - 2] = id; + return olddeps; +} + /* * add dependency (as Id) to repo, also unifies dependencies * olddeps = offset into idarraydata @@ -323,108 +427,24 @@ repo_addid_dep(Repo *repo, Offset olddeps, Id id, Id marker) return repo_addid(repo, olddeps, id); } + /* check if we should use the hash optimization */ + if (olddeps == repo->lastoff) + { + int size = repo->idarraysize - 1 - repo->lastoff; + if (size >= REPO_ADDID_DEP_HASHTHRES) + return repo_addid_dep_hash(repo, olddeps, id, marker, size); + } + before = 0; if (marker) { - if (marker == id) - marker = 0; if (marker < 0) { marker = -marker; before = 1; } - } - - /* optimization for packages with an excessive amount of provides/requires: - * if the number of deps exceed a threshold, we build a hash of the already - * seen ids. - */ - if (olddeps == repo->lastoff) - { - int size = repo->idarraysize - 1 - repo->lastoff; - if (size >= REPO_ADDID_DEP_HASHTHRES) - { - Hashval h, hh; - Id hid; - - /* maintain hash and lastmarkerpos */ - if (repo->lastidhash_idarraysize != repo->idarraysize || size * 2 > repo->lastidhash_mask || repo->lastmarker != marker) - { - if (size * 2 > repo->lastidhash_mask) - { - repo->lastidhash_mask = mkmask(size < REPO_ADDID_DEP_HASHMIN ? REPO_ADDID_DEP_HASHMIN : size); - repo->lastidhash = solv_realloc2(repo->lastidhash, repo->lastidhash_mask + 1, sizeof(Id)); - } - memset(repo->lastidhash, 0, (repo->lastidhash_mask + 1) * sizeof(Id)); - for (oidp = repo->idarraydata + olddeps; (oid = *oidp) != 0; oidp++) - { - h = oid & repo->lastidhash_mask; - hh = HASHCHAIN_START; - while (repo->lastidhash[h] != 0) - h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); - repo->lastidhash[h] = oid; - if (marker && oid == marker) - repo->lastmarkerpos = oidp - repo->idarraydata; - } - repo->lastmarker = marker; - repo->lastidhash_idarraysize = repo->idarraysize; - } - - /* check the hash! */ - h = id & repo->lastidhash_mask; - hh = HASHCHAIN_START; - while ((hid = repo->lastidhash[h]) != 0 && hid != id) - h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); - /* put new element in hash */ - if (!hid) - repo->lastidhash[h] = id; - if (marker && !before && !repo->lastmarkerpos) - { - /* we have to add the marker first */ - repo->lastmarkerpos = repo->idarraysize - 1; - olddeps = repo_addid(repo, olddeps, marker); - /* now put marker in hash */ - h = marker & repo->lastidhash_mask; - hh = HASHCHAIN_START; - while (repo->lastidhash[h] != 0) - h = HASHCHAIN_NEXT(h, hh, repo->lastidhash_mask); - repo->lastidhash[h] = marker; - repo->lastidhash_idarraysize = repo->idarraysize; - } - if (!hid) - { - if (marker && before && repo->lastmarkerpos) - { - /* need to add it before the marker */ - olddeps = repo_addid(repo, olddeps, 0); /* dummy to make room */ - memmove(repo->idarraydata + repo->lastmarkerpos + 1, repo->idarraydata + repo->lastmarkerpos, repo->idarraysize - repo->lastmarkerpos - 2); - repo->idarraydata[repo->lastmarkerpos++] = id; - } - else - { - /* just append it to the end */ - olddeps = repo_addid(repo, olddeps, id); - } - repo->lastidhash_idarraysize = repo->idarraysize; - return olddeps; - } - /* we already have it in the hash */ - if (!marker || before) - return olddeps; - /* check if it is in the correct half */ - for (oidp = repo->idarraydata + repo->lastmarkerpos + 1; (oid = *oidp) != 0; oidp++) - if (oid == id) - return olddeps; - /* nope, copy it over */ - for (oidp = repo->idarraydata + olddeps; (oid = *oidp) != 0; oidp++) - if (oid == id) - break; - if (!oid) - return olddeps; /* should not happen */ - memmove(oidp, oidp + 1, repo->idarraydata + repo->idarraysize - oidp - 2); - repo->idarraydata[repo->idarraysize - 2] = id; - return olddeps; - } + if (marker == id) + marker = 0; } if (!marker) @@ -446,7 +466,7 @@ repo_addid_dep(Repo *repo, Offset olddeps, Id id, Id marker) if (oid) { - if (markerp || before) + if (markerp || before || marker == SOLVABLE_FILEMARKER) return olddeps; /* we found it, but in the first half */ markerp = oidp++; -- 2.7.4