diff options
Diffstat (limited to 'CPP/Common/Wildcard.cpp')
-rwxr-xr-x | CPP/Common/Wildcard.cpp | 462 |
1 files changed, 462 insertions, 0 deletions
diff --git a/CPP/Common/Wildcard.cpp b/CPP/Common/Wildcard.cpp new file mode 100755 index 00000000..ddadc7b1 --- /dev/null +++ b/CPP/Common/Wildcard.cpp @@ -0,0 +1,462 @@ +// Common/Wildcard.cpp + +#include "StdAfx.h" + +#include "Wildcard.h" + +static const wchar_t kPeriodChar = L'.'; +static const wchar_t kAnyCharsChar = L'*'; +static const wchar_t kAnyCharChar = L'?'; + +#ifdef _WIN32 +static const wchar_t kDirDelimiter1 = L'\\'; +#endif +static const wchar_t kDirDelimiter2 = L'/'; + +static const UString kWildCardCharSet = L"?*"; + +static const UString kIllegalWildCardFileNameChars= + L"\x1\x2\x3\x4\x5\x6\x7\x8\x9\xA\xB\xC\xD\xE\xF" + L"\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F" + L"\"/:<>\\|"; + +static const UString kIllegalFileNameChars = kIllegalWildCardFileNameChars + + kWildCardCharSet; + +static inline bool IsCharDirLimiter(wchar_t c) +{ + return ( + #ifdef _WIN32 + c == kDirDelimiter1 || + #endif + c == kDirDelimiter2); +} + +// ----------------------------------------- +// this function tests is name matches mask +// ? - any wchar_t or empty +// * - any characters or empty + +static bool EnhancedMaskTest(const UString &mask, int maskPos, + const UString &name, int namePos) +{ + int maskLen = mask.Length() - maskPos; + int nameLen = name.Length() - namePos; + if (maskLen == 0) + if (nameLen == 0) + return true; + else + return false; + wchar_t maskChar = mask[maskPos]; + if(maskChar == kAnyCharChar) + { + /* + if (EnhancedMaskTest(mask, maskPos + 1, name, namePos)) + return true; + */ + if (nameLen == 0) + return false; + return EnhancedMaskTest(mask, maskPos + 1, name, namePos + 1); + } + else if(maskChar == kAnyCharsChar) + { + if (EnhancedMaskTest(mask, maskPos + 1, name, namePos)) + return true; + if (nameLen == 0) + return false; + return EnhancedMaskTest(mask, maskPos, name, namePos + 1); + } + else + { + wchar_t c = name[namePos]; + if (maskChar != c) +#ifdef _WIN32 + if (MyCharUpper(maskChar) != MyCharUpper(c)) +#endif + return false; + return EnhancedMaskTest(mask, maskPos + 1, name, namePos + 1); + } +} + +// -------------------------------------------------- +// Splits path to strings + +void SplitPathToParts(const UString &path, UStringVector &pathParts) +{ + pathParts.Clear(); + UString name; + int len = path.Length(); + if (len == 0) + return; + for (int i = 0; i < len; i++) + { + wchar_t c = path[i]; + if (IsCharDirLimiter(c)) + { + pathParts.Add(name); + name.Empty(); + } + else + name += c; + } + pathParts.Add(name); +} + +void SplitPathToParts(const UString &path, UString &dirPrefix, UString &name) +{ + int i; + for(i = path.Length() - 1; i >= 0; i--) + if(IsCharDirLimiter(path[i])) + break; + dirPrefix = path.Left(i + 1); + name = path.Mid(i + 1); +} + +UString ExtractDirPrefixFromPath(const UString &path) +{ + int i; + for(i = path.Length() - 1; i >= 0; i--) + if(IsCharDirLimiter(path[i])) + break; + return path.Left(i + 1); +} + +UString ExtractFileNameFromPath(const UString &path) +{ + int i; + for(i = path.Length() - 1; i >= 0; i--) + if(IsCharDirLimiter(path[i])) + break; + return path.Mid(i + 1); +} + + +bool CompareWildCardWithName(const UString &mask, const UString &name) +{ + return EnhancedMaskTest(mask, 0, name, 0); +} + +bool DoesNameContainWildCard(const UString &path) +{ + return (path.FindOneOf(kWildCardCharSet) >= 0); +} + + +// ----------------------------------------------------------' +// NWildcard + +namespace NWildcard { + +static inline int BoolToIndex(bool value) +{ + return value ? 1: 0; +} + + +/* +M = MaskParts.Size(); +N = TestNameParts.Size(); + + File Dir +ForFile req M<=N [N-M, N) - + nonreq M=N [0, M) - + +ForDir req M<N [0, M) ... [N-M-1, N-1) same as ForBoth-File + nonreq [0, M) same as ForBoth-File + +ForBoth req m<=N [0, M) ... [N-M, N) same as ForBoth-File + nonreq [0, M) same as ForBoth-File + +*/ + +bool CItem::CheckPath(const UStringVector &pathParts, bool isFile) const +{ + if (!isFile && !ForDir) + return false; + int delta = (int)pathParts.Size() - (int)PathParts.Size(); + if (delta < 0) + return false; + int start = 0; + int finish = 0; + if (isFile) + { + if (!ForDir && !Recursive && delta !=0) + return false; + if (!ForFile && delta == 0) + return false; + if (!ForDir && Recursive) + start = delta; + } + if (Recursive) + { + finish = delta; + if (isFile && !ForFile) + finish = delta - 1; + } + for (int d = start; d <= finish; d++) + { + int i; + for (i = 0; i < PathParts.Size(); i++) + if (!CompareWildCardWithName(PathParts[i], pathParts[i + d])) + break; + if (i == PathParts.Size()) + return true; + } + return false; +} + +int CCensorNode::FindSubNode(const UString &name) const +{ + for (int i = 0; i < SubNodes.Size(); i++) + if (SubNodes[i].Name.CompareNoCase(name) == 0) + return i; + return -1; +} + +void CCensorNode::AddItemSimple(bool include, CItem &item) +{ + if (include) + IncludeItems.Add(item); + else + ExcludeItems.Add(item); +} + +void CCensorNode::AddItem(bool include, CItem &item) +{ + if (item.PathParts.Size() <= 1) + { + AddItemSimple(include, item); + return; + } + const UString &front = item.PathParts.Front(); + if (DoesNameContainWildCard(front)) + { + AddItemSimple(include, item); + return; + } + int index = FindSubNode(front); + if (index < 0) + index = SubNodes.Add(CCensorNode(front, this)); + item.PathParts.Delete(0); + SubNodes[index].AddItem(include, item); +} + +void CCensorNode::AddItem(bool include, const UString &path, bool recursive, bool forFile, bool forDir) +{ + CItem item; + SplitPathToParts(path, item.PathParts); + item.Recursive = recursive; + item.ForFile = forFile; + item.ForDir = forDir; + AddItem(include, item); +} + +bool CCensorNode::NeedCheckSubDirs() const +{ + for (int i = 0; i < IncludeItems.Size(); i++) + { + const CItem &item = IncludeItems[i]; + if (item.Recursive || item.PathParts.Size() > 1) + return true; + } + return false; +} + +bool CCensorNode::AreThereIncludeItems() const +{ + if (IncludeItems.Size() > 0) + return true; + for (int i = 0; i < SubNodes.Size(); i++) + if (SubNodes[i].AreThereIncludeItems()) + return true; + return false; +} + +bool CCensorNode::CheckPathCurrent(bool include, const UStringVector &pathParts, bool isFile) const +{ + const CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems; + for (int i = 0; i < items.Size(); i++) + if (items[i].CheckPath(pathParts, isFile)) + return true; + return false; +} + +bool CCensorNode::CheckPath(UStringVector &pathParts, bool isFile, bool &include) const +{ + if (CheckPathCurrent(false, pathParts, isFile)) + { + include = false; + return true; + } + include = true; + bool finded = CheckPathCurrent(true, pathParts, isFile); + if (pathParts.Size() == 1) + return finded; + int index = FindSubNode(pathParts.Front()); + if (index >= 0) + { + UStringVector pathParts2 = pathParts; + pathParts2.Delete(0); + if (SubNodes[index].CheckPath(pathParts2, isFile, include)) + return true; + } + return finded; +} + +bool CCensorNode::CheckPath(const UString &path, bool isFile, bool &include) const +{ + UStringVector pathParts; + SplitPathToParts(path, pathParts); + return CheckPath(pathParts, isFile, include); +} + +bool CCensorNode::CheckPath(const UString &path, bool isFile) const +{ + bool include; + if(CheckPath(path, isFile, include)) + return include; + return false; +} + +bool CCensorNode::CheckPathToRoot(bool include, UStringVector &pathParts, bool isFile) const +{ + if (CheckPathCurrent(include, pathParts, isFile)) + return true; + if (Parent == 0) + return false; + pathParts.Insert(0, Name); + return Parent->CheckPathToRoot(include, pathParts, isFile); +} + +/* +bool CCensorNode::CheckPathToRoot(bool include, const UString &path, bool isFile) const +{ + UStringVector pathParts; + SplitPathToParts(path, pathParts); + return CheckPathToRoot(include, pathParts, isFile); +} +*/ + +void CCensorNode::AddItem2(bool include, const UString &path, bool recursive) +{ + if (path.IsEmpty()) + return; + bool forFile = true; + bool forFolder = true; + UString path2 = path; + if (IsCharDirLimiter(path[path.Length() - 1])) + { + path2.Delete(path.Length() - 1); + forFile = false; + } + AddItem(include, path2, recursive, forFile, forFolder); +} + +void CCensorNode::ExtendExclude(const CCensorNode &fromNodes) +{ + ExcludeItems += fromNodes.ExcludeItems; + for (int i = 0; i < fromNodes.SubNodes.Size(); i++) + { + const CCensorNode &node = fromNodes.SubNodes[i]; + int subNodeIndex = FindSubNode(node.Name); + if (subNodeIndex < 0) + subNodeIndex = SubNodes.Add(CCensorNode(node.Name, this)); + SubNodes[subNodeIndex].ExtendExclude(node); + } +} + +int CCensor::FindPrefix(const UString &prefix) const +{ + for (int i = 0; i < Pairs.Size(); i++) + if (Pairs[i].Prefix.CompareNoCase(prefix) == 0) + return i; + return -1; +} + +void CCensor::AddItem(bool include, const UString &path, bool recursive) +{ + UStringVector pathParts; + SplitPathToParts(path, pathParts); + bool forFile = true; + if (pathParts.Back().IsEmpty()) + { + forFile = false; + pathParts.DeleteBack(); + } + const UString &front = pathParts.Front(); + bool isAbs = false; + if (front.IsEmpty()) + isAbs = true; + else if (front.Length() == 2 && front[1] == L':') + isAbs = true; + else + { + for (int i = 0; i < pathParts.Size(); i++) + { + const UString &part = pathParts[i]; + if (part == L".." || part == L".") + { + isAbs = true; + break; + } + } + } + int numAbsParts = 0; + if (isAbs) + if (pathParts.Size() > 1) + numAbsParts = pathParts.Size() - 1; + else + numAbsParts = 1; + UString prefix; + for (int i = 0; i < numAbsParts; i++) + { + const UString &front = pathParts.Front(); + if (DoesNameContainWildCard(front)) + break; + prefix += front; + prefix += WCHAR_PATH_SEPARATOR; + pathParts.Delete(0); + } + int index = FindPrefix(prefix); + if (index < 0) + index = Pairs.Add(CPair(prefix)); + + CItem item; + item.PathParts = pathParts; + item.ForDir = true; + item.ForFile = forFile; + item.Recursive = recursive; + Pairs[index].Head.AddItem(include, item); +} + +bool CCensor::CheckPath(const UString &path, bool isFile) const +{ + bool finded = false; + for (int i = 0; i < Pairs.Size(); i++) + { + bool include; + if (Pairs[i].Head.CheckPath(path, isFile, include)) + { + if (!include) + return false; + finded = true; + } + } + return finded; +} + +void CCensor::ExtendExclude() +{ + int i; + for (i = 0; i < Pairs.Size(); i++) + if (Pairs[i].Prefix.IsEmpty()) + break; + if (i == Pairs.Size()) + return; + int index = i; + for (i = 0; i < Pairs.Size(); i++) + if (index != i) + Pairs[i].Head.ExtendExclude(Pairs[index].Head); +} + +} |