1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/LICENSE.txt Sun Sep 20 15:14:12 2009 -0700
1.3 @@ -0,0 +1,23 @@
1.4 +[This is a standard BSD license.]
1.5 +
1.6 +Copyright (c) 2009, Jens Alfke <jens@mooseyard.com>. All rights reserved.
1.7 +
1.8 +Redistribution and use in source and binary forms, with or without modification,
1.9 +are permitted provided that the following conditions are met:
1.10 +
1.11 +* Redistributions of source code must retain the above copyright notice, this
1.12 + list of conditions and the following disclaimer.
1.13 +* Redistributions in binary form must reproduce the above copyright notice, this
1.14 + list of conditions and the following disclaimer in the documentation and/or
1.15 + other materials provided with the distribution.
1.16 +
1.17 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
1.18 +ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
1.19 +WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1.20 +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
1.21 +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.22 +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1.23 +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1.24 +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
1.25 +TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1.26 +THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/Ottoman.xcodeproj/project.pbxproj Sun Sep 20 15:14:12 2009 -0700
2.3 @@ -0,0 +1,322 @@
2.4 +// !$*UTF8*$!
2.5 +{
2.6 + archiveVersion = 1;
2.7 + classes = {
2.8 + };
2.9 + objectVersion = 45;
2.10 + objects = {
2.11 +
2.12 +/* Begin PBXBuildFile section */
2.13 + 27156CAA104C9C44009EBD39 /* gtest.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 27156CA9104C9C44009EBD39 /* gtest.framework */; };
2.14 + 27603901105AC81200D931A7 /* CoreFoundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 27603900105AC81200D931A7 /* CoreFoundation.framework */; };
2.15 + 276E5BCD1066D13D008A2171 /* Base.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC41066D13D008A2171 /* Base.cpp */; };
2.16 + 276E5BCE1066D13D008A2171 /* Chunk.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC51066D13D008A2171 /* Chunk.cpp */; };
2.17 + 276E5BCF1066D13D008A2171 /* Dictionary.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC61066D13D008A2171 /* Dictionary.cpp */; };
2.18 + 276E5BD01066D13D008A2171 /* File.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC71066D13D008A2171 /* File.cpp */; };
2.19 + 276E5BD11066D13D008A2171 /* Hash.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC81066D13D008A2171 /* Hash.cpp */; };
2.20 + 276E5BD21066D13D008A2171 /* Index.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BC91066D13D008A2171 /* Index.cpp */; };
2.21 + 276E5BD31066D13D008A2171 /* MemoryMap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BCA1066D13D008A2171 /* MemoryMap.cpp */; };
2.22 + 276E5BD41066D13D008A2171 /* Ottoman.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BCB1066D13D008A2171 /* Ottoman.cpp */; };
2.23 + 276E5BD51066D13D008A2171 /* VersionDictionary.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BCC1066D13D008A2171 /* VersionDictionary.cpp */; };
2.24 + 276E5BDD1066D142008A2171 /* Dictionary_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BD71066D142008A2171 /* Dictionary_test.cpp */; };
2.25 + 276E5BDE1066D142008A2171 /* Hash_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BD81066D142008A2171 /* Hash_test.cpp */; };
2.26 + 276E5BDF1066D142008A2171 /* Ottoman_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BD91066D142008A2171 /* Ottoman_test.cpp */; };
2.27 + 276E5BE01066D142008A2171 /* TestUtils.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BDA1066D142008A2171 /* TestUtils.cpp */; };
2.28 + 276E5BE11066D142008A2171 /* VersionDictionary_test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 276E5BDC1066D142008A2171 /* VersionDictionary_test.cpp */; };
2.29 +/* End PBXBuildFile section */
2.30 +
2.31 +/* Begin PBXCopyFilesBuildPhase section */
2.32 + 8DD76F690486A84900D96B5E /* CopyFiles */ = {
2.33 + isa = PBXCopyFilesBuildPhase;
2.34 + buildActionMask = 8;
2.35 + dstPath = /usr/share/man/man1/;
2.36 + dstSubfolderSpec = 0;
2.37 + files = (
2.38 + );
2.39 + runOnlyForDeploymentPostprocessing = 1;
2.40 + };
2.41 +/* End PBXCopyFilesBuildPhase section */
2.42 +
2.43 +/* Begin PBXFileReference section */
2.44 + 27156CA9104C9C44009EBD39 /* gtest.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = gtest.framework; path = /Library/Frameworks/gtest.framework; sourceTree = "<absolute>"; };
2.45 + 27603900105AC81200D931A7 /* CoreFoundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreFoundation.framework; path = System/Library/Frameworks/CoreFoundation.framework; sourceTree = SDKROOT; };
2.46 + 276E5BBA1066D135008A2171 /* Base.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Base.h; sourceTree = "<group>"; };
2.47 + 276E5BBB1066D135008A2171 /* Chunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Chunk.h; path = ../include/Chunk.h; sourceTree = "<group>"; };
2.48 + 276E5BBC1066D135008A2171 /* Dictionary.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dictionary.h; sourceTree = "<group>"; };
2.49 + 276E5BBD1066D135008A2171 /* File.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = File.h; sourceTree = "<group>"; };
2.50 + 276E5BBE1066D135008A2171 /* Hash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Hash.h; path = ../include/Hash.h; sourceTree = "<group>"; };
2.51 + 276E5BBF1066D135008A2171 /* Index.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Index.h; path = ../include/Index.h; sourceTree = "<group>"; };
2.52 + 276E5BC01066D135008A2171 /* MemoryMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MemoryMap.h; path = ../include/MemoryMap.h; sourceTree = "<group>"; };
2.53 + 276E5BC11066D135008A2171 /* Ottoman.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Ottoman.h; sourceTree = "<group>"; };
2.54 + 276E5BC21066D135008A2171 /* VersionDictionary.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VersionDictionary.h; sourceTree = "<group>"; };
2.55 + 276E5BC41066D13D008A2171 /* Base.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Base.cpp; sourceTree = "<group>"; };
2.56 + 276E5BC51066D13D008A2171 /* Chunk.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Chunk.cpp; sourceTree = "<group>"; };
2.57 + 276E5BC61066D13D008A2171 /* Dictionary.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Dictionary.cpp; sourceTree = "<group>"; };
2.58 + 276E5BC71066D13D008A2171 /* File.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = File.cpp; sourceTree = "<group>"; };
2.59 + 276E5BC81066D13D008A2171 /* Hash.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Hash.cpp; sourceTree = "<group>"; };
2.60 + 276E5BC91066D13D008A2171 /* Index.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Index.cpp; sourceTree = "<group>"; };
2.61 + 276E5BCA1066D13D008A2171 /* MemoryMap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MemoryMap.cpp; sourceTree = "<group>"; };
2.62 + 276E5BCB1066D13D008A2171 /* Ottoman.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Ottoman.cpp; sourceTree = "<group>"; };
2.63 + 276E5BCC1066D13D008A2171 /* VersionDictionary.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VersionDictionary.cpp; sourceTree = "<group>"; };
2.64 + 276E5BD71066D142008A2171 /* Dictionary_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Dictionary_test.cpp; sourceTree = "<group>"; };
2.65 + 276E5BD81066D142008A2171 /* Hash_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Hash_test.cpp; sourceTree = "<group>"; };
2.66 + 276E5BD91066D142008A2171 /* Ottoman_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Ottoman_test.cpp; sourceTree = "<group>"; };
2.67 + 276E5BDA1066D142008A2171 /* TestUtils.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TestUtils.cpp; sourceTree = "<group>"; };
2.68 + 276E5BDB1066D142008A2171 /* TestUtils.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TestUtils.h; sourceTree = "<group>"; };
2.69 + 276E5BDC1066D142008A2171 /* VersionDictionary_test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VersionDictionary_test.cpp; sourceTree = "<group>"; };
2.70 + 8DD76F6C0486A84900D96B5E /* SafeStorageTest */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.executable"; includeInIndex = 0; path = SafeStorageTest; sourceTree = BUILT_PRODUCTS_DIR; };
2.71 +/* End PBXFileReference section */
2.72 +
2.73 +/* Begin PBXFrameworksBuildPhase section */
2.74 + 8DD76F660486A84900D96B5E /* Frameworks */ = {
2.75 + isa = PBXFrameworksBuildPhase;
2.76 + buildActionMask = 2147483647;
2.77 + files = (
2.78 + 27156CAA104C9C44009EBD39 /* gtest.framework in Frameworks */,
2.79 + 27603901105AC81200D931A7 /* CoreFoundation.framework in Frameworks */,
2.80 + );
2.81 + runOnlyForDeploymentPostprocessing = 0;
2.82 + };
2.83 +/* End PBXFrameworksBuildPhase section */
2.84 +
2.85 +/* Begin PBXGroup section */
2.86 + 08FB7794FE84155DC02AAC07 /* BPlusTree */ = {
2.87 + isa = PBXGroup;
2.88 + children = (
2.89 + 276E5BB91066D135008A2171 /* include */,
2.90 + 276E5BC31066D13D008A2171 /* src */,
2.91 + 276E5BD61066D142008A2171 /* test */,
2.92 + 27603900105AC81200D931A7 /* CoreFoundation.framework */,
2.93 + 27156CA9104C9C44009EBD39 /* gtest.framework */,
2.94 + 1AB674ADFE9D54B511CA2CBB /* Products */,
2.95 + );
2.96 + name = BPlusTree;
2.97 + sourceTree = "<group>";
2.98 + };
2.99 + 1AB674ADFE9D54B511CA2CBB /* Products */ = {
2.100 + isa = PBXGroup;
2.101 + children = (
2.102 + 8DD76F6C0486A84900D96B5E /* SafeStorageTest */,
2.103 + );
2.104 + name = Products;
2.105 + sourceTree = "<group>";
2.106 + };
2.107 + 276E5BB91066D135008A2171 /* include */ = {
2.108 + isa = PBXGroup;
2.109 + children = (
2.110 + 276E5BBA1066D135008A2171 /* Base.h */,
2.111 + 276E5BBC1066D135008A2171 /* Dictionary.h */,
2.112 + 276E5BBD1066D135008A2171 /* File.h */,
2.113 + 276E5BC11066D135008A2171 /* Ottoman.h */,
2.114 + 276E5BC21066D135008A2171 /* VersionDictionary.h */,
2.115 + );
2.116 + path = include;
2.117 + sourceTree = "<group>";
2.118 + };
2.119 + 276E5BC31066D13D008A2171 /* src */ = {
2.120 + isa = PBXGroup;
2.121 + children = (
2.122 + 276E5BC41066D13D008A2171 /* Base.cpp */,
2.123 + 276E5BBB1066D135008A2171 /* Chunk.h */,
2.124 + 276E5BC51066D13D008A2171 /* Chunk.cpp */,
2.125 + 276E5BC61066D13D008A2171 /* Dictionary.cpp */,
2.126 + 276E5BC71066D13D008A2171 /* File.cpp */,
2.127 + 276E5BBE1066D135008A2171 /* Hash.h */,
2.128 + 276E5BC81066D13D008A2171 /* Hash.cpp */,
2.129 + 276E5BBF1066D135008A2171 /* Index.h */,
2.130 + 276E5BC91066D13D008A2171 /* Index.cpp */,
2.131 + 276E5BC01066D135008A2171 /* MemoryMap.h */,
2.132 + 276E5BCA1066D13D008A2171 /* MemoryMap.cpp */,
2.133 + 276E5BCB1066D13D008A2171 /* Ottoman.cpp */,
2.134 + 276E5BCC1066D13D008A2171 /* VersionDictionary.cpp */,
2.135 + );
2.136 + path = src;
2.137 + sourceTree = "<group>";
2.138 + };
2.139 + 276E5BD61066D142008A2171 /* test */ = {
2.140 + isa = PBXGroup;
2.141 + children = (
2.142 + 276E5BD71066D142008A2171 /* Dictionary_test.cpp */,
2.143 + 276E5BD81066D142008A2171 /* Hash_test.cpp */,
2.144 + 276E5BD91066D142008A2171 /* Ottoman_test.cpp */,
2.145 + 276E5BDC1066D142008A2171 /* VersionDictionary_test.cpp */,
2.146 + 276E5BDB1066D142008A2171 /* TestUtils.h */,
2.147 + 276E5BDA1066D142008A2171 /* TestUtils.cpp */,
2.148 + );
2.149 + path = test;
2.150 + sourceTree = "<group>";
2.151 + };
2.152 +/* End PBXGroup section */
2.153 +
2.154 +/* Begin PBXNativeTarget section */
2.155 + 8DD76F620486A84900D96B5E /* OttomanTest */ = {
2.156 + isa = PBXNativeTarget;
2.157 + buildConfigurationList = 1DEB923108733DC60010E9CD /* Build configuration list for PBXNativeTarget "OttomanTest" */;
2.158 + buildPhases = (
2.159 + 8DD76F640486A84900D96B5E /* Sources */,
2.160 + 8DD76F660486A84900D96B5E /* Frameworks */,
2.161 + 8DD76F690486A84900D96B5E /* CopyFiles */,
2.162 + );
2.163 + buildRules = (
2.164 + );
2.165 + dependencies = (
2.166 + );
2.167 + name = OttomanTest;
2.168 + productInstallPath = "$(HOME)/bin";
2.169 + productName = BPlusTree;
2.170 + productReference = 8DD76F6C0486A84900D96B5E /* SafeStorageTest */;
2.171 + productType = "com.apple.product-type.tool";
2.172 + };
2.173 +/* End PBXNativeTarget section */
2.174 +
2.175 +/* Begin PBXProject section */
2.176 + 08FB7793FE84155DC02AAC07 /* Project object */ = {
2.177 + isa = PBXProject;
2.178 + buildConfigurationList = 1DEB923508733DC60010E9CD /* Build configuration list for PBXProject "Ottoman" */;
2.179 + compatibilityVersion = "Xcode 3.1";
2.180 + hasScannedForEncodings = 1;
2.181 + mainGroup = 08FB7794FE84155DC02AAC07 /* BPlusTree */;
2.182 + projectDirPath = "";
2.183 + projectRoot = "";
2.184 + targets = (
2.185 + 8DD76F620486A84900D96B5E /* OttomanTest */,
2.186 + );
2.187 + };
2.188 +/* End PBXProject section */
2.189 +
2.190 +/* Begin PBXSourcesBuildPhase section */
2.191 + 8DD76F640486A84900D96B5E /* Sources */ = {
2.192 + isa = PBXSourcesBuildPhase;
2.193 + buildActionMask = 2147483647;
2.194 + files = (
2.195 + 276E5BCD1066D13D008A2171 /* Base.cpp in Sources */,
2.196 + 276E5BCE1066D13D008A2171 /* Chunk.cpp in Sources */,
2.197 + 276E5BCF1066D13D008A2171 /* Dictionary.cpp in Sources */,
2.198 + 276E5BD01066D13D008A2171 /* File.cpp in Sources */,
2.199 + 276E5BD11066D13D008A2171 /* Hash.cpp in Sources */,
2.200 + 276E5BD21066D13D008A2171 /* Index.cpp in Sources */,
2.201 + 276E5BD31066D13D008A2171 /* MemoryMap.cpp in Sources */,
2.202 + 276E5BD41066D13D008A2171 /* Ottoman.cpp in Sources */,
2.203 + 276E5BD51066D13D008A2171 /* VersionDictionary.cpp in Sources */,
2.204 + 276E5BDD1066D142008A2171 /* Dictionary_test.cpp in Sources */,
2.205 + 276E5BDE1066D142008A2171 /* Hash_test.cpp in Sources */,
2.206 + 276E5BDF1066D142008A2171 /* Ottoman_test.cpp in Sources */,
2.207 + 276E5BE01066D142008A2171 /* TestUtils.cpp in Sources */,
2.208 + 276E5BE11066D142008A2171 /* VersionDictionary_test.cpp in Sources */,
2.209 + );
2.210 + runOnlyForDeploymentPostprocessing = 0;
2.211 + };
2.212 +/* End PBXSourcesBuildPhase section */
2.213 +
2.214 +/* Begin XCBuildConfiguration section */
2.215 + 1DEB923208733DC60010E9CD /* Debug */ = {
2.216 + isa = XCBuildConfiguration;
2.217 + buildSettings = {
2.218 + ALWAYS_SEARCH_USER_PATHS = NO;
2.219 + COPY_PHASE_STRIP = NO;
2.220 + FRAMEWORK_SEARCH_PATHS = (
2.221 + "$(inherited)",
2.222 + /Code/googletest/xcode/build/Debug,
2.223 + );
2.224 + GCC_DYNAMIC_NO_PIC = NO;
2.225 + GCC_ENABLE_FIX_AND_CONTINUE = YES;
2.226 + GCC_MODEL_TUNING = G5;
2.227 + GCC_OPTIMIZATION_LEVEL = 0;
2.228 + GCC_PREPROCESSOR_DEFINITIONS = "";
2.229 + INSTALL_PATH = /usr/local/bin;
2.230 + LIBRARY_SEARCH_PATHS = (
2.231 + "$(inherited)",
2.232 + /Code/googletest/xcode/build/Debug,
2.233 + );
2.234 + PRODUCT_NAME = SafeStorageTest;
2.235 + };
2.236 + name = Debug;
2.237 + };
2.238 + 1DEB923308733DC60010E9CD /* Release */ = {
2.239 + isa = XCBuildConfiguration;
2.240 + buildSettings = {
2.241 + ALWAYS_SEARCH_USER_PATHS = NO;
2.242 + DEBUG_INFORMATION_FORMAT = "dwarf-with-dsym";
2.243 + FRAMEWORK_SEARCH_PATHS = (
2.244 + "$(inherited)",
2.245 + /Code/googletest/xcode/build/Debug,
2.246 + );
2.247 + GCC_MODEL_TUNING = G5;
2.248 + INSTALL_PATH = /usr/local/bin;
2.249 + LIBRARY_SEARCH_PATHS = (
2.250 + "$(inherited)",
2.251 + /Code/googletest/xcode/build/Debug,
2.252 + );
2.253 + PRODUCT_NAME = SafeStorageTest;
2.254 + };
2.255 + name = Release;
2.256 + };
2.257 + 1DEB923608733DC60010E9CD /* Debug */ = {
2.258 + isa = XCBuildConfiguration;
2.259 + buildSettings = {
2.260 + ARCHS = "$(ARCHS_STANDARD_32_BIT)";
2.261 + GCC_C_LANGUAGE_STANDARD = c99;
2.262 + GCC_OPTIMIZATION_LEVEL = 0;
2.263 + GCC_PRECOMPILE_PREFIX_HEADER = YES;
2.264 + GCC_PREPROCESSOR_DEFINITIONS = "";
2.265 + GCC_TREAT_WARNINGS_AS_ERRORS = YES;
2.266 + GCC_VERSION = com.apple.compilers.llvm.clang.1_0;
2.267 + GCC_WARN_ABOUT_MISSING_NEWLINE = YES;
2.268 + GCC_WARN_ABOUT_RETURN_TYPE = YES;
2.269 + GCC_WARN_EFFECTIVE_CPLUSPLUS_VIOLATIONS = NO;
2.270 + GCC_WARN_SHADOW = NO;
2.271 + GCC_WARN_UNUSED_VARIABLE = YES;
2.272 + ONLY_ACTIVE_ARCH = YES;
2.273 + PREBINDING = NO;
2.274 + SDKROOT = macosx10.5;
2.275 + WARNING_CFLAGS = "-Wall";
2.276 + };
2.277 + name = Debug;
2.278 + };
2.279 + 1DEB923708733DC60010E9CD /* Release */ = {
2.280 + isa = XCBuildConfiguration;
2.281 + buildSettings = {
2.282 + ARCHS = "$(ARCHS_STANDARD_32_BIT)";
2.283 + DEAD_CODE_STRIPPING = YES;
2.284 + GCC_C_LANGUAGE_STANDARD = c99;
2.285 + GCC_PRECOMPILE_PREFIX_HEADER = YES;
2.286 + GCC_PREPROCESSOR_DEFINITIONS = NDEBUG;
2.287 + GCC_TREAT_WARNINGS_AS_ERRORS = YES;
2.288 + GCC_VERSION = com.apple.compilers.llvm.clang.1_0;
2.289 + GCC_WARN_ABOUT_MISSING_NEWLINE = YES;
2.290 + GCC_WARN_ABOUT_RETURN_TYPE = YES;
2.291 + GCC_WARN_EFFECTIVE_CPLUSPLUS_VIOLATIONS = NO;
2.292 + GCC_WARN_SHADOW = NO;
2.293 + GCC_WARN_UNINITIALIZED_AUTOS = YES;
2.294 + GCC_WARN_UNUSED_VARIABLE = YES;
2.295 + PREBINDING = NO;
2.296 + SDKROOT = macosx10.5;
2.297 + WARNING_CFLAGS = "-Wall";
2.298 + };
2.299 + name = Release;
2.300 + };
2.301 +/* End XCBuildConfiguration section */
2.302 +
2.303 +/* Begin XCConfigurationList section */
2.304 + 1DEB923108733DC60010E9CD /* Build configuration list for PBXNativeTarget "OttomanTest" */ = {
2.305 + isa = XCConfigurationList;
2.306 + buildConfigurations = (
2.307 + 1DEB923208733DC60010E9CD /* Debug */,
2.308 + 1DEB923308733DC60010E9CD /* Release */,
2.309 + );
2.310 + defaultConfigurationIsVisible = 0;
2.311 + defaultConfigurationName = Release;
2.312 + };
2.313 + 1DEB923508733DC60010E9CD /* Build configuration list for PBXProject "Ottoman" */ = {
2.314 + isa = XCConfigurationList;
2.315 + buildConfigurations = (
2.316 + 1DEB923608733DC60010E9CD /* Debug */,
2.317 + 1DEB923708733DC60010E9CD /* Release */,
2.318 + );
2.319 + defaultConfigurationIsVisible = 0;
2.320 + defaultConfigurationName = Release;
2.321 + };
2.322 +/* End XCConfigurationList section */
2.323 + };
2.324 + rootObject = 08FB7793FE84155DC02AAC07 /* Project object */;
2.325 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/include/Base.h Sun Sep 20 15:14:12 2009 -0700
3.3 @@ -0,0 +1,113 @@
3.4 +/*
3.5 + * Base.h
3.6 + * Ottoman
3.7 + *
3.8 + * Created by Jens Alfke on 8/18/09.
3.9 + * Copyright 2009 Jens Alfke. All rights reserved.
3.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
3.11 + */
3.12 +
3.13 +#ifndef _MOOSEYARD_BASE_
3.14 +#define _MOOSEYARD_BASE_
3.15 +#include <stdlib.h>
3.16 +#include <stdint.h>
3.17 +#include <string.h>
3.18 +#include <libkern/OSByteOrder.h>
3.19 +#include <CoreFoundation/CFByteOrder.h>
3.20 +
3.21 +namespace Mooseyard {
3.22 +
3.23 + /** A 32-bit file position/offset. Supports files of up to 4GB. */
3.24 + typedef uint32_t FilePosition;
3.25 + const FilePosition kNoFilePosition = (FilePosition)-1L;
3.26 +
3.27 +
3.28 + /** A simple structure representing a range of memory (a pointer plus a length).
3.29 + It doesn't do any memory management; it just points. */
3.30 + struct Blob {
3.31 + const void *bytes;
3.32 + size_t length;
3.33 +
3.34 + Blob() :bytes(NULL), length(0) { }
3.35 + Blob (const void *b, size_t len) :bytes(b), length(len) { }
3.36 + Blob (const char *str);
3.37 + const void* end() const {return (const uint8_t*)bytes+length;}
3.38 +
3.39 + operator bool() const {return bytes!=NULL;}
3.40 + bool operator== (const Blob &b) {return bytes==b.bytes && length==b.length;}
3.41 + bool equals (const Blob &b) const {return length==b.length && memcmp(bytes,b.bytes,length)==0;}
3.42 + void clear() {bytes=NULL; length=0;}
3.43 + };
3.44 +
3.45 +
3.46 + // Utility to offset a pointer by some number of bytes.
3.47 + inline const void* offsetBy(const void *src, size_t off) {return (const uint8_t*)src + off;}
3.48 + inline void* offsetBy(void *src, size_t off) {return (uint8_t*)src + off;}
3.49 +
3.50 +
3.51 + #define UNCOPYABLE(CLASS) private: CLASS(const CLASS&); CLASS& operator=(const CLASS&)
3.52 +
3.53 +
3.54 +#pragma mark -
3.55 +#pragma mark LITTLE-ENDIAN:
3.56 +
3.57 + /** A template for numeric types that are always stored in little-endian form.
3.58 + Useful for structures stored in files that need to be useable on all architectures. */
3.59 + template <typename INT, typename REP=INT>
3.60 + class LittleEndian {
3.61 + public:
3.62 + inline LittleEndian ();
3.63 + inline LittleEndian (INT);
3.64 + inline operator INT() const;
3.65 + inline LittleEndian& operator= (INT);
3.66 + inline LittleEndian& operator= (const LittleEndian&);
3.67 + inline LittleEndian& operator++();
3.68 + inline LittleEndian& operator--();
3.69 + private:
3.70 + static inline REP makeLittle (INT);
3.71 + static inline INT makeNative (REP);
3.72 + REP _value;
3.73 + };
3.74 +
3.75 + typedef LittleEndian<double,CFSwappedFloat64> LittleEndianDouble;
3.76 +
3.77 +
3.78 + // Implementation gunk:
3.79 + template <typename INT, typename REP>
3.80 + inline LittleEndian<INT,REP>::LittleEndian () :_value() { }
3.81 + template <typename INT, typename REP>
3.82 + inline LittleEndian<INT,REP>::LittleEndian (INT i) :_value(makeLittle(i)) { }
3.83 + template <typename INT, typename REP>
3.84 + inline LittleEndian<INT,REP>::operator INT() const {return makeNative(_value);}
3.85 + template <typename INT, typename REP>
3.86 + inline LittleEndian<INT,REP>& LittleEndian<INT,REP>::operator++() {return *this = (INT)*this + 1;}
3.87 + template <typename INT, typename REP>
3.88 + inline LittleEndian<INT,REP>& LittleEndian<INT,REP>::operator--() {return *this = (INT)*this - 1;}
3.89 +
3.90 + template <typename INT, typename REP>
3.91 + inline LittleEndian<INT,REP>& LittleEndian<INT,REP>::operator= (INT i) {
3.92 + _value = makeLittle(i);
3.93 + return *this;
3.94 + }
3.95 + template <typename INT, typename REP>
3.96 + inline LittleEndian<INT,REP>& LittleEndian<INT,REP>::operator= (const LittleEndian<INT,REP> &p) {
3.97 + _value = p._value;
3.98 + return *this;
3.99 + }
3.100 +
3.101 + template <> inline uint32_t LittleEndian<uint32_t>::makeLittle (uint32_t i)
3.102 + {return OSSwapHostToLittleInt32(i);}
3.103 + template <> inline uint32_t LittleEndian<uint32_t>::makeNative (uint32_t i)
3.104 + {return OSSwapLittleToHostInt32(i);}
3.105 + template <> inline uint16_t LittleEndian<uint16_t>::makeLittle (uint16_t i)
3.106 + {return OSSwapHostToLittleInt16(i);}
3.107 + template <> inline uint16_t LittleEndian<uint16_t>::makeNative (uint16_t i)
3.108 + {return OSSwapLittleToHostInt16(i);}
3.109 + template <> inline CFSwappedFloat64 LittleEndian<double,CFSwappedFloat64>::makeLittle (double d)
3.110 + {return CFConvertDoubleHostToSwapped(d);}
3.111 + template <> inline double LittleEndian<double,CFSwappedFloat64>::makeNative (CFSwappedFloat64 d)
3.112 + {return CFConvertDoubleSwappedToHost(d);}
3.113 +
3.114 +}
3.115 +
3.116 +#endif _MOOSEYARD_BASE_
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/include/Chunk.h Sun Sep 20 15:14:12 2009 -0700
4.3 @@ -0,0 +1,97 @@
4.4 +/*
4.5 + * Chunk.h
4.6 + * Ottoman
4.7 + *
4.8 + * Created by Jens Alfke on 8/27/09.
4.9 + * Copyright 2009 Jens Alfke. All rights reserved.
4.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
4.11 + */
4.12 +
4.13 +#ifndef _MOOSEYARD_CHUNK_
4.14 +#define _MOOSEYARD_CHUNK_
4.15 +#include "File.h"
4.16 +
4.17 +namespace Mooseyard {
4.18 +
4.19 + class KeyValueChunk;
4.20 +
4.21 +#pragma pack(2)
4.22 +
4.23 + /** An item stored in a file. It's prefixed with its length, so that the entire file
4.24 + can be scanned for chunks easily. */
4.25 + class Chunk {
4.26 + public:
4.27 + uint32_t size() const {return _size;}
4.28 + uint16_t type() const;
4.29 +
4.30 + /** If this is a KeyValueChunk, returns itself cast to that type, else NULL. */
4.31 + const KeyValueChunk* asKeyValue() const;
4.32 +
4.33 + /** Write a Chunk to the file, in pieces a la writev. */
4.34 + static size_t writeMultiple (File *file, uint16_t type,
4.35 + Blob blobs[], int count) throw(File::Error);
4.36 +
4.37 + static size_t writePadding (File *file);
4.38 +
4.39 + static const uint16_t kChunkTypePadding = 0;
4.40 +
4.41 + const void* end() const {return offsetBy(this,_size);}
4.42 +
4.43 + protected:
4.44 + Chunk (uint32_t size, uint16_t type) :_size(size), _keyLength(0xFFFF), _type(type) { }
4.45 +
4.46 + private:
4.47 + // This is mapped to data in the file! Don't mess with it!
4.48 + LittleEndian<uint32_t> _size;
4.49 + LittleEndian<uint16_t> _keyLength; // Used by KeyValueChunk; else 0xFFFF
4.50 + LittleEndian<uint16_t> _type; // Not used by KeyValueChunk
4.51 + friend class KeyValueChunk;
4.52 + };
4.53 +
4.54 +
4.55 + /** A key/value pair as stored in the memory-mapped file. */
4.56 + class KeyValueChunk :public Chunk {
4.57 + public:
4.58 + Blob key() const;
4.59 + Blob value() const;
4.60 +
4.61 + bool hasKey (Blob key) const;
4.62 +
4.63 + void validate() const throw(File::Error);
4.64 +
4.65 + /** Write a KeyValueChunk to a file. */
4.66 + static size_t write (File* file, FilePosition pos, Blob key, Blob value) throw(File::Error);
4.67 +
4.68 + static const uint16_t kChunkType = 1;
4.69 +
4.70 + private:
4.71 + const char* valuePtr() const;
4.72 + };
4.73 +
4.74 +#pragma options align=reset
4.75 +
4.76 +
4.77 + /** An iterator over all the Chunks in a file. */
4.78 + class ChunkIterator {
4.79 + public:
4.80 + ChunkIterator (File*, FilePosition start);
4.81 +
4.82 + const Chunk* chunk() const {return _chunk;}
4.83 + FilePosition position() const {return _pos;}
4.84 + bool atEOF() const;
4.85 + bool next();
4.86 +
4.87 + operator const Chunk*() const {return _chunk;}
4.88 + virtual bool hasValue() const {return _chunk != NULL;}
4.89 + operator bool() const {return hasValue();}
4.90 + ChunkIterator& operator++() {next(); return *this;}
4.91 + private:
4.92 + void _loadChunk();
4.93 + File *_file;
4.94 + FilePosition _pos, _length;
4.95 + const Chunk* _chunk;
4.96 + };
4.97 +
4.98 +}
4.99 +
4.100 +#endif _MOOSEYARD_CHUNK_
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/include/Dictionary.h Sun Sep 20 15:14:12 2009 -0700
5.3 @@ -0,0 +1,208 @@
5.4 +/*
5.5 + * Dictionary.h
5.6 + * Ottoman
5.7 + *
5.8 + * Created by Jens Alfke on 8/23/09.
5.9 + * Copyright 2009 Jens Alfke. All rights reserved.
5.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
5.11 + */
5.12 +
5.13 +#ifndef _MOOSEYARD_DICTIONARY_
5.14 +#define _MOOSEYARD_DICTIONARY_
5.15 +#include "Base.h"
5.16 +
5.17 +namespace Mooseyard {
5.18 +
5.19 + typedef uint32_t HashCode;
5.20 +
5.21 + /** A Key is a data blob treated as a dictionary key.
5.22 + It carries its hash-code around with it, to avoid redundant computation. */
5.23 + struct Key :public Blob {
5.24 + HashCode hash;
5.25 +
5.26 + Key () :Blob(), hash(0) { }
5.27 + explicit Key (const Blob &b) :Blob(b), hash(computeHash(b)) { }
5.28 + Key (const Blob &b, HashCode h) :Blob(b), hash(h) { }
5.29 + Key (const char *str) :Blob(str), hash(computeHash(*this)) { }
5.30 + Key (const void *b, uint32_t len, HashCode h) :Blob(b,len), hash(h) { }
5.31 +
5.32 + static HashCode computeHash (Blob);
5.33 + };
5.34 +
5.35 +
5.36 + /** An abstract interface for key/value dictionaries.
5.37 + Dictionary itself is read-only; its subclass MutableDictionary allows changes. */
5.38 + class Dictionary {
5.39 + public:
5.40 + class Iterator;
5.41 + class ChangeIterator;
5.42 +
5.43 + virtual ~Dictionary();
5.44 +
5.45 + /** The number of items in the dictionary. */
5.46 + virtual int count() const =0;
5.47 +
5.48 + /** Returns the value associated with the given key.
5.49 + Keys are compared by exact binary data equality.
5.50 + The data pointed to by the value returned is valid at least until the next call to
5.51 + this Dictionary; some subclasses may guarantee a longer lifetime.
5.52 + If there is no value for the given key, a Blob of {NULL, 0} will be returned. */
5.53 + virtual Blob get (Key) const =0;
5.54 +
5.55 + /** Returns true iff there is a value associated with the given key. */
5.56 + virtual bool contains (Key key) const {return get(key).bytes != NULL;}
5.57 +
5.58 + /** Returns a pointer to a new Iterator object that can be used to iterate this Dictionary.
5.59 + The iterator must be deleted when you're done with it. */
5.60 + virtual Iterator* iterate() const =0;
5.61 +
5.62 + /** A singleton empty Dictionary. */
5.63 + static const Dictionary& kEmpty;
5.64 +
5.65 + // utilities
5.66 + /** Returns a suggested size for a hash table that can hold 'capacity' items without
5.67 + being more than the 'load' fraction full; result is always a power of two. */
5.68 + static int choosePowerOfTwoSize (int capacity, float load = kMaxLoadFactor);
5.69 +
5.70 + static int chooseAnyOldSize (int capacity, float load = kMaxLoadFactor);
5.71 +
5.72 + static const int kMinSize;
5.73 + static const float kMinLoadFactor;
5.74 + static const float kMaxLoadFactor;
5.75 +
5.76 + protected:
5.77 + Dictionary();
5.78 + };
5.79 +
5.80 +
5.81 + /** An abstract interface for mutable key/value dictionaries; extends Dictionary. */
5.82 + class MutableDictionary : public Dictionary {
5.83 + public:
5.84 + /** Stores the given value for the given key, replacing any prior value.
5.85 + The memory for the key and value is copied, so you don't need to preserve it after
5.86 + the call returns. */
5.87 + virtual void put (Key, Blob value) =0;
5.88 +
5.89 + /** Adds the contents of the given Dictionary to this one.
5.90 + Effectively calls this->put() with every key/value pair in the source Dictionary. */
5.91 + virtual void add (Dictionary*);
5.92 +
5.93 + /** Removes the value for the given key, if any.
5.94 + Returns true if the value was removed, false if there was no value. */
5.95 + virtual bool remove (Key) =0;
5.96 +
5.97 + /** Removes all keys and values, returning the dictionary to an empty state. */
5.98 + virtual void removeAll() = 0;
5.99 + };
5.100 +
5.101 +
5.102 + /** Abstract iterator interface. Each Dictionary subclass defines its own.
5.103 + The order in which items are returned is undefined, and in effect quite random, due to
5.104 + the properties of hash tables. */
5.105 + class Dictionary::Iterator {
5.106 + public:
5.107 + virtual ~Iterator();
5.108 +
5.109 + /** The current key the iterator is pointing to. */
5.110 + virtual Key key() const =0;
5.111 + /** The current value the iterator is pointing to. */
5.112 + virtual Blob value() const =0;
5.113 + /** Returns true if the iterator has a current item, or false if it's reached the end. */
5.114 + virtual bool hasValue() const {return key().bytes != 0;}
5.115 + /** Advances the Iterator to the next item. Returns false if it's reached the end.
5.116 + (Note that the order of items is undefined and in practice quite random.) */
5.117 + virtual bool next() =0;
5.118 +
5.119 + operator bool() const {return hasValue();}
5.120 + Iterator& operator++() {next(); return *this;}
5.121 + };
5.122 +
5.123 + class OverlayDictionary;
5.124 +
5.125 +
5.126 + /** An iterator that walks through the differences between two Dictionaries. */
5.127 + class Dictionary::ChangeIterator :public Dictionary::Iterator {
5.128 + public:
5.129 + ChangeIterator (const Dictionary *dict1, const Dictionary *dict2);
5.130 + explicit ChangeIterator (const OverlayDictionary*);
5.131 + virtual ~ChangeIterator();
5.132 +
5.133 + /** Returns the current key, whose values in the two dictionaries differ. */
5.134 + virtual Key key() const {return _iter->key();}
5.135 + /** Returns the corresponding value from dict1.
5.136 + May be empty (NULL,0) if the key does not appear in dict1 (i.e. inserted into dict2.) */
5.137 + virtual Blob value() const {return _iter->value();}
5.138 + /** Returns the corresponding value from dict2.
5.139 + May be empty (NULL,0) if the key does not appear in dict2 (i.e. deleted from dict2.) */
5.140 + virtual Blob otherValue() const {return _otherValue;}
5.141 + virtual bool hasValue() const {return _iter->hasValue();}
5.142 + virtual bool next();
5.143 +
5.144 + private:
5.145 + void _init (const Dictionary *dict1, const Dictionary *dict2);
5.146 + bool _skipMatching();
5.147 + const Dictionary *_dict2;
5.148 + Iterator *_iter;
5.149 + Blob _otherValue;
5.150 + };
5.151 +
5.152 +
5.153 + /** Adapter class that allows a Dictionary to appear to be mutable, by using a separate
5.154 + mutable dictionary to remember the changes. */
5.155 + class OverlayDictionary :public MutableDictionary {
5.156 + public:
5.157 + /** Creates a mutable dictionary that overlays base. Initially its contents will appear
5.158 + identical to base. It can be changed, but the changes will not affect the base. */
5.159 + explicit OverlayDictionary (const Dictionary *base);
5.160 + virtual ~OverlayDictionary();
5.161 +
5.162 + /** The base dictionary this is overlaying. */
5.163 + const Dictionary* base() const {return _base;}
5.164 + /** The dictionary that contains the changes made to the base.
5.165 + Only keys/values that have been changed appear here. */
5.166 + const Dictionary* overlay() const {return _overlay;}
5.167 + /** Returns true if changes have been made. */
5.168 + bool isChanged() const;
5.169 + /** Returns true if the base has been completely replaced by calling removeAll. */
5.170 + bool baseReplaced() const {return _allRemoved;}
5.171 +
5.172 + /** Removes all changes, restoring the overlay to look identical to the base. */
5.173 + void revert();
5.174 + /** Changes the overlay to a new base, clearing all changes. */
5.175 + void revertTo (const Dictionary* newBase);
5.176 +
5.177 + /** Changes the base without clearing changes. */
5.178 + void rebase (const Dictionary* newBase);
5.179 +
5.180 + virtual int count() const;
5.181 + virtual Blob get (Key) const;
5.182 + virtual bool contains (Key) const;
5.183 + virtual void put (Key, Blob value);
5.184 + virtual bool remove (Key);
5.185 + virtual void removeAll();
5.186 + virtual Iterator* iterate() const {return new Iterator(*this);}
5.187 +
5.188 + class Iterator :public Dictionary::Iterator {
5.189 + public:
5.190 + explicit Iterator (const OverlayDictionary&);
5.191 + virtual Key key() const;
5.192 + virtual Blob value() const;
5.193 + virtual bool next();
5.194 + private:
5.195 + bool skipCurrentState();
5.196 + Dictionary::Iterator *_iter;
5.197 + const MutableDictionary *_overlay;
5.198 + };
5.199 +
5.200 + private:
5.201 + const Dictionary *_base;
5.202 + MutableDictionary *_overlay;
5.203 + int _count;
5.204 + bool _allRemoved;
5.205 + friend class ChangeIterator;
5.206 + };
5.207 +
5.208 +
5.209 +}
5.210 +
5.211 +#endif _MOOSEYARD_DICTIONARY_
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/include/File.h Sun Sep 20 15:14:12 2009 -0700
6.3 @@ -0,0 +1,107 @@
6.4 +/*
6.5 + * File.h
6.6 + * Ottoman
6.7 + *
6.8 + * Created by Jens Alfke on 8/20/09.
6.9 + * Copyright 2009 Jens Alfke. All rights reserved.
6.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
6.11 + */
6.12 +
6.13 +#ifndef _MOOSEYARD_FILE_
6.14 +#define _MOOSEYARD_FILE_
6.15 +#include "Base.h"
6.16 +
6.17 +namespace Mooseyard {
6.18 +
6.19 +struct Blob;
6.20 +class MemoryMap;
6.21 +
6.22 +/** An open file on disk; a thin wrapper around a Unix file descriptor. */
6.23 +class File {
6.24 +public:
6.25 +
6.26 + struct Error {
6.27 + const int code;
6.28 + const char* const message;
6.29 +
6.30 + Error(int c, const char *m) :code(c), message(m) { }
6.31 + Error(const char *m);
6.32 + };
6.33 + static const int kEOF = 10001;
6.34 +
6.35 +
6.36 + File (const char *filename, bool writeable =false, bool create =false) throw(Error);
6.37 + File (const char *filename, int oflag) throw(Error);
6.38 + ~File();
6.39 +
6.40 + off_t length() const throw(Error);
6.41 + void setLength (off_t) throw(Error);
6.42 +
6.43 + off_t position() const throw(Error);
6.44 + void setPosition (off_t) throw(Error);
6.45 + off_t setPositionToEnd (off_t bytesBefore =0) throw(Error);
6.46 +
6.47 + void read (void *dst, size_t) throw(Error);
6.48 + size_t write (const void *src, size_t) throw(Error);
6.49 +
6.50 + void readFrom (off_t where, void *dst, size_t) throw(Error);
6.51 + void writeTo (off_t where, const void *src, size_t) throw(Error);
6.52 +
6.53 + size_t writeMultiple (Blob blobs[], int count) throw(Error);
6.54 + size_t writePadding (int alignment); // alignment should be a power of 2
6.55 +
6.56 + MemoryMap* map();
6.57 + const MemoryMap* map() const {return const_cast<File*>(this)->map();}
6.58 + void mapRegion (off_t position, size_t length);
6.59 + const void* mappedPosition (off_t position) const;
6.60 +
6.61 + void flush() throw(Error); // Regular fsync call
6.62 + void flushDisk() throw(Error); // Expensive F_FULLFSYNC call
6.63 +
6.64 + template <typename T>
6.65 + void read (T& t) throw(Error) {read(&t,sizeof(t));}
6.66 + template <typename T>
6.67 + size_t write (const T& t) throw(Error) {return write(&t,sizeof(t));}
6.68 + template <typename T>
6.69 + void readFrom (off_t where, T &t) throw(Error) {readFrom(where,&t,sizeof(t));}
6.70 + template <typename T>
6.71 + void writeTo (off_t where, const T &t) throw(Error) {writeTo(where,&t,sizeof(t));}
6.72 +
6.73 + bool hasPath (const char *path) const throw(Error);
6.74 +
6.75 + static void unlink (const char *filename) throw(Error);
6.76 + static void rename (const char *srcFilename, const char *dstFilename) throw(Error);
6.77 +
6.78 +
6.79 + class Lock {
6.80 + public:
6.81 + Lock (File*, bool block =true) throw(Error);
6.82 + ~Lock();
6.83 + bool isLocked() const {return _locked;}
6.84 + operator bool() const {return _locked;}
6.85 + bool retry();
6.86 + private:
6.87 + UNCOPYABLE(Lock);
6.88 + File *_file;
6.89 + int _mode;
6.90 + bool _locked;
6.91 + };
6.92 +
6.93 +private:
6.94 + static int _open (const char *filename, int posixMode) throw(Error);
6.95 + static int _check (int result) throw(Error);
6.96 + static void _checkRead (ssize_t result, size_t expectedSize) throw(Error);
6.97 + bool _lock (bool block);
6.98 + void _unlock();
6.99 + UNCOPYABLE(File);
6.100 +
6.101 + const int _fd;
6.102 + mutable MemoryMap *_memoryMap;
6.103 + int _locked;
6.104 + friend class Lock;
6.105 + friend class MemoryMap;
6.106 +};
6.107 +
6.108 +}
6.109 +
6.110 +#endif _MOOSEYARD_FILE_
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/include/Hash.h Sun Sep 20 15:14:12 2009 -0700
7.3 @@ -0,0 +1,119 @@
7.4 +/*
7.5 + * Hash.h
7.6 + * Ottoman
7.7 + *
7.8 + * Created by Jens Alfke on 8/20/09.
7.9 + * Copyright 2009 Jens Alfke. All rights reserved.
7.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
7.11 + */
7.12 +
7.13 +#ifndef _MOOSEYARD_HASH_
7.14 +#define _MOOSEYARD_HASH_
7.15 +#include "Base.h"
7.16 +#include "Dictionary.h"
7.17 +
7.18 +namespace Mooseyard {
7.19 +
7.20 + /** A fairly low-level hash-table class whose keys and values are arbitrary data blobs.
7.21 + This class does no memory management of the keys and values: the memory ranges
7.22 + pointed to by the key and value parameters to put() must remain valid as long as
7.23 + that key or value remains in the hash-table. */
7.24 + class Hash {
7.25 +
7.26 + public:
7.27 + typedef void* Value;
7.28 +
7.29 + /** Creates a new, empty Hash. */
7.30 + explicit Hash (int capacity = 50);
7.31 +
7.32 + ~Hash();
7.33 +
7.34 + /** Gets the value associated with the given key. */
7.35 + Value get(Key) const;
7.36 + Value operator[] (Key key) const {return get(key);}
7.37 +
7.38 + /** Returns the number of values in the Hash. */
7.39 + int count() const {return _count;}
7.40 +
7.41 + /** Sets the given value for the given key, replacing any existing value. */
7.42 + void put(Key, Value);
7.43 +
7.44 + /** Removes the value with the given key. */
7.45 + bool remove(Key);
7.46 +
7.47 + /** Removes all values. */
7.48 + void removeAll();
7.49 +
7.50 + void dump() const;
7.51 +
7.52 + class IndexEntry;
7.53 +
7.54 + class Iterator {
7.55 + public:
7.56 + Iterator (const Hash *h);
7.57 + Iterator (const Hash &h);
7.58 + operator bool() const {return hasValue();}
7.59 + Value operator*() const {return value();}
7.60 + Iterator& operator++() {next(); return *this;}
7.61 +
7.62 + Key key() const;
7.63 + Value value() const;
7.64 + bool hasValue() const {return _entry < _end;}
7.65 + bool next();
7.66 + private:
7.67 + Iterator (IndexEntry *start, IndexEntry*end);
7.68 + IndexEntry* _entry;
7.69 + IndexEntry* const _end;
7.70 + UNCOPYABLE(Iterator);
7.71 + };
7.72 +
7.73 + private:
7.74 + IndexEntry& _find (Key key) const;
7.75 + IndexEntry& _findForPut (const IndexEntry &newEntry);
7.76 + void _resize(int newSize);
7.77 + void _read();
7.78 + UNCOPYABLE(Hash);
7.79 +
7.80 + int _count;
7.81 + int _tableSize;
7.82 + IndexEntry *_table;
7.83 +
7.84 + friend class Iterator;
7.85 + };
7.86 +
7.87 +
7.88 +
7.89 + /** A concrete Dictionary implemented with a Hash. */
7.90 + class HashDictionary :public MutableDictionary {
7.91 + public:
7.92 + explicit HashDictionary (int capacity =50) :_hash(capacity) { }
7.93 + virtual ~HashDictionary();
7.94 + virtual int count() const {return _hash.count();}
7.95 + virtual bool contains (Key) const;
7.96 + virtual Blob get (Key key) const {return _convertValue(_hash.get(key));}
7.97 + virtual void put (Key, Blob value);
7.98 + virtual bool remove (Key);
7.99 + virtual void removeAll();
7.100 + virtual Iterator* iterate() const {return new Iterator(*this);}
7.101 +
7.102 + class Iterator :public Dictionary::Iterator {
7.103 + public:
7.104 + explicit Iterator (const HashDictionary &d) :_it(d._hash) { }
7.105 + virtual Key key() const {return _it.key();}
7.106 + virtual Blob value() const {return _convertValue(_it.value());}
7.107 + virtual bool hasValue() const {return _it.hasValue();}
7.108 + virtual bool next() {return _it.next();}
7.109 + private:
7.110 + Hash::Iterator _it;
7.111 + };
7.112 +
7.113 + private:
7.114 + static Blob _convertValue (void*);
7.115 + Hash _hash;
7.116 + friend class Iterator;
7.117 + };
7.118 +
7.119 +
7.120 +}
7.121 +
7.122 +#endif _MOOSEYARD_HASH_
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/include/Index.h Sun Sep 20 15:14:12 2009 -0700
8.3 @@ -0,0 +1,76 @@
8.4 +/*
8.5 + * Index.h
8.6 + * Ottoman
8.7 + *
8.8 + * Created by Jens Alfke on 8/27/09.
8.9 + * Copyright 2009 Jens Alfke. All rights reserved.
8.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
8.11 + */
8.12 +
8.13 +#ifndef _MOOSEYARD_INDEX_
8.14 +#define _MOOSEYARD_INDEX_
8.15 +#include "Chunk.h"
8.16 +#include "Dictionary.h"
8.17 +
8.18 +namespace Mooseyard {
8.19 +
8.20 + class KeyValueChunk;
8.21 +
8.22 + /** An in-file hash table. This structure is stored directly in the file, memory-mapped.
8.23 + Index is normally only used internally by VersionDictionary. */
8.24 + class Index :public Chunk {
8.25 + public:
8.26 +
8.27 + class Entry;
8.28 +
8.29 + static const Index* indexMappedAt (const void*);
8.30 + static Index* create (int capacity);
8.31 +
8.32 + int count() const {return _count;}
8.33 +
8.34 + Blob get (File *file, Key) const;
8.35 + bool put (File *file, Key, FilePosition valuePosition, FilePosition maxPosition);
8.36 + bool remove (File *file, Key, FilePosition maxPosition);
8.37 + void removeAll();
8.38 +
8.39 + void copyFrom (File *file, const Index *index);
8.40 +
8.41 + class Iterator;
8.42 +
8.43 + void validate() const throw(File::Error);
8.44 + void validateEntries (const File *file) const throw(File::Error);
8.45 + static const uint16_t kChunkType = 2;
8.46 +
8.47 + private:
8.48 + Index (uint32_t tableSize);
8.49 + const Entry* table (int index) const;
8.50 + Entry* table (int index);
8.51 + const KeyValueChunk* _find (File *file, Key) const;
8.52 + bool _put (File *file, Key, FilePosition, FilePosition maxPosition);
8.53 +
8.54 + // This is mapped to data in the file! Don't mess with it!
8.55 + LittleEndian<uint32_t> _magicNumber;
8.56 + LittleEndian<uint32_t> _count;
8.57 + LittleEndian<uint32_t> _tableSize;
8.58 + char _table[0]; // Actually Entry[]
8.59 + };
8.60 +
8.61 +
8.62 +
8.63 + class Index::Iterator :public Dictionary::Iterator {
8.64 + public:
8.65 + Iterator (File*, const Index*);
8.66 + virtual Key key() const;
8.67 + virtual Blob value() const;
8.68 + virtual bool next();
8.69 + virtual bool hasValue() const;
8.70 +
8.71 + FilePosition valuePosition();
8.72 + private:
8.73 + File* const _file;
8.74 + const Index::Entry *_current, *_end;
8.75 + };
8.76 +
8.77 +}
8.78 +
8.79 +#endif //_MOOSEYARD_INDEX_
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/include/MemoryMap.h Sun Sep 20 15:14:12 2009 -0700
9.3 @@ -0,0 +1,53 @@
9.4 +/*
9.5 + * MemoryMap.h
9.6 + * Ottoman
9.7 + *
9.8 + * Created by Jens Alfke on 9/17/09.
9.9 + * Copyright 2009 Jens Alfke. All rights reserved.
9.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
9.11 + */
9.12 +
9.13 +#include "File.h"
9.14 +
9.15 +namespace Mooseyard {
9.16 +
9.17 + /** A flexible memory-map on a file, which can handle multiple discontiguous mapped regions.
9.18 + Clients usually access this functionality through File, which delegates to it. */
9.19 + class MemoryMap {
9.20 + public:
9.21 + MemoryMap (File* file) :_file(file), _nRegions(0), _regions(NULL) { }
9.22 + ~MemoryMap();
9.23 +
9.24 + void mapRegion (off_t position, size_t length);
9.25 + const void* mappedPosition (off_t position) const;
9.26 +
9.27 + private:
9.28 + UNCOPYABLE(MemoryMap);
9.29 + class Region;
9.30 + const void* _at (off_t) const;
9.31 +
9.32 + File *_file;
9.33 + int _nRegions;
9.34 + Region **_regions;
9.35 + };
9.36 +
9.37 +
9.38 + class MemoryMap::Region {
9.39 + public:
9.40 + Region (File*, off_t position, size_t length);
9.41 + ~Region();
9.42 + off_t position() const {return _position;}
9.43 + size_t length() const {return _length;}
9.44 + off_t end() const {return _position + _length;}
9.45 + bool setLength (size_t); // Returns false if it failed
9.46 + const void* mappedPosition(off_t);
9.47 + private:
9.48 + UNCOPYABLE(Region);
9.49 + File* const _file;
9.50 + const off_t _position;
9.51 + size_t _length;
9.52 + const uint8_t *_start;
9.53 + };
9.54 +
9.55 +
9.56 +}
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/include/Ottoman.h Sun Sep 20 15:14:12 2009 -0700
10.3 @@ -0,0 +1,99 @@
10.4 +/*
10.5 + * Ottoman.h
10.6 + * Ottoman
10.7 + *
10.8 + * Created by Jens Alfke on 8/31/09.
10.9 + * Copyright 2009 Jens Alfke. All rights reserved.
10.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
10.11 + */
10.12 +
10.13 +#ifndef _MOOSEYARD_OTTOMAN_
10.14 +#define _MOOSEYARD_OTTOMAN_
10.15 +
10.16 +namespace Mooseyard {
10.17 +
10.18 + class ChunkIterator;
10.19 + class Dictionary;
10.20 + class File;
10.21 + class VersionDictionary;
10.22 + class OverlayDictionary;
10.23 +
10.24 +
10.25 + /** A version-controlled persistent dictionary.
10.26 + Each version is stored as a VersionDictionary, unsaved changes as an OverlayDictionary. */
10.27 + class Ottoman {
10.28 + public:
10.29 + /** Creates an "untitled" Ottoman with no file and no lastVersion.
10.30 + After adding values to the currentVersion, use saveAs to save it. */
10.31 + Ottoman ();
10.32 +
10.33 + /** Opens an existing Ottoman file. */
10.34 + explicit Ottoman (const char *filename, bool writeable =true);
10.35 +
10.36 + /** Closes an Ottoman. */
10.37 + virtual ~Ottoman();
10.38 +
10.39 + /** The current filename, or NULL if the receiver is still in the "untitled" state. */
10.40 + virtual const char* filename() const {return _filename;}
10.41 +
10.42 + /** The latest saved version of the dictionary.
10.43 + Earlier versions can be accessed through its previousVersion() accessor.
10.44 + This will be NULL if the receiver is still in the "untitled" state. */
10.45 + virtual VersionDictionary* lastVersion() const {return _lastVersion;}
10.46 +
10.47 + /** A mutable overlay representing the current state of the dictionary.
10.48 + Changes are made in memory until save() is called.
10.49 + This will be NULL if the receiver was opened read-only (writeable=false). */
10.50 + virtual OverlayDictionary* currentVersion() const {return _current;}
10.51 +
10.52 + /** Has the on-disk file been updated with newer revisions than what I know about? */
10.53 + virtual bool needsSync() const;
10.54 +
10.55 + /** Reads any newer versions from disk.
10.56 + Returns true if new versions were read, false if there were none.
10.57 + Afterwards, lastVersion() will return the latest version in the file.
10.58 + (The old lastVersion dictionary is still around, so you can save a pointer to it
10.59 + before the call and use it later to see what changed.)
10.60 + Changes made to the currentVersion dictionary are not lost, but are now relative
10.61 + to the new lastVersion. You may want to scan them and resolve conflicts. */
10.62 + virtual bool sync();
10.63 +
10.64 + /** Saves the current version to the file, by appending.
10.65 + Returns false if there is a version conflict; in that case you need to call sync(),
10.66 + possibly resolve conflicts, and then call save() again. */
10.67 + virtual bool save();
10.68 +
10.69 + /** Saves the current version to the file, by writing to a new temporary file and
10.70 + then atomically replacing the original.
10.71 + Older versions, and older copies of the data, are not preserved, so this
10.72 + will typically shrink the file quite a bit.
10.73 + Returns false if there is a version conflict. */
10.74 + virtual bool saveAndCompact();
10.75 +
10.76 + /** Saves the current version to a new file, leaving the new file open,
10.77 + so subsequent saves will be written to it. */
10.78 + virtual void saveAs (const char *newFilename, bool overwriteAllowed =true);
10.79 +
10.80 + /** Scans the file for damage. Returns true if the file is OK, false if problems are found.
10.81 + If the 'repair' flag is set, will truncate the file to the last valid version. */
10.82 + bool scavenge (bool repair =false);
10.83 +
10.84 + ChunkIterator* chunkIterator() const; // for testing purposes
10.85 +
10.86 + private:
10.87 + Ottoman(const Ottoman&); // forbid copying/assignment
10.88 + Ottoman& operator=(const Ottoman&);
10.89 +
10.90 + void _open();
10.91 + void _append (File *dstFile);
10.92 + File* _writeTo (const char *dstFileName, bool overwriteAllowed);
10.93 +
10.94 + bool _writeable;
10.95 + File *_file;
10.96 + char *_filename;
10.97 + VersionDictionary *_lastVersion;
10.98 + OverlayDictionary *_current;
10.99 + };
10.100 +
10.101 +}
10.102 +#endif // _MOOSEYARD_OTTOMAN_
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/include/VersionDictionary.h Sun Sep 20 15:14:12 2009 -0700
11.3 @@ -0,0 +1,127 @@
11.4 +/*
11.5 + * VersionDictionary.h
11.6 + * Ottoman
11.7 + *
11.8 + * Created by Jens Alfke on 8/21/09.
11.9 + * Copyright 2009 Jens Alfke. All rights reserved.
11.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
11.11 + */
11.12 +
11.13 +#ifndef _MOOSEYARD_VERSIONDICTIONARY_
11.14 +#define _MOOSEYARD_VERSIONDICTIONARY_
11.15 +#include "Dictionary.h"
11.16 +
11.17 +namespace Mooseyard {
11.18 +
11.19 + class File;
11.20 + class Index;
11.21 +
11.22 + /** A persistent Dictionary embedded in a memory-mapped file,
11.23 + representing one complete version of an Ottoman dictionary. */
11.24 + class VersionDictionary :public Dictionary {
11.25 + public:
11.26 +
11.27 + /** The generation number. The first version in a new file is zero. */
11.28 + int generation() const;
11.29 +
11.30 + /** The absolute time at which this version was written to the file. */
11.31 + time_t timestamp() const;
11.32 +
11.33 + /** The previous version, before this one was saved. */
11.34 + const VersionDictionary* previousVersion() const;
11.35 +
11.36 + /** Is this the latest version in the file? */
11.37 + bool isLatestVersion() const;
11.38 +
11.39 + virtual int count() const;
11.40 + virtual Blob get (Key) const;
11.41 + class Iterator;
11.42 + virtual Dictionary::Iterator* iterate() const;
11.43 +
11.44 + class ChangeIterator;
11.45 + /** Iterates over the changes between this dictionary and the previous version. */
11.46 + virtual ChangeIterator* iterateChanges() const;
11.47 +
11.48 +
11.49 + // Stuff you probably won't need to use:
11.50 +
11.51 + File* file() const {return _file;}
11.52 + explicit VersionDictionary (File*);
11.53 + VersionDictionary (File *file, FilePosition trailerPosition);
11.54 +
11.55 + private:
11.56 + /** The type of the trailer chunk that's used as the position of the dictionary. */
11.57 + static const uint16_t kChunkType = 3;
11.58 +
11.59 + struct IndexPositions {
11.60 + LittleEndian<FilePosition> position[256];
11.61 + LittleEndian<FilePosition>& operator[] (int i) {return position[i];}
11.62 + LittleEndian<FilePosition> const& operator[] (int i) const {return position[i];}
11.63 + };
11.64 +
11.65 + class Trailer;
11.66 + const Trailer* _trailer() const;
11.67 + const Index* _index (int i) const;
11.68 + void _read (FilePosition trailerPosition =0);
11.69 + static FilePosition _append (const VersionDictionary *baseDict,
11.70 + const Dictionary *addDict,
11.71 + File *dstFile,
11.72 + bool replace);
11.73 +
11.74 + File *_file;
11.75 + FilePosition _trailerPosition, _previousTrailerPosition;
11.76 + IndexPositions _indexPositions;
11.77 + int _count;
11.78 + mutable const VersionDictionary *_previousVersion;
11.79 +
11.80 +#if VERSIONDICTIONARY_TESTING
11.81 + public:
11.82 +#endif
11.83 + static VersionDictionary* create (File *file, const Dictionary *srcDict);
11.84 + VersionDictionary* byAppending (const Dictionary* d) const {return _appendAndOpen(d,_file,false);}
11.85 + VersionDictionary* byReplacing (const Dictionary* d) const {return _appendAndOpen(d,_file,true);}
11.86 + VersionDictionary* _appendAndOpen (const Dictionary *addDict, File *dstFile, bool replace) const;
11.87 +
11.88 + friend class Ottoman;
11.89 + UNCOPYABLE(VersionDictionary);
11.90 + };
11.91 +
11.92 +
11.93 + class VersionDictionary::Iterator :public Dictionary::Iterator {
11.94 + public:
11.95 + explicit Iterator (const VersionDictionary*);
11.96 + virtual ~Iterator();
11.97 + virtual Key key() const;
11.98 + virtual Blob value() const;
11.99 + virtual bool next();
11.100 + virtual bool hasValue() const;
11.101 + private:
11.102 + bool nextIndex();
11.103 +
11.104 + const VersionDictionary *_file;
11.105 + int _bucket;
11.106 + Dictionary::Iterator *_iter;
11.107 + UNCOPYABLE(Iterator);
11.108 + };
11.109 +
11.110 +
11.111 + class VersionDictionary::ChangeIterator :public Dictionary::Iterator {
11.112 + public:
11.113 + explicit ChangeIterator (const VersionDictionary*);
11.114 + virtual ~ChangeIterator();
11.115 + virtual Key key() const;
11.116 + virtual Blob value() const;
11.117 + virtual bool next();
11.118 + virtual bool hasValue() const;
11.119 + private:
11.120 + bool nextIndex();
11.121 +
11.122 + const VersionDictionary *_file;
11.123 + int _bucket;
11.124 + Dictionary::Iterator *_iter;
11.125 + UNCOPYABLE(ChangeIterator);
11.126 + };
11.127 +
11.128 +}
11.129 +
11.130 +#endif //_MOOSEYARD_VERSIONDICTIONARY_
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/Base.cpp Sun Sep 20 15:14:12 2009 -0700
12.3 @@ -0,0 +1,66 @@
12.4 +/*
12.5 + * Base.cpp
12.6 + * Ottoman
12.7 + *
12.8 + * Created by Jens Alfke on 8/18/09.
12.9 + * Copyright 2009 Jens Alfke. All rights reserved.
12.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
12.11 + */
12.12 +
12.13 +#include "Base.h"
12.14 +#include "File.h"
12.15 +#include <assert.h>
12.16 +#include <errno.h>
12.17 +#include <CoreFoundation/CFUUID.h>
12.18 +
12.19 +namespace Mooseyard {
12.20 +
12.21 +#pragma mark -
12.22 +#pragma mark BLOB:
12.23 +
12.24 + Blob::Blob (const char *str)
12.25 + :bytes(str),
12.26 + length(str ?strlen(str) :0)
12.27 + { }
12.28 +
12.29 + /*
12.30 + struct MutableBlob :public Blob {
12.31 + MutableBlob(void *b, size_t len) :Blob(b,len) { }
12.32 + void* mutableBytes() {return (void*)bytes;}
12.33 + void freeBytes() {::free(mutableBytes()); bytes=NULL; length=0;}
12.34 + };
12.35 + MutableBlob Blob::copyBytes() const {
12.36 + MutableBlob copy( malloc(length), length);
12.37 + memcpy(copy.mutableBytes(), bytes, length);
12.38 + return copy;
12.39 + }
12.40 + */
12.41 +
12.42 +#pragma mark -
12.43 +#pragma mark UUID:
12.44 +
12.45 +#if 0
12.46 + /** Typical 128-bit universally-unique identifier. */
12.47 + class UUID {
12.48 + public:
12.49 + UUID();
12.50 + const void *bytes() const {return _bytes;}
12.51 + bool operator== (const UUID&) const;
12.52 + private:
12.53 + uint8_t _bytes[16];
12.54 + };
12.55 +
12.56 +
12.57 + UUID::UUID() {
12.58 + CFUUIDRef u = CFUUIDCreate(NULL);
12.59 + CFUUIDBytes bytes = CFUUIDGetUUIDBytes(u);
12.60 + memcpy(&_bytes, &bytes, sizeof(_bytes));
12.61 + CFRelease(u);
12.62 + }
12.63 +
12.64 + bool UUID::operator== (const UUID& u) const {
12.65 + return memcmp(_bytes, u._bytes, sizeof(_bytes)) == 0;
12.66 + }
12.67 +#endif
12.68 +
12.69 +}
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/src/Chunk.cpp Sun Sep 20 15:14:12 2009 -0700
13.3 @@ -0,0 +1,135 @@
13.4 +/*
13.5 + * Chunk.cpp
13.6 + * Ottoman
13.7 + *
13.8 + * Created by Jens Alfke on 8/27/09.
13.9 + * Copyright 2009 Jens Alfke. All rights reserved.
13.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
13.11 + */
13.12 +
13.13 +#include "Chunk.h"
13.14 +#include <assert.h>
13.15 +#include <errno.h>
13.16 +#include <stddef.h>
13.17 +
13.18 +namespace Mooseyard {
13.19 +
13.20 + uint16_t Chunk::type() const {
13.21 + return _keyLength == 0xFFFF ?(uint16_t)_type :KeyValueChunk::kChunkType;
13.22 + }
13.23 +
13.24 + const KeyValueChunk* Chunk::asKeyValue() const {
13.25 + return _keyLength == 0xFFFF ?NULL :(const KeyValueChunk*)this;
13.26 + }
13.27 +
13.28 + size_t Chunk::writeMultiple (File *file, uint16_t type,
13.29 + Blob blobs[], int count) throw(File::Error) {
13.30 + assert(type != KeyValueChunk::kChunkType);
13.31 + Blob nuBlobs[count+1];
13.32 + uint32_t size = sizeof(Chunk);
13.33 + for (int i=0; i<count; i++) {
13.34 + nuBlobs[i+1] = blobs[i];
13.35 + size += blobs[i].length;
13.36 + }
13.37 + Chunk chunk(size, type);
13.38 + nuBlobs[0] = Blob(&chunk, sizeof(chunk));
13.39 + return file->writeMultiple(nuBlobs, count+1);
13.40 + }
13.41 +
13.42 + size_t Chunk::writePadding (File *file) {
13.43 + int padding = file->position() & 0x03;
13.44 + if (padding == 0)
13.45 + return 0;
13.46 + else {
13.47 + padding = 4 - padding;
13.48 + uint32_t zero = 0;
13.49 + Blob pad(&zero, padding);
13.50 + return writeMultiple(file, kChunkTypePadding, &pad, 1);
13.51 + }
13.52 + }
13.53 +
13.54 +
13.55 +
13.56 + void KeyValueChunk::validate() const throw(File::Error) {
13.57 + if (_keyLength >= 0xFFFFU)
13.58 + throw File::Error(ERANGE, "Invalid key length (0xFFFF)");
13.59 + if (valuePtr() > end())
13.60 + throw File::Error(ERANGE, "Bad KeyValueChunk (key-length too large to fit)");
13.61 + }
13.62 +
13.63 + Blob KeyValueChunk::key() const {
13.64 + return Blob(&_keyLength +1, _keyLength); // KeyValueChunk doesn't have _type
13.65 + }
13.66 +
13.67 + const char* KeyValueChunk::valuePtr() const {
13.68 + size_t vptr = (size_t) key().end();
13.69 + vptr = (vptr+3) & ~3; // 4-byte align
13.70 + return (const char*)vptr;
13.71 + }
13.72 +
13.73 + Blob KeyValueChunk::value() const {
13.74 + const char *vp = valuePtr();
13.75 + return Blob(vp, (const char*)end()-vp);
13.76 + }
13.77 +
13.78 + bool KeyValueChunk::hasKey (Blob key) const {
13.79 + return key.length==_keyLength
13.80 + && memcmp(key.bytes, &_keyLength +1, key.length)==0;
13.81 + }
13.82 +
13.83 + size_t KeyValueChunk::write (File* file, FilePosition pos, Blob key, Blob value) throw(File::Error) {
13.84 + if (key.length >= 0xFFFFU)
13.85 + throw File::Error(ERANGE, "Key too long (>=64k)");
13.86 + uint16_t keyLength = key.length;
13.87 + uint32_t size = sizeof(uint32_t) + sizeof(uint16_t) + keyLength;
13.88 + size_t pad = (pos + size) & 0x3;
13.89 + if (pad)
13.90 + pad = 4-pad;
13.91 + uint32_t zeros = 0;
13.92 + size += pad + value.length;
13.93 +
13.94 + Chunk chunk(size, KeyValueChunk::kChunkType);
13.95 + chunk._keyLength = keyLength;
13.96 + Blob b[4] = {
13.97 + Blob(&chunk, sizeof(chunk._size)+sizeof(chunk._keyLength)),
13.98 + key,
13.99 + Blob(&zeros, pad),
13.100 + value};
13.101 + return file->writeMultiple(b,4);
13.102 + }
13.103 +
13.104 +
13.105 +
13.106 + ChunkIterator::ChunkIterator (File* file, FilePosition start)
13.107 + :_file(file),
13.108 + _pos(start),
13.109 + _length(_file->length()),
13.110 + _chunk(NULL)
13.111 + {
13.112 + _loadChunk();
13.113 + }
13.114 +
13.115 + void ChunkIterator::_loadChunk() {
13.116 + if (_pos < _length) {
13.117 + _chunk = (const Chunk*) _file->mappedPosition(_pos);
13.118 + if (_chunk->size() < sizeof(Chunk) || _pos+_chunk->size() > _length)
13.119 + _chunk = NULL;
13.120 + } else {
13.121 + _chunk = NULL;
13.122 + }
13.123 +
13.124 + }
13.125 +
13.126 + bool ChunkIterator::atEOF() const {
13.127 + return _pos == _length;
13.128 + }
13.129 +
13.130 + bool ChunkIterator::next() {
13.131 + if (_chunk) {
13.132 + _pos += _chunk->size();
13.133 + _loadChunk();
13.134 + }
13.135 + return _chunk != NULL;
13.136 + }
13.137 +
13.138 +}
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/src/Dictionary.cpp Sun Sep 20 15:14:12 2009 -0700
14.3 @@ -0,0 +1,376 @@
14.4 +/*
14.5 + * Dictionary.cpp
14.6 + * Ottoman
14.7 + *
14.8 + * Created by Jens Alfke on 8/23/09.
14.9 + * Copyright 2009 Jens Alfke. All rights reserved.
14.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
14.11 + */
14.12 +
14.13 +#include "Dictionary.h"
14.14 +#include "Hash.h"
14.15 +#include <assert.h>
14.16 +#include <algorithm>
14.17 +#include <math.h>
14.18 +
14.19 +namespace Mooseyard {
14.20 +
14.21 + Dictionary::Dictionary() {
14.22 + }
14.23 +
14.24 + Dictionary::~Dictionary() {
14.25 + }
14.26 +
14.27 + Dictionary::Iterator::~Iterator() {
14.28 + }
14.29 +
14.30 +
14.31 + const int Dictionary::kMinSize = 8;
14.32 + const float Dictionary::kMinLoadFactor = 0.25;
14.33 + const float Dictionary::kMaxLoadFactor = 0.75;
14.34 +
14.35 + // Choose the smallest power of two that's large enough to hold the given capacity
14.36 + // of entries with no greater than the given load (fraction full).
14.37 + int Dictionary::choosePowerOfTwoSize (int capacity, float load) {
14.38 + int idealSize = capacity / load;
14.39 + int size;
14.40 + for (size=kMinSize; size<idealSize; size *= 2)
14.41 + ;
14.42 + return size;
14.43 + }
14.44 +
14.45 + int Dictionary::chooseAnyOldSize (int capacity, float load) {
14.46 + return std::max((int)::ceil(capacity / load), 2);
14.47 + }
14.48 +
14.49 +
14.50 + //-----------------------------------------------------------------------------
14.51 + // MurmurHashNeutral2, by Austin Appleby
14.52 + // http://murmurhash.googlepages.com/MurmurHashNeutral2.cpp
14.53 +
14.54 + // Same as MurmurHash2, but endian- and alignment-neutral.
14.55 + // Half the speed though, alas.
14.56 +
14.57 + static uint32_t MurmurHashNeutral2 ( const void * key, int32_t len, uint32_t seed )
14.58 + {
14.59 + static const uint32_t m = 0x5bd1e995;
14.60 + static const int32_t r = 24;
14.61 +
14.62 + uint32_t h = seed ^ len;
14.63 +
14.64 + const unsigned char * data = (const unsigned char *)key;
14.65 +
14.66 + while(len >= 4)
14.67 + {
14.68 + uint32_t k;
14.69 +
14.70 + k = data[0];
14.71 + k |= data[1] << 8;
14.72 + k |= data[2] << 16;
14.73 + k |= data[3] << 24;
14.74 +
14.75 + k *= m;
14.76 + k ^= k >> r;
14.77 + k *= m;
14.78 +
14.79 + h *= m;
14.80 + h ^= k;
14.81 +
14.82 + data += 4;
14.83 + len -= 4;
14.84 + }
14.85 +
14.86 + switch(len)
14.87 + {
14.88 + case 3: h ^= data[2] << 16;
14.89 + case 2: h ^= data[1] << 8;
14.90 + case 1: h ^= data[0];
14.91 + h *= m;
14.92 + };
14.93 +
14.94 + h ^= h >> 13;
14.95 + h *= m;
14.96 + h ^= h >> 15;
14.97 +
14.98 + return h;
14.99 + }
14.100 +
14.101 + HashCode Key::computeHash (Blob key) {
14.102 + return MurmurHashNeutral2(key.bytes, key.length, 0);
14.103 + }
14.104 +
14.105 +
14.106 +
14.107 + void MutableDictionary::add (Dictionary* dict) {
14.108 + Iterator *it = dict->iterate();
14.109 + for (; *it; it->next())
14.110 + put(it->key(), it->value());
14.111 + delete it;
14.112 + }
14.113 +
14.114 +
14.115 +
14.116 + const Dictionary& Dictionary::kEmpty = * new HashDictionary();
14.117 +
14.118 +
14.119 +#pragma mark -
14.120 +#pragma mark KEY AND VALUE
14.121 +
14.122 + class KeyAndValue {
14.123 + public:
14.124 + static KeyAndValue* create (Blob key, Blob value) {
14.125 + size_t size = 2*sizeof(uint32_t) + key.length;
14.126 + size = (size + 0x3) & ~0x3; // 32-bit align start of value
14.127 + if (value!=kDeletedValue)
14.128 + size += value.length;
14.129 + KeyAndValue *kv = (KeyAndValue*) ::operator new(size);
14.130 + kv->_keyLength = key.length;
14.131 + memcpy(&kv->_keyLength + 1, key.bytes, key.length);
14.132 + uint32_t *valueLengthPtr = const_cast<uint32_t*>(kv->valueLengthPtr());
14.133 + *valueLengthPtr = value.length;
14.134 + if (value!=kDeletedValue)
14.135 + memcpy(valueLengthPtr + 1, value.bytes, value.length);
14.136 + return kv;
14.137 + }
14.138 + Blob key() const {
14.139 + return Blob(&_keyLength+1, _keyLength);
14.140 + }
14.141 +
14.142 + Blob value() const{
14.143 + const uint32_t *v = this->valueLengthPtr();
14.144 + if (*v != kDeletedValue.length)
14.145 + return Blob(v+1, *v);
14.146 + else
14.147 + return kDeletedValue;
14.148 + }
14.149 +
14.150 + /** Magic value OverlayDictionary stores in me to represent a deleted value. */
14.151 + static const Blob kDeletedValue;
14.152 + private:
14.153 + const uint32_t* valueLengthPtr() const {
14.154 + size_t ptr = (size_t)(&_keyLength + 1) + _keyLength;
14.155 + ptr = (ptr + 0x3) & ~0x3; // 32-bit align
14.156 + return (uint32_t*)ptr;
14.157 + }
14.158 +
14.159 + uint32_t _keyLength;
14.160 + //...there follows the key, valueLength and value...
14.161 + };
14.162 +
14.163 + const Blob KeyAndValue::kDeletedValue(NULL, (size_t)-1);
14.164 +
14.165 +
14.166 +
14.167 +
14.168 +#pragma mark -
14.169 +#pragma mark HASH DICTIONARY:
14.170 +
14.171 + HashDictionary::~HashDictionary() {
14.172 + removeAll();
14.173 + }
14.174 +
14.175 + Blob HashDictionary::_convertValue (void *value) {
14.176 + return value ?((KeyAndValue*)value)->value() :Blob();
14.177 + }
14.178 +
14.179 + bool HashDictionary::contains (Key key) const {
14.180 + Blob value = get(key);
14.181 + return value.bytes || value.length;
14.182 + }
14.183 +
14.184 +
14.185 + void HashDictionary::put (Key key, Blob value) {
14.186 + // Allocate a block to store both the Blob struct and the data
14.187 + KeyAndValue *kv = KeyAndValue::create(key,value);
14.188 + _hash.put(Key(kv->key(),key.hash), kv);
14.189 + }
14.190 +
14.191 + bool HashDictionary::remove (Key key) {
14.192 + KeyAndValue *kv = (KeyAndValue*) _hash.get(key);
14.193 + if (kv) {
14.194 + free(kv);
14.195 + return true;
14.196 + } else
14.197 + return false;
14.198 + }
14.199 +
14.200 + void HashDictionary::removeAll() {
14.201 + for (Hash::Iterator it(&_hash); it; ++it)
14.202 + free(it.value());
14.203 + _hash.removeAll();
14.204 + }
14.205 +
14.206 +
14.207 +
14.208 +
14.209 +#pragma mark -
14.210 +#pragma mark OVERLAY DICTIONARY:
14.211 +
14.212 +
14.213 + OverlayDictionary::OverlayDictionary (const Dictionary *base)
14.214 + :_base(base),
14.215 + _overlay(new HashDictionary()),
14.216 + _count(base->count()),
14.217 + _allRemoved(false)
14.218 + { }
14.219 +
14.220 + OverlayDictionary::~OverlayDictionary() {
14.221 + delete _overlay;
14.222 + }
14.223 +
14.224 + int OverlayDictionary::count() const {
14.225 + return _count;
14.226 + }
14.227 +
14.228 + bool OverlayDictionary::isChanged() const {
14.229 + return _overlay->count() > 0;
14.230 + }
14.231 +
14.232 + Blob OverlayDictionary::get (Key key) const {
14.233 + Blob result = _overlay->get(key);
14.234 + if (!result) {
14.235 + if (result==KeyAndValue::kDeletedValue)
14.236 + result = Blob(); // It's been marked as deleted
14.237 + else if (!_allRemoved)
14.238 + result = _base->get(key);
14.239 + }
14.240 + return result;
14.241 + }
14.242 +
14.243 + bool OverlayDictionary::contains (Key key) const {
14.244 + Blob result = _overlay->get(key);
14.245 + if (result)
14.246 + return true;
14.247 + else if (result==KeyAndValue::kDeletedValue)
14.248 + return false;
14.249 + else if (!_allRemoved)
14.250 + return _base->get(key);
14.251 + else
14.252 + return false;
14.253 + }
14.254 +
14.255 + void OverlayDictionary::put (Key key, Blob value) {
14.256 + assert(value.bytes || value.length==0); // make sure it doesn't look like magic kDeletedValue
14.257 + _overlay->put(key,value);
14.258 + if (_allRemoved || !_base->contains(key))
14.259 + _count++;
14.260 + }
14.261 +
14.262 + bool OverlayDictionary::remove (Key key) {
14.263 + if (!_allRemoved && _base->contains(key)) {
14.264 + _overlay->put(key,KeyAndValue::kDeletedValue);
14.265 + _count--;
14.266 + return true;
14.267 + } else if (_overlay->remove(key)) {
14.268 + _count--;
14.269 + return true;
14.270 + } else
14.271 + return false;
14.272 + }
14.273 +
14.274 + void OverlayDictionary::removeAll() {
14.275 + _allRemoved = true;
14.276 + _count = 0;
14.277 + }
14.278 +
14.279 +
14.280 + void OverlayDictionary::revert() {
14.281 + _overlay->removeAll();
14.282 + _count = _base->count();
14.283 + _allRemoved = false;
14.284 + }
14.285 +
14.286 + void OverlayDictionary::revertTo (const Dictionary* newBase) {
14.287 + _base = newBase;
14.288 + revert();
14.289 + }
14.290 +
14.291 + void OverlayDictionary::rebase (const Dictionary* newBase) {
14.292 + _base = newBase;
14.293 + }
14.294 +
14.295 + OverlayDictionary::Iterator::Iterator (const OverlayDictionary &dict)
14.296 + :_iter(dict.base()->iterate()),
14.297 + _overlay(dict._overlay)
14.298 + {
14.299 + if (skipCurrentState())
14.300 + next();
14.301 + }
14.302 +
14.303 + Key OverlayDictionary::Iterator::key() const {return _iter ?_iter->key() :Key();}
14.304 + Blob OverlayDictionary::Iterator::value() const {return _iter ?_iter->value() :Blob();}
14.305 +
14.306 + bool OverlayDictionary::Iterator::next() {
14.307 + if (_iter) {
14.308 + do {
14.309 + _iter->next();
14.310 + } while (skipCurrentState());
14.311 + }
14.312 + return _iter && *_iter;
14.313 + }
14.314 +
14.315 + bool OverlayDictionary::Iterator::skipCurrentState() {
14.316 + if (_iter) {
14.317 + if (*_iter) {
14.318 + if (_overlay) {
14.319 + if (_overlay->contains(_iter->key()))
14.320 + return true; // Skip overridden value in base dict
14.321 + } else {
14.322 + if (_iter->value() == KeyAndValue::kDeletedValue)
14.323 + return true; // Skip marked-deleted value in overlay dict
14.324 + }
14.325 + } else {
14.326 + delete _iter;
14.327 + if (_overlay) {
14.328 + // end of base iterator; switch to overlay
14.329 + _iter = _overlay->iterate();
14.330 + _overlay = NULL;
14.331 + return skipCurrentState();
14.332 + } else {
14.333 + _iter = NULL;
14.334 + }
14.335 + }
14.336 + }
14.337 + return false;
14.338 + }
14.339 +
14.340 +
14.341 +#pragma mark -
14.342 +#pragma mark CHANGE ITERATOR:
14.343 +
14.344 +
14.345 + Dictionary::ChangeIterator::ChangeIterator (const Dictionary *dict1, const Dictionary *dict2) {
14.346 + _init(dict1, dict2);
14.347 + }
14.348 +
14.349 + Dictionary::ChangeIterator::ChangeIterator (const OverlayDictionary *overlay) {
14.350 + _init(overlay->_overlay, overlay->base());
14.351 + }
14.352 +
14.353 + void Dictionary::ChangeIterator::_init(const Dictionary *dict1, const Dictionary *dict2) {
14.354 + _dict2 = dict2;
14.355 + _iter = dict1->iterate();
14.356 + if (*_iter)
14.357 + _skipMatching();
14.358 + }
14.359 +
14.360 + Dictionary::ChangeIterator::~ChangeIterator() {
14.361 + delete _iter;
14.362 + }
14.363 +
14.364 + bool Dictionary::ChangeIterator::next() {
14.365 + return _iter->next() && this->_skipMatching();
14.366 + }
14.367 +
14.368 + bool Dictionary::ChangeIterator::_skipMatching() {
14.369 + do{
14.370 + _otherValue = _dict2->get(_iter->key());
14.371 + if (!_otherValue.equals(_iter->value()))
14.372 + return true;
14.373 + }while (_iter->next());
14.374 + return false;
14.375 + }
14.376 +
14.377 +
14.378 +
14.379 +}
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/src/File.cpp Sun Sep 20 15:14:12 2009 -0700
15.3 @@ -0,0 +1,214 @@
15.4 +/*
15.5 + * File.cpp
15.6 + * Ottoman
15.7 + *
15.8 + * Created by Jens Alfke on 8/20/09.
15.9 + * Copyright 2009 Jens Alfke. All rights reserved.
15.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
15.11 + */
15.12 +
15.13 +#include "File.h"
15.14 +#include "MemoryMap.h"
15.15 +
15.16 +#include <assert.h>
15.17 +#include <errno.h>
15.18 +#include <fcntl.h>
15.19 +#include <stdio.h>
15.20 +#include <sys/stat.h>
15.21 +#include <sys/uio.h>
15.22 +#include <unistd.h>
15.23 +
15.24 +namespace Mooseyard {
15.25 +
15.26 + File::File (const char *filename, bool writeable, bool create) throw(Error)
15.27 + :_fd(_check( ::open(filename, writeable ?(create ?O_RDWR|O_CREAT :O_RDWR) :O_RDONLY, 0644) )),
15.28 + _memoryMap(NULL),
15.29 + _locked(0)
15.30 + { }
15.31 +
15.32 + File::File (const char *filename, int oflag) throw(Error)
15.33 + :_fd(_check( ::open(filename, oflag, 0644) )),
15.34 + _memoryMap(NULL),
15.35 + _locked( (oflag | O_EXLOCK) ?1 :0)
15.36 + { }
15.37 +
15.38 + File::~File() {
15.39 + delete _memoryMap;
15.40 + _unlock();
15.41 + ::close(_fd);
15.42 + }
15.43 +
15.44 +
15.45 + off_t File::length() const throw(Error) {
15.46 + struct stat s;
15.47 + _check( ::fstat(_fd,&s) );
15.48 + return s.st_size;
15.49 + }
15.50 +
15.51 + void File::setLength (off_t length) throw(Error) {
15.52 + _check( ftruncate(_fd,length) );
15.53 + }
15.54 +
15.55 + off_t File::position() const throw(Error) {
15.56 + return _check( lseek(_fd,0,SEEK_CUR) );
15.57 + }
15.58 +
15.59 + void File::setPosition (off_t pos) throw(Error) {
15.60 + _check( lseek(_fd,pos,SEEK_SET) );
15.61 + }
15.62 +
15.63 + off_t File::setPositionToEnd (off_t bytesBefore) throw(Error) {
15.64 + return _check( lseek(_fd,-bytesBefore,SEEK_END) );
15.65 + }
15.66 +
15.67 + void File::read (void *dst, size_t size) throw(Error) {
15.68 + _checkRead( ::read(_fd, dst, size), size );
15.69 + }
15.70 +
15.71 + size_t File::write (const void *src, size_t size) throw(Error) {
15.72 + return _check( ::write(_fd, src, size) );
15.73 + }
15.74 +
15.75 +
15.76 + void File::readFrom (off_t where, void *dst, size_t size) throw(Error) {
15.77 + _checkRead( ::pread(_fd, dst, size, where), size );
15.78 + }
15.79 +
15.80 + void File::writeTo (off_t where, const void *src, size_t size) throw(Error) {
15.81 + _check( ::pwrite(_fd, src, size, where) );
15.82 + }
15.83 +
15.84 + size_t File::writeMultiple (Blob blobs[], int count) throw(Error) {
15.85 + struct iovec vec[count];
15.86 + for (int i=0; i<count; i++) {
15.87 + vec[i].iov_base = (void*) blobs[i].bytes;
15.88 + vec[i].iov_len = blobs[i].length;
15.89 + }
15.90 + return _check( ::writev(_fd, vec, count) );
15.91 + }
15.92 +
15.93 + size_t File::writePadding (int alignment) {
15.94 + off_t pad = alignment - (position() & (alignment-1));
15.95 + if (pad == alignment)
15.96 + return 0;
15.97 + uint8_t zero[pad];
15.98 + memset(zero, 0, pad);
15.99 + return write(zero, pad);
15.100 + }
15.101 +
15.102 +
15.103 + void File::flush() throw(Error) {
15.104 + _check( ::fsync(_fd) );
15.105 + }
15.106 +
15.107 + void File::flushDisk() throw(Error) {
15.108 + _check( ::fcntl(_fd,F_FULLFSYNC) );
15.109 + }
15.110 +
15.111 + bool File::hasPath (const char *path) const throw(Error) {
15.112 + struct stat myStat, pathStat;
15.113 + _check( ::fstat(_fd, &myStat) );
15.114 + if ( ::stat(path, &pathStat) != 0 ) {
15.115 + if (errno == ENOENT)
15.116 + return false;
15.117 + _check(errno);
15.118 + }
15.119 + // Compare my inode number with that of the file at path:
15.120 + return myStat.st_ino == pathStat.st_ino;
15.121 + }
15.122 +
15.123 +
15.124 + void File::unlink (const char *filename) throw(Error) {
15.125 + _check( ::unlink(filename) );
15.126 + }
15.127 +
15.128 + void File::rename (const char *srcFilename, const char *dstFilename) throw(Error) {
15.129 + _check( ::rename(srcFilename, dstFilename) );
15.130 + }
15.131 +
15.132 +
15.133 +#pragma mark -
15.134 +#pragma mark UTILITIES:
15.135 +
15.136 + int File::_check (int result) throw(Error) {
15.137 + if (result >= 0)
15.138 + return result;
15.139 + //printf("*** File::_check: Error %i: %s\n", errno, strerror(errno));
15.140 + throw Error(errno, strerror(errno));
15.141 + }
15.142 +
15.143 + void File::_checkRead (ssize_t result, size_t expectedSize) throw(Error) {
15.144 + if ((size_t)result < expectedSize) {
15.145 + if (result < 0)
15.146 + throw Error(errno, strerror(errno));
15.147 + else
15.148 + throw Error(kEOF, "unexpected EOF");
15.149 + }
15.150 + }
15.151 +
15.152 + File::Error::Error(const char *m)
15.153 + :code(ERANGE),
15.154 + message(m)
15.155 + { }
15.156 +
15.157 +
15.158 +#pragma mark -
15.159 +#pragma mark LOCKS:
15.160 +
15.161 + bool File::_lock (bool block) {
15.162 + if (_locked) {
15.163 + _locked++;
15.164 + } else {
15.165 + int mode = LOCK_EX;
15.166 + if (block)
15.167 + mode |= LOCK_NB;
15.168 + if (::flock(_fd, mode) == 0)
15.169 + _locked = 1;
15.170 + else if (errno != EWOULDBLOCK) // may be returned in LOCK_UN mode
15.171 + _check(-1);
15.172 + }
15.173 + return _locked > 0;
15.174 + }
15.175 +
15.176 + void File::_unlock() {
15.177 + if (_locked > 0) {
15.178 + _locked--;
15.179 + ::flock(_fd, LOCK_UN);
15.180 + }
15.181 + }
15.182 +
15.183 + File::Lock::Lock (File *file, bool block) throw(Error)
15.184 + :_file(file),
15.185 + _locked( _file->_lock(block) )
15.186 + { }
15.187 +
15.188 + File::Lock::~Lock() {
15.189 + if (_locked)
15.190 + _file->_unlock();
15.191 + }
15.192 +
15.193 + bool File::Lock::retry() {
15.194 + if (!_locked)
15.195 + _locked = _file->_lock(false);
15.196 + return _locked;
15.197 + }
15.198 +
15.199 +
15.200 +#pragma mark -
15.201 +#pragma mark MEMORY MAP:
15.202 +
15.203 + MemoryMap* File::map() {
15.204 + if (!_memoryMap)
15.205 + _memoryMap = new MemoryMap(this);
15.206 + return _memoryMap;
15.207 + }
15.208 +
15.209 + void File::mapRegion (off_t position, size_t length) {
15.210 + return map()->mapRegion(position,length);
15.211 + }
15.212 +
15.213 + const void* File::mappedPosition (off_t position) const {
15.214 + return map()->mappedPosition(position);
15.215 + }
15.216 +
15.217 +}
16.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
16.2 +++ b/src/Hash.cpp Sun Sep 20 15:14:12 2009 -0700
16.3 @@ -0,0 +1,160 @@
16.4 +/*
16.5 + * Hash.cpp
16.6 + * Ottoman
16.7 + *
16.8 + * Created by Jens Alfke on 8/20/09.
16.9 + * Copyright 2009 Jens Alfke. All rights reserved.
16.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
16.11 + */
16.12 +
16.13 +#include "Hash.h"
16.14 +#include "Dictionary.h"
16.15 +#include <algorithm>
16.16 +
16.17 +namespace Mooseyard {
16.18 +
16.19 + class Hash::IndexEntry {
16.20 + public:
16.21 + IndexEntry (Key key, Hash::Value value =NULL)
16.22 + :_key(key),
16.23 + _value(value)
16.24 + { }
16.25 +
16.26 + Key key() const {return _key;}
16.27 + HashCode hash() const {return _key.hash;}
16.28 + Hash::Value value() const {return _key.bytes ?_value :NULL;}
16.29 + void setValue (Hash::Value value) {_value = value;}
16.30 +
16.31 + bool isAvailable() const {return _value == NULL;} // false if deleted
16.32 + bool hasValue() const {return _key.bytes != NULL;}// false if deleted
16.33 + bool operator==(const IndexEntry &e) const {return _key.hash==e._key.hash && _key.equals(e._key);}
16.34 + bool operator!=(const IndexEntry &e) const {return ! (*this==e);}
16.35 +
16.36 + void markDeleted() {_key.bytes = NULL; _value = (Hash::Value)-1;}
16.37 + void markEmpty() {_key.bytes = NULL; _value = NULL;}
16.38 +
16.39 + private:
16.40 + Key _key; // bytes will be NULL if empty or deleted
16.41 + Hash::Value _value; // NULL if empty, -1 if deleted
16.42 + };
16.43 +
16.44 +
16.45 + Hash::Hash (int capacity)
16.46 + :_count(0),
16.47 + _tableSize( Dictionary::choosePowerOfTwoSize(capacity) ),
16.48 + _table( (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry)) )
16.49 + { }
16.50 +
16.51 + Hash::~Hash() {
16.52 + free(_table);
16.53 + }
16.54 +
16.55 + Hash::IndexEntry& Hash::_find (Key key) const {
16.56 + Key k = Key(key);
16.57 + IndexEntry newEntry(k);
16.58 + int index = newEntry.hash() % _tableSize;
16.59 + IndexEntry *found = &_table[index];
16.60 + int probe = 0;
16.61 + while (!found->isAvailable() && (!found->hasValue() || *found != newEntry)) {
16.62 + index = (index + ++probe) % _tableSize;
16.63 + found = &_table[index];
16.64 + }
16.65 + return *found;
16.66 + }
16.67 +
16.68 + Hash::IndexEntry& Hash::_findForPut (const Hash::IndexEntry &newEntry) {
16.69 + int index = newEntry.hash() % _tableSize;
16.70 + IndexEntry *found = &_table[index];
16.71 + int probe = 0;
16.72 + while (found->hasValue() && *found != newEntry) {
16.73 + index = (index + ++probe) % _tableSize;
16.74 + found = &_table[index];
16.75 + }
16.76 + return *found;
16.77 + }
16.78 +
16.79 + Hash::Value Hash::get(Key key) const {
16.80 + return _find(key).value();
16.81 + }
16.82 +
16.83 + void Hash::put(Key key, Hash::Value value) {
16.84 + IndexEntry newEntry = IndexEntry(Key(key),value);
16.85 + IndexEntry &found = _findForPut(newEntry);
16.86 + if (found.hasValue())
16.87 + found.setValue(value);
16.88 + else {
16.89 + found = newEntry;
16.90 + _count++;
16.91 + if (_count/(float)_tableSize > Dictionary::kMaxLoadFactor)
16.92 + _resize(2*_tableSize);
16.93 + }
16.94 + }
16.95 +
16.96 + bool Hash::remove(Key key) {
16.97 + IndexEntry &entry = _find(key);
16.98 + if (!entry.value())
16.99 + return false;
16.100 + entry.markDeleted();
16.101 + _count--;
16.102 + if (_count/(float)_tableSize < Dictionary::kMinLoadFactor)
16.103 + _resize(_tableSize/2);
16.104 + return true;
16.105 + }
16.106 +
16.107 + void Hash::removeAll() {
16.108 + memset(_table, 0, _tableSize*sizeof(*_table));
16.109 + _count = 0;
16.110 + }
16.111 +
16.112 + void Hash::dump() const {
16.113 + for (int index=0; index<_tableSize; index++)
16.114 + if (_table[index].hasValue()) {
16.115 + Blob key = _table[index].key();
16.116 + printf("%3i: %*s -> %p\n",
16.117 + index, (int)key.length,(const char*)key.bytes, _table[index].value());
16.118 + }
16.119 + }
16.120 +
16.121 +
16.122 + void Hash::_resize(int newSize) {
16.123 + newSize = std::max(newSize, Dictionary::kMinSize);
16.124 + if (newSize != _tableSize) {
16.125 + IndexEntry* oldTable = _table;
16.126 + int oldTableSize = _tableSize;
16.127 + _tableSize = newSize;
16.128 + _table = (IndexEntry*) calloc(_tableSize,sizeof(IndexEntry));
16.129 +
16.130 + // Add existing entries to new table:
16.131 + for (int index=0; index<oldTableSize; index++) {
16.132 + IndexEntry &entry = oldTable[index];
16.133 + if (entry.value())
16.134 + _findForPut(entry) = entry;
16.135 + }
16.136 + free(oldTable);
16.137 + }
16.138 + }
16.139 +
16.140 + Hash::Iterator::Iterator (const Hash *hash)
16.141 + :_entry(hash->_table-1), _end(hash->_table+hash->_tableSize)
16.142 + {
16.143 + next();
16.144 + }
16.145 +
16.146 + Hash::Iterator::Iterator (const Hash &hash)
16.147 + :_entry(hash._table-1), _end(hash._table+hash._tableSize)
16.148 + {
16.149 + next();
16.150 + }
16.151 +
16.152 + bool Hash::Iterator::next() {
16.153 + while (++_entry < _end) {
16.154 + if (_entry->hasValue())
16.155 + return true;
16.156 + }
16.157 + return false;
16.158 + }
16.159 +
16.160 + Key Hash::Iterator::key() const {return _entry->key();}
16.161 + Hash::Value Hash::Iterator::value() const {return _entry->value();}
16.162 +
16.163 +}
17.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
17.2 +++ b/src/Index.cpp Sun Sep 20 15:14:12 2009 -0700
17.3 @@ -0,0 +1,270 @@
17.4 +/*
17.5 + * Index.cpp
17.6 + * Ottoman
17.7 + *
17.8 + * Created by Jens Alfke on 8/27/09.
17.9 + * Copyright 2009 Jens Alfke. All rights reserved.
17.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
17.11 + */
17.12 +
17.13 +#include "Index.h"
17.14 +#include "Chunk.h"
17.15 +#include "File.h"
17.16 +#include "Dictionary.h"
17.17 +#include <assert.h>
17.18 +#include <errno.h>
17.19 +#include <algorithm>
17.20 +#include <math.h>
17.21 +
17.22 +namespace Mooseyard {
17.23 +
17.24 + // Quadratic probing results in fewer bucket tests on lookup, but makes the hash tables
17.25 + // significantly larger, which increases the file size. In practice a smaller table size seems
17.26 + // to be a bigger win since disk I/O is slow.
17.27 + #define PROBE_QUADRATIC 0
17.28 +
17.29 + // Similarly use a higher max load than for memory-resident tables, to save space.
17.30 + static const float kMaxLoadFactor = 0.85;
17.31 +
17.32 + static const uint32_t kIndexMagicNumber = 0x54378543;
17.33 +
17.34 +
17.35 + /** An index (hash-table) entry as stored in the memory-mapped file. */
17.36 + class Index::Entry {
17.37 + public:
17.38 + explicit Entry() :_hash(0), _valuePosition(0) { }
17.39 + explicit Entry (HashCode h, FilePosition p)
17.40 + :_hash(h), _valuePosition(p) { }
17.41 + LittleEndian<HashCode> hash() const {return _hash;}
17.42 + bool hasHash (LittleEndian<HashCode> h) const {return _hash == h;}
17.43 +
17.44 + const KeyValueChunk* value (const File *file) const {
17.45 + return (const KeyValueChunk*) file->mappedPosition(_valuePosition);
17.46 + }
17.47 + FilePosition valuePosition() const {return _valuePosition;}
17.48 +
17.49 +
17.50 + bool isAvailable() const {return _valuePosition == 0;} // false if deleted
17.51 + bool hasValue() const {return _valuePosition > 1;} // false if deleted
17.52 +
17.53 + void markDeleted() {_valuePosition = kDeletedPosition;}
17.54 + void markEmpty() {_valuePosition = 0;}
17.55 +
17.56 +
17.57 + static const FilePosition kDeletedPosition = 1;
17.58 +
17.59 + private:
17.60 + LittleEndian<HashCode> _hash;
17.61 + LittleEndian<FilePosition> _valuePosition;
17.62 + };
17.63 +
17.64 +
17.65 +#pragma mark -
17.66 +#pragma mark CREATION:
17.67 +
17.68 + Index::Index (uint32_t itsTableSize)
17.69 + :Chunk(sizeof(Index) + itsTableSize*sizeof(Index::Entry), kChunkType),
17.70 + _magicNumber(kIndexMagicNumber),
17.71 + _count(0),
17.72 + _tableSize(itsTableSize)
17.73 + { }
17.74 +
17.75 + Index* Index::create (int capacity) {
17.76 +#if PROBE_QUADRATIC
17.77 + int tableSize = Dictionary::choosePowerOfTwoSize(capacity);
17.78 +#else
17.79 + int tableSize = Dictionary::chooseAnyOldSize(capacity, kMaxLoadFactor);
17.80 +#endif
17.81 + size_t size = sizeof(Index) + tableSize*sizeof(Index::Entry);
17.82 + void* storage = ::operator new(size);
17.83 + memset(storage,0,size);
17.84 + return new(storage) Index(tableSize);
17.85 + }
17.86 +
17.87 + const Index* Index::indexMappedAt (const void* ptr) {
17.88 + const Index *index = (const Index*)ptr;
17.89 + index->validate();
17.90 + return index;
17.91 + }
17.92 +
17.93 + void Index::validate() const throw(File::Error) {
17.94 + if (_magicNumber != kIndexMagicNumber)
17.95 + throw File::Error(ERANGE, "Bad Index (wrong magic number)");
17.96 + if (_tableSize < 2 || _count > _tableSize)
17.97 + throw File::Error(ERANGE, "Bad Index (wrong count or tableSize)");
17.98 +#if PROBE_QUADRATIC
17.99 + if ((_tableSize & (_tableSize-1)) != 0)
17.100 + throw File::Error(ERANGE, "Bad Index (size not power of 2)");
17.101 +#endif
17.102 + if (size() != sizeof(Index)+_tableSize*sizeof(Index::Entry))
17.103 + throw File::Error(ERANGE, "Bad Index (wrong size)");
17.104 + }
17.105 +
17.106 + void Index::validateEntries (const File *file) const throw(File::Error) {
17.107 + validate();
17.108 + uint32_t size = _tableSize;
17.109 + uint32_t count = 0;
17.110 + const Entry *entry = table(0);
17.111 + for (uint32_t i=0; i<size; i++, entry++) {
17.112 + if (entry->hasValue()) {
17.113 + count++;
17.114 + const KeyValueChunk *chunk = entry->value(file);
17.115 + if ((void*)chunk->end() > (void*)this)
17.116 + throw File::Error(ERANGE, "Bad Index entry (points beyond index)");
17.117 + chunk->validate();
17.118 + if (entry->hash() != Key::computeHash(chunk->key()))
17.119 + throw File::Error(ERANGE, "Bad Index entry (wrong hash code)");
17.120 + }
17.121 + }
17.122 + if (count != _count)
17.123 + throw File::Error(ERANGE, "Bad Index (inconsistent count)");
17.124 + }
17.125 +
17.126 +
17.127 +#pragma mark -
17.128 +#pragma mark LOOKUP:
17.129 +
17.130 + const Index::Entry* Index::table (int index) const {
17.131 + return &((const Index::Entry*)&_table)[index];
17.132 + }
17.133 +
17.134 + Index::Entry* Index::table (int index) {
17.135 + return &((Index::Entry*)&_table)[index];
17.136 + }
17.137 +
17.138 +
17.139 + const KeyValueChunk* Index::_find (File *file, Key key) const {
17.140 + int index = key.hash % _tableSize;
17.141 + LittleEndian<HashCode> lhash = key.hash;
17.142 +#if PROBE_QUADRATIC
17.143 + int probe = 0;
17.144 +#endif
17.145 + for(;;) {
17.146 + const Index::Entry *found = table(index);
17.147 + if (found->isAvailable()) {
17.148 + return NULL;
17.149 + } else if (found->hasHash(lhash)) {
17.150 + const KeyValueChunk *value = found->value(file);
17.151 + if (value->hasKey(key)) {
17.152 + return value;
17.153 + }
17.154 + }
17.155 +#if PROBE_QUADRATIC
17.156 + index = (index + ++probe) % _tableSize;
17.157 +#else
17.158 + index = (index + 1) % _tableSize;
17.159 +#endif
17.160 + }
17.161 + }
17.162 +
17.163 + Blob Index::get (File *file, Key key) const {
17.164 + const KeyValueChunk *kv = _find(file, key);
17.165 + return kv ?kv->value() :Blob();
17.166 + }
17.167 +
17.168 +
17.169 + // Common implementation of put and delete. (If deleting, valuePosition will be kDeletedPosition.)
17.170 + // While searching, entries past maxPosition should be considered newly-added and not compared,
17.171 + // since they're not in the memory-mapped part of the file yet.
17.172 + // Returns true if the entry was added/removed.
17.173 + bool Index::_put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {
17.174 + bool result = (valuePosition <= Entry::kDeletedPosition);
17.175 + int index = key.hash % _tableSize;
17.176 + Index::Entry entry(key.hash, valuePosition);
17.177 +#if PROBE_QUADRATIC
17.178 + int probe = 0;
17.179 +#endif
17.180 + Index::Entry *found;
17.181 + for(;;) {
17.182 + found = table(index);
17.183 + if (!found->hasValue()) {
17.184 + if (entry.hasValue()) {
17.185 + result = true;
17.186 + break; // it's a put and we found an empty entry
17.187 + } else if (found->isAvailable()) {
17.188 + return false; // it's a delete but the key wasn't found
17.189 + }
17.190 + }
17.191 + else if (found->hasHash(entry.hash())) {
17.192 + if (!file)
17.193 + break; // no file given, so assume no duplicate keys
17.194 + else if (found->valuePosition() < maxPosition && found->value(file)->hasKey(key))
17.195 + break; // found existing (not newly-inserted) entry with the matching key
17.196 + /*else
17.197 + printf("** hash collision! hash=%u\n", key.hash);*/
17.198 + }
17.199 +#if PROBE_QUADRATIC
17.200 + index = (index + ++probe) % _tableSize;
17.201 +#else
17.202 + index = (index + 1) % _tableSize;
17.203 +#endif
17.204 + }
17.205 + // Finally found where to put it:
17.206 + *found = entry;
17.207 + return result;
17.208 + }
17.209 +
17.210 + bool Index::put (File *file, Key key, FilePosition valuePosition, FilePosition maxPosition) {
17.211 + bool added = _put(file, key, valuePosition, maxPosition);
17.212 + if (added)
17.213 + ++_count;
17.214 + return added;
17.215 + }
17.216 +
17.217 + bool Index::remove (File *file, Key key, FilePosition maxPosition) {
17.218 + bool removed = _put(file, key, Index::Entry::kDeletedPosition, maxPosition);
17.219 + if (removed) {
17.220 + assert(_count > 0);
17.221 + --_count;
17.222 + }
17.223 + return removed;
17.224 + }
17.225 +
17.226 + void Index::removeAll () {
17.227 + memset(table(0), 0, _tableSize*sizeof(Entry));
17.228 + _count = 0;
17.229 + }
17.230 +
17.231 +
17.232 + void Index::copyFrom (File *file, const Index *index) {
17.233 + const Entry *src = index->table(0);
17.234 + if (index->_tableSize == _tableSize) {
17.235 + memcpy(table(0), src, _tableSize*sizeof(Entry));
17.236 + } else {
17.237 + removeAll();
17.238 + for (uint32_t i=0; i<index->_tableSize; i++,src++)
17.239 + if (src->hasValue())
17.240 + _put(NULL, Key(NULL,0,src->hash()), src->valuePosition(), UINT32_MAX);
17.241 + }
17.242 + _count = index->count();
17.243 + }
17.244 +
17.245 +
17.246 +
17.247 + Index::Iterator::Iterator (File *file, const Index *index)
17.248 + :_file(file),
17.249 + _current(index->table(-1)),
17.250 + _end(index->table(index->_tableSize))
17.251 + {
17.252 + next();
17.253 + }
17.254 +
17.255 + bool Index::Iterator::hasValue() const {return _current != NULL;}
17.256 + Key Index::Iterator::key() const {return Key(_current->value(_file)->key(), _current->hash());}
17.257 + Blob Index::Iterator::value() const {return _current->value(_file)->value();}
17.258 +
17.259 + bool Index::Iterator::next() {
17.260 + if (_current) {
17.261 + while (++_current < _end) {
17.262 + if (_current->hasValue())
17.263 + return true;
17.264 + }
17.265 + _current = NULL;
17.266 + }
17.267 + return false;
17.268 + }
17.269 +
17.270 + FilePosition Index::Iterator::valuePosition() {
17.271 + return _current ?_current->valuePosition() :0;
17.272 + }
17.273 +}
18.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
18.2 +++ b/src/MemoryMap.cpp Sun Sep 20 15:14:12 2009 -0700
18.3 @@ -0,0 +1,103 @@
18.4 +/*
18.5 + * MemoryMap.cpp
18.6 + * Ottoman
18.7 + *
18.8 + * Created by Jens Alfke on 9/17/09.
18.9 + * Copyright 2009 Jens Alfke. All rights reserved.
18.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
18.11 + */
18.12 +
18.13 +#include "MemoryMap.h"
18.14 +
18.15 +#include <errno.h>
18.16 +#include <stdio.h>
18.17 +#include <sys/mman.h>
18.18 +
18.19 +namespace Mooseyard {
18.20 +
18.21 + MemoryMap::~MemoryMap() {
18.22 + for (int i=0; i<_nRegions; i++)
18.23 + delete _regions[i];
18.24 + free(_regions);
18.25 + }
18.26 +
18.27 + void MemoryMap::mapRegion (off_t pos, size_t length) {
18.28 + size_t end = pos+length;
18.29 + for (int i=0; i<_nRegions; i++) {
18.30 + Region *region = _regions[i];
18.31 + if (region->position() <= pos) {
18.32 + if (end <= region->end())
18.33 + return; // found an existing region covering this range
18.34 + else if (region->setLength(end - region->position()))
18.35 + return; // able to grow the existing region
18.36 + }
18.37 + }
18.38 +
18.39 + // No existing region, so add a new one:
18.40 + Region *region = new Region(_file, pos,length);
18.41 + _regions = (Region**) realloc(_regions, (_nRegions+1)*sizeof(*_regions));
18.42 + _regions[_nRegions++] = region;
18.43 + }
18.44 +
18.45 + const void* MemoryMap::_at (off_t pos) const {
18.46 + for (int i=0; i<_nRegions; i++) {
18.47 + const void *ptr = _regions[i]->mappedPosition(pos);
18.48 + if (ptr)
18.49 + return ptr;
18.50 + }
18.51 + return NULL;
18.52 + }
18.53 +
18.54 + const void* MemoryMap::mappedPosition (off_t pos) const {
18.55 + const void *result = _at(pos);
18.56 + if (!result)
18.57 + throw File::Error("No memory mapped at this position");
18.58 + return result;
18.59 + }
18.60 +
18.61 +
18.62 +
18.63 +
18.64 + MemoryMap::Region::Region (File* file, off_t position, size_t length)
18.65 + :_file(file),
18.66 + _position(position),
18.67 + _length (length),
18.68 + _start( (const uint8_t*) ::mmap(NULL, length, PROT_READ, MAP_PRIVATE, file->_fd, position) )
18.69 + {
18.70 + printf("File#%i: Mapped (%6llu -- %6llu) --> %p\n", file->_fd, _position, end(), _start);
18.71 + if (_start==NULL || _start == MAP_FAILED) {
18.72 + _start = NULL;
18.73 + throw File::Error(errno, strerror(errno));
18.74 + }
18.75 + }
18.76 +
18.77 + MemoryMap::Region::~Region() {
18.78 + if (_start) {
18.79 + printf("File#%i: Unmapped (%6llu -- %6llu) from %p\n", _file->_fd, _position, end(), _start);
18.80 + ::munmap((void*)_start,_length);
18.81 + }
18.82 + }
18.83 +
18.84 + bool MemoryMap::Region::setLength (size_t length) {
18.85 + if (length != _length) {
18.86 + printf("File#%i: Resiging (%6llu -- %6llu) from %lu to %lu ...",
18.87 + _file->_fd, _position, end(), _length,length);
18.88 + if (::mmap((void*)_start, length, PROT_READ, MAP_PRIVATE | MAP_FIXED, _file->_fd, _position) == MAP_FAILED) {
18.89 + printf("failed! errno=%i\n", errno);
18.90 + return false;
18.91 + }
18.92 + printf("OK\n");
18.93 + _length = length;
18.94 + }
18.95 + return true;
18.96 + }
18.97 +
18.98 + const void* MemoryMap::Region::mappedPosition (off_t pos) {
18.99 + if (pos >= _position && pos < end())
18.100 + return _start + (pos-_position);
18.101 + else
18.102 + return NULL;
18.103 + }
18.104 +
18.105 +
18.106 +}
19.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
19.2 +++ b/src/Ottoman.cpp Sun Sep 20 15:14:12 2009 -0700
19.3 @@ -0,0 +1,261 @@
19.4 +/*
19.5 + * Ottoman.cpp
19.6 + * Ottoman
19.7 + *
19.8 + * Created by Jens Alfke on 8/31/09.
19.9 + * Copyright 2009 Jens Alfke. All rights reserved.
19.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
19.11 + */
19.12 +
19.13 +#include "Ottoman.h"
19.14 +#include "VersionDictionary.h"
19.15 +#include "Chunk.h"
19.16 +#include "Index.h"
19.17 +#include "File.h"
19.18 +#include <fcntl.h>
19.19 +#include <stdio.h>
19.20 +#include <unistd.h>
19.21 +
19.22 +namespace Mooseyard {
19.23 +
19.24 + class DictionaryFileHeader :public Chunk {
19.25 + public:
19.26 + DictionaryFileHeader()
19.27 + :Chunk(sizeof(DictionaryFileHeader),kChunkType)
19.28 + {
19.29 + memcpy(&magicNumber, &kMagicNumber, sizeof(magicNumber));
19.30 + }
19.31 +
19.32 + bool valid() const {
19.33 + return type()==kChunkType && memcmp(&magicNumber,&kMagicNumber,sizeof(magicNumber))==0;
19.34 + }
19.35 +
19.36 + uint8_t magicNumber[8];
19.37 +
19.38 + static const uint16_t kChunkType = 4;
19.39 + static const uint8_t kMagicNumber[8];
19.40 + };
19.41 +
19.42 + const uint8_t DictionaryFileHeader::kMagicNumber[8] = {0x4A, 0x54, 0xF1, 0x1E, 'h', 'A', 's', 'H'};
19.43 +
19.44 +
19.45 +
19.46 + Ottoman::Ottoman()
19.47 + :_writeable(true),
19.48 + _filename(NULL),
19.49 + _lastVersion(NULL),
19.50 + _current( new OverlayDictionary(&Dictionary::kEmpty) )
19.51 + {
19.52 + }
19.53 +
19.54 + Ottoman::Ottoman (const char *filename, bool writeable)
19.55 + :_writeable(writeable),
19.56 + _filename(strdup(filename)),
19.57 + _lastVersion(),
19.58 + _current()
19.59 + {
19.60 + _file = new File(_filename, writeable ?O_RDWR :O_RDONLY);
19.61 + _lastVersion = new VersionDictionary(_file);
19.62 + if (writeable)
19.63 + _current = new OverlayDictionary(_lastVersion);
19.64 + }
19.65 +
19.66 + Ottoman::~Ottoman() {
19.67 + delete _current;
19.68 + delete _lastVersion;
19.69 + delete _file;
19.70 + free(_filename);
19.71 + }
19.72 +
19.73 +
19.74 + bool Ottoman::needsSync() const {
19.75 + return _file && (!_lastVersion->isLatestVersion() || !_file->hasPath(_filename));
19.76 + }
19.77 +
19.78 + bool Ottoman::sync() {
19.79 + if (!needsSync())
19.80 + return false;
19.81 + File *curFile = _file;
19.82 + if (!curFile->hasPath(_filename))
19.83 + curFile = new File(_filename, _writeable ?O_RDWR :O_RDONLY);
19.84 +
19.85 + VersionDictionary *newest = new VersionDictionary(curFile);
19.86 + bool changed = (newest->generation() != _lastVersion->generation());
19.87 + if (changed) {
19.88 + if (newest->generation() < _lastVersion->generation())
19.89 + throw File::Error("Versions got lost in file update");
19.90 +
19.91 + if (_current)
19.92 + _current->rebase(newest);
19.93 +
19.94 + delete _lastVersion;
19.95 + _lastVersion = newest;
19.96 + }
19.97 +
19.98 + if (_file != curFile) {
19.99 + delete _file;
19.100 + _file = curFile;
19.101 + }
19.102 + return changed;
19.103 + }
19.104 +
19.105 +
19.106 + ChunkIterator* Ottoman::chunkIterator() const {
19.107 + return _file ?new ChunkIterator(_file, sizeof(DictionaryFileHeader)) :NULL;
19.108 + }
19.109 +
19.110 + bool Ottoman::scavenge (bool repair) {
19.111 + if (!_file)
19.112 + return true;
19.113 +
19.114 + const off_t actualEOF = _file->length();
19.115 + fprintf(stderr, "Ottoman::scavenge: Scanning %s (%llu / 0x%llX bytes) ...\n",
19.116 + _filename, actualEOF, actualEOF);
19.117 + _file->setPosition(0);
19.118 + ChunkIterator it(_file, 0);
19.119 + const DictionaryFileHeader *header = (const DictionaryFileHeader *) it.chunk();
19.120 + if (!header || !header->valid()) {
19.121 + fprintf(stderr, "Ottoman::scavenge: No valid file header at all!\n");
19.122 + return false;
19.123 + }
19.124 +
19.125 + // Scan through all the chunks:
19.126 + FilePosition lastValidTrailer = 0;
19.127 + FilePosition validEOF = 0;
19.128 + int lastType = -1;
19.129 + int count = 0;
19.130 + try{
19.131 + for (; it; ++it) {
19.132 + const Chunk *chunk = it.chunk();
19.133 +
19.134 + uint16_t type = it.chunk()->type();
19.135 + if (type != lastType) {
19.136 + if (count > 0)
19.137 + printf("%6d\n", count);
19.138 + fprintf(stderr, "Ottoman::scavenge: at 0x%08X: type %u ... ",
19.139 + it.position(), type);
19.140 + lastType = type;
19.141 + count = 0;
19.142 + }
19.143 + count++;
19.144 +
19.145 + switch (type) {
19.146 + case KeyValueChunk::kChunkType:
19.147 + ((const KeyValueChunk*)chunk)->validate();
19.148 + break;
19.149 + case Index::kChunkType:
19.150 + ((const Index*)chunk)->validateEntries(_file);
19.151 + break;
19.152 + case VersionDictionary::kChunkType: {
19.153 + fprintf(stderr, "Found dictionary trailer at %u!\n", it.position());
19.154 + count = 0;
19.155 + // Validate by instantiating the VersionDictionary:
19.156 + VersionDictionary tempDict(_file, it.position());
19.157 + // If constructor succeeded, it's valid, so remember it:
19.158 + lastValidTrailer = it.position();
19.159 + validEOF = lastValidTrailer + chunk->size();
19.160 + fprintf(stderr, "Ottoman::scavenge: Valid dictionary trailer at %X--%X\n",
19.161 + lastValidTrailer, validEOF);
19.162 + break;
19.163 + }
19.164 + }
19.165 + }
19.166 + if (count > 0)
19.167 + fprintf(stderr, "%6d\n", count);
19.168 + } catch (File::Error &err) {
19.169 + fprintf(stderr, "Ottoman::scavenge caught File::Error(%i,\"%s\") at pos %llX\n",
19.170 + err.code, err.message, _file->position());
19.171 + // Keep going; we can recover the dictionary(ies) before the bad one.
19.172 + }
19.173 +
19.174 + if (lastValidTrailer == 0) {
19.175 + fprintf(stderr, "Ottoman::scavenge: No valid dictionaries found!\n");
19.176 + return false;
19.177 + } else if (validEOF < actualEOF) {
19.178 + fprintf(stderr, "Ottoman::scavenge: Need to truncate to 0x%X (0x%llX bytes)\n",
19.179 + lastValidTrailer, actualEOF-lastValidTrailer);
19.180 + if (repair) {
19.181 + _file->setLength(validEOF);
19.182 + _file->flushDisk();
19.183 + }
19.184 + return false;
19.185 + }
19.186 +
19.187 + fprintf(stderr, "Ottoman::scavenge: File is OK!\n");
19.188 + return true;
19.189 + }
19.190 +
19.191 +
19.192 +#pragma mark -
19.193 +#pragma mark SAVING:
19.194 +
19.195 +
19.196 + // low-level write. Does not lock or check for conflicts!
19.197 + void Ottoman::_append (File *dstFile) {
19.198 + VersionDictionary *lastVersion = _lastVersion;
19.199 + if (!lastVersion)
19.200 + lastVersion = new VersionDictionary(dstFile);
19.201 + VersionDictionary *saved = lastVersion->_appendAndOpen(_current->overlay(),
19.202 + dstFile,
19.203 + _current->baseReplaced());
19.204 + // (don't delete _lastVersion: saved->_previousVersion now points to it.)
19.205 + _lastVersion = saved;
19.206 + _current->revertTo(_lastVersion);
19.207 + }
19.208 +
19.209 + bool Ottoman::save() {
19.210 + if (!_file)
19.211 + return false;
19.212 + if (_current && _current->isChanged()) {
19.213 + File::Lock lock(_file);
19.214 + if (needsSync())
19.215 + return false; // conflict!
19.216 + _append(_file);
19.217 + }
19.218 + return true;
19.219 + }
19.220 +
19.221 + File* Ottoman::_writeTo (const char *dstFileName, bool overwriteAllowed) {
19.222 + int mode = O_RDWR | O_CREAT | O_TRUNC | O_EXLOCK;
19.223 + if (!overwriteAllowed)
19.224 + mode |= O_EXCL;
19.225 + File *dstFile = new File(dstFileName, mode);
19.226 + try {
19.227 + dstFile->write(DictionaryFileHeader());
19.228 + _append(dstFile);
19.229 + } catch (...) {
19.230 + delete dstFile;
19.231 + File::unlink(dstFileName);
19.232 + throw;
19.233 + }
19.234 + return dstFile;
19.235 + }
19.236 +
19.237 + void Ottoman::saveAs (const char *dstFileName, bool overwriteAllowed) {
19.238 + File *dstFile = _writeTo(dstFileName, overwriteAllowed);
19.239 + free(_filename);
19.240 + _filename = strdup(dstFileName);
19.241 + _file = dstFile;
19.242 + }
19.243 +
19.244 + bool Ottoman::saveAndCompact() {
19.245 + if (!_file)
19.246 + return false;
19.247 + char tempFileName[1024];
19.248 + strlcpy(tempFileName, _filename, sizeof(tempFileName)-1);
19.249 + strlcat(tempFileName, "~", sizeof(tempFileName));
19.250 + File *tempFile;
19.251 + {
19.252 + // Check for conflict in existing file:
19.253 + File::Lock lock(_file);
19.254 + if (needsSync())
19.255 + return false;
19.256 + tempFile = _writeTo(tempFileName, false);
19.257 + File::rename(tempFileName, _filename);
19.258 + }
19.259 + delete _file;
19.260 + _file = tempFile;
19.261 + return true;
19.262 + }
19.263 +
19.264 +}
20.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
20.2 +++ b/src/VersionDictionary.cpp Sun Sep 20 15:14:12 2009 -0700
20.3 @@ -0,0 +1,429 @@
20.4 +/*
20.5 + * VersionDictionary.cpp
20.6 + * Ottoman
20.7 + *
20.8 + * Created by Jens Alfke on 8/21/09.
20.9 + * Copyright 2009 Jens Alfke. All rights reserved.
20.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
20.11 + */
20.12 +
20.13 +#include "VersionDictionary.h"
20.14 +#include "Chunk.h"
20.15 +#include "Index.h"
20.16 +#include "File.h"
20.17 +#include "Chunk.h"
20.18 +#include <assert.h>
20.19 +#include <errno.h>
20.20 +#include <algorithm>
20.21 +
20.22 +namespace Mooseyard {
20.23 +
20.24 + // Trailer is stored in file; all numbers are little-endian.
20.25 + class VersionDictionary::Trailer :public Chunk {
20.26 + public:
20.27 + LittleEndian<uint32_t> magicNumber1;
20.28 + LittleEndian<uint32_t> count;
20.29 + VersionDictionary::IndexPositions indexPositions;
20.30 + LittleEndian<FilePosition> previousTrailerPosition;
20.31 + LittleEndian<uint32_t> generation;
20.32 + LittleEndianDouble timestamp;
20.33 + LittleEndian<uint32_t> magicNumber2;
20.34 +
20.35 + Trailer ()
20.36 + :Chunk(sizeof(Trailer), kChunkType)
20.37 + { }
20.38 +
20.39 + Trailer (int c,
20.40 + VersionDictionary::IndexPositions indexPos,
20.41 + FilePosition previousTrailerPos,
20.42 + uint32_t gen)
20.43 + :Chunk(sizeof(Trailer), kChunkType),
20.44 + magicNumber1(kMagicNumber1),
20.45 + count(c),
20.46 + indexPositions(indexPos),
20.47 + previousTrailerPosition(previousTrailerPos),
20.48 + generation(gen),
20.49 + timestamp(::time(NULL)),
20.50 + magicNumber2(kMagicNumber2)
20.51 + { }
20.52 +
20.53 + static const uint32_t kMagicNumber1 = 0xfe83b1cd;
20.54 + static const uint32_t kMagicNumber2 = 0xff84b2c1;
20.55 + };
20.56 +
20.57 +
20.58 +
20.59 + VersionDictionary::VersionDictionary (File *file)
20.60 + :_file(file),
20.61 + _trailerPosition(0),
20.62 + _previousTrailerPosition(0),
20.63 + _indexPositions(),
20.64 + _count(0),
20.65 + _previousVersion()
20.66 + {
20.67 + if (file->length() > sizeof(Trailer))
20.68 + _read();
20.69 + }
20.70 +
20.71 + VersionDictionary::VersionDictionary (File *file, FilePosition trailerPosition)
20.72 + :_file(file),
20.73 + _trailerPosition(trailerPosition),
20.74 + _previousTrailerPosition(0),
20.75 + _indexPositions(),
20.76 + _count(0),
20.77 + _previousVersion()
20.78 + {
20.79 + _read(trailerPosition);
20.80 + }
20.81 +
20.82 + int VersionDictionary::count() const {
20.83 + return _count;
20.84 + }
20.85 +
20.86 + const VersionDictionary::Trailer* VersionDictionary::_trailer() const {
20.87 + if (_trailerPosition > 0)
20.88 + return (const VersionDictionary::Trailer*) _file->mappedPosition(_trailerPosition);
20.89 + else
20.90 + return NULL; // Only happens in the empty-file case
20.91 + }
20.92 +
20.93 + const Index* VersionDictionary::_index (int i) const {
20.94 + if (_indexPositions[i] > 0)
20.95 + return (const Index*) _file->mappedPosition(_indexPositions[i]);
20.96 + else
20.97 + return NULL;
20.98 + }
20.99 +
20.100 + int VersionDictionary::generation() const {
20.101 + const VersionDictionary::Trailer *trailer = _trailer();
20.102 + return trailer ? (int)trailer->generation : -1;
20.103 + }
20.104 +
20.105 + time_t VersionDictionary::timestamp() const {
20.106 + const VersionDictionary::Trailer *trailer = _trailer();
20.107 + return trailer ? (time_t)trailer->timestamp : 0;
20.108 + }
20.109 +
20.110 + const VersionDictionary* VersionDictionary::previousVersion() const {
20.111 + if (!_previousVersion)
20.112 + if (_previousTrailerPosition > 0)
20.113 + _previousVersion = new VersionDictionary(_file, _previousTrailerPosition);
20.114 + return _previousVersion;
20.115 + }
20.116 +
20.117 +
20.118 + Blob VersionDictionary::get (Key key) const {
20.119 + const Index *index = _index(key.hash >> 24);
20.120 + return index ?index->get(_file, key) :Blob();
20.121 + }
20.122 +
20.123 + void VersionDictionary::_read (FilePosition trailerPos) {
20.124 + assert(_file);
20.125 +
20.126 + if (trailerPos > 0) {
20.127 + _file->setPosition(trailerPos);
20.128 + } else {
20.129 + // Determine position of trailer, at EOF:
20.130 + off_t pos = _file->setPositionToEnd(sizeof(VersionDictionary::Trailer));
20.131 + if (pos < 0 || (pos & 0x03) || pos > UINT32_MAX)
20.132 + throw File::Error(ERANGE, "No trailer found in file (wrong EOF)");
20.133 + trailerPos = pos;
20.134 + }
20.135 +
20.136 + // Read & verify trailer:
20.137 + VersionDictionary::Trailer trailer;
20.138 + _file->read(trailer);
20.139 + _trailerPosition = trailerPos;
20.140 + _count = trailer.count;
20.141 + _indexPositions = trailer.indexPositions;
20.142 +
20.143 + if (trailer.magicNumber1 != VersionDictionary::Trailer::kMagicNumber1
20.144 + || trailer.magicNumber2 != VersionDictionary::Trailer::kMagicNumber2)
20.145 + throw File::Error(ERANGE, "No trailer found in file (invalid magic numbers)");\
20.146 +
20.147 +
20.148 + // Map in the file:
20.149 + _file->mapRegion(0, _trailerPosition+sizeof(trailer));
20.150 +
20.151 + // Verify Indexes:
20.152 + for (int i=0; i<256; i++) {
20.153 + const Index *index = _index(i);
20.154 + if (index)
20.155 + index->validate();
20.156 + }
20.157 +}
20.158 +
20.159 +
20.160 + bool VersionDictionary::isLatestVersion() const {
20.161 + return _file->length() <= _trailerPosition+sizeof(VersionDictionary::Trailer);
20.162 + }
20.163 +
20.164 +
20.165 + /* Append addDict to baseDict, writing the results into dstFile (which is usually the same
20.166 + as baseDict->file().) If 'replace' is true, ignore the old contents of baseDict.
20.167 + Returns the position of the new trailer. */
20.168 + FilePosition VersionDictionary::_append (const VersionDictionary *baseDict,
20.169 + const Dictionary *addDict,
20.170 + File *dstFile,
20.171 + bool replace)
20.172 + {
20.173 + File *srcFile = baseDict->_file;
20.174 + bool incremental = !replace && dstFile==srcFile;
20.175 + Index* newIndex[256];
20.176 +
20.177 + {
20.178 + // Work out the needed capacity for each Index bucket:
20.179 + int newCounts[256] = {0};
20.180 + if (!replace) {
20.181 + for (int i=0; i<256; i++) {
20.182 + const Index *oldIndex = baseDict->_index(i);
20.183 + if (oldIndex)
20.184 + newCounts[i] = oldIndex->count();
20.185 + }
20.186 + }
20.187 + Dictionary::Iterator *it = addDict->iterate();
20.188 + for (; *it; ++*it)
20.189 + newCounts[it->key().hash >> 24]++;
20.190 + delete it;
20.191 +
20.192 + // Allocate new Indexes, of sufficient capacity, for each growing bucket:
20.193 + for (int i=0; i<256; i++) {
20.194 + const Index *oldIndex = baseDict->_index(i);
20.195 + if (newCounts[i] && (!incremental || !oldIndex || newCounts[i] > oldIndex->count())) {
20.196 + newIndex[i] = Index::create(newCounts[i]);
20.197 + if (incremental && oldIndex)
20.198 + newIndex[i]->copyFrom(srcFile, oldIndex);
20.199 + } else
20.200 + newIndex[i] = NULL;
20.201 + }
20.202 + }
20.203 +
20.204 + // Lock the file now, seek to the end, and make sure it's been prepared with a header,
20.205 + // since FilePositions of 0 and 1 are reserved.
20.206 + File::Lock lock(dstFile);
20.207 + const FilePosition startPos = dstFile->setPositionToEnd();
20.208 + if (startPos <= 1)
20.209 + throw File::Error(ERANGE, "Cannot write VersionDictionary to empty file");
20.210 +
20.211 + // For safety's sake, make sure the old file hasn't been destroyed:
20.212 + FilePosition oldEOF = baseDict->_trailerPosition;
20.213 + if (oldEOF > 0)
20.214 + oldEOF += sizeof(VersionDictionary::Trailer);
20.215 + if (srcFile->length() < oldEOF)
20.216 + throw File::Error(ERANGE, "File has been truncated since being read");
20.217 +
20.218 + try{
20.219 + FilePosition pos = startPos;
20.220 +
20.221 + int newCount;
20.222 + if (replace)
20.223 + newCount = 0;
20.224 + else if (dstFile == srcFile)
20.225 + newCount = baseDict->_count;
20.226 + else {
20.227 + // Write out the surviving pre-existing entries from the old file:
20.228 + newCount = 0;
20.229 + for (VersionDictionary::Iterator it(baseDict); it; ++it) {
20.230 + Key key = it.key();
20.231 + if (!addDict->contains(key)) {
20.232 + int bucket = key.hash >> 24;
20.233 + int size = KeyValueChunk::write(dstFile,pos, key, it.value());
20.234 + newIndex[bucket]->put(srcFile, key, pos, startPos);
20.235 + pos += size;
20.236 + newCount++;
20.237 + }
20.238 + }
20.239 + }
20.240 +
20.241 + // Now write the items from the new dict:
20.242 + Dictionary::Iterator *it = addDict->iterate();
20.243 + for (; *it; ++*it) {
20.244 + Key key=it->key();
20.245 + Blob value=it->value();
20.246 + int bucket = key.hash >> 24;
20.247 + Index *index = newIndex[bucket];
20.248 + assert(index);
20.249 +
20.250 + if (value.bytes) {
20.251 + int size = KeyValueChunk::write(dstFile,pos, key, value);
20.252 + if (index->put(srcFile, key, pos, startPos))
20.253 + newCount++;
20.254 + pos += size;
20.255 + } else if (incremental) {
20.256 + // NULL value is a deleted-entry marker used by OverlayDictionary
20.257 + if (index->remove(srcFile, key, startPos))
20.258 + newCount--;
20.259 + }
20.260 + }
20.261 + delete it;
20.262 +
20.263 + // Write out the new indexes:
20.264 + IndexPositions newIndexPositions;
20.265 + if (incremental)
20.266 + newIndexPositions = baseDict->_indexPositions;
20.267 + else
20.268 + memset(&newIndexPositions, 0, sizeof(newIndexPositions));
20.269 +
20.270 + pos += Chunk::writePadding(dstFile);
20.271 + for (int i=0; i<256; i++) {
20.272 + if (newIndex[i]) {
20.273 + Index *index = newIndex[i];
20.274 + newIndexPositions[i] = pos;
20.275 + pos += dstFile->write(index, index->size());
20.276 + delete index;
20.277 + }
20.278 + }
20.279 +
20.280 + // Flush everything out to disk, with maximum paranoia, before writing the trailer.
20.281 + // Since scavenging corrupt files looks for trailers, we don't want to append a
20.282 + // trailer until we're certain that all of the real data is safely on-disk.
20.283 + dstFile->flushDisk();
20.284 +
20.285 + // Write the trailer:
20.286 + FilePosition newTrailerPosition = pos;
20.287 + VersionDictionary::Trailer trailer(newCount,
20.288 + newIndexPositions,
20.289 + baseDict->_trailerPosition,
20.290 + baseDict->generation() + 1);
20.291 + pos += dstFile->write(trailer);
20.292 +
20.293 + // Just a mild flush here; flushDisk() is very expensive and can be disruptive to
20.294 + // real-time I/O in other apps, so it's bad to call it too often.
20.295 + dstFile->flush();
20.296 + assert(pos==dstFile->position());
20.297 +
20.298 + return newTrailerPosition;
20.299 +
20.300 + } catch (...) {
20.301 + // If something goes wrong, try to back out everything we wrote:
20.302 + try{
20.303 + dstFile->setLength(startPos);
20.304 + }catch(...) { }
20.305 + throw;
20.306 + }
20.307 + }
20.308 +
20.309 +
20.310 +#pragma mark -
20.311 +#pragma mark TESTING-ONLY:
20.312 +
20.313 + VersionDictionary* VersionDictionary::_appendAndOpen (const Dictionary *addDict,
20.314 + File *dstFile,
20.315 + bool replace) const
20.316 + {
20.317 + FilePosition nextVersionPos = _append(this, addDict, dstFile, replace);
20.318 + VersionDictionary *nextVersion = new VersionDictionary(dstFile, nextVersionPos);
20.319 + nextVersion->_previousVersion = this;
20.320 + return nextVersion;
20.321 + }
20.322 +
20.323 + VersionDictionary* VersionDictionary::create (File *file, const Dictionary *srcDict) {
20.324 + return VersionDictionary(file)._appendAndOpen(srcDict, file, true);
20.325 + }
20.326 +
20.327 +
20.328 +#pragma mark -
20.329 +#pragma mark ITERATOR:
20.330 +
20.331 + Dictionary::Iterator* VersionDictionary::iterate() const {
20.332 + return new VersionDictionary::Iterator(this);
20.333 + }
20.334 +
20.335 + VersionDictionary::Iterator::Iterator (const VersionDictionary *file)
20.336 + :_file(file),
20.337 + _bucket(-1),
20.338 + _iter(NULL)
20.339 + {
20.340 + nextIndex();
20.341 + }
20.342 +
20.343 + VersionDictionary::Iterator::~Iterator() {
20.344 + delete _iter;
20.345 + }
20.346 +
20.347 + bool VersionDictionary::Iterator::hasValue() const {return _iter && _iter->hasValue();}
20.348 + Key VersionDictionary::Iterator::key() const {return _iter->key();}
20.349 + Blob VersionDictionary::Iterator::value() const {return _iter->value();}
20.350 +
20.351 + bool VersionDictionary::Iterator::next() {
20.352 + if (_iter->next())
20.353 + return true;
20.354 + else {
20.355 + delete _iter;
20.356 + return nextIndex();
20.357 + }
20.358 + }
20.359 +
20.360 + bool VersionDictionary::Iterator::nextIndex() {
20.361 + while (++_bucket < 256) {
20.362 + const Index *index = _file->_index(_bucket);
20.363 + if (index) {
20.364 + _iter = new Index::Iterator(_file->_file, index);
20.365 + if (*_iter)
20.366 + return true;
20.367 + else
20.368 + delete _iter;
20.369 + }
20.370 + }
20.371 + _iter = NULL;
20.372 + return false;
20.373 + }
20.374 +
20.375 +
20.376 +#pragma mark -
20.377 +#pragma mark CHANGE ITERATOR:
20.378 +
20.379 + VersionDictionary::ChangeIterator* VersionDictionary::iterateChanges() const {
20.380 + return new VersionDictionary::ChangeIterator(this);
20.381 + }
20.382 +
20.383 + VersionDictionary::ChangeIterator::ChangeIterator (const VersionDictionary *file)
20.384 + :_file(file),
20.385 + _bucket(-1),
20.386 + _iter(NULL)
20.387 + {
20.388 + next();
20.389 + }
20.390 +
20.391 + VersionDictionary::ChangeIterator::~ChangeIterator() {
20.392 + delete _iter;
20.393 + }
20.394 +
20.395 + bool VersionDictionary::ChangeIterator::hasValue() const {return _iter && _iter->hasValue();}
20.396 + Key VersionDictionary::ChangeIterator::key() const {return _iter->key();}
20.397 + Blob VersionDictionary::ChangeIterator::value() const {return _iter->value();}
20.398 +
20.399 + bool VersionDictionary::ChangeIterator::next() {
20.400 + const VersionDictionary::Trailer *trailer = _file->_trailer();
20.401 + for (;;) {
20.402 + // Check if current iterator has a value that's from this version:
20.403 + if (_iter && _iter->hasValue()) {
20.404 + if (((Index::Iterator*)_iter)->valuePosition() > trailer->previousTrailerPosition)
20.405 + return true;
20.406 + else if (_iter->next())
20.407 + continue;
20.408 + }
20.409 + // If not, go to next Index:
20.410 + if (!nextIndex())
20.411 + return false;
20.412 + }
20.413 + }
20.414 +
20.415 + bool VersionDictionary::ChangeIterator::nextIndex() {
20.416 + delete _iter;
20.417 + const VersionDictionary::Trailer *trailer = _file->_trailer();
20.418 + while (++_bucket < 256) {
20.419 + const Index *index = _file->_index(_bucket);
20.420 + if (index) {
20.421 + // Skip indexes that weren't updated in this version:
20.422 + if (trailer->indexPositions[_bucket] > trailer->previousTrailerPosition) {
20.423 + _iter = new Index::Iterator(_file->_file, index);
20.424 + return true;
20.425 + }
20.426 + }
20.427 + }
20.428 + _iter = NULL;
20.429 + return false;
20.430 + }
20.431 +
20.432 +}
21.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
21.2 +++ b/test/Dictionary_test.cpp Sun Sep 20 15:14:12 2009 -0700
21.3 @@ -0,0 +1,111 @@
21.4 +/*
21.5 + * Dictionary_test.cpp
21.6 + * Ottoman
21.7 + *
21.8 + * Created by Jens Alfke on 9/4/09.
21.9 + * Copyright 2009 Jens Alfke. All rights reserved.
21.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
21.11 + */
21.12 +
21.13 +
21.14 +#include <gtest/gtest.h>
21.15 +#include "TestUtils.h"
21.16 +#include "File.h"
21.17 +#include "Dictionary.h"
21.18 +#include "Hash.h"
21.19 +#include <fcntl.h>
21.20 +#include <stdio.h>
21.21 +
21.22 +using namespace Mooseyard;
21.23 +
21.24 +static const HashDictionary& getDict() {
21.25 + static HashDictionary *sDict;
21.26 + if (!sDict) {
21.27 + printf("Building large HashDictionary...\n");
21.28 + sDict = new HashDictionary();
21.29 + readWords();
21.30 + for( int i=0; i<sNWords; i++) {
21.31 + Blob kv(sWords[i]);
21.32 + sDict->put(Key(kv),kv);
21.33 + }
21.34 + }
21.35 + return *sDict;
21.36 +}
21.37 +
21.38 +TEST(Dictionary,GetAll) {
21.39 + const Dictionary &dict = getDict();
21.40 + EXPECT_EQ( sNWords , dict.count() );
21.41 + for( int i=0; i<sNWords; i++) {
21.42 + Key key(sWords[i]);
21.43 + Blob value = dict.get(key);
21.44 + EXPECT_TRUE(value);
21.45 + EXPECT_TRUE( value.equals(key) );
21.46 + }
21.47 +}
21.48 +
21.49 +TEST(Dictionary,Iterate) {
21.50 + const HashDictionary &dict = getDict();
21.51 + Timer t("Iterating Dictionary", sNWords);
21.52 + int n=0;
21.53 + for( HashDictionary::Iterator it(dict); it; ++it) {
21.54 + n++;
21.55 + EXPECT_TRUE(it.key().length > 0 && it.key().length < 50);
21.56 + EXPECT_TRUE(it.key().equals(it.value()));
21.57 + EXPECT_EQ( 0, ((size_t)it.value().bytes & 0x3) ); // 4-byte aligned
21.58 + }
21.59 + EXPECT_EQ(sNWords, n);
21.60 +}
21.61 +
21.62 +TEST(Dictionary,Overlay) {
21.63 + const Dictionary &dict = getDict();
21.64 + OverlayDictionary overlay(&dict);
21.65 +
21.66 + EXPECT_EQ( sNWords , overlay.count() );
21.67 + EXPECT_TRUE(overlay.get("animal").equals("animal"));
21.68 + EXPECT_TRUE(overlay.get("asparagus").equals("asparagus"));
21.69 + EXPECT_FALSE(overlay.get("growf"));
21.70 +
21.71 + overlay.put("animal", "AMINAL");
21.72 + overlay.put("growf", "growf");
21.73 + EXPECT_TRUE(overlay.remove("asparagus"));
21.74 +
21.75 + EXPECT_EQ( sNWords, overlay.count() );
21.76 + EXPECT_TRUE(overlay.get("animal").equals("AMINAL"));
21.77 + EXPECT_TRUE(overlay.get("growf").equals("growf"));
21.78 + EXPECT_TRUE(overlay.contains("growf"));
21.79 + EXPECT_FALSE(overlay.get("asparagus"));
21.80 + EXPECT_FALSE(overlay.contains("asparagus"));
21.81 +
21.82 + int n=0;
21.83 + for( OverlayDictionary::Iterator it(overlay); it; ++it) {
21.84 + n++;
21.85 + EXPECT_TRUE(!it.key().equals("asparagus"));
21.86 + }
21.87 + EXPECT_EQ(sNWords, n);
21.88 +
21.89 + printf("Testing ChangeIterator...\n");
21.90 + n=0;
21.91 + int foundAsparagus=0, foundAnimal=0, foundGrowf=0;
21.92 + for( Dictionary::ChangeIterator it(&overlay); it; ++it) {
21.93 + n++;
21.94 + if (it.key().equals("animal")) {
21.95 + foundAnimal++;
21.96 + EXPECT_TRUE(it.value().equals("AMINAL"));
21.97 + EXPECT_TRUE(it.otherValue().equals("animal"));
21.98 + } else if (it.key().equals("asparagus")) {
21.99 + foundAsparagus++;
21.100 + EXPECT_FALSE(it.value());
21.101 + EXPECT_TRUE(it.otherValue().equals("asparagus"));
21.102 + } else if (it.key().equals("growf")) {
21.103 + foundGrowf++;
21.104 + EXPECT_TRUE(it.value().equals("growf"));
21.105 + EXPECT_FALSE(it.otherValue());
21.106 + } else {
21.107 + EXPECT_TRUE(false);
21.108 + }
21.109 + }
21.110 + EXPECT_EQ(1, foundAnimal);
21.111 + EXPECT_EQ(1, foundAsparagus);
21.112 + EXPECT_EQ(1, foundGrowf);
21.113 + EXPECT_EQ(3, n);
21.114 +}
22.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
22.2 +++ b/test/Hash_test.cpp Sun Sep 20 15:14:12 2009 -0700
22.3 @@ -0,0 +1,193 @@
22.4 +/*
22.5 + * Hash_test.cpp
22.6 + * Ottoman
22.7 + *
22.8 + * Created by Jens Alfke on 9/2/09.
22.9 + * Copyright 2009 Jens Alfke. All rights reserved.
22.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
22.11 + */
22.12 +
22.13 +#include <gtest/gtest.h>
22.14 +#include "TestUtils.h"
22.15 +#include "File.h"
22.16 +#include "Hash.h"
22.17 +#include <stdio.h>
22.18 +
22.19 +using namespace Mooseyard;
22.20 +
22.21 +
22.22 +static bool verbose = false;
22.23 +static int num = 100;
22.24 +
22.25 +
22.26 +#pragma mark -
22.27 +#pragma mark UTILITIES:
22.28 +
22.29 +
22.30 +char* mkKey (int i) {
22.31 + static char* sKeys[100];
22.32 + if (i>=0 && i<100 && sKeys[i] != NULL)
22.33 + return sKeys[i];
22.34 + char str[10];
22.35 + sprintf(str, "%i",i);
22.36 + char *key = strdup(str);
22.37 + if (i>=0 && i<100)
22.38 + sKeys[i] = key;
22.39 + return key;
22.40 +}
22.41 +
22.42 +static char* Insert(Hash &hash, const char* key) {
22.43 + char string[100];
22.44 + sprintf(string, "value for %s", key);
22.45 + if (verbose)
22.46 + fprintf(stderr, "\nInserting %s -> '%s'\n", key,string);
22.47 + int count = hash.count();
22.48 + char *leaf = strdup(string);
22.49 +
22.50 + hash.put(key,leaf);
22.51 +
22.52 + if (verbose)
22.53 + hash.dump();
22.54 + EXPECT_EQ( count+1, hash.count() );
22.55 + EXPECT_EQ( leaf, hash.get(key) );
22.56 + return leaf;
22.57 +}
22.58 +
22.59 +static char* Insert(Hash &hash, int i) {
22.60 + return Insert(hash, mkKey(i));
22.61 +}
22.62 +
22.63 +static void Remove(Hash &hash, int i) {
22.64 + char* key = mkKey(i);
22.65 + char string[100];
22.66 + sprintf(string, "value for %s", key);
22.67 + if (verbose)
22.68 + fprintf(stderr, "\nRemoving %s\n", key);
22.69 + int count = hash.count();
22.70 + char *value = (char*) hash.get(key);
22.71 + EXPECT_TRUE(value!=NULL);
22.72 + EXPECT_EQ(0, strcmp(value,string));
22.73 +
22.74 + EXPECT_TRUE(hash.remove(key));
22.75 +
22.76 + if (verbose)
22.77 + hash.dump();
22.78 + EXPECT_EQ( count-1, hash.count() );
22.79 + EXPECT_EQ( NULL, hash.get(key) );
22.80 +}
22.81 +
22.82 +
22.83 +
22.84 +#pragma mark -
22.85 +#pragma mark TESTS:
22.86 +
22.87 +
22.88 +TEST(Hash,Simple) {
22.89 + Hash hash;
22.90 + hash.dump();
22.91 + EXPECT_EQ(0, hash.count());
22.92 +
22.93 + char *seventeen = Insert(hash, "seventeen");
22.94 +
22.95 + EXPECT_EQ(NULL, hash.get("zero"));
22.96 + EXPECT_EQ(NULL, hash.get("eighteen"));
22.97 +
22.98 + char *four = Insert(hash, "four");
22.99 + EXPECT_EQ(seventeen, hash.get("seventeen"));
22.100 +
22.101 + char *zero = Insert(hash, "zero");
22.102 + char *hundred = Insert(hash, "one hundred");
22.103 + char *eight = Insert(hash, "eight");
22.104 + char *twenty = Insert(hash, "twenty");
22.105 +
22.106 + EXPECT_EQ(zero, hash.get("zero"));
22.107 + EXPECT_EQ(four, hash.get("four"));
22.108 + EXPECT_EQ(eight, hash.get("eight"));
22.109 + EXPECT_EQ(seventeen, hash.get("seventeen"));
22.110 + EXPECT_EQ(twenty, hash.get("twenty"));
22.111 + EXPECT_EQ(hundred, hash.get("one hundred"));
22.112 +
22.113 + int i=0;
22.114 + for (Hash::Iterator iter(&hash); iter; ++iter, ++i) {
22.115 + Blob key = iter.key();
22.116 + if (verbose)
22.117 + fprintf(stderr, " %*s -> %s\n",
22.118 + (int)key.length,(const char*)key.bytes,
22.119 + ((char*)iter.value()));
22.120 + }
22.121 + EXPECT_EQ(6, i);
22.122 +}
22.123 +
22.124 +TEST(Hash,InsertLotsAtRandom) {
22.125 + int map[num];
22.126 + for (int i=0; i<num; i++)
22.127 + map[i] = i;
22.128 + shuffle(map,num);
22.129 + if (verbose) {
22.130 + for (int i=0; i<num; i++)
22.131 + fprintf(stderr, "%3d ",map[i]);
22.132 + fprintf(stderr, "\n");
22.133 + }
22.134 +
22.135 + Hash hash(8);
22.136 + char* expected[num];
22.137 + memset(&expected,0,sizeof(expected));
22.138 + for (int i=0; i<num; i++) {
22.139 + expected[map[i]] = Insert(hash, map[i]);
22.140 + for (int j=0; j<num; j++)
22.141 + EXPECT_EQ(expected[map[j]], hash.get(mkKey(map[j])));
22.142 + }
22.143 +}
22.144 +
22.145 +TEST(Hash,DeleteAtRandom) {
22.146 + Hash hash;
22.147 + for (int i=0; i<num; i++)
22.148 + Insert(hash,i);
22.149 +
22.150 + int map[num];
22.151 + for (int i=0; i<num; i++)
22.152 + map[i] = i;
22.153 + shuffle(map,num);
22.154 + if (verbose) {
22.155 + for (int i=0; i<num; i++)
22.156 + fprintf(stderr, "%3d ",map[i]);
22.157 + fprintf(stderr, "\n");
22.158 + }
22.159 +
22.160 + for (int i=0; i<num; i++)
22.161 + Remove(hash,map[i]);
22.162 +}
22.163 +
22.164 +TEST(Hash,Words) {
22.165 + const int kIterations = 3;
22.166 + readWords();
22.167 + double totalAdd = 0.0, totalGet = 0.0, totalRemove = 0.0;
22.168 + for (int iter=0; iter<kIterations; iter++) {
22.169 + printf("Adding words to Hash...\n");
22.170 + Hash hash;
22.171 + {
22.172 + Timer t("adding");
22.173 + for( int i=0; i<sNWords; i++)
22.174 + hash.put(sWords[i], sWords[i]);
22.175 + EXPECT_EQ(sNWords, hash.count());
22.176 + totalAdd += t.elapsed();
22.177 + }
22.178 + {
22.179 + Timer t("getting");
22.180 + for( int i=0; i<sNWords; i++)
22.181 + EXPECT_EQ( sWords[i] , hash.get(sWords[i]) );
22.182 + totalGet += t.elapsed();
22.183 + }
22.184 + {
22.185 + Timer t("removing");
22.186 + for( int i=0; i<sNWords; i++)
22.187 + EXPECT_TRUE( hash.remove(sWords[i]) );
22.188 + totalRemove += t.elapsed();
22.189 + }
22.190 + }
22.191 + printf("Average put = %.0lfns\n", totalAdd/kIterations/sNWords*1e9);
22.192 + printf("Average get = %.0lfns\n", totalGet/kIterations/sNWords*1e9);
22.193 + printf("Average remove= %.0lfns\n", totalRemove/kIterations/sNWords*1e9);
22.194 +}
22.195 +
22.196 +
23.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
23.2 +++ b/test/Ottoman_test.cpp Sun Sep 20 15:14:12 2009 -0700
23.3 @@ -0,0 +1,203 @@
23.4 +/*
23.5 + * Ottoman_test.cpp
23.6 + * Ottoman
23.7 + *
23.8 + * Created by Jens Alfke on 9/11/09.
23.9 + * Copyright 2009 Jens Alfke. All rights reserved.
23.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
23.11 + */
23.12 +
23.13 +#include <gtest/gtest.h>
23.14 +#include "TestUtils.h"
23.15 +#include "Chunk.h"
23.16 +#include "Ottoman.h"
23.17 +#include "VersionDictionary.h"
23.18 +#include <fcntl.h>
23.19 +#include <stdio.h>
23.20 +
23.21 +using namespace Mooseyard;
23.22 +
23.23 +
23.24 +TEST(Ottoman,Build) {
23.25 + ASSERT_EQ(8, sizeof(Chunk));
23.26 + ASSERT_EQ(8, sizeof(KeyValueChunk));
23.27 +
23.28 + time_t startTime = ::time(NULL);
23.29 + time_t createTime;
23.30 + {
23.31 + Ottoman otto;
23.32 + EXPECT_EQ((void*)NULL, otto.lastVersion());
23.33 + ASSERT_NE((void*)NULL, otto.currentVersion());
23.34 + readWords();
23.35 + for( int i=0; i<sNWords; i++) {
23.36 + Blob kv(sWords[i]);
23.37 + otto.currentVersion()->put(Key(kv),kv);
23.38 + }
23.39 + Timer t("Saving Ottoman", sNWords);
23.40 + otto.saveAs("/tmp/test.ottoman");
23.41 +
23.42 + VersionDictionary *last = otto.lastVersion();
23.43 + ASSERT_NE((void*)NULL, last);
23.44 + EXPECT_EQ(sNWords, last->count());
23.45 + ASSERT_NE((void*)NULL, otto.currentVersion());
23.46 + EXPECT_FALSE(otto.currentVersion()->isChanged());
23.47 + createTime = last->timestamp();
23.48 + EXPECT_GE(createTime, startTime);
23.49 + EXPECT_LE(createTime, ::time(NULL));
23.50 + }
23.51 + {
23.52 + Ottoman otto("/tmp/test.ottoman");
23.53 + VersionDictionary *last = otto.lastVersion();
23.54 + ASSERT_NE((void*)NULL, last);
23.55 + ASSERT_EQ(0, last->generation());
23.56 + ASSERT_EQ(createTime, last->timestamp());
23.57 + {
23.58 + Timer t("Reading from Ottoman", sNWords);
23.59 + EXPECT_EQ( sNWords , last->count() );
23.60 + for( int i=0; i<sNWords; i++) {
23.61 + Key key(sWords[i]);
23.62 + Blob value = last->get(key);
23.63 + ASSERT_TRUE(value);
23.64 + ASSERT_TRUE( value.equals(key) ) << "expected '" << key << "', got '" << value << "' (i=" << i <<")";
23.65 + }
23.66 + }
23.67 +
23.68 + printf("Iterating through the Ottoman...\n");
23.69 + Timer t("Iterating Ottoman", sNWords);
23.70 + int n=0;
23.71 + for( VersionDictionary::Iterator it(last); it; ++it) {
23.72 + n++;
23.73 + ASSERT_TRUE(it.key().length > 0 && it.key().length < 50);
23.74 + ASSERT_TRUE(it.key().equals(it.value()));
23.75 + ASSERT_EQ( 0, ((size_t)it.value().bytes & 0x3) ); // 4-byte aligned
23.76 + }
23.77 + ASSERT_EQ(sNWords, n);
23.78 + }
23.79 + {
23.80 + printf("Opening Ottoman...\n");
23.81 + Ottoman otto("/tmp/test.ottoman");
23.82 + OverlayDictionary *current = otto.currentVersion();
23.83 + ASSERT_TRUE(current != NULL);
23.84 + EXPECT_EQ( sNWords , current->count() );
23.85 + EXPECT_TRUE(current->get("asparagus").equals("asparagus"));
23.86 +
23.87 + current->put("animal", "AMINAL");
23.88 + current->put("growf", "growf");
23.89 + EXPECT_TRUE(current->remove("asparagus"));
23.90 +
23.91 + EXPECT_EQ( sNWords, current->count() );
23.92 + EXPECT_TRUE(current->get("animal").equals("AMINAL"));
23.93 + EXPECT_TRUE(current->get("growf").equals("growf"));
23.94 + EXPECT_EQ( NULL, current->get("asparagus").bytes );
23.95 + EXPECT_TRUE(!current->contains("asparagus"));
23.96 +
23.97 + int n=0;
23.98 + for( OverlayDictionary::Iterator it(*current); it; ++it) {
23.99 + n++;
23.100 + ASSERT_TRUE(!it.key().equals("asparagus"));
23.101 + }
23.102 + ASSERT_EQ(sNWords, n);
23.103 +
23.104 + printf("Saving Ottoman...\n");
23.105 + {
23.106 + Timer t("Saving Ottoman");
23.107 + otto.save();
23.108 + }
23.109 +
23.110 + EXPECT_EQ( sNWords, current->count() );
23.111 + EXPECT_TRUE(current->get("animal").equals("AMINAL"));
23.112 + EXPECT_TRUE(current->get("growf").equals("growf"));
23.113 + EXPECT_EQ( NULL, current->get("asparagus").bytes );
23.114 + EXPECT_TRUE(!current->contains("asparagus"));
23.115 +
23.116 + n=0;
23.117 + for( OverlayDictionary::Iterator it(*current); it; ++it) {
23.118 + n++;
23.119 + ASSERT_TRUE(!it.key().equals("asparagus"));
23.120 + }
23.121 + ASSERT_EQ(sNWords, n);
23.122 +
23.123 + EXPECT_EQ(1, otto.lastVersion()->generation());
23.124 + const VersionDictionary *prev = otto.lastVersion()->previousVersion();
23.125 + ASSERT_TRUE(prev != NULL);
23.126 + EXPECT_EQ(0, prev->generation());
23.127 + EXPECT_TRUE(prev->get("asparagus").equals("asparagus"));
23.128 + EXPECT_TRUE(prev->get("growf").equals(NULL));
23.129 + }
23.130 + {
23.131 + printf("Re-opening Ottoman...\n");
23.132 + Ottoman otto("/tmp/test.ottoman", false);
23.133 + ASSERT_EQ(NULL, otto.currentVersion());
23.134 + VersionDictionary *last = otto.lastVersion();
23.135 + ASSERT_TRUE(last != NULL);
23.136 + EXPECT_EQ(1, last->generation());
23.137 + EXPECT_GE(last->timestamp(), createTime);
23.138 + EXPECT_LE(last->timestamp(), ::time(NULL));
23.139 + EXPECT_EQ( sNWords , last->count() );
23.140 + EXPECT_TRUE(last->get("animal").equals("AMINAL"));
23.141 + EXPECT_TRUE(last->get("growf").equals("growf"));
23.142 + EXPECT_EQ( NULL, last->get("asparagus").bytes );
23.143 + EXPECT_TRUE(!last->contains("asparagus"));
23.144 +
23.145 + int n=0;
23.146 + for( VersionDictionary::Iterator it(last); it; ++it) {
23.147 + n++;
23.148 + ASSERT_TRUE(!it.key().equals("asparagus"));
23.149 + }
23.150 + ASSERT_EQ(sNWords, n);
23.151 + }
23.152 + {
23.153 + printf("Writing Ottoman to a new file...\n");
23.154 + Ottoman oldhf("/tmp/test.ottoman");
23.155 +
23.156 + oldhf.saveAs("/tmp/test2.ottoman");
23.157 + }
23.158 + {
23.159 + printf("Opening new file...\n");
23.160 + Ottoman otto("/tmp/test2.ottoman");
23.161 + OverlayDictionary *current = otto.currentVersion();
23.162 + ASSERT_TRUE(current != NULL);
23.163 +
23.164 + EXPECT_EQ( sNWords , current->count() );
23.165 + EXPECT_TRUE(current->get("animal").equals("AMINAL"));
23.166 + EXPECT_TRUE(current->get("growf").equals("growf"));
23.167 + EXPECT_EQ( NULL, current->get("asparagus").bytes );
23.168 + EXPECT_TRUE(!current->contains("asparagus"));
23.169 +
23.170 + int n=0;
23.171 + for( OverlayDictionary::Iterator it(*current); it; ++it) {
23.172 + n++;
23.173 + ASSERT_TRUE(!it.key().equals("asparagus"));
23.174 + }
23.175 + ASSERT_EQ(sNWords, n);
23.176 +
23.177 + printf("Iterating the chunks...\n");
23.178 + int lastType = -1;
23.179 + int count = 0;
23.180 + n = 0;
23.181 + ChunkIterator *it = otto.chunkIterator();
23.182 + for (; *it; it->next()) {
23.183 + uint16_t type = it->chunk()->type();
23.184 + if (type != lastType) {
23.185 + if (count > 0)
23.186 + printf("%6d\n", count);
23.187 + printf("type %u ... ", type);
23.188 + lastType = type;
23.189 + count = 0;
23.190 + }
23.191 + count++;
23.192 + ASSERT_LE(type, 3);
23.193 + if (type != 0) // don't count padding chunks
23.194 + n++;
23.195 + }
23.196 + if (count > 0)
23.197 + printf("%6d\n", count);
23.198 + printf("Iterated over %i chunks\n",n);
23.199 + EXPECT_EQ(sNWords+256+1, n);
23.200 + EXPECT_TRUE(it->atEOF());
23.201 +
23.202 + printf("Scavenging...\n");
23.203 + EXPECT_TRUE( otto.scavenge() );
23.204 + }
23.205 +}
23.206 +
24.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
24.2 +++ b/test/TestUtils.cpp Sun Sep 20 15:14:12 2009 -0700
24.3 @@ -0,0 +1,104 @@
24.4 +/*
24.5 + * TestUtils.cpp
24.6 + * Ottoman
24.7 + *
24.8 + * Created by Jens Alfke on 9/12/09.
24.9 + * Copyright 2009 Jens Alfke. All rights reserved.
24.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
24.11 + */
24.12 +
24.13 +#include "TestUtils.h"
24.14 +#include "File.h"
24.15 +#include <time.h>
24.16 +#include <sys/time.h>
24.17 +
24.18 +namespace Mooseyard {
24.19 +
24.20 + std::ostream& operator<< (std::ostream &out, const Blob &blob) {
24.21 + char str[blob.length+1];
24.22 + memcpy(str,blob.bytes,blob.length);
24.23 + str[blob.length] = 0;
24.24 + out << str;
24.25 + return out;
24.26 + }
24.27 +
24.28 + void shuffle(int a[], int n, unsigned seed) {
24.29 + if (seed==0) {
24.30 + srandomdev();
24.31 + seed = random();
24.32 + }
24.33 + fprintf(stderr,"shuffle(n=%i, seed=%u)\n", n,seed);
24.34 + srandom(seed);
24.35 + for (int i=0; i<n-1; i++) {
24.36 + int j = i + (random() % (n-i));
24.37 + int temp = a[i];
24.38 + a[i] = a[j];
24.39 + a[j] = temp;
24.40 + }
24.41 + }
24.42 +
24.43 + char **sWords;
24.44 + int sNWords;
24.45 +
24.46 + void readWords() {
24.47 + if (!sWords) {
24.48 + sWords = new char*[250000];
24.49 + sNWords = 0;
24.50 +
24.51 + FILE *in = fopen("/usr/share/dict/words", "r");
24.52 + const char *word;
24.53 + size_t wordLen;
24.54 + while (NULL != (word=fgetln(in,&wordLen))) {
24.55 + if (word[wordLen-1]=='\n')
24.56 + wordLen--;
24.57 + char *str = new char[wordLen+1];
24.58 + memcpy(str, word, wordLen);
24.59 + str[wordLen] = 0;
24.60 + sWords[sNWords] = str;
24.61 + //if( sNWords % 10000 == 0)
24.62 + // printf("'%s' ... ", sWords[sNWords]->string());
24.63 + sNWords++;
24.64 + }
24.65 + }
24.66 + }
24.67 +
24.68 +#pragma mark -
24.69 +#pragma mark TIMER:
24.70 +
24.71 + Timer::Timer (const char *operation, int divisor) {
24.72 + _operation = operation;
24.73 + _divisor = divisor;
24.74 + _cpuTime = clock();
24.75 + _time = now();
24.76 + }
24.77 +
24.78 + Timer::~Timer() {
24.79 + double elapsedCPU = (clock() - _cpuTime) / 1.0e6;
24.80 + double elapsed = now() - _time;
24.81 + printf("### %s took %.6lf sec (used %.6lf sec CPU)", _operation, elapsed, elapsedCPU);
24.82 + if (_divisor > 1)
24.83 + printf(" ... per item: %.3lf usec, %.3lf usec CPU", elapsed/_divisor*1e6, elapsedCPU/_divisor*1e6);
24.84 + printf("\n");
24.85 + }
24.86 +
24.87 + double Timer::now() {
24.88 + struct timeval t;
24.89 + gettimeofday(&t,NULL);
24.90 + return (double)t.tv_sec + t.tv_usec/1.0e6;
24.91 + }
24.92 +
24.93 +}
24.94 +
24.95 +
24.96 +using namespace Mooseyard;
24.97 +
24.98 +int main(int argc, char **argv) {
24.99 + srandomdev();
24.100 + try {
24.101 + ::testing::InitGoogleTest(&argc, argv);
24.102 + return RUN_ALL_TESTS();
24.103 + } catch (const File::Error &err) {
24.104 + fprintf(stderr, "\n*** File::Error thrown: %i/%s\n", err.code,err.message);
24.105 + throw;
24.106 + }
24.107 +}
25.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
25.2 +++ b/test/TestUtils.h Sun Sep 20 15:14:12 2009 -0700
25.3 @@ -0,0 +1,37 @@
25.4 +/*
25.5 + * TestUtils.h
25.6 + * Ottoman
25.7 + *
25.8 + * Created by Jens Alfke on 9/2/09.
25.9 + * Copyright 2009 Jens Alfke. All rights reserved.
25.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
25.11 + */
25.12 +
25.13 +#include <gtest/gtest.h> // Get gtest from <http://code.google.com/p/googletest/>
25.14 +#include <iosfwd>
25.15 +#include "Base.h"
25.16 +
25.17 +namespace Mooseyard {
25.18 +
25.19 + std::ostream& operator<< (std::ostream &out, const Blob&);
25.20 +
25.21 + void shuffle(int a[], int n, unsigned seed =0);
25.22 +
25.23 + extern char **sWords;
25.24 + extern int sNWords;
25.25 +
25.26 + void readWords();
25.27 +
25.28 + class Timer {
25.29 + public:
25.30 + Timer (const char *operation, int divisor =1);
25.31 + ~Timer();
25.32 + double elapsed() {return now() - _time;}
25.33 + static double now();
25.34 + private:
25.35 + const char *_operation;
25.36 + int _divisor;
25.37 + double _cpuTime, _time;
25.38 + };
25.39 +
25.40 +}
26.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
26.2 +++ b/test/VersionDictionary_test.cpp Sun Sep 20 15:14:12 2009 -0700
26.3 @@ -0,0 +1,265 @@
26.4 +/*
26.5 + * VersionDictionary_test.cpp
26.6 + * Ottoman
26.7 + *
26.8 + * Created by Jens Alfke on 9/2/09.
26.9 + * Copyright 2009 Jens Alfke. All rights reserved.
26.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
26.11 + */
26.12 +
26.13 +
26.14 +#define VERSIONDICTIONARY_TESTING 1
26.15 +
26.16 +#include <gtest/gtest.h>
26.17 +#include "TestUtils.h"
26.18 +#include "Chunk.h"
26.19 +#include "File.h"
26.20 +#include "VersionDictionary.h"
26.21 +#include "Hash.h"
26.22 +#include <fcntl.h>
26.23 +#include <stdio.h>
26.24 +
26.25 +using namespace Mooseyard;
26.26 +
26.27 +
26.28 +class OverlayVersionDictionary :public OverlayDictionary {
26.29 +public:
26.30 + OverlayVersionDictionary (File *file)
26.31 + :OverlayDictionary(new VersionDictionary(file))
26.32 + { }
26.33 +
26.34 + int generation() const {return ((VersionDictionary*)base())->generation();}
26.35 + time_t timestamp() const {return ((VersionDictionary*)base())->timestamp();}
26.36 +
26.37 + void save(){
26.38 + saveAs(((VersionDictionary*)base())->file());
26.39 + }
26.40 +
26.41 + void saveAs (File *dstFile) {
26.42 + VersionDictionary* oldBase = (VersionDictionary*) base();
26.43 + revertTo( ((VersionDictionary*)base())->_appendAndOpen(overlay(), dstFile, baseReplaced()) );
26.44 + delete oldBase;
26.45 + }
26.46 +};
26.47 +
26.48 +
26.49 +
26.50 +TEST(File,HasPath) {
26.51 + {
26.52 + File f("/tmp/jubba", O_RDWR | O_CREAT | O_TRUNC);
26.53 + f.write("howdy");
26.54 + }
26.55 + {
26.56 + File f("/tmp/jubba", O_RDWR);
26.57 + EXPECT_TRUE(f.hasPath("/tmp/jubba"));
26.58 + File::unlink("/tmp/jubba");
26.59 + EXPECT_FALSE(f.hasPath("/tmp/jubba"));
26.60 +
26.61 + File f2("/tmp/jubba", O_RDWR | O_CREAT | O_TRUNC);
26.62 + f2.write("howdy");
26.63 + f2.flush();
26.64 +
26.65 + EXPECT_FALSE(f.hasPath("/tmp/jubba"));
26.66 + EXPECT_TRUE(f2.hasPath("/tmp/jubba"));
26.67 + }
26.68 + File::unlink("/tmp/jubba");
26.69 +}
26.70 +
26.71 +
26.72 +static int TestIterate (File *file) {
26.73 + printf("Iterating the chunks...\n");
26.74 + int lastType = -1;
26.75 + int count = 0;
26.76 + int n = 0;
26.77 + ChunkIterator it(file, 4);
26.78 + for (; it; ++it) {
26.79 + uint16_t type = it.chunk()->type();
26.80 + if (type != lastType) {
26.81 + if (count > 0)
26.82 + printf("%6d\n", count);
26.83 + printf("type %u ... ", type);
26.84 + lastType = type;
26.85 + count = 0;
26.86 + }
26.87 + count++;
26.88 + EXPECT_LE(type, 3);
26.89 + if (type != 0) // don't count padding chunks
26.90 + n++;
26.91 + }
26.92 + if (count > 0)
26.93 + printf("%6d\n", count);
26.94 + EXPECT_TRUE(it.atEOF());
26.95 + return n;
26.96 +}
26.97 +
26.98 +
26.99 +static void TestWithWords (const int nWords) {
26.100 + ASSERT_EQ(8, sizeof(Chunk));
26.101 + ASSERT_EQ(8, sizeof(KeyValueChunk));
26.102 +
26.103 + printf("Building dictionary of %i words...\n", nWords);
26.104 + readWords();
26.105 + HashDictionary dict;
26.106 + for( int i=0; i<nWords; i++) {
26.107 + Blob kv(sWords[i]);
26.108 + dict.put(Key(kv),kv);
26.109 + }
26.110 +
26.111 + time_t startTime = ::time(NULL);
26.112 + time_t createTime;
26.113 + {
26.114 + File file("/tmp/hashfiletest", O_RDWR | O_CREAT | O_TRUNC);
26.115 + VersionDictionary *hf;
26.116 + {
26.117 + Timer t("Creating & writing VersionDictionary", nWords);
26.118 + file.write("Ha5h", 4); // VersionDictionary won't write to an empty file
26.119 + hf = VersionDictionary::create(&file, &dict);
26.120 + }
26.121 + printf("File size: %llu bytes\n", file.length());
26.122 + ASSERT_TRUE(hf!=NULL);
26.123 + ASSERT_EQ(0, hf->generation());
26.124 + createTime = hf->timestamp();
26.125 + ASSERT_GE(createTime, startTime);
26.126 + ASSERT_LE(createTime, ::time(NULL));
26.127 + delete hf;
26.128 + }
26.129 + {
26.130 + File file("/tmp/hashfiletest");
26.131 + VersionDictionary hf(&file);
26.132 + ASSERT_EQ(0, hf.generation());
26.133 + ASSERT_EQ(createTime, hf.timestamp());
26.134 + {
26.135 + Timer t("Reading from VersionDictionary", nWords);
26.136 + EXPECT_EQ( nWords , hf.count() );
26.137 + for( int i=0; i<nWords; i++) {
26.138 + Key key(sWords[i]);
26.139 + Blob value = hf.get(key);
26.140 + ASSERT_TRUE(value);
26.141 + ASSERT_TRUE( value.equals(key) ) << "expected '" << key << "', got '" << value << "' (i=" << i <<")";
26.142 + }
26.143 + }
26.144 +
26.145 + printf("Iterating through the VersionDictionary...\n");
26.146 + Timer t("Iterating VersionDictionary", nWords);
26.147 + int n=0;
26.148 + for( VersionDictionary::Iterator it(&hf); it; ++it) {
26.149 + n++;
26.150 + ASSERT_TRUE(it.key().length > 0 && it.key().length < 50);
26.151 + ASSERT_TRUE(it.key().equals(it.value()));
26.152 + ASSERT_EQ( 0, ((size_t)it.value().bytes & 0x3) ); // 4-byte aligned
26.153 + }
26.154 + ASSERT_EQ(nWords, n);
26.155 + }
26.156 + {
26.157 + printf("Opening OverlayVersionDictionary...\n");
26.158 + File file("/tmp/hashfiletest", O_RDWR);
26.159 + OverlayVersionDictionary hf(&file);
26.160 + EXPECT_EQ( nWords , hf.count() );
26.161 + EXPECT_TRUE(hf.get("abatement").equals("abatement"));
26.162 +
26.163 + hf.put("abaser", "DEBASER");
26.164 + hf.put("growf", "growf");
26.165 + EXPECT_TRUE(hf.remove("abatement"));
26.166 +
26.167 + EXPECT_EQ( nWords, hf.count() );
26.168 + EXPECT_TRUE(hf.get("abaser").equals("DEBASER"));
26.169 + EXPECT_TRUE(hf.get("growf").equals("growf"));
26.170 + EXPECT_EQ( NULL, hf.get("abatement").bytes );
26.171 + EXPECT_TRUE(!hf.contains("abatement"));
26.172 +
26.173 + int n=0;
26.174 + for( OverlayVersionDictionary::Iterator it(hf); it; ++it) {
26.175 + n++;
26.176 + ASSERT_TRUE(!it.key().equals("abatement"));
26.177 + }
26.178 + ASSERT_EQ(nWords, n);
26.179 +
26.180 + printf("Saving OverlayVersionDictionary...\n");
26.181 + {
26.182 + Timer t("Saving OverlayVersionDictionary");
26.183 + hf.save();
26.184 + }
26.185 + printf("File size: %llu bytes\n", file.length());
26.186 +
26.187 + EXPECT_EQ( nWords, hf.count() );
26.188 + EXPECT_TRUE(hf.get("abaser").equals("DEBASER"));
26.189 + EXPECT_TRUE(hf.get("growf").equals("growf"));
26.190 + EXPECT_EQ( NULL, hf.get("abatement").bytes );
26.191 + EXPECT_TRUE(!hf.contains("abatement"));
26.192 +
26.193 + n=0;
26.194 + for( OverlayVersionDictionary::Iterator it(hf); it; ++it) {
26.195 + n++;
26.196 + ASSERT_TRUE(!it.key().equals("abatement"));
26.197 + }
26.198 + ASSERT_EQ(nWords, n);
26.199 + }
26.200 + {
26.201 + printf("Re-opening OverlayVersionDictionary...\n");
26.202 + File file("/tmp/hashfiletest");
26.203 + OverlayVersionDictionary hf(&file);
26.204 +
26.205 + ASSERT_EQ(1, hf.generation());
26.206 + ASSERT_GE(hf.timestamp(), createTime);
26.207 + ASSERT_LE(hf.timestamp(), ::time(NULL));
26.208 + EXPECT_EQ( nWords , hf.count() );
26.209 + EXPECT_TRUE(hf.get("abaser").equals("DEBASER"));
26.210 + EXPECT_TRUE(hf.get("growf").equals("growf"));
26.211 + EXPECT_EQ( NULL, hf.get("abatement").bytes );
26.212 + EXPECT_TRUE(!hf.contains("abatement"));
26.213 +
26.214 + int n=0;
26.215 + for( OverlayVersionDictionary::Iterator it(hf); it; ++it) {
26.216 + n++;
26.217 + ASSERT_TRUE(!it.key().equals("abatement"));
26.218 + }
26.219 + ASSERT_EQ(nWords, n);
26.220 +
26.221 + n = TestIterate(&file);
26.222 + EXPECT_GE(n, nWords+1+4);
26.223 + if (nWords > 1000)
26.224 + EXPECT_GE(n, nWords+256+4);
26.225 + }
26.226 + {
26.227 + printf("Writing VersionDictionary to a new file...\n");
26.228 + File oldFile("/tmp/hashfiletest");
26.229 + OverlayVersionDictionary oldhf(&oldFile);
26.230 +
26.231 + File newFile("/tmp/hashfiletest2", O_RDWR | O_CREAT | O_TRUNC);
26.232 + newFile.write("Ha5h", 4); // VersionDictionary won't write to an empty file
26.233 + oldhf.saveAs(&newFile);
26.234 + printf("File size: %llu bytes\n", newFile.length());
26.235 + }
26.236 + {
26.237 + printf("Opening new file...\n");
26.238 + File file("/tmp/hashfiletest2");
26.239 + OverlayVersionDictionary hf(&file);
26.240 +
26.241 + EXPECT_EQ( nWords , hf.count() );
26.242 + EXPECT_TRUE(hf.get("abaser").equals("DEBASER"));
26.243 + EXPECT_TRUE(hf.get("growf").equals("growf"));
26.244 + EXPECT_EQ( NULL, hf.get("abatement").bytes );
26.245 + EXPECT_TRUE(!hf.contains("abatement"));
26.246 +
26.247 + int n=0;
26.248 + for( OverlayVersionDictionary::Iterator it(hf); it; ++it) {
26.249 + n++;
26.250 + ASSERT_TRUE(!it.key().equals("abatement"));
26.251 + }
26.252 + ASSERT_EQ(nWords, n);
26.253 +
26.254 + n = TestIterate(&file);
26.255 + EXPECT_GE(n, nWords+1+1);
26.256 + if (nWords > 1000)
26.257 + EXPECT_EQ(nWords+256+1, n);
26.258 + }
26.259 +}
26.260 +
26.261 +
26.262 +TEST(VersionDictionary,BuildSmall) {
26.263 + TestWithWords(100);
26.264 +}
26.265 +
26.266 +TEST(VersionDictionary,BuildLarge) {
26.267 + TestWithWords(sNWords);
26.268 +}