init

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