{"id":381175,"date":"2024-06-29T03:31:15","date_gmt":"2024-06-29T03:31:15","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=381175"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=381175","title":{"rendered":"\u0414\u0435\u0440\u0435\u0432\u043e \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u043f\u043e\u043a\u0430\u0436\u0443 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u042f \u0434\u0443\u043c\u0430\u044e \u0447\u0442\u043e \u043e\u043d\u043e \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u0443\u0434\u043e\u0431\u043d\u043e, \u043d\u0435\u0436\u0435\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0435\u0439.<\/p>\n

\u0418\u0442\u0430\u043a, \u043d\u0430\u0447\u043d\u0435\u043c. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0435\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u043a\u0430, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f. \u042f \u043d\u0430\u0448\u0435\u043b \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0435\u0439 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0435 \u0438 \u043f\u043e\u043d\u044f\u043b \u043a\u0430\u043a \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e. \u041c\u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u043e\u0441\u044c \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0447\u0442\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0441\u0442\u0435\u043a \u0438 \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u044c, \u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u0432\u044b\u0445\u043e\u0434\u043e\u0432 \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u042f \u0437\u0430\u0445\u043e\u0442\u0435\u043b \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043d\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u042f \u0431\u0443\u0434\u0443 \u043f\u0438\u0441\u0430\u0442\u044c \u043d\u0430 C, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u044d\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u044f\u0437\u044b\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u043d\u044f\u0442\u044c \u0432\u0441\u0435.<\/p>\n

\u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443.<\/p>\n

struct node {         unsigned long number;         unsigned long count;         unsigned long step;         struct node *parent;         struct node *left;         struct node *right; };<\/code><\/pre>\n
\u0417\u0434\u0435\u0441\u044c number \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u0443\u0434\u0435\u0442 \u0438\u0434\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 node. Count \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439. Step \u043d\u0443\u0436\u0435\u043d \u0431\u0443\u0434\u0435\u0442 \u0434\u043b\u044f \u0432\u044b\u0432\u043e\u0434\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u044c, \u043e\u043d \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0431\u044b\u043b\u043e \u043b\u0438 \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0432 \u044d\u0442\u043e\u0442 node \u0438\u043b\u0438 \u043d\u0435\u0442.<\/p>\n
\u0414\u0435\u043b\u0430\u0435\u043c \u0433\u043b\u043e\u0431\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n
struct node *root;<\/code><\/pre>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043d\u0430\u0448\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0447\u0438\u0441\u0435\u043b, \u043e\u043d\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u043e \u0434\u0440\u0443\u0433\u043e\u043c\u0443 — \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0442\u0435\u043f\u0435\u0440\u044c \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u043e\u043d\u0430 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0430\u0434\u0440\u0435\u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b.<\/p>\n
static void add_node (const int number) { register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root;  while (1) { if (p == NULL) { p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) { if (left) prev->left = p; else prev->right = p; p->parent = prev; } if (root == NULL)  { root = p; p->parent = NULL; } return; } prev = p; if (p->number > number) { left = 1; if (p->left && p->number < p->left->number) { register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; } p = p->left; } else if (p->number < number) { left = 0; if (p->right && p->number > p->right->number) { register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; } p = p->right; } else if (p->number == number) { p->count++; return; } } } <\/code><\/pre>\n
\u042f \u0443\u043a\u0430\u0437\u0430\u043b \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043a\u0430\u043a \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u044b, \u0447\u0442\u043e\u0431\u044b \u0445\u043e\u0442\u044c \u0447\u0443\u0442\u043e\u0447\u043a\u0443 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u043e. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u0434\u0438\u0437\u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0443 64 \u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0430 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u043e\u0432.<\/p>\n
[0x00401080]> s sym.add_node [0x00401166]> pd 30             ;-- add_node:             0x00401166      55             push rbp             0x00401167      4889e5         mov rbp, rsp             0x0040116a      4155           push r13             0x0040116c      4154           push r12             0x0040116e      53             push rbx             0x0040116f      4883ec18       sub rsp, 0x18             0x00401173      897ddc         mov dword [rbp - 0x24], edi             0x00401176      41bc00000000   mov r12d, 0             0x0040117c      41bd00000000   mov r13d, 0             0x00401182      488b1dcf2e00.  mov rbx, qword [obj.root]   ; [0x404058:8]=0             0x00401189      4885db         test rbx, rbx         \u250c\u2500< 0x0040118c      7559           jne 0x4011e7 <\/code><\/pre>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u0414\u0430\u043b\u0435\u0435 \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0439\u0442\u0438\u0441\u044c \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0435\u0441\u0442\u044c \u043b\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f. \u0422\u0430\u043a\u043e\u0435 \u0442\u043e\u0436\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044e. \u0412\u043e\u0442 \u043a\u043e\u0434.<\/p>\n
static void find_matches ( ) { register struct node *n = root; register nm = 0; register n->step = 0; while (n) { if (n->step == 0 && n->count > 1)  {  printf (\"%ld: %ld\\n\", n->number, n->count);  nm++;  } n->step = 1; if (n->left && n->left->step == 0) { n = n->left; continue; } else if (n->right && n->right->step == 0) { n = n->right; continue; } else if (n->step == 1)  { if (n->left) n->left->step = 0; if (n->right) n->right->step = 0; n = n->parent; if (n && n->step == 1 && n->parent == NULL)  { n->step == 2; continue; } else if (!n) break; } if (n->step == 1 && n->parent == NULL) break; } }<\/code><\/pre>\n
\u0414\u0430, \u043e\u043d\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u043e \u043c\u043d\u043e\u0433\u043e \u0447\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043d\u043e \u044d\u0442\u043e \u0446\u0435\u043d\u0430 \u0437\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u043e\u0434\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435. \u042f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b step \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0433\u0434\u0435 \u0443\u0436\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u044b\u043b, \u0430 \u0433\u0434\u0435 \u043d\u0435 \u0431\u044b\u043b.<\/p>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u043f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434.<\/p>\n
static void add_node (const int number) {     register struct node *prev = NULL;     register unsigned long left = 0;     register struct node *p = root;      while (1)     {         if (p == NULL)         {             p = calloc (1, sizeof (struct node));             p->number = number;             p->count = 1;             if (prev)             {                 if (left) prev->left = p;                 else prev->right = p;                 p->parent = prev;             }             if (root == NULL)              {                 root = p;                 p->parent = NULL;             }             return;         }         prev = p;         if (p->number > number)         {             left = 1;             if (p->left && p->number < p->left->number)             {                 register struct node *up = p;                 register struct node *down = p->left;                 p = calloc (1, sizeof (struct node));                 p->number = number;                 p->count = 1;                 p->parent = up;                 p->left = down;                 return;             }             p = p->left;         } else if (p->number < number)         {             left = 0;             if (p->right && p->number > p->right->number)             {                 register struct node *up = p;                 register struct node *down = p->right;                 p = calloc (1, sizeof (struct node));                 p->number = number;                 p->count = 1;                 p->parent = up;                 p->right = down;                 return;             }             p = p->right;         } else if (p->number == number)         {             p->count++;             return;         }     } } <\/code><\/pre>\n
\u0412 \u0446\u0435\u043b\u043e\u043c \u044f \u043d\u0435 \u0432\u0438\u0434\u0435\u043b \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043d\u0430 \u043c\u0438\u043b\u043b\u0438\u043e\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u043b\u0438 10 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432, \u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f \u0431\u0443\u0434\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u043f\u0440\u0438\u0432\u0435\u043b \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0434\u0430\u0436\u0435 \u043b\u0443\u0447\u0448\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u041d\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0440\u0430\u0441\u0447\u0451\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u0447\u0443\u0441\u044c \u0434\u0435\u043b\u0430\u0442\u044c.<\/p>\n
\u042f \u043f\u043e\u043c\u0435\u043d\u044f\u043b \u0441\u0442\u0430\u0442\u044c\u044e, \u0434\u0435\u0440\u0435\u0432\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435.<\/p>\n
\u0412\u0441\u0435\u043c \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435.<\/p>\n<\/div>\n<\/div>\n<\/div>\n
<\/div>\n

 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/articles\/590485\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
<\/div>\n
\n
\n
\n
\n
\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u043f\u043e\u043a\u0430\u0436\u0443 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u042f \u0434\u0443\u043c\u0430\u044e \u0447\u0442\u043e \u043e\u043d\u043e \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u0443\u0434\u043e\u0431\u043d\u043e, \u043d\u0435\u0436\u0435\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0435\u0439.<\/p>\n
\u0418\u0442\u0430\u043a, \u043d\u0430\u0447\u043d\u0435\u043c. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0435\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u043a\u0430, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f. \u042f \u043d\u0430\u0448\u0435\u043b \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0435\u0439 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0435 \u0438 \u043f\u043e\u043d\u044f\u043b \u043a\u0430\u043a \u044d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e. \u041c\u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u043e\u0441\u044c \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u043c\u044b \u0437\u043d\u0430\u0435\u043c \u0447\u0442\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0441\u0442\u0435\u043a \u0438 \u0435\u0441\u043b\u0438 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u044c, \u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043c\u043d\u043e\u0433\u043e \u0432\u044b\u0445\u043e\u0434\u043e\u0432 \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0439. \u042f \u0437\u0430\u0445\u043e\u0442\u0435\u043b \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043d\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u042f \u0431\u0443\u0434\u0443 \u043f\u0438\u0441\u0430\u0442\u044c \u043d\u0430 C, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u044d\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u044f\u0437\u044b\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u043d\u044f\u0442\u044c \u0432\u0441\u0435.<\/p>\n
\u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443.<\/p>\n
struct node {         unsigned long number;         unsigned long count;         unsigned long step;         struct node *parent;         struct node *left;         struct node *right; };<\/code><\/pre>\n
\u0417\u0434\u0435\u0441\u044c number \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0431\u0443\u0434\u0435\u0442 \u0438\u0434\u0442\u0438 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 node. Count \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439. Step \u043d\u0443\u0436\u0435\u043d \u0431\u0443\u0434\u0435\u0442 \u0434\u043b\u044f \u0432\u044b\u0432\u043e\u0434\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u043e\u043d\u0441\u043e\u043b\u044c, \u043e\u043d \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0431\u044b\u043b\u043e \u043b\u0438 \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0432 \u044d\u0442\u043e\u0442 node \u0438\u043b\u0438 \u043d\u0435\u0442.<\/p>\n
\u0414\u0435\u043b\u0430\u0435\u043c \u0433\u043b\u043e\u0431\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n
struct node *root;<\/code><\/pre>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043d\u0430\u0448\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043f\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0435 \u0447\u0438\u0441\u0435\u043b, \u043e\u043d\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u043e \u0434\u0440\u0443\u0433\u043e\u043c\u0443 — \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0442\u0435\u043f\u0435\u0440\u044c \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u043e\u043d\u0430 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0430\u0434\u0440\u0435\u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b.<\/p>\n
static void add_node (const int number) { register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root;  while (1) { if (p == NULL) { p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) { if (left) prev->left = p; else prev->right = p; p->parent = prev; } if (root == NULL)  { root = p; p->parent = NULL; } return; } prev = p; if (p->number > number) { left = 1; if (p->left && p->number < p->left->number) { register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; } p = p->left; } else if (p->number < number) { left = 0; if (p->right && p->number > p->right->number) { register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; } p = p->right; } else if (p->number == number) { p->count++; return; } } } <\/code><\/pre>\n
\u042f \u0443\u043a\u0430\u0437\u0430\u043b \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043a\u0430\u043a \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u044b, \u0447\u0442\u043e\u0431\u044b \u0445\u043e\u0442\u044c \u0447\u0443\u0442\u043e\u0447\u043a\u0443 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u043e. \u0415\u0441\u043b\u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u0434\u0438\u0437\u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0443 64 \u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0430 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u043e\u0432.<\/p>\n
[0x00401080]> s sym.add_node [0x00401166]> pd 30             ;-- add_node:             0x00401166      55             push rbp             0x00401167      4889e5         mov rbp, rsp             0x0040116a      4155           push r13             0x0040116c      4154           push r12             0x0040116e      53             push rbx             0x0040116f      4883ec18       sub rsp, 0x18             0x00401173      897ddc         mov dword [rbp - 0x24], edi             0x00401176      41bc00000000   mov r12d, 0             0x0040117c      41bd00000000   mov r13d, 0             0x00401182      488b1dcf2e00.  mov rbx, qword [obj.root]   ; [0x404058:8]=0             0x00401189      4885db         test rbx, rbx         \u250c\u2500< 0x0040118c      7559           jne 0x4011e7 <\/code><\/pre>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438. \u0414\u0430\u043b\u0435\u0435 \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0439\u0442\u0438\u0441\u044c \u043f\u043e \u0434\u0435\u0440\u0435\u0432\u0443 \u0438 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0435\u0441\u0442\u044c \u043b\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f. \u0422\u0430\u043a\u043e\u0435 \u0442\u043e\u0436\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043d\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044e. \u0412\u043e\u0442 \u043a\u043e\u0434.<\/p>\n
static void find_matches ( ) { register struct node *n = root; register nm = 0; register n->step = 0; while (n) { if (n->step == 0 && n->count > 1)  {  printf (\"%ld: %ld\\n\", n->number, n->count);  nm++;  } n->step = 1; if (n->left && n->left->step == 0) { n = n->left; continue; } else if (n->right && n->right->step == 0) { n = n->right; continue; } else if (n->step == 1)  { if (n->left) n->left->step = 0; if (n->right) n->right->step = 0; n = n->parent; if (n && n->step == 1 && n->parent == NULL)  { n->step == 2; continue; } else if (!n) break; } if (n->step == 1 && n->parent == NULL) break; } }<\/code><\/pre>\n
\u0414\u0430, \u043e\u043d\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u043e \u043c\u043d\u043e\u0433\u043e \u0447\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043d\u043e \u044d\u0442\u043e \u0446\u0435\u043d\u0430 \u0437\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u043e\u0434\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435. \u042f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b step \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0433\u0434\u0435 \u0443\u0436\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0431\u044b\u043b, \u0430 \u0433\u0434\u0435 \u043d\u0435 \u0431\u044b\u043b.<\/p>\n
\u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u043f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434.<\/p>\n
static void add_node (const int number) {     register struct node *prev = NULL;     register unsigned long left = 0;     register struct node *p = root;      while (1)     {         if (p == NULL)         {             p = calloc (1, sizeof (struct node));             p->number = number;             p->count = 1;             if (prev)             {                 if (left) prev->left = p;                 else prev->right = p;                 p->parent = prev;             }             if (root == NULL)              {                 root = p;                 p->parent = NULL;             }             return;         }         prev = p;         if (p->number > number)         {             left = 1;             if (p->left && p->number < p->left->number)             {                 register struct node *up = p;                 register struct node *down = p->left;                 p = calloc (1, sizeof (struct node));                 p->number = number;                 p->count = 1;                 p->parent = up;                 p->left = down;                 return;             }             p = p->left;         } else if (p->number < number)         {             left = 0;             if (p->right && p->number > p->right->number)             {                 register struct node *up = p;                 register struct node *down = p->right;                 p = calloc (1, sizeof (struct node));                 p->number = number;                 p->count = 1;                 p->parent = up;                 p->right = down;                 return;             }             p = p->right;         } else if (p->number == number)         {             p->count++;             return;         }     } } <\/code><\/pre>\n
\u0412 \u0446\u0435\u043b\u043e\u043c \u044f \u043d\u0435 \u0432\u0438\u0434\u0435\u043b \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043d\u0430 \u043c\u0438\u043b\u043b\u0438\u043e\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u043b\u0438 10 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432, \u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f \u0431\u0443\u0434\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u043f\u0440\u0438\u0432\u0435\u043b \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0434\u0430\u0436\u0435 \u043b\u0443\u0447\u0448\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u041d\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0440\u0430\u0441\u0447\u0451\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u0447\u0443\u0441\u044c \u0434\u0435\u043b\u0430\u0442\u044c.<\/p>\n
\u042f \u043f\u043e\u043c\u0435\u043d\u044f\u043b \u0441\u0442\u0430\u0442\u044c\u044e, \u0434\u0435\u0440\u0435\u0432\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u0441\u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435.<\/p>\n
\u0412\u0441\u0435\u043c \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435.<\/p>\n<\/div>\n<\/div>\n<\/div>\n
<\/div>\n

 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/articles\/590485\/<\/a>
<\/br><\/br><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-381175","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/381175","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=381175"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/381175\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=381175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=381175"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=381175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}