From abfd07702c1bbc3ed489d015b43db58ab677af0c Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 27 Sep 2016 17:32:24 +0200 Subject: TagSection: Introduce functions for looking up by key ids Introduce a new enum class and add functions that can do a lookup with that enum class. This uses triehash. --- apt-pkg/CMakeLists.txt | 15 +++++++- apt-pkg/tagfile-keys.list | 82 ++++++++++++++++++++++++++++++++++++++++++ apt-pkg/tagfile.cc | 92 +++++++++++++++++++++++++++++++++++++++++------ apt-pkg/tagfile.h | 12 +++++++ 4 files changed, 190 insertions(+), 11 deletions(-) create mode 100644 apt-pkg/tagfile-keys.list (limited to 'apt-pkg') diff --git a/apt-pkg/CMakeLists.txt b/apt-pkg/CMakeLists.txt index 1b493c819..25ed13ec3 100644 --- a/apt-pkg/CMakeLists.txt +++ b/apt-pkg/CMakeLists.txt @@ -3,6 +3,19 @@ include_directories(${PROJECT_BINARY_DIR}/include/apt-pkg) add_definitions("-DAPT_PKG_EXPOSE_STRING_VIEW") +file(MAKE_DIRECTORY ${PROJECT_BINARY_DIR}/include/apt-pkg/) +execute_process(COMMAND ${PROJECT_SOURCE_DIR}/triehash/triehash.pl + --ignore-case + --header ${PROJECT_BINARY_DIR}/include/apt-pkg/tagfile-keys.h + --code ${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.cc + --enum-class + --enum-name pkgTagSection::Key + --function-name pkgTagHash + --include "" + ${CMAKE_CURRENT_SOURCE_DIR}/tagfile-keys.list) +set_property(DIRECTORY APPEND PROPERTY CMAKE_CONFIGURE_DEPENDS "tagfile-keys.list") + + # Set the version of the library execute_process(COMMAND awk -v ORS=. "/^\#define APT_PKG_M/ {print \$3}" COMMAND sed "s/\\.\$//" @@ -17,7 +30,7 @@ message(STATUS "Building libapt-pkg ${MAJOR} (release ${MINOR})") set(APT_PKG_MAJOR ${MAJOR} PARENT_SCOPE) # exporting for methods/CMakeLists.txt # Definition of the C++ files used to build the library -file(GLOB_RECURSE library "*.cc") +file(GLOB_RECURSE library "*.cc" "${CMAKE_CURRENT_BINARY_DIR}/tagfile-keys.cc") file(GLOB_RECURSE headers "*.h") # Create a library using the C++ files diff --git a/apt-pkg/tagfile-keys.list b/apt-pkg/tagfile-keys.list new file mode 100644 index 000000000..82f0d8316 --- /dev/null +++ b/apt-pkg/tagfile-keys.list @@ -0,0 +1,82 @@ +Architecture +Binary +Breaks +Bugs +Build-Conflicts +Build-Conflicts-Arch +Build-Conflicts-Indep +Build-Depends +Build-Depends-Arch +Build-Depends-Indep +Built-For-Profiles +Built-Using +Checksums-Md5 +Checksums-Sha1 +Checksums-Sha256 +Checksums-Sha512 +Class +Conffiles +Config-Version +Conflicts +Depends +Description +Description-md5 +Directory +Dm-Upload-Allowed +Enhances +Essential +Filename +Files +Format +Homepage +Important +Installed-Size +Installer-Menu-Item +Kernel-Version +Maintainer +MD5sum +MSDOS-Filename +Multi-Arch +Optional +Origin +Original-Maintainer +Package +Package-List +Package_Revision +Package-Revision +Package-Type +Pre-Depends +Priority +Provides +Recommended +Recommends +Replaces +Revision +Section +SHA1 +SHA256 +SHA512 +Size +Source +Standards-Version +Status +Subarchitecture +Suggests +Tag +Task +Testsuite +Testsuite-Triggers +Triggers-Awaited +Triggers-Pending +Uploaders +Vcs-Arch +Vcs-Browse +Vcs-Browser +Vcs-Bzr +Vcs-Cvs +Vcs-Darcs +Vcs-Git +Vcs-Hg +Vcs-Mtn +Vcs-Svn +Version diff --git a/apt-pkg/tagfile.cc b/apt-pkg/tagfile.cc index b81efe42a..200a7f2fd 100644 --- a/apt-pkg/tagfile.cc +++ b/apt-pkg/tagfile.cc @@ -14,6 +14,7 @@ #include #include +#include #include #include #include @@ -512,7 +513,8 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R pkgTagSectionPrivate::TagData lastTagData(0); lastTagData.EndTag = 0; - unsigned long lastTagHash = 0; + Key lastTagKey = Key::Unknown; + unsigned int lastTagHash = 0; while (Stop < End) { TrimRecord(true,End); @@ -528,11 +530,15 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R // store the last found tag if (lastTagData.EndTag != 0) { - if (BetaIndexes[lastTagHash] != 0) - lastTagData.NextInBucket = BetaIndexes[lastTagHash]; - APT_IGNORE_DEPRECATED_PUSH - BetaIndexes[lastTagHash] = TagCount; - APT_IGNORE_DEPRECATED_POP + if (lastTagKey != Key::Unknown) { + AlphaIndexes[static_cast(lastTagKey)] = TagCount; + } else { + if (BetaIndexes[lastTagHash] != 0) + lastTagData.NextInBucket = BetaIndexes[lastTagHash]; + APT_IGNORE_DEPRECATED_PUSH + BetaIndexes[lastTagHash] = TagCount; + APT_IGNORE_DEPRECATED_POP + } d->Tags.push_back(lastTagData); } @@ -549,7 +555,9 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R ; ++EndTag; lastTagData.EndTag = EndTag - Section; - lastTagHash = BetaHash(Stop, EndTag - Stop); + lastTagKey = pkgTagHash(Stop, EndTag - Stop); + if (lastTagKey == Key::Unknown) + lastTagHash = BetaHash(Stop, EndTag - Stop); // find the beginning of the value Stop = Colon + 1; for (; Stop < End && isspace_ascii(*Stop) != 0; ++Stop) @@ -574,9 +582,13 @@ bool pkgTagSection::Scan(const char *Start,unsigned long MaxLength, bool const R { if (lastTagData.EndTag != 0) { - if (BetaIndexes[lastTagHash] != 0) - lastTagData.NextInBucket = BetaIndexes[lastTagHash]; - APT_IGNORE_DEPRECATED(BetaIndexes[lastTagHash] = TagCount;) + if (lastTagKey != Key::Unknown) { + AlphaIndexes[static_cast(lastTagKey)] = TagCount; + } else { + if (BetaIndexes[lastTagHash] != 0) + lastTagData.NextInBucket = BetaIndexes[lastTagHash]; + APT_IGNORE_DEPRECATED(BetaIndexes[lastTagHash] = TagCount;) + } d->Tags.push_back(lastTagData); } @@ -620,10 +632,20 @@ bool pkgTagSection::Exists(StringView Tag) const // TagSection::Find - Locate a tag /*{{{*/ // --------------------------------------------------------------------- /* This searches the section for a tag that matches the given string. */ +bool pkgTagSection::Find(Key key,unsigned int &Pos) const +{ + auto Bucket = AlphaIndexes[static_cast(key)]; + Pos = Bucket - 1; + return Bucket != 0; +} bool pkgTagSection::Find(StringView TagView,unsigned int &Pos) const { const char * const Tag = TagView.data(); size_t const Length = TagView.length(); + auto key = pkgTagHash(Tag, Length); + if (key != Key::Unknown) + return Find(key, Pos); + unsigned int Bucket = BetaIndexes[BetaHash(Tag, Length)]; if (Bucket == 0) return false; @@ -663,6 +685,12 @@ bool pkgTagSection::Find(StringView Tag,const char *&Start, { unsigned int Pos; return Find(Tag, Pos) && FindInternal(Pos, Start, End); +} +bool pkgTagSection::Find(Key key,const char *&Start, + const char *&End) const +{ + unsigned int Pos; + return Find(key, Pos) && FindInternal(Pos, Start, End); } /*}}}*/ // TagSection::FindS - Find a string /*{{{*/ @@ -673,6 +701,14 @@ StringView pkgTagSection::Find(StringView Tag) const if (Find(Tag,Start,End) == false) return StringView(); return StringView(Start, End - Start); +} +StringView pkgTagSection::Find(Key key) const +{ + const char *Start; + const char *End; + if (Find(key,Start,End) == false) + return StringView(); + return StringView(Start, End - Start); } /*}}}*/ // TagSection::FindRawS - Find a string /*{{{*/ @@ -692,6 +728,11 @@ StringView pkgTagSection::FindRaw(StringView Tag) const { unsigned int Pos; return Find(Tag, Pos) ? FindRawInternal(Pos) : ""; +} +StringView pkgTagSection::FindRaw(Key key) const +{ + unsigned int Pos; + return Find(key, Pos) ? FindRawInternal(Pos) : ""; } /*}}}*/ // TagSection::FindI - Find an integer /*{{{*/ @@ -723,6 +764,12 @@ signed int pkgTagSection::FindIInternal(unsigned int Pos,signed long Default) co return Default; return Result; } +signed int pkgTagSection::FindI(Key key,signed long Default) const +{ + unsigned int Pos; + + return Find(key, Pos) ? FindIInternal(Pos) : Default; +} signed int pkgTagSection::FindI(StringView Tag,signed long Default) const { unsigned int Pos; @@ -753,6 +800,12 @@ unsigned long long pkgTagSection::FindULLInternal(unsigned int Pos, unsigned lon return Default; return Result; } +unsigned long long pkgTagSection::FindULL(Key key, unsigned long long const &Default) const +{ + unsigned int Pos; + + return Find(key, Pos) ? FindULLInternal(Pos, Default) : Default; +} unsigned long long pkgTagSection::FindULL(StringView Tag, unsigned long long const &Default) const { unsigned int Pos; @@ -770,6 +823,11 @@ bool pkgTagSection::FindBInternal(unsigned int Pos, bool Default) const return Default; return StringToBool(string(Start, Stop)); } +bool pkgTagSection::FindB(Key key, bool Default) const +{ + unsigned int Pos; + return Find(key, Pos) ? FindBInternal(Pos, Default): Default; +} bool pkgTagSection::FindB(StringView Tag, bool Default) const { unsigned int Pos; @@ -788,6 +846,14 @@ bool pkgTagSection::FindFlagInternal(unsigned int Pos, uint8_t &Flags, return true; return FindFlag(Flags, Flag, Start, Stop); } +bool pkgTagSection::FindFlag(Key key, uint8_t &Flags, + uint8_t const Flag) const +{ + unsigned int Pos; + if (Find(key,Pos) == false) + return true; + return FindFlagInternal(Pos, Flags, Flag); +} bool pkgTagSection::FindFlag(StringView Tag, uint8_t &Flags, uint8_t const Flag) const { @@ -824,6 +890,12 @@ bool pkgTagSection::FindFlagInternal(unsigned int Pos,unsigned long &Flags, return true; return FindFlag(Flags, Flag, Start, Stop); } +bool pkgTagSection::FindFlag(Key key,unsigned long &Flags, + unsigned long Flag) const +{ + unsigned int Pos; + return Find(key, Pos) ? FindFlagInternal(Pos, Flags, Flag) : true; +} bool pkgTagSection::FindFlag(StringView Tag,unsigned long &Flags, unsigned long Flag) const { diff --git a/apt-pkg/tagfile.h b/apt-pkg/tagfile.h index cdca54756..3b89d0e45 100644 --- a/apt-pkg/tagfile.h +++ b/apt-pkg/tagfile.h @@ -89,7 +89,19 @@ class pkgTagSection std::string FindS(const char *Tag) const; std::string FindRawS(const char *Tag) const; + // Functions for lookup with a perfect hash function + enum class Key; + APT_HIDDEN bool Find(Key key,const char *&Start, const char *&End) const; + APT_HIDDEN bool Find(Key key,unsigned int &Pos) const; + APT_HIDDEN signed int FindI(Key key,signed long Default = 0) const; + APT_HIDDEN bool FindB(Key key, bool Default = false) const; + APT_HIDDEN unsigned long long FindULL(Key key, unsigned long long const &Default = 0) const; + APT_HIDDEN bool FindFlag(Key key,uint8_t &Flags, uint8_t const Flag) const; + APT_HIDDEN bool FindFlag(Key key,unsigned long &Flags, unsigned long Flag) const; + APT_HIDDEN bool Exists(Key key) const; #ifdef APT_PKG_EXPOSE_STRING_VIEW + APT_HIDDEN APT::StringView Find(Key key) const; + APT_HIDDEN APT::StringView FindRaw(Key key) const; APT_HIDDEN bool Find(APT::StringView Tag,const char *&Start, const char *&End) const; APT_HIDDEN bool Find(APT::StringView Tag,unsigned int &Pos) const; APT_HIDDEN APT::StringView Find(APT::StringView Tag) const; -- cgit v1.2.3