diff options
| -rw-r--r-- | .clang-format | 358 | ||||
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | cheesemap.c | 25 | ||||
| -rw-r--r-- | cheesemap.h | 120 | ||||
| -rwxr-xr-x | format.sh | 2 | ||||
| -rw-r--r-- | makefile | 28 |
6 files changed, 537 insertions, 0 deletions
diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..8d371ca --- /dev/null +++ b/.clang-format @@ -0,0 +1,358 @@ +--- +Language: Cpp +AlignAfterOpenBracket: true +AccessModifierOffset: -1 +AlignArrayOfStructures: None +AlignConsecutiveAssignments: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: true +AlignConsecutiveBitFields: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: false +AlignConsecutiveDeclarations: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: true + AlignFunctionPointers: false + PadOperators: false +AlignConsecutiveMacros: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: false +AlignConsecutiveShortCaseStatements: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCaseArrows: false + AlignCaseColons: false +AlignConsecutiveTableGenBreakingDAGArgColons: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: false +AlignConsecutiveTableGenCondOperatorColons: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: false +AlignConsecutiveTableGenDefinitionColons: + Enabled: false + AcrossEmptyLines: false + AcrossComments: false + AlignCompound: false + AlignFunctionDeclarations: false + AlignFunctionPointers: false + PadOperators: false +AlignEscapedNewlines: Left +AlignOperands: Align +AlignTrailingComments: + AlignPPAndNotPP: true + Kind: Always + OverEmptyLines: 0 +AllowAllArgumentsOnNextLine: true +AllowAllParametersOfDeclarationOnNextLine: true +AllowBreakBeforeNoexceptSpecifier: Never +AllowBreakBeforeQtProperty: false +AllowShortBlocksOnASingleLine: Never +AllowShortCaseExpressionOnASingleLine: true +AllowShortCaseLabelsOnASingleLine: false +AllowShortCompoundRequirementOnASingleLine: true +AllowShortEnumsOnASingleLine: true +AllowShortFunctionsOnASingleLine: All +AllowShortIfStatementsOnASingleLine: WithoutElse +AllowShortLambdasOnASingleLine: All +AllowShortLoopsOnASingleLine: true +AllowShortNamespacesOnASingleLine: false +AlwaysBreakAfterDefinitionReturnType: None +AlwaysBreakBeforeMultilineStrings: true +AttributeMacros: + - __capability + - absl_nonnull + - absl_nullable + - absl_nullability_unknown +BinPackArguments: true +BinPackLongBracedList: true +BinPackParameters: BinPack +BitFieldColonSpacing: Both +BracedInitializerIndentWidth: -1 +BraceWrapping: + AfterCaseLabel: false + AfterClass: false + AfterControlStatement: Never + AfterEnum: false + AfterExternBlock: false + AfterFunction: false + AfterNamespace: false + AfterObjCDeclaration: false + AfterStruct: false + AfterUnion: false + BeforeCatch: false + BeforeElse: false + BeforeLambdaBody: false + BeforeWhile: false + IndentBraces: false + SplitEmptyFunction: true + SplitEmptyRecord: true + SplitEmptyNamespace: true +BreakAdjacentStringLiterals: true +BreakAfterAttributes: Leave +BreakAfterJavaFieldAnnotations: false +BreakAfterOpenBracketBracedList: false +BreakAfterOpenBracketFunction: false +BreakAfterOpenBracketIf: false +BreakAfterOpenBracketLoop: false +BreakAfterOpenBracketSwitch: false +BreakAfterReturnType: None +BreakArrays: true +BreakBeforeBinaryOperators: None +BreakBeforeCloseBracketBracedList: false +BreakBeforeCloseBracketFunction: false +BreakBeforeCloseBracketIf: false +BreakBeforeCloseBracketLoop: false +BreakBeforeCloseBracketSwitch: false +BreakBeforeConceptDeclarations: Always +BreakBeforeBraces: Attach +BreakBeforeInlineASMColon: OnlyMultiline +BreakBeforeTemplateCloser: false +BreakBeforeTernaryOperators: true +BreakBinaryOperations: Never +BreakConstructorInitializers: BeforeColon +BreakFunctionDefinitionParameters: false +BreakInheritanceList: BeforeColon +BreakStringLiterals: true +BreakTemplateDeclarations: Yes +ColumnLimit: 80 +CommentPragmas: '^ IWYU pragma:' +CompactNamespaces: false +ConstructorInitializerIndentWidth: 4 +ContinuationIndentWidth: 4 +Cpp11BracedListStyle: AlignFirstComment +DerivePointerAlignment: false +DisableFormat: false +EmptyLineAfterAccessModifier: Never +EmptyLineBeforeAccessModifier: LogicalBlock +EnumTrailingComma: Leave +ExperimentalAutoDetectBinPacking: false +FixNamespaceComments: true +ForEachMacros: + - foreach + - Q_FOREACH + - BOOST_FOREACH +IfMacros: + - KJ_IF_MAYBE +IncludeBlocks: Regroup +IncludeCategories: + - Regex: '^<ext/.*\.h>' + Priority: 2 + SortPriority: 0 + CaseSensitive: false + - Regex: '^<.*\.h>' + Priority: 1 + SortPriority: 0 + CaseSensitive: false + - Regex: '^<.*' + Priority: 2 + SortPriority: 0 + CaseSensitive: false + - Regex: '.*' + Priority: 3 + SortPriority: 0 + CaseSensitive: false +IncludeIsMainRegex: '([-_](test|unittest))?$' +IncludeIsMainSourceRegex: '' +IndentAccessModifiers: false +IndentCaseBlocks: false +IndentCaseLabels: true +IndentExportBlock: true +IndentExternBlock: AfterExternBlock +IndentGotoLabels: true +IndentPPDirectives: None +IndentRequiresClause: true +IndentWidth: 2 +IndentWrappedFunctionNames: false +InsertBraces: false +InsertNewlineAtEOF: false +InsertTrailingCommas: None +IntegerLiteralSeparator: + Binary: 0 + BinaryMinDigitsInsert: 0 + BinaryMaxDigitsRemove: 0 + Decimal: 0 + DecimalMinDigitsInsert: 0 + DecimalMaxDigitsRemove: 0 + Hex: 0 + HexMinDigitsInsert: 0 + HexMaxDigitsRemove: 0 + BinaryMinDigits: 0 + DecimalMinDigits: 0 + HexMinDigits: 0 +JavaScriptQuotes: Leave +JavaScriptWrapImports: true +KeepEmptyLines: + AtEndOfFile: false + AtStartOfBlock: false + AtStartOfFile: true +KeepFormFeed: false +LambdaBodyIndentation: Signature +LineEnding: DeriveLF +MacroBlockBegin: '' +MacroBlockEnd: '' +MainIncludeChar: Quote +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: None +NumericLiteralCase: + ExponentLetter: Leave + HexDigit: Leave + Prefix: Leave + Suffix: Leave +ObjCBinPackProtocolList: Never +ObjCBlockIndentWidth: 2 +ObjCBreakBeforeNestedBlockParam: true +ObjCSpaceAfterProperty: false +ObjCSpaceBeforeProtocolList: true +OneLineFormatOffRegex: '' +PackConstructorInitializers: NextLine +PenaltyBreakAssignment: 2 +PenaltyBreakBeforeFirstCallParameter: 1 +PenaltyBreakBeforeMemberAccess: 150 +PenaltyBreakComment: 300 +PenaltyBreakFirstLessLess: 120 +PenaltyBreakOpenParenthesis: 0 +PenaltyBreakScopeResolution: 500 +PenaltyBreakString: 1000 +PenaltyBreakTemplateDeclaration: 10 +PenaltyExcessCharacter: 1000000 +PenaltyIndentedWhitespace: 0 +PenaltyReturnTypeOnItsOwnLine: 200 +PointerAlignment: Left +PPIndentWidth: -1 +QualifierAlignment: Leave +RawStringFormats: + - Language: Cpp + Delimiters: + - cc + - CC + - cpp + - Cpp + - CPP + - 'c++' + - 'C++' + CanonicalDelimiter: '' + BasedOnStyle: google + - Language: TextProto + Delimiters: + - pb + - PB + - proto + - PROTO + EnclosingFunctions: + - EqualsProto + - EquivToProto + - PARSE_PARTIAL_TEXT_PROTO + - PARSE_TEST_PROTO + - PARSE_TEXT_PROTO + - ParseTextOrDie + - ParseTextProtoOrDie + - ParseTestProto + - ParsePartialTestProto + CanonicalDelimiter: pb + BasedOnStyle: google +ReferenceAlignment: Pointer +ReflowComments: Always +RemoveBracesLLVM: false +RemoveEmptyLinesInUnwrappedLines: false +RemoveParentheses: Leave +RemoveSemicolon: false +RequiresClausePosition: OwnLine +RequiresExpressionIndentation: OuterScope +SeparateDefinitionBlocks: Leave +ShortNamespaceLines: 1 +SkipMacroDefinitionBody: false +SortIncludes: + Enabled: true + IgnoreCase: false + IgnoreExtension: false +SortJavaStaticImport: Before +SortUsingDeclarations: LexicographicNumeric +SpaceAfterCStyleCast: false +SpaceAfterLogicalNot: false +SpaceAfterOperatorKeyword: false +SpaceAfterTemplateKeyword: true +SpaceAroundPointerQualifiers: Default +SpaceBeforeAssignmentOperators: true +SpaceBeforeCaseColon: false +SpaceBeforeCpp11BracedList: false +SpaceBeforeCtorInitializerColon: true +SpaceBeforeInheritanceColon: true +SpaceBeforeJsonColon: false +SpaceBeforeParens: ControlStatements +SpaceBeforeParensOptions: + AfterControlStatements: true + AfterForeachMacros: true + AfterFunctionDefinitionName: false + AfterFunctionDeclarationName: false + AfterIfMacros: true + AfterNot: false + AfterOverloadedOperator: false + AfterPlacementOperator: true + AfterRequiresInClause: false + AfterRequiresInExpression: false + BeforeNonEmptyParentheses: false +SpaceBeforeRangeBasedForLoopColon: true +SpaceBeforeSquareBrackets: false +SpaceInEmptyBraces: Never +SpacesBeforeTrailingComments: 2 +SpacesInAngles: Never +SpacesInContainerLiterals: true +SpacesInLineCommentPrefix: + Minimum: 1 + Maximum: -1 +SpacesInParens: Never +SpacesInParensOptions: + ExceptDoubleParentheses: false + InCStyleCasts: false + InConditionalStatements: false + InEmptyParentheses: false + Other: false +SpacesInSquareBrackets: false +Standard: Auto +StatementAttributeLikeMacros: + - Q_EMIT +StatementMacros: + - Q_UNUSED + - QT_REQUIRE_VERSION +TableGenBreakInsideDAGArg: DontBreak +TabWidth: 8 +UseTab: Never +VerilogBreakBetweenInstancePorts: true +WhitespaceSensitiveMacros: + - BOOST_PP_STRINGIZE + - CF_SWIFT_NAME + - NS_SWIFT_NAME + - PP_STRINGIZE + - STRINGIZE +WrapNamespaceBodyWithEmptyLines: Leave +... + diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..8109a16 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +*.o +*.d +*.json +.cache/
\ No newline at end of file diff --git a/cheesemap.c b/cheesemap.c new file mode 100644 index 0000000..c443593 --- /dev/null +++ b/cheesemap.c @@ -0,0 +1,25 @@ +#include "cheesemap.h" + +#include <stddef.h> + +static inline uintptr_t cm_raw_capacity(const struct cheesemap_raw* map) { + assert(map != NULL); + return map->cap_mask + 1; +} + +static inline uint8_t* cm_raw_origin(const struct cheesemap_raw* map, + uintptr_t entry_size) { + assert(map != NULL); + return map->ctrl - entry_size * cm_raw_capacity(map); +} + +void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size, + struct cheesemap_fns* fns) { + assert(map != NULL); + assert(fns != NULL); + + if (map->ctrl == NULL) return; + + uint8_t* origin = cm_raw_origin(map, entry_size); + fns->free(origin, fns->mem_usr); +} diff --git a/cheesemap.h b/cheesemap.h new file mode 100644 index 0000000..0afdf5a --- /dev/null +++ b/cheesemap.h @@ -0,0 +1,120 @@ +#ifndef CHEESEMAP +#define CHEESEMAP + +//////////////////////////////// +// options and includes +// + +#include <stdbool.h> +#include <stdint.h> +#include <string.h> + +#include CM_OPT_ASSERT_PATH +#ifndef assert +#error "assert is not defined" +#endif + +enum { + CM_GROUP_SIZE = 8, +}; + +//////////////////////////////// +// cheesemap callback functions +// + +typedef uint64_t cm_hash_t; + +/* memory methods */ +typedef void* (*cm_malloc_fn)(uintptr_t size, uintptr_t alignment, + uint8_t* user); +typedef void (*cm_free_fn)(void* ptr, uint8_t* user); + +/* hash and compare methods */ +typedef cm_hash_t (*cm_hash_fn)(const uint8_t* key, uint8_t* user); +typedef bool (*cm_compare_fn)(const uint8_t* key1, const uint8_t* key2, + uint8_t* user); + +//////////////////////////////// +// callback methods needed by cheesemap +// + +struct cheesemap_fns { + uint8_t *mem_usr, *map_usr; + cm_malloc_fn malloc; + cm_free_fn free; + cm_hash_fn hash; + cm_compare_fn compare; +}; + +//////////////////////////////// +// raw cheesemap implementation +// +// layout: +// [entries...][control bits...][mirror first CM_GROUP_SIZE bits] + +enum { + CM_INITIAL_CAPACITY = CM_GROUP_SIZE, + CM_CTRL_EMPTY = 0x80, + CM_CTRL_DELETED = 0xFE, + CM_H2_MASK = 0x7F, + CM_FP_SIZE = 7 +}; + +static inline uintptr_t cm_h1(cm_hash_t hash) { + return (uintptr_t)(hash >> CM_FP_SIZE); +} + +static inline uint8_t cm_h2(cm_hash_t hash) { + return (uint8_t)(hash & CM_H2_MASK); +} + +struct cheesemap_raw { + // mask of the capacity + uintptr_t cap_mask; + // number of entries in the map + uintptr_t entry_count; + // number of entry left until resize + uintptr_t growth_left; + // pointer to the control bytes + uint8_t* ctrl; +}; + +#define cm_raw_new() ((struct cheesemap_raw){0}) + +void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size, + struct cheesemap_fns* fns); + +//////////////////////////////// +// cheesemap implementation +// + +struct cheesemap { + uintptr_t entry_size; + struct cheesemap_fns fns; + struct cheesemap_raw raw; +}; + +static inline struct cheesemap cm_new(uintptr_t entry_size, uint8_t* mem_usr, + cm_malloc_fn malloc, cm_free_fn free, + uint8_t* map_usr, cm_hash_fn hash, + cm_compare_fn compare) { + assert(malloc != NULL && free != NULL); + assert(hash != NULL && compare != NULL); + + struct cheesemap_fns fns = { + mem_usr, map_usr, // + malloc, free, // + hash, compare, // + }; + + return (struct cheesemap){entry_size, fns, cm_raw_new()}; +} + +static inline void cm_drop(struct cheesemap* map) { + assert(map != NULL); + + cm_raw_drop(&map->raw, map->entry_size, &map->fns); + memset(map, 0, sizeof(*map)); +} + +#endif diff --git a/format.sh b/format.sh new file mode 100755 index 0000000..02b0d0d --- /dev/null +++ b/format.sh @@ -0,0 +1,2 @@ +#!/bin/bash +clang-format -i $(find . -name "*.h" -o -name "*.c") diff --git a/makefile b/makefile new file mode 100644 index 0000000..8e7686a --- /dev/null +++ b/makefile @@ -0,0 +1,28 @@ +# Header in which assert(x) is defined +CM_OPT_ASSERT_PATH ?= <assert.h> + +CC ?= gcc + +CM_DIR := $(abspath $(dir $(lastword $(MAKEFILE_LIST)))) + +CM_SOURCE := $(CM_DIR)/cheesemap.c +CM_OBJECT := $(CM_SOURCE:.c=.o) +CM_DEPEND := $(CM_SOURCE:.c=.d) + +CM_CC_FLAGS := \ + -Wall -Wextra -pedantic \ + -MMD -MP -I$(CM_DIR) + +CM_CC_FLAGS += -DCM_OPT_ASSERT_PATH='$(CM_OPT_ASSERT_PATH)' + +.PHONY: all +all: $(CM_OBJECT) + +$(CM_OBJECT): $(CM_SOURCE) + $(CC) $(CM_CC_FLAGS) -c $< -o $@ + +.PHONY: clean +clean:: + $(RM) $(CM_OBJECT) $(CM_DEPEND) + +-include $(CM_DEPEND)
\ No newline at end of file |