summaryrefslogtreecommitdiff
path: root/posts
diff options
context:
space:
mode:
authorDmitry Ilvokhin <d@ilvokhin.com>2023-07-02 13:08:36 +0100
committerDmitry Ilvokhin <d@ilvokhin.com>2023-07-02 13:08:36 +0100
commit21d68ac5605f12ffea3f05ad677c717577f767ee (patch)
tree1f79b5925f5fa642ea45e6a247afc6aa040b0749 /posts
parent45792695457388109f3341ff5ac483530f531e80 (diff)
downloadblog-21d68ac5605f12ffea3f05ad677c717577f767ee.tar.gz
blog-21d68ac5605f12ffea3f05ad677c717577f767ee.tar.bz2
blog-21d68ac5605f12ffea3f05ad677c717577f767ee.zip
Add a post about libstdc++ `std::unordered_map`
Detailed description of libstdc++ `std::unordered_map` implementation with URLs to source code and some explanations.
Diffstat (limited to 'posts')
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.excalidraw738
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.pngbin0 -> 275574 bytes
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.excalidraw2253
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.pngbin0 -> 637322 bytes
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.excalidraw854
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.pngbin0 -> 274163 bytes
-rw-r--r--posts/libstdc++-std-unordered-map/libstdc++-unordered-map.md615
-rw-r--r--posts/libstdc++-std-unordered-map/metadata.txt3
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
new file mode 100644
index 0000000..ec45011
--- /dev/null
+++ b/posts/libstdc++-std-unordered-map/libstdc++-hash-node-layout.png
Binary files differ
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
new file mode 100644
index 0000000..2856dbc
--- /dev/null
+++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-layout.png
Binary files differ
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
new file mode 100644
index 0000000..34d8154
--- /dev/null
+++ b/posts/libstdc++-std-unordered-map/libstdc++-hashtable-linked-list.png
Binary files differ
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.
+
+![](libstdc++-hash-node-layout.png "libstdc++ _Hash_node data layout")
+
+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.
+
+![](libstdc++-hashtable-linked-list.png "_Hashtable internal linked list")
+
+
+Let's make a real hash table from the linked list by adding
+buckets ([original](libstdc++-hashtable-layout.png)).
+
+![](libstdc++-hashtable-layout.png "libstdc++ _Hashtable data layout")
+
+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
generated by cgit v1.2.3-70-g09d2 (git 2.49.0) at 2025-04-28 14:11:03 +0000