Android系統筆記 - Surface simple flow (1)

ZygoteConnection.java
 => boolean runOnce() 最後會 fork 出新的 process

#################################################
ActivityThread.java
main ()

=> handleLaunchActivity
 -----------------------------------------------------------------------------------------------------------------
 => performLaunchActivity

  // 生出 Activity
  => activity = mInstrumentation.newActivity(cl,component.getClassName(), r.intent);

   => activity.attach

    // 生出 PhoneWindow, 並取得 WindowManager "WindowManagerImpl", 他的 parentWindow 是 mWindow (PhoneWindow)
    => mWindow = new PhoneWindow(this);
    => mWindow.setWindowManager(
       (WindowManager)context.getSystemService(Context.WINDOW_SERVICE),
       mToken, mComponent.flattenToString(),
       (info.flags & ActivityInfo.FLAG_HARDWARE_ACCELERATED) != 0);
    => mWindowManager = ((WindowManagerImpl)wm).createLocalWindowManager(this);
                        // new WindowManagerImpl(mDisplay, parentWindow);


  // 呼叫 Activity 的 onCreate (這裡已經被你的Activity override掉了)
  => onCreate

   // 呼叫setContentView();
   => setContentView(R.layout.activity_main);

    // 呼叫 PhoneWindow::setContentView()
    => getWindow().setContentView(view);

     // 取得 mDecor 以及 mContentParent
     // 其中 mContentParent 是 ViewGroup, 在創建的時候我們會把這個 mDecor帶入
     => installDecor(); // new DecorView(getContext(), -1);
     => generateLaout(mDecor); // ViewGroup contentParent = (ViewGroup)findViewById(ID_ANDROID_CONTENT);

     // 呼叫 addView, 這邊的 view 是一開始帶進來的 R.layout.activity_main
     => mContentParent.addView(view, params);
      // 將傳入的 view 作為 child 保存起來, 並指定 parent為自己
      => addViewInner(child, index, params, false);
       => child.mParent = this;
 -----------------------------------------------------------------------------------------------------------------
 => handleResumeActivity

  // 呼叫 Activity 的 onResume()Activity的onResume()方法
  => ActivityClientRecord r = performResumeActivity(token, clearHide);

  // 呼叫 WindowManager, 也就是 WindowManagerImpl 的 addView
  => wm.addView(decor, l);

   // 實作在 WindowManagerGlobal
   => mGlobal.addView(view, params, mDisplay, mParentWindow);

    // 建立 ViewRootImpl
    => ViewRootImpl root;
       root = new ViewRootImpl(view.getContext(), display);

     // 在 ViewRootImpl 的建構子內部又透過了 windowManager 去呼叫 openSession
     // 最後取得了 Session 用來作為跟 WindowManagerService 通信的手段
     => sWindowSession = windowManager.openSession(
           new IWindowSessionCallback.Stub() {
               @Override
               public void onAnimatorScaleChanged(float scale) {
                   ValueAnimator.setDurationScale(scale);
               }
           },
           imm.getClient(), imm.getInputContext());
        // Session session = new Session(this, callback, client, inputContext);
        // 對於 ViewRootImpl 來說是他內部的 mWindowSession

        // 另外這裡還 new 了一個 W class, 用處是收取發生的事件
        // 他繼承了 IWindow, 可以看到裡面實作的 API 諸如 dispatchGetNewSurface, dispatchAppVisibility 這種
        mWindow = new W(this);

     // 注意 ViewRootImpl 內部有個 mSurface 對象, 之後會拿這個對象來繪圖
     => final Surface mSurface = new Surface();

    // 接著我們繼續回到 WindowManagerGlobal 的 addView 函數,
    // 接下來是呼叫了 ViewRootImpl 的 setView, 這邊的 view 參數是 decorView 而不是一開始傳入的 R.layout.activity_main
    => root.setView(view, wparams, panelParentView);

     // ViewRootImpl 的 requestLayout 可就做了不少事情
     +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
     => requestLayout();

      // 規劃了接下來的 Traversal callback
      => scheduleTraversals();

       // Posts a callback to run on the next frame
       // The callback runs once then is automatically removed.
       // 怎麼觸發的後面再看, 我們先跳離 requestLayout()
       => mChoreographer.postCallback(
                    Choreographer.CALLBACK_TRAVERSAL, mTraversalRunnable, null);
     +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

     // mWindowSession 就是前面 new 出來的 Session
     => mWindowSession.addToDisplay(mWindow, mSeq, mWindowAttributes,
                            getHostVisibility(), mDisplay.getDisplayId(),
                            mAttachInfo.mContentInsets, mAttachInfo.mStableInsets,
                            mAttachInfo.mOutsets, mInputChannel);

      // mService 是 WindowManagerService (前面有提到說透過 Session 來跟 WindowManagerService 溝通)
      => mService.addWindow(this, window, seq, attrs, viewVisibility, displayId,
                outContentInsets, outStableInsets, outOutsets, outInputChannel);

       // 創建一個 WindowState 對象, 並呼叫他的 attach() 函數
       => WindowState win = new WindowState(this, session, client, token,
                    attachedWindow, appOp[0], seq, attrs, viewVisibility, displayContent);
       => win.attach();

        // 呼叫 Session 的 windowAddedLocked();
        => mSession.windowAddedLocked();

         // new 出一個 SurfaceSession 對象
         => mSurfaceSession = new SurfaceSessionSurfaceSession();

          /** Create a new connection with the surface flinger. */
          // 跟 SurfaceFlinger 搭上線了
          => mNativeClient = nativeCreate();

           // 生成了一個 SurfaceComposerClient 對象, 他之後會被用來跟 SurfaceControl 進行溝通
           => SurfaceComposerClient* client = new SurfaceComposerClient();

       // 把這個 WindowState 對象放進mWindowMap, 後面畫圖的時候會用到
       => mWindowMap.put(client.asBinder(), win);
     +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
     // 回到 scheduleTraversals(), 從 mTraversalRunnable 進入
     => final TraversalRunnable mTraversalRunnable = new TraversalRunnable();
      => doTraversal();
       => performTraversals();
        **************************************************************************
        => relayoutResult = relayoutWindow(params, viewVisibility, insetsPending);
        => performMeasure(childWidthMeasureSpec, childHeightMeasureSpec);
        => performLayout(lp, desiredWindowWidth, desiredWindowHeight);
        => performDraw();
        **************************************************************************
        // 先從 relayoutWindow 開始
        => relayoutResult = mWindowSession.relayout(
                mWindow, mSeq, params,
                (int) (mView.getMeasuredWidth() * appScale + 0.5f),
                (int) (mView.getMeasuredHeight() * appScale + 0.5f),
                viewVisibility, insetsPending ? WindowManagerGlobal.RELAYOUT_INSETS_PENDING : 0,
                mWinFrame, mPendingOverscanInsets, mPendingContentInsets, mPendingVisibleInsets,
                mPendingStableInsets, mPendingOutsets, mPendingConfiguration, mSurface);

         // Session
         // 注意這個 mSurface 傳入以後命名變成了 outSurface (這是在 ViewRootImpl 建構子生成的那個 Surface 對象
         => mService.relayoutWindow(this, window, seq, attrs,
                requestedWidth, requestedHeight, viewFlags, flags,
                outFrame, outOverscanInsets, outContentInsets, outVisibleInsets,
                outStableInsets, outsets, outConfig, outSurface);

          // WindowManagerService
          // 拿出剛剛在 addWindow 生出來的 WindowState
          => WindowState win = windowForClientLocked(session, client, false); // WindowState win = mWindowMap.get(client);
          => WindowStateAnimator winAnimator = win.mWinAnimator; // 在 WindowState 建構時, new WindowStateAnimator(this);

          // 建構出 SurfaceControl ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
          => SurfaceControl surfaceControl = winAnimator.createSurfaceLocked();
           => mSurfaceControl = new SurfaceControl(
                        mSession.mSurfaceSession,
                        attrs.getTitle().toString(),
                        width, height, format, flags);

            // 又是一個 nativeCreate, 這次是經由 SurfaceComposerClient 產生一個 SurfaceControl 對象
            => mNativeObject = nativeCreate(session, name, w, h, format, flags);
             => sp<SurfaceComposerClient> client(android_view_SurfaceSession_getClient(env, sessionObj));

             // 在 SurfaceComposerClient 的 createSurface 還會去申請 gbp (IGraphicBufferProducer)
             => sp<SurfaceControl> surface = client->createSurface(String8(name.c_str()), w, h, format, flags);

              // 這裡的 mClient 是 SuffaceFlinger 的 Client 對象
              => mClient->createSurface(name, w, h, format, flags, &handle, &gbp);

               => sp<MessageBase> msg = new MessageCreateLayer(mFlinger.get(), name, this, w, h, format, flags, handle, gbp);

                // 這裡會通過 SurfaceFlinger 的 mEventQueue 才會完成
                /*
                   簡易流程大致如下:
                   1.) SurfaceFlinger Init 的時候, mEventQueue 開始等待 Message
                       => PollOnce, 時間是無限長, 最後會停在 epoll_wait 等待事件
                   2.) 透過 mFlinger->postMessageSync(msg); 塞入 Message
                   3.) epoll_wait() return, 取得各個 Message (messageEnvelope = mMessageEnvelopes.itemAt(0);)
                   4.) 取出 Message 中的 handler 跟 message, 執行 handler->handleMessage(message);
                       在這個 case 中會先執行完 handler
virtual bool handler() {
   result = flinger->createLayer(name, client, w, h, format, flags,
   handle, gbp);
   return true;
}

                       並且將 barrier unlock (open)
void MessageBase::handleMessage(const Message&) {
   this->handler();
   barrier.open();
};
                */

                // createLayer
                => SurfaceFlinger::createNormalLayer

                 // 取得 handle 與 bufferProducer
                 => *outLayer = new Layer(this, client, name, w, h, flags);
   status_t err = (*outLayer)->setBuffers(w, h, format, flags);
   if (err == NO_ERROR) {
*handle = (*outLayer)->getHandle();
*gbp = (*outLayer)->getProducer();
   }

                // 將 Layer 放置到 client 上
                => result = addClientLayer(client, *handle, *gbp, layer);
          // ------------------------------------------------------------------ 建構出 SurfaceControl

          // 接著呼叫 outSurface 也就是 Surface 對象的 copyFrom
          => outSurface.copyFrom(surfaceControl);

           => long newNativeObject = nativeCreateFromSurfaceControl(surfaceControlPtr);

            // 取得 native 的 Surface 對象
            => sp<Surface> surface(ctrl->getSurface());

             // 這裡的 mGraphicBufferProducer 就是前面帶進去的 gbp, 已經在 SurfaceFlinger 裡面創建了
             // 它就是 mProducer = new MonitoredProducer(producer, mFlinger);
             => mSurfaceData = new Surface(mGraphicBufferProducer, false);\

           // 將這個 native 的 Surface 對象保存起來
           => setNativeObjectLocked(newNativeObject); // mNativeObject = ptr;

        **************************************************************************
        // 待續...接下來是 performMeasure, performLayout, performDraw

C++ 語法小技巧 - array[0]

在看SurfaceFlinger的時候看到了一個奇妙的 array[0] 參數

標準C/C++中不支援長度為0的array,
但GNU C允許這種宣告方式, 目的是為了access不定長度的結構體時,
可以節省空間與便利性.

範例, 宣告一個 demo struct如下:

struct demo_t {
    int     a;
    char    b[256];
    char    follow[0];
};

接著要在程式中使用這個 struct demo, 並在其後分配長度為LEN的char空間.

struct demo_t *demo = (struct demo_t *) malloc (sizeof(strcut demo_t) + LEN);

接著你就可以使用 demo->follow 來存取到這段空間.

另外一個作法是宣告為 char *follow, 但這樣在不定長度為 0 時則會多佔用一個 char 的 pointer.

當然要記得把這個變數放在結構體的最後面 >.0

演算法筆記 - Robot路徑全展開

第一篇文章!

到大陸上班之後發現沒辦法存取大部份的網路資源....所以想找個地方來放自己的筆記.
終極目標是希望在大陸工作的時候也可以輕易的存取,
不過看起來好像只有CSDN可以比較簡單做到....
就先放在Blogger暫存一下好了 XD

這是上禮拜跟Jay哥拿了一本演算法的題庫的其中一題:

[題目]
掃地機器人可以進行上下左右的任意移動, 每次移動一格, 且不能走到重複的格子

當移動 1 次的時候, 總共會有 4 種移動結果
( ↑ / ↓ / ← / → )

當移動 2 次的時候, 總共會有 12 種移動結果
(↑↑ / ↑← / ↑→ ) * 4

當移動 3 次的時候, 總共會有 36 種移動結果
{(↑↑↑ / ↑↑← / ↑↑→ ) + (↑←← / ↑←↑ / ↑←↓) + (↑→→ / ↑→↑ / ↑→↓)} * 4

問題來了,

當移動了 13 次的時候, 總共會有幾種可能性?

[想法紀錄]
1.) 我可以固定起始方向, 之後將該計算結果*4就是答案
2.) 我需要記錄機器人走過的座標, 這樣才知道是否有走到重複的路徑上
3.) 或者....機器人的每一步都是自由的, 我應該讓他每一步都可以自由的進行上下左右移動,
再將不能移動到的位置幹掉.

羅列出來的想法大概就如上述這樣,
那麼接下來把需要的元素都展開來看看

[實作想法]
1.) 我需要紀錄座標, 那麼是不是需要一個二維Array?
2.) 我需要紀錄當前機器人所在的位置,
     並且我想要初始化它的座標點到(0, 0)去, 那麼長寬最好是一個奇數.
3.) 我可能需要傳遞這個二維Array進去函數內進行運算,
     而我們需要知道二維函數的傳遞形式並不是pointer to pointer:

int test[5][10];

void wrongFunc(int **array);
wrongFunc(&test[0]);

/* array 變數本身可以 decay 成記憶體起頭的位置,
    所以你要描述的是一個 array 的 pointer, 長度為10,
    並且這個 pointer 的 array 成員會再分別指向各自的一維 array
*/

void rightFunc(int (*array)[10]); // array 是一個 pointer, 它指向 int [10]
rightFunc(test);
rightFunc(&test[0]); //這兩個敘述式等價

4.) 我可以先展開寬度, 或者先展開深度.
展開寬度一般是會搭配權重, 進行縮減 (像是 Beam Search 這種演算)
但由於要做的是全路徑展開, 所以我應該可以用遞迴搭配深度展開來完成

[開始實作]
我需要的元素有這些:
1.) 整個走過的點 (map[50][50])
2.) 目前的座標 (x, y)
3.) 目前的深度 (depth)

Pseudo code大概長這樣:

boolean freeRun( map, x, y, depth, target) {
    if (depth == target) {
        return true;
    } else {
        for (way = 0; way < 4; way++) {
            switch (way) {
               case 0:
                  x++;
                  break;
               ...
               case 3:
                  y--;
                  break;
            }
            depth++;
            if (map[x][y] == 1) {return false;} // hit end
            else {
                map[x][y] = 1;
                boolean result = freeRun(map, x, y, depth);
                if (result != true) {
                    reset(map, x, y, depth);
                    continue;
                }
            }
        }
    }
    // Should never come here
    return false;
}

我要傳入陣列, 座標, 有時候還得Reset它們!?
是否有點太麻煩?
=> 使用Structure, 這樣我就不用管到底要怎麼傳陣列了 +_+

想複製, 那就直接傳Structure
想改值, 那就傳入&Structure
太美妙惹~~~

那麼就定義一個Structure吧~

#define COLUME_SIZE (50)
#define ROW_SIZE (50)
typedef struct Map {
 int pos[ROW_SIZE][COLUME_SIZE];
 int x;
 int y;
} Map;

把採點另外放到subFunction, 並加入debug log

void recordMap(Map *map) {
 int x = map->x;
 int y = map->y;
 map->pos[x][y] = 1;
 if (bDebug) printf("\t***record map[%d][%d] = %d\n", x-25, y-25, map->pos[x][y]);
}

最後改寫freeRun函式跟main函式, 完成~

int finalCnt = 0;
int bDebug = 0;

int main(int argc, char** argv) {
 int steps = 0;
 cout << "Steps to go: ";
 cin >> steps;
 cout << "Calculating for " << steps << " steps." << endl;

 getSteps(steps);
}

int getSteps(int step) {
 Map map;
 memset(&map, 0, sizeof(map));

 // Start from (25, 25)
 map.x = 25;
 map.y = 25;
 recordMap(&map);
 step--;

 // Running
 // - Consider only 1 ways when start running, then multiple as 4 will be the answer
 map.y++;
 recordMap(&map);
 step--;

 cout << "Ready to free run..." << endl;
 // - Free run
 freeRun(map, step);

 cout << "finalCnt = " << finalCnt*4 << endl;
}

void freeRun(Map map, int step) {
 int i = 0;

 // Backup the current step
 Map tempMap = map;

 if (bDebug) printf("+++========================================\n");
 for (i = 0; i < 4; i++) {
  if (bDebug) printf("\nfreeRun - step %d at [%d][%d]\n", step, tempMap.x - 25, tempMap.y - 25);
  switch (i) {
   case 0:
    // x+
    map.x++;
    break;
   case 1:
    // x-
    map.x--;
    break;
   case 2:
    // y+
    map.y++;
    break;
   case 3:
    // y-
    map.y--;
    break;
  }

  if (bDebug) printf("\t (i: %d) [%d][%d] => [%d][%d]\n", i, tempMap.x-25, tempMap.y-25, map.x-25, map.y-25);
  step--;

  if (map.pos[map.x][map.y] == 1) {
   // Dead end, go next try
   if (bDebug) printf("\t\tDead end: map[%d][%d] is 1\n", map.x-25, map.y-25);
  } else {
   recordMap(&map);
   if (step == 0) {
    finalCnt++;
    if (bDebug) printf("Meet final count at map[%d][%d]...%d\n\n", map.x-25, map.y-25, finalCnt);
    // Dead end, go next try
   } else {
    // Deep first, go next layer
    freeRun(map, step);
   }
  }

  // Recover for this turn running;
  step++;
  map = tempMap;

 }
 if (bDebug) printf("===========================================\n");
}