pthread from a class with suspend and resume function

below is an template for pthread for a cpp class which default suspend until ResumeThread() called

#include <pthread.h>

class MyThreadClass
{
public:
    MyThreadClass() {
        // suspend the Internal thread by default
        suspended = true;
    }
    virtual ~MyThreadClass() {/* empty */}

    /** Returns true if the thread was successfully started, false if there was an error starting the thread */
    bool StartInternalThread()
    {
        return (pthread_create(&_thread, NULL, InternalThreadEntryFunc, this) == 0);
    }

    /** Will not return until the internal thread has exited. */
    void WaitForInternalThreadToExit()
    {
        (void) pthread_join(_thread, NULL);
    }

    void SuspendThread()
    {
        pthread_mutex_lock(&_suspendMutex);
        if ( suspended == false ) {
            fprintf(stdout, "Suspend thread\n");
            suspended = true;
        }
        pthread_mutex_unlock(&_suspendMutex);
    }

    void ResumeThread()
    {
        /* The shared state 'suspended' must be updated with the mutex held. */
        pthread_mutex_lock(&_suspendMutex);
        if ( suspended == true ) {
            fprintf(stdout, "Resume thread\n");
            suspended = false;
            pthread_cond_signal(&_resumeCond);
        }
        pthread_mutex_unlock(&_suspendMutex);
    }

    void CondWaitThread()
    {
        pthread_mutex_lock(&_suspendMutex);
        while(suspended) {
            // suspend is true by default
            // thread wait for signal to resume
            pthread_cond_wait(&_resumeCond, &_suspendMutex);
        }
        pthread_mutex_unlock(&_suspendMutex);
    }
protected:
    /** Implement this method in your subclass with the code you want your thread to run. */
    virtual void InternalThreadEntry() = 0;

private:
    static void * InternalThreadEntryFunc(void * This) {((MyThreadClass *)This)->InternalThreadEntry(); return NULL;}
    pthread_t _thread;
    bool suspended;
    pthread_mutex_t _suspendMutex;
    pthread_cond_t _resumeCond;

};
#ifndef HTC_DISABLE_COMBINEKEY_RESET_H
#define HTC_DISABLE_COMBINEKEY_RESET_H

#define DISABLE_COMBINEKEY_RESET "12"
#define ENABLE_COMBINEKEY_RESET  "0"
#define FILENODE_DISABLE_COMBINEKEY_RESET "path/to/filenode"
#define FILENODE_S2 "path/to/filenode"
#define FILENODE_S3 "path/to/filenode"
#define INIT_COUNT_PROP "recovery.initcount"
#define INIT_LIMIT (5)
#define COUNT_DOWN (200)
#define CHECK_INTERVAL (8)

#include "MyThread.h"

class CombineKeyReset : public MyThreadClass {
    public:
        CombineKeyReset();
        virtual ~CombineKeyReset() {/* empty */}

        // call this before Init()
        // recovery had redirect stdout,stderr to recovery log
        // hosd log to kernel log by LogRedirect("/dev/kmsg")
        void LogRedirect(const char *);

        // init thread to decrease count_down
        int Init(void);

        // if process crash and restart infinitely
        // then stop the disable combinekey reset mechanism
        void InitCount(void);

        // if FILENODE_S2 and FILENODE_S3 exist
        // then echo 1 > FILENODE_S2, echo 1 > FILENODE_S3
        // else if FILENODE_DISABLE_COMBINEKEY_RESET exist
        // then echo DISABLE_COMBINEKEY_RESET > FILENODE_DISABLE_COMBINEKEY_RESET
        // else do nothing
        int Disable(void);

        // if FILENODE_S2 and FILENODE_S3 exist
        // then echo 0 > FILENODE_S3
        // else if FILENODE_DISABLE_COMBINEKEY_RESET exist
        // then echo 0 > FILENODE_DISABLE_COMBINEKEY_RESET
        // else do nothing
        int Enable(void);

    protected:
        void InternalThreadEntry();

    private:
        // write args to filenode
        int WriteFilenode(const char* filenode, const char* value);

        unsigned int count_down;
        char filenode[64];
        int initcount;
};
#endif
#include <ctype.h>
#include <errno.h>
#include <unistd.h>
#include <time.h>
#include <string.h>
#include <stdio.h>
#include <cutils/klog.h>
#include <stdlib.h>
#include <pthread.h>

#include "cutils/properties.h"
#include "htc_disable_combinekey_reset.h"

// Return the current time as a double (including fractions of a second).
static double now() {
    struct timeval tv;
    gettimeofday(&tv, nullptr);
    return tv.tv_sec + tv.tv_usec / 1000000.0;
}

CombineKeyReset::CombineKeyReset() {
    count_down = 0;
    initcount = 0;
    memset(filenode, 0, sizeof(filenode));
}

void CombineKeyReset::InitCount() {
    // 1. INIT_COUNT_PROP will be set as 0 if property not exist
    // 2. INIT_COUNT_PROP increased by 1 when process start
    // 3. INIT_COUNT_PROP increased by 1 only if less than
    //    INIT_LIMIT prevent from overflow
    // 4. initcount will be set as INIT_LIMIT to enable
    //    combinekey reset if property_set fail
    char initcount_prop[PROPERTY_VALUE_MAX+1] = {0};
    int len = 0;
    len = property_get(INIT_COUNT_PROP, initcount_prop, "false");
    if ( len == 0 || !strncmp(initcount_prop, "false", strlen("false")) ) {
        // property get fail (property not exist)
        if ( property_set(INIT_COUNT_PROP, "0") == 0 ) {
            // property set success
            fprintf(stdout, "init property %s=0 success\n", INIT_COUNT_PROP);
        } else {
            // property set fail
            // enable combinekey reset if cannot set property
            // so that device can be comebinekey reset if recovery go into infinitely crash
            initcount = INIT_LIMIT;
            fprintf(stderr, "init property %s fail, set initcount=%d\n", INIT_COUNT_PROP, INIT_LIMIT);
        }
    } else {
        // property get success
        initcount = atoi(initcount_prop);
        if ( initcount < INIT_LIMIT ) {
            fprintf(stdout, "initcount(%s) < INIT_LIMIT(%d)\n", initcount_prop, INIT_LIMIT);
            initcount++;
            snprintf(initcount_prop, sizeof(initcount_prop), "%d", initcount);
            if ( property_set(INIT_COUNT_PROP, initcount_prop) == 0 ) {
                // property set success                                                                                                                                                           [73/122805]
                len = property_get(INIT_COUNT_PROP, initcount_prop, "false");
                if ( len == 0 || !strncmp(initcount_prop, "false", strlen("false")) ) {
                    // property get fail
                    fprintf(stderr, "initcount_prop get fail\n");
                }
                fprintf(stdout, "initcount_prop set %s=%s success\n", INIT_COUNT_PROP, initcount_prop);
            } else {
                // property set fail
                // enable combinekey reset if cannot set property
                // so that device can be comebinekey reset if recovery go into infinitely crash
                initcount = INIT_LIMIT;
                fprintf(stderr, "initcount set %s=%s fail\n", INIT_COUNT_PROP, initcount_prop);
            }
        }
    }
    if ( initcount >= INIT_LIMIT ) {
        fprintf(stderr, "initcount(%s) >= INIT_LIMIT(%d), enable combinekey reset\n", initcount_prop, INIT_LIMIT);
        Enable();
    }
}

void CombineKeyReset::InternalThreadEntry() {
    while(true) {
        // thread will wait untill ResumeThread() called
        CondWaitThread();

        if ( count_down > 0) {
            fprintf(stdout, "Internal Thread count_down(%d) > 0\n", count_down);
            count_down-=CHECK_INTERVAL;
            WriteFilenode(filenode, DISABLE_COMBINEKEY_RESET);
            if ( strncmp(filenode, FILENODE_S2, strlen(FILENODE_S2)) == 0 ){
                WriteFilenode(FILENODE_S3, "1");
            }
        } else {
            fprintf(stdout, "Internal Thread count_down(%d) <= 0\n", count_down);
        }
        sleep(CHECK_INTERVAL);
    }
}

int CombineKeyReset::Init(){
    if ( access(FILENODE_DISABLE_COMBINEKEY_RESET, R_OK | W_OK) == 0 ){
        snprintf(filenode, sizeof(filenode), "%s", FILENODE_DISABLE_COMBINEKEY_RESET);
        fprintf(stdout, "%s read, write OK\n", FILENODE_DISABLE_COMBINEKEY_RESET);
    } else if ( access(FILENODE_S2, R_OK | W_OK) == 0 ){
        snprintf(filenode, sizeof(filenode), "%s", FILENODE_S2);
        fprintf(stdout, "%s read, write OK\n", FILENODE_S2);
    } else {
        fprintf(stdout, "No filenode for disable combinekey reset\n");
        return 0;
    }

    // InitCount will write to filenode
    // setup filenode before call InitCount
    InitCount();

    if ( StartInternalThread() == true ) {
        fprintf(stdout, "Start Internal Thread success\n");
        SuspendThread();
    }
    return 0;
}

int CombineKeyReset::Disable(){
    // filenode not exist
    if ( filenode[0] == 0 ) { return 0; }
    // filenode exist
    if ( initcount < INIT_LIMIT ) {
        count_down = COUNT_DOWN;
        ResumeThread();
    }
    return 0;
}

int CombineKeyReset::Enable(){
    // filenode not exist
    if ( filenode[0] == 0 ){ return 0; }
    // filenode exist
    count_down = 0;
    WriteFilenode(filenode, ENABLE_COMBINEKEY_RESET);
    SuspendThread();
    return 0;
}

int CombineKeyReset::WriteFilenode(const char* path, const char* value){
    static bool filenode_open_fail = 0;

    // filenode not exist
    if ( path[0] == 0 ){
        fprintf(stderr, "filenode(%s) not exist\n", path);
        return 0;
    }

    FILE *fp = NULL;
    fp = fopen(path, "w");
    if ( fp == nullptr ){
        if ( filenode_open_fail == 0 ){
            fprintf(stderr, "filenode exist but fopen fail: %s\n", path);
            filenode_open_fail = 1;
            return -1;
        }
    }
    else{
        if ( count_down == 0 && strncmp(path, FILENODE_S2, strlen(FILENODE_S2)) == 0 ){
            // do not write to S2, since wirte any value to S2 will reset S2 timer
        } else {
            fwrite(value, strlen(value), 1, fp);
            if ( ferror(fp) ){
                // write fail
                fprintf(stderr, "write to %s fail\n", path);
                return -1;
            }
            else{
                // write success
                fprintf(stdout, "write %s to %s\n", value, path);
            }
        }
        if ( fp != nullptr ){
            fclose(fp);
        }
    }
    return 0;
}

void CombineKeyReset::LogRedirect(const char* filename){
    freopen(filename, "a", stdout); setbuf(stdout, NULL);
    freopen(filename, "a", stderr); setbuf(stderr, NULL);
}

Rotate Array

這題目我以前在臉書就看過了,也還不知道如何解釋

題意,給一整數陣列,陣列長度n,以及一整數k,將陣列向右移動k次,往右邊移動的那一位填補到最左邊的空位

例如

[1,2,3],1 ->[3,1,2]

[1,2,3,4,5,6,7],2 -> [6,7,1,2,3,4,5]

操作方法是先將全部reverse,再reverse前面第零個到第k個,最後reverse第k個後面到結尾

考慮進去三次reverse,時間複雜度為O(2n)

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        reverse(nums, nums+n);
        reverse(nums, nums+k%n);
        reverse(nums+k%n, nums+n);
    }
};

想出解釋的方法了

向右移動 k 次,代表會有末尾 k 位跑到右邊去

所以先將整個數列反轉一次之後,把前面 k 位再反轉一次,就可以讓前面 k 位保持原本的順序

然後在將後面 n-k 位翻轉一次,讓後面剩下的位數也都保持原本的順序

這樣就完成了

Remove Element

https://oj.leetcode.com/problems/remove-element/

題意,輸入一整數陣列、陣列長度,數值A

移除該整數陣列中的數值A,並且回傳移除之後的陣列長度,長度之後的元素值無所謂,陣列中的元素順序也無所謂

例如122334,移除2,則變成133422回傳4,或者143322回傳4,第4個數字後面的值是什麼無所謂

操作方法是:遍歷每個元素,如果元素是要移除的,則往後找尋不等於要移除的元素並且找到之後進行交換

如果找到了最後一個元素都沒有找到可以交換的,那就代表整個陣列操作完成

時間複雜度是O(n+m)

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int i=0, j=0;
        int d=0;
        bool end=false;
        while(i<n){
            if(A[i]==elem){
                if(n==1){
                    break;
                }
                j=i;
                while(1){
                    j++;
                    if(j==n){
                        end=true;
                        break;
                    }
                    if(A[j]!=elem){
                        swap(A[j],A[i]);
                        d++;
                        break;
                    }
                }
            }
            else{
                d++;
            }
            if(end){
                break;
            }
            i++;
        }
        return d;
    }
};

Remove Duplicates from Sorted Array

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

題目輸入一個已經從小到大排序完成的整數陣列,以及陣列長度

移除該陣列中重複的元素

操作方法是:依序讀取每一個元素,如果與前一個元素相同的話就做i++讀取下一個

如果前一個元素不同的話就做d++並且把A[i]寫到A[d]裡面去,然後做i++讀取下一個

這樣的時間複雜度是O(n)

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int i=0;
        int d=0;
        if(n==0){
            return 0;
        }
        while(i<n){
            if(i==0){
                i++;
                d++;
                continue;
            }
            if(A[i]==A[i-1]){
            }
            else{
                A[d]=A[i];
                d++;
            }
            i++;
        }
        return d;
    }
};

Same Tree

https://oj.leetcode.com/problems/same-tree/

題目輸入兩個二元樹,判斷兩個樹是否長的一模一樣

操作邏輯是,遞迴方式檢查每一個節點的左子節點和右子節點

時間複雜度是O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p==NULL && q==NULL){
            return true;
        }
        if(p==NULL || q==NULL){
            return false;
        }
        if(p->val != q->val){
            return false;
        }
        if(!isSameTree(p->left, q->left)){
            return false;
        }
        if(!isSameTree(p->right, q->right)){
            return false;
        }
        return true;
    }
};

Symmetric Tree

https://oj.leetcode.com/problems/symmetric-tree/

題目:判斷一個二元樹是否對稱

操作的邏輯是,建樹的時候遇到節點左或右子樹空缺,則補-1

每一層建立完成之後取值進行比較

這個方法的時間複雜度是O(n^2)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if(root==NULL){
            return true;
        }
        if(root->left==NULL&&root->right==NULL){
            return true;
        }
        list<int> int_list;
        queue<TreeNode*> tn_queue1;
        queue<TreeNode*> tn_queue2;
        TreeNode* tmp;
        tn_queue1.push(root);
        while(!tn_queue1.empty()){
            tmp = tn_queue1.front();
            if(tmp->left!=NULL){
                tn_queue2.push(tmp->left);
                int_list.push_back(tmp->left->val);
            }
            else{
                int_list.push_back(-1);
            }
            if(tmp->right!=NULL){
                tn_queue2.push(tmp->right);
                int_list.push_back(tmp->right->val);
            }
            else{
                int_list.push_back(-1);
            }
            tn_queue1.pop();
            if(tn_queue1.empty()){
                tn_queue1 = tn_queue2;
                tn_queue2 = queue<TreeNode*>();
                while(int_list.size()>1){
                    if(int_list.front() != int_list.back()){
                        return false;
                    }
                    int_list.pop_front();
                    int_list.pop_back();
                }
                int_list.clear();
            }
        }
        return true;
    }
};

看討論區裡面有個O(n)的作法,概念是把節點的L node, R node作為參數放入helper()

然後比較L->val, R->val

如果相同的話再比較helper(L->left, R->right) and helper(L->right, r->left)

只要有一個回傳 false 就算不對稱了

Binary Tree Level Order Traversal II

https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

目前只有想到O(2N)的解法

第一個N是建立正序 myvector

第二個N是將 myvector 顛倒過來

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> myvector;
        vector<vector<int>> myvector2;
        if(root==NULL){
            return myvector;
        }
        TreeNode* tmp;
        queue<TreeNode*> queue_node1;
        queue<TreeNode*> queue_node2;
        vector<int> vector_num1;
        queue_node1.push(root);
        while(!queue_node1.empty()){
            tmp = queue_node1.front();
            if(tmp->left!=NULL){
                queue_node2.push(tmp->left);
            }
            if(tmp->right!=NULL){
                queue_node2.push(tmp->right);
            }
            vector_num1.push_back(tmp->val);
            queue_node1.pop();
            if(queue_node1.empty()){
                queue_node1 = queue_node2;
                queue_node2 = queue<TreeNode*>();
                myvector.push_back(vector_num1);
                vector_num1.clear();
            }
        }
        vector<vector<int>>::reverse_iterator rit = myvector.rbegin();
        for(; rit!=myvector.rend(); rit++){
            myvector2.push_back(*rit);
        }
        return myvector2;
    }
};