fork download
copy 
  1. #include <iostream>
  2. #include <new>
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. struct supernode {
  8.   int id;
  9.   unsigned int size;
  10.   void *data;
  11.   struct supernode *next;
  12.   struct supernode *before;
  13. };
  14.  
  15. void xmallocdump(void);
  16. void *xmalloc(unsigned int, int);
  17. void xfree(void *, int);
  18. void *xrealloc(void *, unsigned int, int);
  19.  
  20. static struct supernode *superrootS = NULL;
  21.  
  22. #define N 16
  23. void xmallocdump(void)
  24. {
  25.   int i;
  26.   unsigned char c;
  27.   struct supernode *p;
  28.   if (superrootS == NULL) {
  29.     fprintf(stderr, "xmallocdump(): root is NULL.\n"); fflush(stderr);
  30.   } else {
  31.     p = superrootS;
  32.     fprintf(stderr, "ERROR: Memory leak occured!\n");
  33.     do {
  34.       fprintf(stderr, "Memory Leak >%p %p %p(%d):%d: ", (void *)p, (void *)p->next, (void *)p->data, p->size, p->id);
  35.       for (i = 0; i < N; i++) {
  36.         c = *(unsigned char *)((char *)(p->data) + i);
  37.         printf("%02x(%c) ", c , (isprint(c)) ? c : '.');
  38.       }
  39.       putchar('\n');
  40.       p = p->next;
  41.     } while (p != superrootS);
  42.   }
  43. }
  44.  
  45. void *xmalloc(unsigned int n, int id)
  46. {
  47.   unsigned int i;
  48.   struct supernode *p;
  49.   rand();
  50.   if (!(p = (struct supernode *)malloc(sizeof(struct supernode)))) {
  51.     fprintf(stderr, "xmalloc(): cannot malloc() in xmalloc()\n");
  52.     abort();
  53.   }
  54.   if (superrootS == NULL) {
  55.     superrootS = p;
  56.     p->size = n;
  57.     p->next = p;
  58.     p->before = p;
  59.   } else {
  60.     p->size = n;
  61.     p->next = superrootS->next;
  62.     p->before = superrootS;
  63.     superrootS->next = p;
  64.     p->next->before = p;
  65.   }
  66.   if (!(p->data = malloc(n))) {
  67.     fprintf(stderr, "xmalloc(): cannot malloc() in malloc()\n");
  68.     abort();
  69.   } else {
  70.     /* nothing */
  71.   }
  72.   for (i = 0; i < n; i++)
  73.     *(char *)((char *)(p->data) + i) = rand() & 0xff;
  74.   p->id = id;
  75. /*printf("xmalloc():malloc id = %d(%p)\n", p->id, p->data); */
  76.   return p->data;
  77. }
  78.  
  79. void xfree(void *p, int id)
  80. {
  81.   unsigned int flag, i;
  82.   struct supernode *q;
  83.   /*printf("xfree():free id = %d(%p)\n", id, p); */
  84.   if (p == NULL)
  85.     return;
  86.   if (superrootS == NULL) {
  87.     fprintf(stderr, "xfree(): root is null.\n");
  88.     abort();
  89.   }
  90.   rand();
  91.   flag = 0;
  92.   q = superrootS;
  93.   for (;;) {
  94.     if (q->data == p) {
  95.       if (q->id != id) {
  96.         fprintf(stderr, "xfree(): bad ID. %d <- %d\n", q->id, id);
  97.         abort();
  98.       }
  99.       if (q->next == q) {
  100.         for (i = 0; i < q->size; i++)
  101.           *(char *)((char *)(q->data) + i) = rand() & 0xff;
  102.         free(q->data);
  103.         free(q);
  104.         flag = 1;
  105.         superrootS = NULL;
  106.         break;
  107.       } else {
  108.         q->before->next = q->next;
  109.         q->next->before = q->before;
  110.         if (q == superrootS)
  111.           superrootS = q->next;
  112.         for (i = 0; i < q->size; i++)
  113.           *(char *)((char *)(q->data) + i) = rand() & 0xff;
  114.         free(q->data);
  115.         free(q);
  116.         flag = 1;
  117.         break;
  118.       }
  119.     }
  120.     if (q->next == superrootS)
  121.       break;
  122.     q = q->next;
  123.   }
  124.   if (flag != 1) {
  125.     fprintf(stderr, "xfree(): cannot xfree(), no data.(id = %d, %p)\n", id, p);
  126.     abort();
  127.   }
  128. }
  129.  
  130. /*------------------*/
  131. #define ID_NODE  1001
  132. /*------------------*/
  133.  
  134.  
  135. template <class T>
  136. class Node {
  137. private:
  138.   T key;
  139.   Node *left, *right;
  140. public:
  141.   Node(T key) {
  142.     this->left = this->right = nullptr;
  143.     this->key = key;
  144.   }    
  145.  
  146.   void *operator new(size_t size) { return xmalloc(size, ID_NODE); }
  147.   void operator delete(void *p) { xfree(p, ID_NODE); }
  148.  
  149.   static void insertNode(Node<T> *&root, T key) {
  150.     if (root == nullptr) {
  151.       root = new Node<T>(key);
  152.       return;
  153.     }
  154.     if (key < root->key)
  155.       insertNode(/*ref*/root->left, key);
  156.     else
  157.       insertNode(/*ref*/root->right, key);
  158.   }
  159.  
  160.  
  161.   static bool deleteNode(Node<T> *&root, T key) {
  162.     if (root == nullptr) return false;
  163.     if (key < root->key)
  164.       return deleteNode(/*ref*/root->left, key);
  165.     else if (key > root->key)
  166.       return deleteNode(/*ref*/root->right, key);
  167.     else {
  168.       if (root->left == nullptr) {
  169.         Node<T> *p;
  170.         p = root;
  171.         root = root->right;
  172.         delete p;
  173.       } else if (root->right == nullptr) {
  174.         Node *p;
  175.         p = root;
  176.         root = root->left;
  177.         delete p;
  178.       } else { // root->left != 0 && root->right != 0
  179.         Node *p, *q;
  180.         for (p = root->left; p->right != nullptr; p = p->right)
  181.           ;
  182.         p->right = root->right;
  183.         q = root;
  184.         root = root->left;
  185.         delete q;
  186.       }
  187.     }
  188.     return true;
  189.   }
  190.  
  191. #if defined(N)
  192. #undef N
  193. #endif
  194. #define N 3
  195.  
  196.   void vomitTree(int c) {
  197.     if (this == nullptr)
  198.       return;
  199.     this->left->vomitTree(c + N);
  200.     for (int i = 0; i < c; i++) std::cout << ' ';
  201.     std::cout << this->key << std::endl;
  202.     this->right->vomitTree(c + N);
  203.   }
  204.  
  205.   static void release(Node<T> *&root) {
  206.     if (root != nullptr) {
  207.       release(/*ref*/root->left);
  208.       release(/*ref*/root->right);
  209.       delete root;
  210.       root = nullptr;
  211.     }
  212.   }
  213.  
  214. };
  215.  
  216. template <class T>
  217. class BinaryTree {
  218. private:
  219.   Node<T> *root;
  220. public:
  221.   BinaryTree<T>() { this->root = nullptr; }
  222.   ~BinaryTree<T>() { Node<T>::release(/*ref*/this->root); }
  223.   void insertNode(T key) { try { Node<T>::insertNode(/*ref*/this->root, key);
  224.                          } catch (std::bad_alloc) { std::cerr << "memory full." << std::cerr; }
  225.   }
  226.   bool deleteNode(T key) { return Node<T>::deleteNode(/*ref*/this->root, key); }
  227.   void vomitTree() { this->root->vomitTree(0); }
  228. };
  229.  
  230. int main() {
  231.   auto tree = new BinaryTree<int>();
  232.   for (;;) {
  233.     auto input = 0;
  234.     //std::cout << "> ";
  235.     std::cin >> input;
  236.     if (input < 0)
  237.       break;
  238.     tree->insertNode(input);
  239.     tree->vomitTree();
  240.   }
  241.   std::cout << "deleting" << std::endl;
  242.   for (;;) {
  243.     auto input = 0;
  244.     //std::cout << "> ";
  245.     std::cin >> input;
  246.     if (input < 0)
  247.       break;
  248.     if (tree->deleteNode(input))
  249.       std::cout << "deleted." << std::endl;
  250.     else
  251.       std::cout << "not found." << std::endl;
  252.     tree->vomitTree();
  253.   }
  254.   delete tree;
  255.   xmallocdump();
  256. }
  257. /* end */
  258.  
Success #stdin #stdout #stderr 0s 3448KB
comments (?)
stdin
copy 
10
5
15
1
8
12
20
-1
5
10
15
100
8
12
20
100
1
1
-1
stdout
copy 
10
   5
10
   5
10
   15
      1
   5
10
   15
      1
   5
      8
10
   15
      1
   5
      8
10
      12
   15
      1
   5
      8
10
      12
   15
      20
deleting
deleted.
   1
      8
10
      12
   15
      20
deleted.
1
   8
         12
      15
         20
deleted.
1
   8
      12
         20
not found.
1
   8
      12
         20
deleted.
1
   12
      20
deleted.
1
   20
deleted.
1
not found.
1
deleted.
not found.
stderr
copy 
xmallocdump(): root is NULL.
https://ideone.com/kuwHRh
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!