diff options
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.excalidraw | 738 | ||||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.png | bin | 0 -> 275574 bytes | |||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.excalidraw | 2253 | ||||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.png | bin | 0 -> 637322 bytes | |||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw | 854 | ||||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.png | bin | 0 -> 274163 bytes | |||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/libstdc++-unordered-map.md | 615 | ||||
| -rw-r--r-- | posts/libstdc++-std-unordered-map/metadata.txt | 3 |
8 files changed, 4463 insertions, 0 deletions
diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.excalidraw b/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.excalidraw new file mode 100644 index 0000000..60b368d --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.excalidraw @@ -0,0 +1,738 @@ +{ + "type": "excalidraw", + "version": 2, + "source": "https://excalidraw.com", + "elements": [ + { + "id": "hDOfSlYNCwNPl2hHjpVEl", + "type": "rectangle", + "x": 123.04882708218719, + "y": -51.47838705152023, + "width": 514, + "height": 418, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 3 + }, + "seed": 575453329, + "version": 168, + "versionNonce": 2089916863, + "isDeleted": false, + "boundElements": [], + "updated": 1683381046263, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 205, + "versionNonce": 1046139263, + "isDeleted": false, + "id": "eDw6E1QC4eq186ZurOA6j", + "fillStyle": "cross-hatch", + "strokeWidth": 2, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 142.5488270821872, + "y": 79.02161294847977, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 479, + "height": 264, + "seed": 891608287, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683380858596, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 436, + "versionNonce": 1105109791, + "isDeleted": false, + "id": "FWKPzKIwu4BQP9PX0giuu", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 167.0488270821872, + "y": 259.4715085643461, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 430.0000000000001, + "height": 68.10020876826724, + "seed": 1578929841, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "z4UMflR39WzqR-p8bpZbC", + "type": "arrow" + } + ], + "updated": 1683380501875, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 335, + "versionNonce": 794095999, + "isDeleted": false, + "id": "vMGaKMGlkksz0KytGp_Yh", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 163.5488270821872, + "y": 103.9214041802125, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 430.0000000000001, + "height": 134.10020876826724, + "seed": 1378606737, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ueQ015UWfFRL7duikh9nH", + "type": "arrow" + }, + { + "id": "z4UMflR39WzqR-p8bpZbC", + "type": "arrow" + }, + { + "id": "-qA0wn3LG59fPQAb9R_mM", + "type": "arrow" + } + ], + "updated": 1683381051726, + "link": null, + "locked": false + }, + { + "id": "ExmVxss4kPKz9c5FpNaOF", + "type": "text", + "x": -22.951172917812812, + "y": 45.72161294847977, + "width": 120.86666870117188, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1119188159, + "version": 162, + "versionNonce": 293171249, + "isDeleted": false, + "boundElements": [ + { + "id": "uhxqjXnvQ4IvdJI4OGlzY", + "type": "arrow" + } + ], + "updated": 1683380501875, + "link": null, + "locked": false, + "text": "_Hash_node", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node", + "lineHeight": 1.25 + }, + { + "id": "uhxqjXnvQ4IvdJI4OGlzY", + "type": "arrow", + "x": 124.64900296234876, + "y": -45.368859054373544, + "width": 99.60017588016157, + "height": 76.8904720028533, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 2 + }, + "seed": 764037201, + "version": 177, + "versionNonce": 770128945, + "isDeleted": false, + "boundElements": null, + "updated": 1683381067108, + "link": null, + "locked": false, + "points": [ + [ + 0, + 0 + ], + [ + -76.60017588016157, + 2.890472002853315 + ], + [ + -99.60017588016157, + 76.8904720028533 + ] + ], + "lastCommittedPoint": null, + "startBinding": { + "elementId": "PwFfvWLGylMQT1yZKbaen", + "focus": 1.2740162694501311, + "gap": 13.890472002853315 + }, + "endBinding": { + "elementId": "ExmVxss4kPKz9c5FpNaOF", + "focus": -0.3223332763513156, + "gap": 14.200000000000017 + }, + "startArrowhead": "arrow", + "endArrowhead": null + }, + { + "id": "onpl8Re9WrZNx32fv4Se5", + "type": "arrow", + "x": 612.0488270821872, + "y": -21.47838705152023, + "width": 144, + "height": 62, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 2 + }, + "seed": 1826351025, + "version": 156, + "versionNonce": 307666943, + "isDeleted": false, + "boundElements": null, + "updated": 1683381076623, + "link": null, + "locked": false, + "points": [ + [ + 0, + 0 + ], + [ + 90, + -51 + ], + [ + 144, + 11 + ] + ], + "lastCommittedPoint": null, + "startBinding": null, + "endBinding": { + "elementId": "TK_jgkHHp6vHcKbQQZvx9", + "focus": 0.16364555982868684, + "gap": 14 + }, + "startArrowhead": "arrow", + "endArrowhead": null + }, + { + "id": "TK_jgkHHp6vHcKbQQZvx9", + "type": "text", + "x": 671.0488270821872, + "y": 3.5216129484797705, + "width": 182.6999969482422, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 808640735, + "version": 69, + "versionNonce": 906876913, + "isDeleted": false, + "boundElements": [ + { + "id": "onpl8Re9WrZNx32fv4Se5", + "type": "arrow" + } + ], + "updated": 1683380501875, + "link": null, + "locked": false, + "text": "_Hash_node_base", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node_base", + "lineHeight": 1.25 + }, + { + "id": "ueQ015UWfFRL7duikh9nH", + "type": "arrow", + "x": 143.33677617823426, + "y": 91.27018997089216, + "width": 113.8364331453071, + "height": 94.25142297758761, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 2 + }, + "seed": 1529493791, + "version": 174, + "versionNonce": 823990705, + "isDeleted": false, + "boundElements": null, + "updated": 1683381083462, + "link": null, + "locked": false, + "points": [ + [ + 0, + 0 + ], + [ + -88.28794909604707, + 14.251422977587609 + ], + [ + -113.8364331453071, + 94.25142297758761 + ] + ], + "lastCommittedPoint": null, + "startBinding": { + "elementId": "vMGaKMGlkksz0KytGp_Yh", + "focus": 1.1563931297943435, + "gap": 20.212050903952957 + }, + "endBinding": { + "elementId": "tYFGjMlcFbD50ALu0U4jN", + "focus": 0.07406223511562718, + "gap": 15 + }, + "startArrowhead": "arrow", + "endArrowhead": null + }, + { + "id": "tYFGjMlcFbD50ALu0U4jN", + "type": "text", + "x": -80.95117291781281, + "y": 200.52161294847977, + "width": 188.76666259765625, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1138291295, + "version": 107, + "versionNonce": 1660637105, + "isDeleted": false, + "boundElements": [ + { + "id": "ueQ015UWfFRL7duikh9nH", + "type": "arrow" + } + ], + "updated": 1683380501875, + "link": null, + "locked": false, + "text": "_Hash_node_value", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node_value", + "lineHeight": 1.25 + }, + { + "id": "XTl9EoGdCPnf2-cQiX5q5", + "type": "text", + "x": 665.0488270821872, + "y": 211.5216129484798, + "width": 250.60000610351562, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1867556031, + "version": 66, + "versionNonce": 1491566559, + "isDeleted": false, + "boundElements": [ + { + "id": "BUNoaUgWgLqvxdgUxGGP7", + "type": "arrow" + } + ], + "updated": 1683380501875, + "link": null, + "locked": false, + "text": "_Hash_node_value_base", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node_value_base", + "lineHeight": 1.25 + }, + { + "id": "BUNoaUgWgLqvxdgUxGGP7", + "type": "arrow", + "x": 585.0488270821872, + "y": 114.52161294847977, + "width": 209, + "height": 82, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 2 + }, + "seed": 165592191, + "version": 128, + "versionNonce": 725102993, + "isDeleted": false, + "boundElements": null, + "updated": 1683380501875, + "link": null, + "locked": false, + "points": [ + [ + 0, + 0 + ], + [ + 156, + 6 + ], + [ + 209, + 82 + ] + ], + "lastCommittedPoint": null, + "startBinding": null, + "endBinding": { + "elementId": "XTl9EoGdCPnf2-cQiX5q5", + "focus": 0.17070677628285585, + "gap": 15.000000000000028 + }, + "startArrowhead": "arrow", + "endArrowhead": null + }, + { + "id": "sAwpQmJk46bC8izcVPKcI", + "type": "text", + "x": 662.0488270821872, + "y": 340.52161294847974, + "width": 251.53334045410156, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 489574993, + "version": 162, + "versionNonce": 242853279, + "isDeleted": false, + "boundElements": [], + "updated": 1683381045881, + "link": null, + "locked": false, + "text": "_Hash_node_code_cache", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node_code_cache", + "lineHeight": 1.25 + }, + { + "id": "vCA2HYT0gDra33BqKdlO2", + "type": "text", + "x": 245.0488270821872, + "y": 281.52161294847974, + "width": 280.8999938964844, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1870791391, + "version": 74, + "versionNonce": 814966975, + "isDeleted": false, + "boundElements": null, + "updated": 1683380625509, + "link": null, + "locked": false, + "text": "std::size_t _M_hash_code", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "std::size_t _M_hash_code", + "lineHeight": 1.25 + }, + { + "id": "y1wNXdaACk8KMTpQ3m6cF", + "type": "text", + "x": 266.0488270821872, + "y": 162.52161294847977, + "width": 185.76666259765625, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1101079967, + "version": 272, + "versionNonce": 1499281841, + "isDeleted": false, + "boundElements": null, + "updated": 1683381014975, + "link": null, + "locked": false, + "text": "Value _M_storage", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "Value _M_storage", + "lineHeight": 1.25 + }, + { + "id": "PwFfvWLGylMQT1yZKbaen", + "type": "rectangle", + "x": 138.0488270821872, + "y": -31.47838705152023, + "width": 479, + "height": 87, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "hachure", + "strokeWidth": 2, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 3 + }, + "seed": 1259435647, + "version": 141, + "versionNonce": 822007135, + "isDeleted": false, + "boundElements": [ + { + "id": "uhxqjXnvQ4IvdJI4OGlzY", + "type": "arrow" + } + ], + "updated": 1683380855181, + "link": null, + "locked": false + }, + { + "id": "sd-jCjpfa3JjqJhMjpnym", + "type": "text", + "x": 238.0488270821872, + "y": -2.4783870515202295, + "width": 283.29998779296875, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1502531473, + "version": 255, + "versionNonce": 1933342737, + "isDeleted": false, + "boundElements": null, + "updated": 1683380682456, + "link": null, + "locked": false, + "text": "_Hash_node_base* _M_nxt", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 18, + "containerId": null, + "originalText": "_Hash_node_base* _M_nxt", + "lineHeight": 1.25 + }, + { + "id": "-qA0wn3LG59fPQAb9R_mM", + "type": "arrow", + "x": 599.0488270821872, + "y": 268.52161294847974, + "width": 205, + "height": 49, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 2 + }, + "seed": 37561777, + "version": 112, + "versionNonce": 1812439263, + "isDeleted": false, + "boundElements": null, + "updated": 1683381058993, + "link": null, + "locked": false, + "points": [ + [ + 0, + 0 + ], + [ + 161, + -2 + ], + [ + 205, + 47 + ] + ], + "lastCommittedPoint": null, + "startBinding": { + "elementId": "vMGaKMGlkksz0KytGp_Yh", + "focus": 1.4384383705794166, + "gap": 30.5 + }, + "endBinding": null, + "startArrowhead": "arrow", + "endArrowhead": null + } + ], + "appState": { + "gridSize": null, + "viewBackgroundColor": "#ffffff" + }, + "files": {} +}
\ No newline at end of file diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.png b/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.png Binary files differnew file mode 100644 index 0000000..ec45011 --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.png diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.excalidraw b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.excalidraw new file mode 100644 index 0000000..58b3fb8 --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.excalidraw @@ -0,0 +1,2253 @@ +{ + "type": "excalidraw", + "version": 2, + "source": "https://excalidraw.com", + "elements": [ + { + "type": "rectangle", + "version": 481, + "versionNonce": 1470651089, + "isDeleted": false, + "id": "OjURoiy25AoGO6MLiyHkR", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 476.6824678776138, + "y": 298.25, + "strokeColor": "#1864ab", + "backgroundColor": "transparent", + "width": 827.9999999999999, + "height": 67.99999999999999, + "seed": 1620584046, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916711, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 3067, + "versionNonce": 408344753, + "isDeleted": false, + "id": "8YlixtkZ0zSU_EvGl4fKh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 367.3062078094441, + "y": 610.7734738864004, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 104.11048411580077, + "height": 249.84665346007102, + "seed": 1355897970, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916711, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "xUttQCOY2JjRwO4r_Zfvh", + "focus": -0.3255907753348359, + "gap": 2.004495521899912 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + -70.6237399318303, + -74.52347388640044 + ], + [ + -104.11048411580077, + -249.84665346007102 + ] + ] + }, + { + "type": "text", + "version": 1452, + "versionNonce": 841962527, + "isDeleted": false, + "id": "4GJnTRmGDjxnh7FpQtrfd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": -17.75256392161066, + "y": 259.9669361343948, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 291.0333251953125, + "height": 20, + "seed": 337238766, + "groupIds": [], + "roundness": null, + "boundElements": [ + { + "id": "8YlixtkZ0zSU_EvGl4fKh", + "type": "arrow" + } + ], + "updated": 1683319938657, + "link": null, + "locked": false, + "fontSize": 16, + "fontFamily": 1, + "text": "_Hash_node_base _M_before_begin", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "_Hash_node_base _M_before_begin", + "lineHeight": 1.25, + "baseline": 14 + }, + { + "type": "rectangle", + "version": 773, + "versionNonce": 507157137, + "isDeleted": false, + "id": "yWNAUOAIDJyGvqDPDgpts", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 343.2745098039216, + "y": 137.96124684077506, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "4Ak9ONcd-1KquAi0rpgCu" + } + ], + "updated": 1683319916711, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 205, + "versionNonce": 1816056575, + "isDeleted": false, + "id": "4Ak9ONcd-1KquAi0rpgCu", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 355.7745098039216, + "y": 152.46124684077506, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "yWNAUOAIDJyGvqDPDgpts", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 723, + "versionNonce": 1920978431, + "isDeleted": false, + "id": "d6zZnv35Pp51FpmjuxvSF", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": -14.630970262577819, + "y": 152.23202211580815, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 276.5, + "height": 20, + "seed": 337238766, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319946894, + "link": null, + "locked": false, + "fontSize": 16, + "fontFamily": 1, + "text": "_Hash_node_base* _M_buckets[]", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "_Hash_node_base* _M_buckets[]", + "lineHeight": 1.25, + "baseline": 14 + }, + { + "type": "rectangle", + "version": 818, + "versionNonce": 940186399, + "isDeleted": false, + "id": "H7Nbia4JidW3iOuMs19BD", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 344.4281105791389, + "y": 193.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "C_Jycp9YorBKZJFf0lUQq" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 252, + "versionNonce": 965732945, + "isDeleted": false, + "id": "C_Jycp9YorBKZJFf0lUQq", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 356.9281105791389, + "y": 207.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "H7Nbia4JidW3iOuMs19BD", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 820, + "versionNonce": 1467440959, + "isDeleted": false, + "id": "HgFmSQx87f1jQYREl9Ubj", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 344.4281105791389, + "y": 250.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "JzlHvq10K3qg75CUO4PSX" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 255, + "versionNonce": 94402609, + "isDeleted": false, + "id": "JzlHvq10K3qg75CUO4PSX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 356.9281105791389, + "y": 264.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "HgFmSQx87f1jQYREl9Ubj", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 902, + "versionNonce": 2095521631, + "isDeleted": false, + "id": "yZ6lIk6u8CuTA2-mEHqbg", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 343.6824678776138, + "y": 305, + "strokeColor": "#1864ab", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 945, + "versionNonce": 2378257, + "isDeleted": false, + "id": "m1IsEtmioJLOw-X2bFwgH", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 342.1824678776138, + "y": 361, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "SBbiT8xOH9jr1VYz2uynS" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 379, + "versionNonce": 984210303, + "isDeleted": false, + "id": "SBbiT8xOH9jr1VYz2uynS", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 354.6824678776138, + "y": 375.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "m1IsEtmioJLOw-X2bFwgH", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 970, + "versionNonce": 34791409, + "isDeleted": false, + "id": "LKRj5KlN41SZPmYfRkXWI", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 340.6824678776138, + "y": 414.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "UjBujmTfnWkhvyywuOIQv" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 404, + "versionNonce": 83891103, + "isDeleted": false, + "id": "UjBujmTfnWkhvyywuOIQv", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 353.1824678776138, + "y": 429, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "LKRj5KlN41SZPmYfRkXWI", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1022, + "versionNonce": 1500756433, + "isDeleted": false, + "id": "WW_5hyqamXEmQo6BXbAj0", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 340.6824678776138, + "y": 471.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "d4vnj3b82KSZ6iWllmFPj" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 456, + "versionNonce": 1947879359, + "isDeleted": false, + "id": "d4vnj3b82KSZ6iWllmFPj", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 353.1824678776138, + "y": 485.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "WW_5hyqamXEmQo6BXbAj0", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1084, + "versionNonce": 660494257, + "isDeleted": false, + "id": "eTNVmZfzhmtaYwrzlHEhX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 341.1824678776138, + "y": 528, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "AEKi-Y7XPzWdD2qWhevd8" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 517, + "versionNonce": 1176041439, + "isDeleted": false, + "id": "AEKi-Y7XPzWdD2qWhevd8", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 353.6824678776138, + "y": 542.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "eTNVmZfzhmtaYwrzlHEhX", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1161, + "versionNonce": 2113550737, + "isDeleted": false, + "id": "7yFs5DP7JyEOLKC2PQrrC", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 340.6824678776138, + "y": 582.5, + "strokeColor": "#2b8a3e", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 1210, + "versionNonce": 1048502129, + "isDeleted": false, + "id": "dZu1QIcloAehd0fvC2YFt", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 343.1824678776138, + "y": 639.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "zZsf5XutQWI2QqNbEkfGf" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 643, + "versionNonce": 351652895, + "isDeleted": false, + "id": "zZsf5XutQWI2QqNbEkfGf", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 355.6824678776138, + "y": 653.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "dZu1QIcloAehd0fvC2YFt", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1271, + "versionNonce": 926140753, + "isDeleted": false, + "id": "9jyZDK5a6C3ZThyLMU8eU", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 343.6824678776138, + "y": 692.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "5jrGXE79tYDNDDEOtBaYk" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 705, + "versionNonce": 1573187647, + "isDeleted": false, + "id": "5jrGXE79tYDNDDEOtBaYk", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 356.1824678776138, + "y": 707, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 1492873454, + "groupIds": [ + "vUybFR0eOiUuHMT9VvdZi" + ], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "9jyZDK5a6C3ZThyLMU8eU", + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1129, + "versionNonce": 24147761, + "isDeleted": false, + "id": "ONtMFi-HJ3osgmAjkuWYs", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 489.1824678776138, + "y": 305, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 1186, + "versionNonce": 92744831, + "isDeleted": false, + "id": "1_dSNhOetsCgtYQ_s51Hx", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 777.4324678776138, + "y": 306.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1205, + "versionNonce": 1529814769, + "isDeleted": false, + "id": "NJlI6XG3fH_8Eia4nlWLy", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 390.6824678776138, + "y": 333.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 115.97585074976507, + "height": 244.97762811297162, + "seed": 1623296366, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "-0i159PySDfAXjLw46YGi", + "gap": 2.25, + "focus": -0.6728174976878056 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 77, + 45 + ], + [ + 115.97585074976507, + 244.97762811297162 + ] + ] + }, + { + "type": "arrow", + "version": 807, + "versionNonce": 168510623, + "isDeleted": false, + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 526.6824678776138, + "y": 333.5474028211833, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 243.99126904170907, + "height": 86.74717869661833, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "ytCfont2iIzHFS7wJr_ci", + "focus": -0.7762833467286282, + "gap": 2.2700465587752774 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 121, + -83.29795688747532 + ], + [ + 243.99126904170907, + 3.449221809143012 + ] + ] + }, + { + "type": "rectangle", + "version": 1335, + "versionNonce": 1655707857, + "isDeleted": false, + "id": "w9t6oond8UfIrkxQyMmM9", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1060.9324678776138, + "y": 305.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 88.00000000000001, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1008, + "versionNonce": 1922521279, + "isDeleted": false, + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 812.544342931109, + "y": 339.9584128865794, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.04427725376036, + "height": 93, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "yC_IWudaRTFJLHBBgwK5a", + "focus": -0.7645761873332839, + "gap": 2.364799194971738 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 114, + -93 + ], + [ + 241.04427725376036, + -5.786352782409267 + ] + ] + }, + { + "type": "rectangle", + "version": 1458, + "versionNonce": 666293937, + "isDeleted": false, + "id": "-0i159PySDfAXjLw46YGi", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 502.0630975614502, + "y": 580.9287298531372, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86.00000000000011, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "NJlI6XG3fH_8Eia4nlWLy", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2094, + "versionNonce": 2095765649, + "isDeleted": false, + "id": "fDGakrHl2y_N1MGaVmSvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 495.5558334850327, + "y": 580.0113367602937, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686747, + "height": 59.9098051159695, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "KzlOPbqaLCtoJknIGsvAx", + "type": "arrow" + }, + { + "id": "NJlI6XG3fH_8Eia4nlWLy", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2113, + "versionNonce": 1946394225, + "isDeleted": false, + "id": "xUttQCOY2JjRwO4r_Zfvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 198.9763864410761, + "y": 304.9223249044295, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "MdHItGBZlhFM9xb42IRYD" + ], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "8YlixtkZ0zSU_EvGl4fKh", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 2522, + "versionNonce": 1986034975, + "isDeleted": false, + "id": "KzlOPbqaLCtoJknIGsvAx", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 235.45423218312015, + "y": 335.89311016027773, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 256.78862854926973, + "height": 293.35688983972227, + "seed": 908754930, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "fDGakrHl2y_N1MGaVmSvh", + "focus": -0.5926224535648676, + "gap": 3.0829639493107095 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 72.22823569449366, + 293.35688983972227 + ], + [ + 256.78862854926973, + 293.01848158351527 + ] + ] + }, + { + "type": "arrow", + "version": 625, + "versionNonce": 2076747857, + "isDeleted": false, + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 536.1514604948921, + "y": 612.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132.22679610543443, + "height": 249.99031234594383, + "seed": 623910702, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "ONtMFi-HJ3osgmAjkuWYs", + "focus": 0.9701129124428218, + "gap": 3.2596876540561652 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 90.58624011998367, + -117 + ], + [ + -41.64055598545076, + -249.99031234594383 + ] + ] + }, + { + "type": "text", + "version": 140, + "versionNonce": 11632959, + "isDeleted": false, + "id": "0KVHqF3l1lAQG2TIieqkX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1071.6824678776138, + "y": 318.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 902878830, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916712, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 2154, + "versionNonce": 1041331761, + "isDeleted": false, + "id": "ytCfont2iIzHFS7wJr_ci", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 772.9763337932766, + "y": 304.47723960906353, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "type": "arrow" + }, + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2055, + "versionNonce": 2123170143, + "isDeleted": false, + "id": "IaZmTKFovKV0N4MauTSwd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 485.9763337932766, + "y": 303.2211091186287, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + } + ], + "updated": 1683319916712, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2269, + "versionNonce": 886857201, + "isDeleted": false, + "id": "yC_IWudaRTFJLHBBgwK5a", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 1055.9763337932764, + "y": 302.4772396090636, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683319916713, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 613, + "versionNonce": 1544910239, + "isDeleted": false, + "id": "of9FXlpX2GdiqhOptmjP1", + "fillStyle": "cross-hatch", + "strokeWidth": 4, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 486.6824678776138, + "y": 572.75, + "strokeColor": "#2b8a3e", + "backgroundColor": "transparent", + "width": 286, + "height": 70.99999999999996, + "seed": 1620584046, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 39, + "versionNonce": 2092816863, + "isDeleted": false, + "id": "MWgAuO0S41DrScm7qgfu8", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 314.6824678776138, + "y": 152.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 13.766666412353516, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "0", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "0", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 106, + "versionNonce": 437024657, + "isDeleted": false, + "id": "PGhSRxiwIvaCd5oh9rST6", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 318.79913467143706, + "y": 205.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 5.433333396911621, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "1", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "1", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 126, + "versionNonce": 885343743, + "isDeleted": false, + "id": "bwI65kVColAL4S0GhqJHb", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 316.79913467143706, + "y": 258.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 14.233333587646484, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "2", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "2", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 152, + "versionNonce": 1503223153, + "isDeleted": false, + "id": "JmMK4NlZS9xapVWh8zXRu", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 316.79913467143706, + "y": 318.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 13.633333206176758, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "3", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "3", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 182, + "versionNonce": 759836191, + "isDeleted": false, + "id": "le4KDLifEpqZ_cUdKNJ33", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 313.79913467143706, + "y": 373.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 12.800000190734863, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "4", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "4", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 200, + "versionNonce": 1179551569, + "isDeleted": false, + "id": "gke8vacx1jIcwTUTZI9ZL", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 311.79913467143706, + "y": 426.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 12.366666793823242, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "5", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "5", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 234, + "versionNonce": 1899827775, + "isDeleted": false, + "id": "5nlISVHShvhnbdYkIeEWG", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 310.79913467143706, + "y": 486.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 12.800000190734863, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "6", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "6", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 274, + "versionNonce": 444822833, + "isDeleted": false, + "id": "eQbrtHbWik-Fyr2BgLc1r", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 318.79913467143706, + "y": 543.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 10.766666412353516, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "7", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "7", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 311, + "versionNonce": 1501459039, + "isDeleted": false, + "id": "noZKGRw4sweJwwaxUG_r1", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 311.79913467143706, + "y": 651.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 12.166666984558105, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "9", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "9", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 394, + "versionNonce": 1503635217, + "isDeleted": false, + "id": "zMqfaBYHHGYM4FU4wm4ZC", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 315.79913467143706, + "y": 710.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 19.200000762939453, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "10", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "10", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 444, + "versionNonce": 1323224703, + "isDeleted": false, + "id": "Ob9hWOikGv6G4vig8H-oV", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 310.79913467143706, + "y": 599.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 15.300000190734863, + "height": 25, + "seed": 1291535282, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916713, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "8", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "8", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "id": "CcBeftkJdOnOJCd3u510f", + "type": "text", + "x": -16.527962452411174, + "y": 189.22690527127978, + "width": 240.13333129882812, + "height": 20, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1189179647, + "version": 623, + "versionNonce": 663932081, + "isDeleted": false, + "boundElements": null, + "updated": 1683319984206, + "link": null, + "locked": false, + "text": "size_t _M_bucket_count = 11", + "fontSize": 16, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 14, + "containerId": null, + "originalText": "size_t _M_bucket_count = 11", + "lineHeight": 1.25 + }, + { + "id": "56jgqKlVGVs597B3fb6m0", + "type": "rectangle", + "x": 594.6824678776138, + "y": 584.25, + "width": 132, + "height": 50, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": { + "type": 3 + }, + "seed": 952556575, + "version": 151, + "versionNonce": 1975940145, + "isDeleted": false, + "boundElements": [ + { + "type": "text", + "id": "QDts3yqcBiUgXuxA-E-oX" + } + ], + "updated": 1683319916713, + "link": null, + "locked": false + }, + { + "id": "QDts3yqcBiUgXuxA-E-oX", + "type": "text", + "x": 624.6158022281998, + "y": 596.75, + "width": 72.13333129882812, + "height": 25, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1458566161, + "version": 87, + "versionNonce": 120513375, + "isDeleted": false, + "boundElements": null, + "updated": 1683319916713, + "link": null, + "locked": false, + "text": "<19, 19>", + "fontSize": 20, + "fontFamily": 1, + "textAlign": "center", + "verticalAlign": "middle", + "baseline": 18, + "containerId": "56jgqKlVGVs597B3fb6m0", + "originalText": "<19, 19>", + "lineHeight": 1.25 + }, + { + "type": "rectangle", + "version": 239, + "versionNonce": 1709825009, + "isDeleted": false, + "id": "buSUoavgf_Af8aPtc-gV1", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 581.6824678776138, + "y": 308.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 910572241, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "5gBibH2KPwn5So0ObiuvP" + } + ], + "updated": 1683319916713, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 185, + "versionNonce": 723965855, + "isDeleted": false, + "id": "5gBibH2KPwn5So0ObiuvP", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 602.7824663517349, + "y": 320.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 89.80000305175781, + "height": 25, + "seed": 674805937, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916714, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<36, 36>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "buSUoavgf_Af8aPtc-gV1", + "originalText": "<36, 36>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 287, + "versionNonce": 818449343, + "isDeleted": false, + "id": "hS7RxZYjoxvAh-xcMcXWw", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 871.6824678776138, + "y": 308.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 71562353, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "hTRSWa0vCqDIfHrhRjJ5A" + } + ], + "updated": 1683319916714, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 241, + "versionNonce": 111563697, + "isDeleted": false, + "id": "hTRSWa0vCqDIfHrhRjJ5A", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 892.6158022281998, + "y": 321, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 90.13333129882812, + "height": 25, + "seed": 227425873, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916714, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<25, 25>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "hS7RxZYjoxvAh-xcMcXWw", + "originalText": "<25, 25>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 351, + "versionNonce": 719500689, + "isDeleted": false, + "id": "rBoiVjSuf474Tru-eeXE3", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1154.6824678776138, + "y": 307.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 1471038015, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "MDQWBmmGzdijwd6PvQ1HW" + } + ], + "updated": 1683319916714, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 313, + "versionNonce": 1912203263, + "isDeleted": false, + "id": "MDQWBmmGzdijwd6PvQ1HW", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1183.9824671146744, + "y": 320, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 73.4000015258789, + "height": 25, + "seed": 977904223, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319916714, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<14, 14>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "rBoiVjSuf474Tru-eeXE3", + "originalText": "<14, 14>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "text", + "version": 746, + "versionNonce": 822796881, + "isDeleted": false, + "id": "G2x1T0NStHCjH5AsPsJFX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "dashed", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": -14.297327280841444, + "y": 611.2407235296181, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 247.96665954589844, + "height": 20, + "seed": 2106006975, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683319934198, + "link": null, + "locked": false, + "fontSize": 16, + "fontFamily": 1, + "text": "size_t _M_element_count = 4", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "size_t _M_element_count = 4", + "lineHeight": 1.25, + "baseline": 14 + }, + { + "id": "KAN-a6dwS0egHBGIHii3J", + "type": "text", + "x": -16.549286059186727, + "y": 644.6138255130141, + "width": 320.8999938964844, + "height": 20, + "angle": 0, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "groupIds": [], + "roundness": null, + "seed": 1094298815, + "version": 383, + "versionNonce": 786068273, + "isDeleted": false, + "boundElements": null, + "updated": 1683319916714, + "link": null, + "locked": false, + "text": "_Prime_rehash_policy _M_rehash_policy", + "fontSize": 16, + "fontFamily": 1, + "textAlign": "left", + "verticalAlign": "top", + "baseline": 14, + "containerId": null, + "originalText": "_Prime_rehash_policy _M_rehash_policy", + "lineHeight": 1.25 + } + ], + "appState": { + "gridSize": null, + "viewBackgroundColor": "#ffffff" + }, + "files": {} +}
\ No newline at end of file diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.png b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.png Binary files differnew file mode 100644 index 0000000..2856dbc --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.png diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw new file mode 100644 index 0000000..ef8e75d --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw @@ -0,0 +1,854 @@ +{ + "type": "excalidraw", + "version": 2, + "source": "https://excalidraw.com", + "elements": [ + { + "type": "text", + "version": 1626, + "versionNonce": 1706265386, + "isDeleted": false, + "id": "4GJnTRmGDjxnh7FpQtrfd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 122.24743607838934, + "y": 176.4669361343948, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 171.1999969482422, + "height": 25, + "seed": 337238766, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683476589551, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "_M_before_begin", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "_M_before_begin", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 1417, + "versionNonce": 1215560554, + "isDeleted": false, + "id": "ONtMFi-HJ3osgmAjkuWYs", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 457.1824678776138, + "y": 352, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 1474, + "versionNonce": 804585002, + "isDeleted": false, + "id": "1_dSNhOetsCgtYQ_s51Hx", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 745.4324678776138, + "y": 353.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1539, + "versionNonce": 1076509354, + "isDeleted": false, + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 493.68246787761376, + "y": 381.5474028211833, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 242.18516432344842, + "height": 86.70204311252468, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475915878, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "ytCfont2iIzHFS7wJr_ci", + "focus": 0.7382390820646367, + "gap": 5.071058646631116 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 123.00000000000006, + 86.70204311252468 + ], + [ + 242.18516432344842, + 2.8683393657897227 + ] + ] + }, + { + "type": "rectangle", + "version": 1625, + "versionNonce": 1678337846, + "isDeleted": false, + "id": "w9t6oond8UfIrkxQyMmM9", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1028.9324678776138, + "y": 352.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 88.00000000000001, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475821296, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 1534, + "versionNonce": 1481153526, + "isDeleted": false, + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 779.544342931109, + "y": 381.9584128865794, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 238.8360551730816, + "height": 90, + "seed": 1536158450, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475923593, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "yC_IWudaRTFJLHBBgwK5a", + "focus": 0.7042011222257625, + "gap": 5.551683800279079 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 97, + 90 + ], + [ + 238.8360551730816, + 3.019680509788941 + ] + ] + }, + { + "type": "rectangle", + "version": 1747, + "versionNonce": 1618607926, + "isDeleted": false, + "id": "-0i159PySDfAXjLw46YGi", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 156.06309756145015, + "y": 349.9287298531372, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 86.00000000000011, + "height": 54, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683475798995, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2411, + "versionNonce": 2073114410, + "isDeleted": false, + "id": "fDGakrHl2y_N1MGaVmSvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 149.55583348503265, + "y": 349.0113367602938, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686747, + "height": 59.9098051159695, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "KzlOPbqaLCtoJknIGsvAx", + "type": "arrow" + } + ], + "updated": 1683475798995, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2166, + "versionNonce": 1890994346, + "isDeleted": false, + "id": "xUttQCOY2JjRwO4r_Zfvh", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 149.9763864410761, + "y": 216.9223249044295, + "strokeColor": "#000000", + "backgroundColor": "#fa5252", + "width": 86, + "height": 54, + "seed": 802113778, + "groupIds": [ + "MdHItGBZlhFM9xb42IRYD" + ], + "roundness": { + "type": 3 + }, + "boundElements": [], + "updated": 1683476607406, + "link": null, + "locked": false + }, + { + "type": "arrow", + "version": 3450, + "versionNonce": 891088694, + "isDeleted": false, + "id": "KzlOPbqaLCtoJknIGsvAx", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 183.45423218312015, + "y": 248.8931101602777, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 50.77176430550634, + "height": 128.70967935539264, + "seed": 908754930, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683475906708, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "fDGakrHl2y_N1MGaVmSvh", + "focus": -1.0228716005205234, + "gap": 6.979300727704427 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + -50.77176430550634, + 50.356889839722356 + ], + [ + -40.870485401541345, + 128.70967935539264 + ] + ] + }, + { + "type": "arrow", + "version": 1487, + "versionNonce": 798940935, + "isDeleted": false, + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "fillStyle": "hachure", + "strokeWidth": 4, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 191.15146049489215, + "y": 380.25000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 258.3568841683801, + "height": 97.77140805893004, + "seed": 623910702, + "groupIds": [], + "roundness": { + "type": 2 + }, + "boundElements": [], + "updated": 1683476888670, + "link": null, + "locked": false, + "startBinding": null, + "endBinding": { + "elementId": "IaZmTKFovKV0N4MauTSwd", + "focus": 0.7648622002620978, + "gap": 4.473432544181321 + }, + "lastCommittedPoint": null, + "startArrowhead": null, + "endArrowhead": "arrow", + "points": [ + [ + 0, + 0 + ], + [ + 118.5862401199837, + 96 + ], + [ + 258.3568841683801, + -1.7714080589300352 + ] + ] + }, + { + "type": "text", + "version": 428, + "versionNonce": 427228074, + "isDeleted": false, + "id": "0KVHqF3l1lAQG2TIieqkX", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1039.6824678776138, + "y": 365.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 61, + "height": 25, + "seed": 902878830, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "nullptr", + "textAlign": "left", + "verticalAlign": "top", + "containerId": null, + "originalText": "nullptr", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 2442, + "versionNonce": 440888310, + "isDeleted": false, + "id": "ytCfont2iIzHFS7wJr_ci", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 740.9763337932766, + "y": 351.47723960906353, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "type": "arrow" + }, + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2346, + "versionNonce": 546491593, + "isDeleted": false, + "id": "IaZmTKFovKV0N4MauTSwd", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 453.9763337932766, + "y": 349.2211091186287, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "Ny2QhsH_O2yzh8cCFQcfG", + "type": "arrow" + }, + { + "id": "Y5tCVK--4hiNPC1bDqqPQ", + "type": "arrow" + } + ], + "updated": 1683476884986, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 2469, + "versionNonce": 1229762102, + "isDeleted": false, + "id": "yC_IWudaRTFJLHBBgwK5a", + "fillStyle": "hachure", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0.011693373069791235, + "x": 1023.9763337932764, + "y": 351.4772396090636, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 241.4122681686746, + "height": 60.90973674926162, + "seed": 802113778, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "id": "ZjjxoMRNfs8gZNqCgD5Nt", + "type": "arrow" + } + ], + "updated": 1683475827842, + "link": null, + "locked": false + }, + { + "type": "rectangle", + "version": 454, + "versionNonce": 1548922102, + "isDeleted": false, + "id": "56jgqKlVGVs597B3fb6m0", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 248.68246787761382, + "y": 353.25000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 952556575, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "QDts3yqcBiUgXuxA-E-oX" + }, + { + "id": "KzlOPbqaLCtoJknIGsvAx", + "type": "arrow" + } + ], + "updated": 1683475798996, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 389, + "versionNonce": 1228096874, + "isDeleted": false, + "id": "QDts3yqcBiUgXuxA-E-oX", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 278.61580222819975, + "y": 365.75000000000006, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 72.13333129882812, + "height": 25, + "seed": 1458566161, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475798996, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<19, 19>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "56jgqKlVGVs597B3fb6m0", + "originalText": "<19, 19>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 527, + "versionNonce": 1974966570, + "isDeleted": false, + "id": "buSUoavgf_Af8aPtc-gV1", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 549.6824678776138, + "y": 355.25, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 910572241, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "5gBibH2KPwn5So0ObiuvP" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 473, + "versionNonce": 369714806, + "isDeleted": false, + "id": "5gBibH2KPwn5So0ObiuvP", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 570.7824663517349, + "y": 367.75, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 89.80000305175781, + "height": 25, + "seed": 674805937, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<36, 36>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "buSUoavgf_Af8aPtc-gV1", + "originalText": "<36, 36>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 575, + "versionNonce": 914285546, + "isDeleted": false, + "id": "hS7RxZYjoxvAh-xcMcXWw", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 839.6824678776138, + "y": 355.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 71562353, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "hTRSWa0vCqDIfHrhRjJ5A" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 529, + "versionNonce": 541140918, + "isDeleted": false, + "id": "hTRSWa0vCqDIfHrhRjJ5A", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 860.6158022281998, + "y": 368, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 90.13333129882812, + "height": 25, + "seed": 227425873, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<25, 25>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "hS7RxZYjoxvAh-xcMcXWw", + "originalText": "<25, 25>", + "lineHeight": 1.25, + "baseline": 18 + }, + { + "type": "rectangle", + "version": 552, + "versionNonce": 1569642154, + "isDeleted": false, + "id": "rBoiVjSuf474Tru-eeXE3", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1122.6824678776138, + "y": 354.5, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 132, + "height": 50, + "seed": 1471038015, + "groupIds": [], + "roundness": { + "type": 3 + }, + "boundElements": [ + { + "type": "text", + "id": "MDQWBmmGzdijwd6PvQ1HW" + } + ], + "updated": 1683475820654, + "link": null, + "locked": false + }, + { + "type": "text", + "version": 514, + "versionNonce": 678346998, + "isDeleted": false, + "id": "MDQWBmmGzdijwd6PvQ1HW", + "fillStyle": "cross-hatch", + "strokeWidth": 1, + "strokeStyle": "solid", + "roughness": 1, + "opacity": 100, + "angle": 0, + "x": 1151.9824671146744, + "y": 367, + "strokeColor": "#000000", + "backgroundColor": "transparent", + "width": 73.4000015258789, + "height": 25, + "seed": 977904223, + "groupIds": [], + "roundness": null, + "boundElements": [], + "updated": 1683475820654, + "link": null, + "locked": false, + "fontSize": 20, + "fontFamily": 1, + "text": "<14, 14>", + "textAlign": "center", + "verticalAlign": "middle", + "containerId": "rBoiVjSuf474Tru-eeXE3", + "originalText": "<14, 14>", + "lineHeight": 1.25, + "baseline": 18 + } + ], + "appState": { + "gridSize": null, + "viewBackgroundColor": "#ffffff" + }, + "files": {} +}
\ No newline at end of file diff --git a/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.png b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.png Binary files differnew file mode 100644 index 0000000..34d8154 --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.png diff --git a/posts/libstdc++-std-unordered-map/libstdc++-unordered-map.md b/posts/libstdc++-std-unordered-map/libstdc++-unordered-map.md new file mode 100644 index 0000000..b76ffe9 --- /dev/null +++ b/posts/libstdc++-std-unordered-map/libstdc++-unordered-map.md @@ -0,0 +1,615 @@ +We all love maps. We love hash maps even more. They should be fast and +help to solve a large number of problems. Do you ever wonder about how they are +working under the hood? In this post I am going to explore implementation +details of unordered associative containers from C++ Standard Library +(precisely GCC's libstdc++ implementation, I'll use [b9b7981f3d][37] revision +for code examples). + +Currently there are four types of unordered associative containers: + +* `std::unordered_map`, +* `std::unordered_set`, +* `std::unordered_multimap`, +* `std::unordered_multiset`. + +Usually, they are implemented on top of some kind of `Hashtable` container. I am +going to jump into implementation of this `Hashtable` container directly, +because that's where all the interesting stuff is hidden. + +I'll focus on the key/value containers with a unique set of keys +(`std::unordered_map`), `std::unordered_set` have mostly similar logic. Multi +keys containers are different beasts. They share a large portion of code with +unique keys containers, but insertion and find logic is quite different, due to +the set of stored keys is actually a [multi set][34] (allows multiple instances of +the same key). + +GCC's libstdc++ implementation can be found in the [hashtable.h header][1], the +class of interest is named `_Hashtable`. There will be a lot of names with +leading underscores. Not everyone is used to such code, but Standard Library +implementers have no choice [to avoid collisions with user defined names][2] +(macros for example). + +## Policy-Based Design + +`_Hashtable` class implemented by decomposition into [policies][35] and closely +recalls [GCC's Policy-Based Data Structures design][36]. Some of these policies +are available for redefinition by the user, for example `_Alloc`, `_Equal` and +`_Hash`. Some depend on the container type, like `_ExtractKey`, `_Value`. And +others like `_RangeHash` and `_RehashPolicy` can be defined by library implementers +only. + +```cpp +template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> +class _Hashtable +<...> +``` + +## Data Layout + +If you don't want to dive into the details, you can use [this comment][3] +from the hashtable.h header to grasp the basics of `_Hashtable` data layout. + +### Nodes + +One of the basic building blocks of the `_Hashtable` is a node. Each node is +allocated from the heap and stores container data along with metadata +information to maintain hash table data structure. The actual content of the +node is data dependent (more about it later). + +The node itself is a compound entity and contains several parts, some of them +are optional. The design of the node structs brings to mind +[matryoshka dolls][12], because they are nested to each other. More complex +node type (with more data) is inherited from the simpler node type (with a +little bit less data). Let's walk through the components bottom up (from +simpler to more complex). + +`_Hash_node_base` [defined][4] in the following way. It has only `_M_nxt` +field, which is a pointer to the next node of the hash table. + +```cpp +struct _Hash_node_base +{ + _Hash_node_base* _M_nxt; + +<...> +}; +``` + +The next one ` _Hash_node_value_base` is a little bit more interesting +(see code [here][5]). `_Hash_node_value_base` has a `_Value` template +parameter which is actual data stored in the container. + +```cpp +template<typename _Value> + struct _Hash_node_value_base + { + typedef _Value value_type; + + __gnu_cxx::__aligned_buffer<_Value> _M_storage; + + <...> + }; +``` + +`_Value` type is wrapped into `__gnu_cxx::__aligned_buffer` (thin wrapper around +`std::aligned_storage`) to [decouple][6] memory allocation from actual object +creation. + +The [next struct][7] is `_Hash_node_code_cache` and it implements hash value +caching logic. + +```cpp +template<bool _Cache_hash_code> + struct _Hash_node_code_cache + { }; + +template<> + struct _Hash_node_code_cache<true> + { std::size_t _M_hash_code; }; +``` + +`_Hash_node_code_cache` uses template specialization mechanism to extend +struct with an additional `_M_hash_code` field. And this optimization, I +believe, is one of the reasons why the «matryoshka dolls»-like design for node structs +are used. This way [Empty Base Optimization (EBO)][8] can be leveraged, when +`_Hash_node_code_cache` will be extended by inheritance. And that's exactly +what `_Hash_node_value` [is doing][8]: + +```cpp +template<typename _Value, bool _Cache_hash_code> + struct _Hash_node_value + : _Hash_node_value_base<_Value> + , _Hash_node_code_cache<_Cache_hash_code> + { }; +``` + +Size of the `_Hash_node_value` will be the same as size of +`_Hash_node_value_base<_Value>` in case template argument `_Cache_hash_code` is +false as `_Hash_node_code_cache` will be an empty struct. + +The final piece of the puzzle is the `_Hash_node` combining everything above +together: + +```cpp +template<typename _Value, bool _Cache_hash_code> + struct _Hash_node + : _Hash_node_base + , _Hash_node_value<_Value, _Cache_hash_code> + { + <...> + }; +``` + +Below is the picture ([original](libstdc++-hash-node-layout.png)) of `_Hash_node` struct +data layout to better visualize what's going on. + + + +Summarizing, `_Hash_node` (directly or inherited from base structs) contains +the following data. + +1. `_Hash_node_base* _M_nxt` is a pointer to the next element in the linked list + of hash table elements. +2. `__gnu_cxx::__aligned_buffer<_Value> _M_storage` — node data itself. For + example for `std::unordered_map<std::string, int>` container `_Value` template + argument is `std::pair<const std::string, int>`. +3. `std::size_t _M_hash_code` optional cached value of key's hash. + +### Hash table + +`_Hashtable` class [defined][10] in the following way (I replaced type aliases +with actual types being used to simplify code reading): + +* `__buckets_ptr` -> `_Hash_node_base**`, +* `size_type` -> `std::size_t`, +* `__node_base` -> `_Hash_node_base`, +* `__node_base_ptr` -> `_Hash_node_base*`. + +```cpp +template<<...>> + class _Hashtable + <...> + { + private: + _Hash_node_base** _M_buckets = &_M_single_bucket; + std::size_t _M_bucket_count = 1; + _Hash_node_base _M_before_begin; + std::size_t _M_element_count = 0; + _RehashPolicy _M_rehash_policy; + + <...> + _Hash_node_base* _M_single_bucket = nullptr; + }; +``` + +The `_Hashtable` class itself is a combination of +`std::forward_list<_Hash_node>` containing the elements and +`std::vector<std::forward_list<_Hash_node>::iterator>` representing the buckets +([code comment][11]). + +`_Hash_node_base** _M_buckets` is an array of pointers to hash table nodes. You +can think of it as `_Hash_node_base* _M_buckets[]` instead of pointer to a +pointer. + +`_Hash_node_base _M_before_begin` is a special node without any user data. +This node stores a pointer to the first hash table element (if there is +any) in `_M_before_begin._M_nxt`. + +An interesting thing is that `_M_buckets` contains `_Hash_node_base*` +instead of `_Hash_node*`. The reason is because `_M_buckets` is kind of a +storage for two types of objects: actual hash table nodes and a special +«before begin node» (`_M_before_begin`). Invariant is each bucket +stores a pointer to the node **before** the first node from the bucket. +Meaning, the bucket containing the first element of the table actually stores +the address of the `_M_before_begin` element. I hope it becomes clearer with +an example. + +Suppose we have the following code. We create `std::unordered_map` and insert +four keys in this order: 14, 25, 36, 19. + +```cpp +std::unordered_map<int, int> map; + +map[14] = 14; +map[25] = 25; +map[36] = 36; +map[19] = 19; +``` + +Then the internal `_Hashtable` linked list will look like one on the picture +below ([original](libstdc++-hashtable-linked-list.png)). The key order in the +hash table is a reverse insertion order, so key's iteration order will be: +19, 36, 25, 14. + + + + +Let's make a real hash table from the linked list by adding +buckets ([original](libstdc++-hashtable-layout.png)). + + + +There are 11 buckets in the picture (vertical stack of rectangles), only two +buckets are not empty: bucket #3 (keys 36, 25 and 14) and bucket #8 (key 19). +Thin arrows are pointers from the `_Hashtable` internal linked list from the +previous picture, this time slightly rearranged and grouped together by +buckets. Now you can probably understand better what I meant by the phrase +«each bucket stores a pointer to the node before the first node from the +bucket». Bucket #3 has keys 36, 25 and 14, but a `_Hash_node_base*` from +`_M_buckets` array point to the element with a key 19, which is a **previous** +element in the hash table iteration order. Same logic is true for the bucket #3. +For this bucket `_M_buckets` array has a pointer to the `_M_before_begin` node. + +## «Fast» and «slow» hash functions + +GCC's libstdc++ hash table implementation distinguish between fast and slow +hash functions. If hash function is slow, then hash code will be cached +inside the hash table node. + +Currently `std::hash` is [fast by default][26] (including user defined types), +except for `long double` and string-like types (`std::string`, +`std::string_view` and all other variations of character types). + +```cpp +template<typename _Hash> +struct __is_fast_hash : public std::true_type +{ }; + +template<> +struct __is_fast_hash<hash<long double>> : public std::false_type +{ }; +``` + +I am not completely sure what is the reasoning behind marking `std::hash<long double>` +as slow (and the [commit message][15] didn't shed more light on the topic), but for +string-like types it totally makes sense. + +Comparison of two strings with length `n` and `m` has a `O(min(n, m))` time +complexity, but if we'll cache hash value in the hash table node, we can +implement faster negative comparison: if hash codes of two strings do not +match, we can instantly conclude they are not equal. Moreover, for a `rehash` +operation we can avoid hash recalculation for every key in the hash table as +well. All of that in exchange for 8 more bytes of memory to store a hash value +(`std::size_t`) for every node. Seems like a reasonable trade-off for me. + + +As a side note I want to mention that for integer types `std::hash` +is [defined][16] as an [identity function][17], which is indeed fast. + +```cpp +#define _Cxx_hashtable_define_trivial_hash(_Tp) \ + template<> \ + struct hash<_Tp> : public __hash_base<size_t, _Tp> \ + { \ + size_t \ + operator()(_Tp __val) const noexcept \ + { return static_cast<size_t>(__val); } \ + }; +``` + + +## Insert + +Now, when we know how hash table data structure is organized internally, let's +look into the implementation of `insert`. + +High level steps are the following. + +1. Check there is no such key in the hash table. +2. Create a hash table node. +3. Insert a new node to a hash table data structure. + +The implementation is in the `_M_insert_unique` [method][13]. And there is +a surprise from the very first line of the code. + +```cpp +if (size() <= __small_size_threshold()) + for (auto __it = begin(); __it != end(); ++__it) + if (this->_M_key_equals_tr(__k, *__it._M_cur)) + return { __it, false }; +``` + +If the hash table is «small» we just iterate from the beginning to the end and +compare all the keys already in the hash table with a key we are trying to +insert. Thresholds for «fast» and «slow» hash functions are [different][18]. + +```cpp +template<typename _Hash> +struct _Hashtable_hash_traits +{ + static constexpr std::size_t + __small_size_threshold() noexcept + { return std::__is_fast_hash<_Hash>::value ? 0 : 20; } +}; +``` + +Then, we generate a hash code from a search key and try to find if there is a +node in the hash table, but only for «big» hash tables, as we already did a +linear search for «small» ones. + +```cpp +__hash_code __code = this->_M_hash_code_tr(__k); +size_type __bkt = _M_bucket_index(__code); + +if (size() > __small_size_threshold()) + if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code)) + return { iterator(__node), false }; +``` + +And finally, if there is no such key in the hash table, we create a new node +and insert it into the data structure. + +```cpp +_Scoped_node __node { + __node_builder_t::_S_build(std::forward<_Kt>(__k), + std::forward<_Arg>(__v), + __node_gen), + this +}; +auto __pos + = _M_insert_unique_node(__bkt, __code, __node._M_node); +__node._M_node = nullptr; +return { __pos, true }; +``` + +Actual insertion logic is hidden inside `_M_insert_unique_node` [method][19]. +There we decide if the hash table requires a rehash and insert a node into +the beginning of the bucket. + +```cpp +const __rehash_state& __saved_state = _M_rehash_policy._M_state(); +std::pair<bool, std::size_t> __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, + __n_elt); + +if (__do_rehash.first) + { + _M_rehash(__do_rehash.second, __saved_state); + __bkt = _M_bucket_index(__code); + } + +this->_M_store_code(*__node, __code); + +// Always insert at the beginning of the bucket. +_M_insert_bucket_begin(__bkt, __node); +++_M_element_count; +return iterator(__node); +``` + +There is a lot of interesting things inside `_M_rehash_policy._M_need_rehash`, +but I don't want to bore you with too many details, only mention the fact that +the number of buckets in the hash table is a [prime number][20]. + + +## Find + +`_Hashtable::find` has the same optimization for small hash tables as `insert`, +for «small» hash tables with «slow» hash function we will do a +[linear search first][21], otherwise do a usual [bucket search][22]. + +```cpp +__hash_code __code = this->_M_hash_code(__k); +std::size_t __bkt = _M_bucket_index(__code); +return const_iterator(_M_find_node(__bkt, __k, __code)); +``` + +`_M_find_node` is [implemented][23] through the call to `_M_find_before_node`. + +```cpp +__node_ptr +_M_find_node(size_type __bkt, const key_type& __key, + __hash_code __c) const +{ + __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); + if (__before_n) + return static_cast<__node_ptr>(__before_n->_M_nxt); + return nullptr; +} +``` + +`_M_find_before_node` is a good building block to have if you'll think about +`erase` implementation as we need to remove an element from the singly linked +lists, so having a pointer to a previous node comes in handy. + +`_M_find_before_node` does mostly what we expect it to do, but has a couple of +interesting things in the sleeve. + +We [locate][24] a pointer to the element before the first bucket element. + +```cpp +__node_base_ptr __prev_p = _M_buckets[__bkt]; +if (!__prev_p) + return nullptr; +``` + +And [iterate][25] through elements in the bucket. + +```cpp +for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; + __p = __p->_M_next()) + { + if (this->_M_equals(__k, __code, *__p)) + return __prev_p; + + if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + break; + __prev_p = __p; + } +``` + +There is no stop condition in the `for` loop statement itself, but only in the +loop body. We will stop when there is no next element in the hash table linked +list or we are done with a current bucket. + +```cpp +if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + break; +``` + +The only way for us to understand we have crossed the bucket's boundary is to +explicitly get the bucket number for the element. To do so, we need to either +locate the cached hash value from the node itself, or recalculate hash code +from the key by calling `std::hash`. Now you probably get a better +understanding of the rationale behind `__is_fast_hash` logic as we need to know +the hash value of each element in the bucket chain until we find the right +one. And if the `std::hash` calls are expensive and hash code wasn't cached in +the node, then `find` performance might severely degrade. + +Well, back to `_M_find_before_node`, to compare the search key with a key in the +node we call `_M_equals`, [where][27] we compare hash values first and if they are +equal, then compare keys. + +```cpp +bool +_M_equals(const _Key& __k, __hash_code __c, +const _Hash_node_value<_Value, __hash_cached::value>& __n) const +{ return _S_equals(__c, __n) && _M_key_equals(__k, __n); } +``` + +And at the same time, `_S_equals` have two overloads, one for nodes with cached +value and one for nodes without hash. When a node [has cached value][28], we +compare key hash with a hash in the node. If there is [no cached hash +value][29], we do nothing. Think about integer keys for example. We know +`std::hash<int>{}(x) == x`, so there is no point in comparing hashes first. + +```cpp +static bool +_S_equals(__hash_code __c, const _Hash_node_code_cache<true>& __n) +{ return __c == __n._M_hash_code; } + +static bool +_S_equals(__hash_code, const _Hash_node_code_cache<false>&) +{ return true; } +``` + +## Erase + +Last operation we need to cover to get a complete understanding of basic hash +table operations is `erase`. As I mentioned above, from the internal +representation point of view, nodes are connected together as a singly linked +list, so erase operation is [similar][30] to element removal from linked list. + +As a first step we need to make sure the key we want to erase from the container is +present, to simplify the code, we actually will find the node **before** the +node we are going to remove. There are again two possible paths for «small» and «big» +hash tables. + +For «small» tables we just do a linear search in the linked list by calling +`_M_find_before_node`. + +```cpp +if (size() <= __small_size_threshold()) + { + __prev_n = _M_find_before_node(__k); + if (!__prev_n) + return 0; + + // We found a matching node, erase it. + __n = static_cast<__node_ptr>(__prev_n->_M_nxt); + __bkt = _M_bucket_index(*__n); + } +``` + +And for bigger ones, we are trying to find the correct bucket for the key and then +do a search in the bucket. + +```cpp +else + { + __hash_code __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + + // Look for the node before the first matching node. + __prev_n = _M_find_before_node(__bkt, __k, __code); + if (!__prev_n) + return 0; + + // We found a matching node, erase it. + __n = static_cast<__node_ptr>(__prev_n->_M_nxt); + } +``` + +If we found something, the actual manipulations with the linked list pointers are +done in the [overload][31] of `_M_erase` method for three arguments: `__bkt` +(bucket), `__prev_n` (previous node in the hash table linked list) and `__n` +(node we want to erase), where we update `_M_nxt ` pointer for `__prev_n` and +`_M_buckets` value if necessary, then destroy the node itself. + +```cpp +if (__prev_n == _M_buckets[__bkt]) + _M_remove_bucket_begin(__bkt, __n->_M_next(), + __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0); +else if (__n->_M_nxt) + { + size_type __next_bkt = _M_bucket_index(*__n->_M_next()); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __prev_n; + } + +__prev_n->_M_nxt = __n->_M_nxt; +iterator __result(__n->_M_next()); +this->_M_deallocate_node(__n); +--_M_element_count; + +return __result; +``` + +## Closing thoughts + +There are a lot of cool tricks implemented to improve performance of +`std::unordered_map` libstdc++ implementation. These tricks help for sure, +but the main issue of `std::unordered_map` (not only libstdc++ implementation, +but all standard compatible ones) is cache unfriendliness. + +Almost every operation on the container is practically a textbook example of +[pointer chasing][32], so for real world use cases performance would not be as great +as it can be in «ideal» implementation from the data locality point of view. The main +problem is standard compatible implementation requires reference and iterator stability +and this requirement forces hash tables to be implemented using [chaining][33]. I hope +we'll find a solution for this in the future and bring faster hash tables in the C++ +standard library, but we are not here yet. + +In any case, libstdc++ implementation of `std::unordered_map` is really +awesome. I really enjoyed reading the code and learnt a lot, I hope you are +too. + +[1]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L177-L1153 +[2]: https://stackoverflow.com/a/228797/1313516 +[3]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L110-L168 +[4]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L301-L316 +[5]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L318-L345 +[6]: https://stackoverflow.com/a/50271887/1313516 +[7]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L347-L359 +[8]: https://en.cppreference.com/w/cpp/language/ebo +[9]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L361-L365 +[10]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L386-L399 +[11]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L123-L126 +[12]: https://en.wikipedia.org/wiki/Matryoshka_doll +[13]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L2231-L2266 +[14]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/functional_hash.h#L283-L300 +[15]: https://github.com/gcc-mirror/gcc/commit/4df047dd3494ad17122ea46134a951a319a81b27 +[16]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/functional_hash.h#L114-L199 +[17]: https://en.wikipedia.org/wiki/Identity_function +[18]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L293-L299 +[19]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L2146-L2174 +[20]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/src/c%2B%2B11/hashtable_c%2B%2B0x.cc#L45C1-L88 +[21]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L1677-L1683 +[22]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L1685-L1687 +[23]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L811-L819 +[24]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L1939-L1941 +[25]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L1943-L1952 +[26]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/functional_hash.h#L294-L300 +[27]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L1740-L1743 +[28]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L1700-L1702 +[29]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L1691-L1693 +[30]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L2344-L2383 +[31]: https://github.com/gcc-mirror/gcc/blob/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc%2B%2B-v3/include/bits/hashtable.h#L2316-L2342 +[32]: https://en.wikichip.org/wiki/pointer_chasing +[33]: https://en.wikipedia.org/wiki/Hash_table#Separate_chaining +[34]: https://en.wikipedia.org/wiki/Multiset +[35]: https://en.wikipedia.org/wiki/Modern_C%2B%2B_Design#Policy-based_design +[36]: https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds +[37]: https://github.com/gcc-mirror/gcc/tree/b9b7981f3d6919518372daf4c7e8c40dfc58f49d/libstdc++-v3 diff --git a/posts/libstdc++-std-unordered-map/metadata.txt b/posts/libstdc++-std-unordered-map/metadata.txt new file mode 100644 index 0000000..1f08fa9 --- /dev/null +++ b/posts/libstdc++-std-unordered-map/metadata.txt @@ -0,0 +1,3 @@ +Title: How libstdc++ `std::unordered_map` implemented? +Date: 2023-07-02 +Status: published |
