MQTTSNGWProcess.h

00001 /**************************************************************************************
00002  * Copyright (c) 2016, Tomoaki Yamaguchi
00003  *
00004  * All rights reserved. This program and the accompanying materials
00005  * are made available under the terms of the Eclipse Public License v1.0
00006  * and Eclipse Distribution License v1.0 which accompany this distribution.
00007  *
00008  * The Eclipse Public License is available at
00009  *    http://www.eclipse.org/legal/epl-v10.html
00010  * and the Eclipse Distribution License is available at
00011  *   http://www.eclipse.org/org/documents/edl-v10.php.
00012  *
00013  * Contributors:
00014  *    Tomoaki Yamaguchi - initial API and implementation and/or initial documentation
00015  **************************************************************************************/
00016 
00017 #ifndef MQTTSNGWPROCESS_H_
00018 #define MQTTSNGWPROCESS_H_
00019 
00020 #include <exception>
00021 #include <string>
00022 #include <signal.h>
00023 #include "MQTTSNGWDefines.h"
00024 #include "Threading.h"
00025 
00026 using namespace std;
00027 
00028 namespace MQTTSNGW
00029 {
00030 
00031 /*=================================
00032  *    Parameters
00033  ==================================*/
00034 #define MQTTSNGW_MAX_TASK           10  // number of Tasks
00035 #define PROCESS_LOG_BUFFER_SIZE  16384  // Ring buffer size for Logs
00036 #define MQTTSNGW_PARAM_MAX         128  // Max length of config records.
00037 
00038 /*=================================
00039  *    Macros
00040  ==================================*/
00041 #define WRITELOG theProcess->putLog
00042 #define CHK_SIGINT (theProcess->checkSignal() == SIGINT)
00043 #define UNUSED(x) ((void)(x))
00044 /*=================================
00045  Class Process
00046  ==================================*/
00047 class Process
00048 {
00049 public:
00050     Process();
00051     virtual ~Process();
00052     virtual void initialize(int argc, char** argv);
00053     virtual void run(void);
00054     void putLog(const char* format, ...);
00055     void resetRingBuffer(void);
00056     int  getArgc(void);
00057     char** getArgv(void);
00058     int getParam(const char* parameter, char* value);
00059     const char* getLog(void);
00060     int checkSignal(void);
00061     const string* getConfigDirName(void);
00062     const string* getConfigFileName(void);
00063 private:
00064     int _argc;
00065     char** _argv;
00066     string  _configDir;
00067     string  _configFile;
00068     RingBuffer* _rb;
00069     Semaphore*  _rbsem;
00070     Mutex _mt;
00071     int  _log;
00072     char _rbdata[PROCESS_LOG_BUFFER_SIZE + 1];
00073 };
00074 
00075 /*=====================================
00076  Class MultiTaskProcess
00077  ====================================*/
00078 class MultiTaskProcess: public Process
00079 {
00080 public:
00081     MultiTaskProcess(void);
00082     ~MultiTaskProcess();
00083     void initialize(int argc, char** argv);
00084     int getParam(const char* parameter, char* value);
00085     void run(void);
00086     void waitStop(void);
00087     void threadStoped(void);
00088     void attach(Thread* thread);
00089 
00090 private:
00091     Thread* _threadList[MQTTSNGW_MAX_TASK];
00092     Mutex _mutex;
00093     int _threadCount;
00094     int _stopCount;
00095 };
00096 
00097 /*=====================================
00098  Class Exception
00099  =====================================*/
00100 class Exception: public exception
00101 {
00102 public:
00103     Exception(const string& message);
00104     Exception(const int exNo, const string& message);
00105     Exception(const int exNo, const string& message,
00106             const char* file, const char* func, const int line);
00107     virtual ~Exception() throw ();
00108     const char* getFileName();
00109     const char* getFunctionName();
00110     const int getLineNo();
00111     const int getExceptionNo();
00112     virtual const char* what() const throw ();
00113     void writeMessage();
00114 
00115 private:
00116     int _exNo;
00117     string _message;
00118     const char* _fileName;
00119     const char* _functionName;
00120     int _line;
00121 };
00122 
00123 
00124 /*=====================================
00125  Class QueElement
00126  ====================================*/
00127 template<class T>
00128 class QueElement
00129 {
00130     template<class U> friend class Que;
00131 public:
00132     QueElement(T* t)
00133     {
00134         _element = t;
00135         _next = nullptr;
00136         _prev = nullptr;
00137     }
00138 
00139     ~QueElement()
00140     {
00141     }
00142 
00143 private:
00144     T* _element;
00145     QueElement<T>* _next;
00146     QueElement<T>* _prev;
00147 };
00148 
00149 /*=====================================
00150  Class Que
00151  ====================================*/
00152 template<class T>
00153 class Que
00154 {
00155 public:
00156     Que()
00157     {
00158         _head = nullptr;
00159         _tail = nullptr;
00160         _cnt = 0;
00161         _maxSize = 0;
00162     }
00163 
00164     ~Que()
00165     {
00166         QueElement<T>* elm = _head;
00167         while (elm)
00168         {
00169             QueElement<T>* next = elm->_next;
00170             delete elm->_element;
00171             delete elm;
00172             elm = next;
00173         }
00174     }
00175 
00176     void pop(void)
00177     {
00178         if ( _head )
00179         {
00180             QueElement<T>* head = _head;
00181             if ( _head == _tail )
00182             {
00183                 _head = _tail = nullptr;
00184             }
00185             else
00186             {
00187                 _head = head->_next;
00188                 head->_prev = nullptr;
00189             }
00190             delete head;
00191             _cnt--;
00192         }
00193     }
00194 
00195     T* front(void)
00196     {
00197         {
00198             if ( _head )
00199             {
00200                 return _head->_element;
00201             }
00202             else
00203             {
00204                 return 0;
00205             }
00206         }
00207     }
00208 
00209     int post(T* t)
00210     {
00211         if ( t && ( _maxSize == 0 || _cnt < _maxSize ))
00212         {
00213             QueElement<T>* elm = new QueElement<T>(t);
00214             if ( _head )
00215             {
00216                 if ( _tail == _head )
00217                 {
00218                     elm->_prev = _tail;
00219                     _tail = elm;
00220                     _head->_next = elm;
00221                 }
00222                 else
00223                 {
00224                 _tail->_next = elm;
00225                 elm->_prev = _tail;
00226                 _tail = elm;
00227                 }
00228             }
00229             else
00230             {
00231                 _head = elm;
00232                 _tail = elm;
00233             }
00234             _cnt++;
00235             return _cnt;
00236         }
00237         return 0;
00238     }
00239 
00240     int size(void)
00241     {
00242         return _cnt;
00243     }
00244 
00245     void setMaxSize(int maxSize)
00246     {
00247         _maxSize = maxSize;
00248     }
00249 
00250 private:
00251     int _cnt;
00252     int _maxSize;
00253     QueElement<T>* _head;
00254     QueElement<T>* _tail;
00255 };
00256 
00257 /*=====================================
00258  Class Tree23
00259  ====================================*/
00260 #define TREE23_INSERT_ACTIVE  (-2)
00261 #define TREE23_DELETE_ACTIVE  (-1)
00262 #define TREE23_BI_NODE        (2)
00263 #define TREE23_TRI_NODE       (3)
00264 
00265 template <typename K, typename V>
00266 class Tree23Elm{
00267     template<typename T, typename U> friend class Tree23;
00268 public:
00269     Tree23Elm()
00270     {
00271         _key = 0;
00272         _val = 0;
00273     }
00274 
00275     Tree23Elm(K* key, V* val)
00276     {
00277         _key = key;
00278         _val = val;
00279     }
00280 
00281     ~Tree23Elm()
00282     {
00283 
00284     }
00285 
00286     int compare(Tree23Elm<K, V>* elm)
00287     {
00288         return _key->compare(elm->_key);
00289     }
00290 private:
00291     K* _key;
00292     V* _val;
00293 };
00294 
00295 
00296 template <typename K, typename V>
00297 class Tree23Node{
00298     template<typename S, typename W> friend class Tree23;
00299 public:
00300     Tree23Node(const int type)
00301     {
00302         _type = type;
00303         _telm0 = _telm1 = NULL;
00304         _left = _midle = _right = NULL;
00305     }
00306 
00307     Tree23Node(const int type, Tree23Node<K, V>* midle)
00308     {
00309         _type = type;
00310         _telm0 = _telm1 = NULL;
00311         _left = _right = NULL;
00312         _midle = midle;
00313     }
00314 
00315     Tree23Node(const int type, Tree23Elm<K, V>* telm)
00316     {
00317         _type = type;
00318         _telm0 = telm;
00319         _telm1 = NULL;
00320         _left = _midle = _right = NULL;
00321     }
00322 
00323     Tree23Node(const int type, Tree23Elm<K, V>* telm, Tree23Node<K, V>* left, Tree23Node<K, V>* right)
00324     {
00325         _type = type;
00326         _telm0 = telm;
00327         _telm1 = NULL;
00328         _left = left;
00329         _midle = NULL;
00330         _right = right;
00331     }
00332 
00333     Tree23Node(const int type, Tree23Elm<K, V>* telm0, Tree23Elm<K, V>* telm1, Tree23Node<K, V>* left, Tree23Node<K, V>* midle, Tree23Node<K, V>* right)
00334     {
00335         _type = type;
00336         _telm0 = telm0;
00337         _telm1 = telm1;
00338         _left = left;
00339         _midle = midle;
00340         _right = right;
00341     }
00342 
00343     ~Tree23Node()
00344     {
00345 
00346     }
00347 
00348 private:
00349     int   _type;
00350     Tree23Elm<K, V>* _telm0;
00351     Tree23Elm<K, V>* _telm1;
00352     Tree23Node<K, V>* _left;
00353     Tree23Node<K, V>* _midle;
00354     Tree23Node<K, V>* _right;
00355 };
00356 
00357 template <typename K, typename V>
00358 class Tree23{
00359 public:
00360     Tree23()
00361     {
00362         _root = NULL;
00363     }
00364 
00365     ~Tree23()
00366     {
00367         if ( _root )
00368         {
00369             delete _root;
00370         }
00371     }
00372 
00373     void add(K* key, V* val)
00374     {
00375         _root = add( _root, new Tree23Elm<K, V>(key, val));
00376         _root->_type = abs(_root->_type);
00377     }
00378 
00379     Tree23Node<K, V>* add(Tree23Node<K, V>* n, Tree23Elm<K, V>* elm)
00380     {
00381         if ( n == 0 )
00382         {
00383             return new Tree23Node<K, V>(TREE23_INSERT_ACTIVE, elm);
00384         }
00385 
00386         int cmp0 = elm->compare(n->_telm0);
00387         int cmp1 = 0;
00388         switch ( n->_type )
00389         {
00390         case 2:
00391             if ( cmp0 < 0 )
00392             {
00393                 n->_left = add(n->_left, elm);
00394                 return addLeft2(n);
00395             }
00396             else if ( cmp0 == 0 )
00397             {
00398                 n->_telm0 = elm;
00399                 return n;
00400             }
00401             else
00402             {
00403                 n->_right = add(n->_right, elm);
00404                 return addRight2(n);
00405             }
00406             break;
00407         case 3:
00408             cmp1 = elm->compare(n->_telm1);
00409             if ( cmp0 < 0 )
00410             {
00411                 n->_left = add(n->_left, elm);
00412                 return addLeft3(n);
00413             }
00414             else if ( cmp0 == 0 )
00415             {
00416                 n->_telm0 = elm;
00417                 return n;
00418             }
00419             else if ( cmp1 < 0 )
00420             {
00421                 n->_midle = add(n->_midle, elm);
00422                 return addMidle3(n);
00423             }
00424             else if ( cmp1 == 0 )
00425             {
00426                 n->_telm1 = elm;
00427                 return n;
00428             }
00429             else
00430             {
00431                 n->_right = add(n->_right, elm);
00432                 return addRight3(n);
00433             }
00434             break;
00435         default:
00436             break;
00437         }
00438         return 0;
00439     }
00440 
00441     void remove(K* k)
00442     {
00443         _root = remove(_root, k);
00444         if ( _root != NULL && _root->_type == TREE23_DELETE_ACTIVE )
00445         {
00446             _root = _root->_midle;
00447         }
00448     }
00449 
00450     Tree23Node<K, V>* remove(Tree23Node<K, V>* node, K* k)
00451     {
00452         if ( node == NULL )
00453         {
00454             return NULL;
00455         }
00456         int cmp0 = k->compare(node->_telm0->_key);
00457         int cmp1 = 0;
00458         switch ( node->_type )
00459         {
00460         case 2:
00461             if ( cmp0 < 0 )
00462             {
00463                 node->_left = remove( node->_left, k);
00464                 return removeLeft2(node);
00465             }
00466             else if ( cmp0 == 0 )
00467             {
00468                 if ( node->_left == NULL)
00469                 {
00470                     return new Tree23Node<K, V>(TREE23_DELETE_ACTIVE);
00471                 }
00472                 Tree23Elm<K, V>* maxLeft = new Tree23Elm<K, V>();
00473                 node->_left = removeMax(node->_left, maxLeft);
00474                 node->_telm0 = maxLeft;
00475                 return removeLeft2(node);
00476             }
00477             else
00478             {
00479                 node->_right = remove(node->_right, k);
00480                 return removeRight2(node);
00481             }
00482         case 3:
00483             cmp1 = k->compare(node->_telm1->_key);
00484             if ( cmp0 < 0 )
00485             {
00486                 node->_left = remove(node->_left, k);
00487                 return removeLeft3(node);
00488             }
00489             else if ( cmp0 == 0 )
00490             {
00491                 if ( node->_left == NULL )
00492                 {
00493                     return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1);
00494                 }
00495                 Tree23Elm<K, V>* maxLeft = new Tree23Elm<K, V>();
00496                 node->_left = removeMax(node->_left, maxLeft);
00497                 node->_telm0 = maxLeft;
00498                 return removeLeft3(node);
00499             }
00500             else if ( cmp1 < 0 )
00501             {
00502                 node->_midle = remove(node->_midle, k);
00503                 return removeMidle3(node);
00504             }
00505             else if ( cmp1 == 0 )
00506             {
00507                 if ( node->_midle == NULL )
00508                 {
00509                     return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0);
00510                 }
00511                 Tree23Elm<K, V>* maxMidle = new Tree23Elm<K, V>();
00512                 node->_midle = removeMax(node->_midle, maxMidle);
00513                 node->_telm1 = maxMidle;
00514                 return removeMidle3(node);
00515             }
00516             else
00517             {
00518                 node->_right = remove(node->_right, k);
00519                 return removeRight3(node);
00520             }
00521         default:
00522             break;
00523         }
00524         return NULL;
00525     }
00526 
00527     bool find(K* key)
00528     {
00529         Tree23Node<K, V>* node = _root;
00530         while (node != NULL)
00531         {
00532             int cmp0 = key->compare(node->_telm0->_key);
00533             int cmp1 = 0;
00534             switch (node->_type)
00535             {
00536             case 2:
00537                 if ( cmp0 <  0 ) node = node->_left;
00538                 else if ( cmp0 == 0 )
00539                 {
00540                 return true;
00541                 }
00542                 else
00543                 {
00544                     node = node->_right;
00545                 }
00546                 break;
00547             case 3:
00548                 cmp1 = key->compare(node->_telm1->_key);
00549                 if ( cmp0 <  0 )
00550                 {
00551                     node = node->_left;
00552                 }
00553                 else if ( cmp0 == 0 )
00554                 {
00555                     return true;
00556                 }
00557                 else if ( cmp1 <  0 )
00558                 {
00559                     node = node->_midle;
00560                 }
00561                 else if ( cmp1 == 0 )
00562                 {
00563                     return true;
00564                 }
00565                 else
00566                 {
00567                     node = node->_right;
00568                 }
00569                 break;
00570             default:
00571                 break;
00572             }
00573         }
00574         return false;
00575     }
00576 
00577 
00578     V* getVal(K* key)
00579     {
00580         Tree23Node<K, V>* node = _root;
00581         while (node != NULL)
00582         {
00583             int cmp0 = key->compare(node->_telm0->_key);
00584             int cmp1 = 0;
00585             switch (node->_type)
00586             {
00587             case 2:
00588                 if ( cmp0 <  0 )
00589                 {
00590                     node = node->_left;
00591                 }
00592                 else if ( cmp0 == 0 )
00593                 {
00594                     return node->_telm0->_val;
00595                 }
00596                 else
00597                 {
00598                     node = node->_right;
00599                 }
00600                 break;
00601             case 3:
00602                 cmp1 = key->compare(node->_telm1->_key);
00603                 if ( cmp0 < 0 )
00604                 {
00605                     node = node->_left;
00606                 }
00607                 else if ( cmp0 == 0 )
00608                 {
00609                     return node->_telm0->_val;
00610                 }
00611                 else if ( cmp1 <  0 )
00612                 {
00613                     node = node->_midle;
00614                 }
00615                 else if ( cmp1 == 0 )
00616                 {
00617                     return node->_telm1->_val;
00618                 }
00619                 else
00620                 {
00621                     node = node->_right;
00622                 }
00623                 break;
00624             default:
00625                 break;
00626             }
00627         }
00628         return NULL;
00629     }
00630 
00631 private:
00632     Tree23Node<K, V>* addLeft2(Tree23Node<K, V>* node)
00633     {
00634         Tree23Node<K, V>* n = node->_left;
00635         if ( n != NULL && n->_type == TREE23_INSERT_ACTIVE )
00636         {
00637             return new Tree23Node<K, V>(TREE23_TRI_NODE, n->_telm0, node->_telm0, n->_left, n->_right, node->_right);
00638         }
00639         return node;
00640     }
00641 
00642     Tree23Node<K, V>* addLeft3(Tree23Node<K, V>* node)
00643     {
00644         Tree23Node<K, V>* n = node->_left;
00645         if ( n != NULL && n->_type == TREE23_INSERT_ACTIVE)
00646         {
00647             n->_type = TREE23_BI_NODE;
00648             Tree23Node<K, V>* nn = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1, node->_midle, node->_right);
00649             return new Tree23Node<K, V>(TREE23_INSERT_ACTIVE, node->_telm0, n, nn);
00650         }
00651         return node;
00652     }
00653 
00654     Tree23Node<K, V>* addRight2(Tree23Node<K, V>* node)
00655     {
00656         Tree23Node<K, V>* n = node->_right;
00657         if (n != NULL &&  n->_type == TREE23_INSERT_ACTIVE)
00658         {
00659             return new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm0, n->_telm0, node->_left, n->_left, n->_right);
00660         }
00661         return node;
00662     }
00663 
00664     Tree23Node<K, V>* addRight3(Tree23Node<K, V>* node)
00665     {
00666         Tree23Node<K, V>* n = node->_right;
00667         if (n != NULL &&  n->_type == TREE23_INSERT_ACTIVE) {
00668             n->_type = TREE23_BI_NODE;
00669             Tree23Node<K, V>* nn = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, node->_left, node->_midle);
00670             return new Tree23Node<K, V>(TREE23_INSERT_ACTIVE, node->_telm1, nn, n);
00671         }
00672         return node;
00673     }
00674 
00675     Tree23Node<K, V>* addMidle3(Tree23Node<K, V>* node)
00676     {
00677         Tree23Node<K, V>* n = node->_midle;
00678         if ( n != NULL && n->_type == TREE23_INSERT_ACTIVE )
00679         {
00680             n->_left = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, node->_left, n->_left);
00681             n->_right = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1, n->_right, node->_right);
00682             return n;
00683         }
00684         return node;
00685     }
00686 
00687 
00688     Tree23Node<K, V>* removeMax(Tree23Node<K, V>* node, Tree23Elm<K, V>* elm)
00689     {
00690         if (node->_right == NULL)
00691         {
00692             switch (node->_type)
00693             {
00694                 case 2:
00695                     elm->_key = node->_telm0->_key;
00696                     elm->_val = node->_telm0->_val;
00697                     return new Tree23Node<K, V>(TREE23_DELETE_ACTIVE);
00698                 case 3:
00699                     elm->_key = node->_telm1->_key;
00700                     elm->_val = node->_telm1->_val;
00701                     return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0);
00702                 default:
00703                     break;
00704             }
00705         }
00706         else
00707         {
00708             node->_right = removeMax(node->_right, elm);
00709             switch (node->_type)
00710             {
00711             case 2:
00712                 return removeRight2(node);
00713             case 3:
00714                 return removeRight3(node);
00715             default:
00716                break;
00717             }
00718         }
00719         return NULL;
00720     }
00721 
00722 
00723     Tree23Node<K, V>* removeLeft2(Tree23Node<K, V>* node)
00724     {
00725         Tree23Node<K, V>* n  = node->_left;
00726         if ( n != NULL && n->_type == TREE23_DELETE_ACTIVE )
00727         {
00728             Tree23Node<K, V>* r = node->_right;
00729             Tree23Node<K, V>* midle;
00730             Tree23Node<K, V>* left;
00731             Tree23Node<K, V>* right;
00732 
00733             switch ( r->_type )
00734             {
00735             case 2:
00736                 midle = new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm0, r->_telm0, n->_midle, r->_left, r->_right);
00737                 return new Tree23Node<K, V>(TREE23_DELETE_ACTIVE, midle);
00738             case 3:
00739                 left = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, n->_midle, r->_left);
00740                 right = new Tree23Node<K, V>(TREE23_BI_NODE, r->_telm1, r->_midle, r->_right);
00741                 return new Tree23Node<K, V>(TREE23_BI_NODE, r->_telm0, left, right);
00742             default:
00743                 break;
00744             }
00745         }
00746         return node;
00747     }
00748 
00749     Tree23Node<K, V>* removeRight2(Tree23Node<K, V>* node)
00750     {
00751         Tree23Node<K, V>* n  = node->_right;
00752         if ( n != NULL && n->_type == TREE23_DELETE_ACTIVE )
00753         {
00754             Tree23Node<K, V>* l = node->_left;
00755             Tree23Node<K, V>* midle;
00756             Tree23Node<K, V>* left;
00757             Tree23Node<K, V>* right;
00758 
00759             switch (l->_type)
00760             {
00761             case 2:
00762                 midle = new Tree23Node<K, V>(TREE23_TRI_NODE, l->_telm0, node->_telm0, l->_left, l->_right, n->_midle);
00763                 return new Tree23Node<K, V>(-1, midle);
00764             case 3:
00765                 right = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, l->_right, n->_midle);
00766                 left = new Tree23Node<K, V>(TREE23_BI_NODE, l->_telm0, l->_left, l->_midle);
00767                 return new Tree23Node<K, V>(TREE23_BI_NODE, l->_telm1, left, right);
00768             default:
00769                 break;
00770             }
00771         }
00772         return node;
00773     }
00774 
00775     Tree23Node<K, V>* removeLeft3(Tree23Node<K, V>* node)
00776     {
00777         Tree23Node<K, V>* n  = node->_left;
00778         if ( n != NULL && n->_type == TREE23_DELETE_ACTIVE )
00779         {
00780             Tree23Node<K, V>* m = node->_midle;
00781             Tree23Node<K, V>* r = node->_right;
00782             Tree23Node<K, V>* left;
00783             Tree23Node<K, V>* midle;
00784 
00785             switch (m->_type) {
00786             case 2:
00787                 left = new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm0, m->_telm0, n->_midle, m->_left, m->_right);
00788                 return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1, left, r);
00789             case 3:
00790                 left = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, n->_midle, m->_left);
00791                 midle = new Tree23Node<K, V>(TREE23_BI_NODE, m->_telm1, m->_midle, m->_right);
00792                 return new Tree23Node<K, V>(TREE23_TRI_NODE, m->_telm0, node->_telm1, left, midle, r);
00793             default:
00794                 break;
00795             }
00796         }
00797         return node;
00798     }
00799 
00800     Tree23Node<K, V>* removeMidle3(Tree23Node<K, V>* node)
00801     {
00802         Tree23Node<K, V>* n  = node->_midle;
00803             if ( n != NULL && n->_type == TREE23_DELETE_ACTIVE )
00804             {
00805                 Tree23Node<K, V>* l = node->_left;
00806                 Tree23Node<K, V>* r = node->_right;
00807                 Tree23Node<K, V>* midle;
00808                 Tree23Node<K, V>* right;
00809                 switch (r->_type)
00810                 {
00811                 case 2:
00812                     right = new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm1, r->_telm0, n->_midle, r->_left, r->_right);
00813                     return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, l, right);
00814                 case 3:
00815                     midle = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1, n->_midle, r->_left);
00816                     right = new Tree23Node<K, V>(TREE23_BI_NODE, r->_telm1, r->_midle, r->_right);
00817                     return new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm0, r->_telm0, l, midle, right);
00818                 default:
00819                     break;
00820                 }
00821             }
00822             return node;
00823     }
00824 
00825     Tree23Node<K, V>* removeRight3(Tree23Node<K, V>* node)
00826     {
00827         Tree23Node<K, V>* n = node->_right;
00828             if ( n != NULL && n->_type == TREE23_DELETE_ACTIVE )
00829             {
00830                 Tree23Node<K, V>* l = node->_left;
00831                 Tree23Node<K, V>* m = node->_midle;
00832                 Tree23Node<K, V>* midle;
00833                 Tree23Node<K, V>* right;
00834                 switch (m->_type)
00835                 {
00836                 case 2:
00837                     right = new Tree23Node<K, V>(TREE23_TRI_NODE, m->_telm0, node->_telm1, m->_left, m->_right, n->_midle);
00838                     return new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm0, l, right);
00839                 case 3:
00840                     right = new Tree23Node<K, V>(TREE23_BI_NODE, node->_telm1, m->_right, n->_midle);
00841                     midle = new Tree23Node<K, V>(TREE23_BI_NODE, m->_telm0, m->_left, m->_midle);
00842                     return new Tree23Node<K, V>(TREE23_TRI_NODE, node->_telm0, m->_telm1, l, midle, right);
00843                 default:
00844                     break;
00845                 }
00846             }
00847             return node;
00848     }
00849 
00850 
00851     Tree23Node<K, V>* _root;
00852 };
00853 
00854 /*=====================================
00855  Class List
00856  =====================================*/
00857 template <typename T>
00858 class ListElm
00859 {
00860     template<typename U> friend class List;
00861 public:
00862     ListElm()
00863     {
00864         _elm = nullptr;
00865         _prev = _next = nullptr;
00866     }
00867     ListElm(T* elm)
00868     {
00869         _elm = elm;
00870         _prev = _next = nullptr;
00871     }
00872     T* getContent(void)
00873     {
00874         return _elm;
00875     }
00876     ~ListElm(){}
00877 
00878 private:
00879     ListElm<T>* getNext(void){return _next;}
00880     T* _elm;
00881     ListElm<T>* _prev;
00882     ListElm<T>* _next;
00883 };
00884 
00885 
00886 template <typename T>
00887 class List{
00888 public:
00889     List()
00890     {
00891         _head = _tail = nullptr;
00892         _size = 0;
00893     }
00894     ~List()
00895     {
00896         clear();
00897     }
00898 
00899     int add(T* t)
00900     {
00901         ListElm<T>* elm = new ListElm<T>(t);
00902         if ( elm == nullptr )
00903         {
00904             return 0;
00905         }
00906         if ( _head == nullptr )
00907         {
00908             _head = elm;
00909             _tail = elm;
00910         }
00911         else
00912         {
00913             elm->_prev = _tail;
00914             _tail->_next = elm;
00915             _tail = elm;
00916         }
00917         _size++;
00918         return 1;
00919     }
00920 
00921     void erase(ListElm<T>* elm)
00922     {
00923         if ( _head == elm )
00924         {
00925             _head = elm->_next;
00926             _size--;
00927             delete elm;
00928         }
00929         else if ( _tail == elm )
00930         {
00931             _tail = elm->_prev;
00932             elm->_prev->_next = nullptr;
00933             _size--;
00934             delete elm;
00935         }
00936         else
00937         {
00938             elm->_prev->_next = elm->_next;
00939             elm->_next->_prev = elm->_prev;
00940             _size--;
00941             delete elm;
00942         }
00943     }
00944     void clear(void)
00945     {
00946         ListElm<T>* p = _head;
00947         while ( p )
00948         {
00949             ListElm<T>* q = p->_next;
00950             delete p;
00951             p = q;
00952         }
00953         _head = nullptr;
00954         _tail = nullptr;
00955         _size = 0;
00956     }
00957 
00958     ListElm<T>* getElm(void)
00959     {
00960         return _head;
00961     }
00962 
00963     ListElm<T>* getNext(ListElm<T>* elm)
00964     {
00965         return elm->getNext();
00966     }
00967 
00968     int getSize(void)
00969     {
00970         return _size;
00971     }
00972 
00973 
00974 private:
00975     ListElm<T>* _head;
00976     ListElm<T>* _tail;
00977     int _size;
00978 };
00979 
00980 
00981 extern Process* theProcess;
00982 extern MultiTaskProcess* theMultiTaskProcess;
00983 
00984 }
00985 #endif /* MQTTSNGWPROCESS_H_ */