永安基金新三板二期:MTK优美代码赏析1：二分查找

MTK优美代码赏析1：二分查找

   MTK刚入门的开发者总是认为自己的工作很无聊，很没有前途，整天就是改bug，实则这种想法是狭隘的，mtk的学习只能算是嵌入式领域的冰山一角，应该感谢他初步的降低了嵌入式的门槛。

   别人都说软件开发语言是相通的，同理嵌入式系统的开发其实也是同样的道理，嵌入式系统也都是相通的，搞精一门其他的系统就可以很快的掌握并进行开发，对于入门级的mtk表面的东西的确很容易掌握，但深入的内容还是需要花很大心血去研究的，这部分内容就是嵌入式系统中所共通的东西，最简单概括，那就是思想。

  看csdn上有一篇报道《只有10%程序员能正确实现二分查找算法》 ，mtk代码中也有这样的一段代码，极其的优美，让人感受到程序员不仅仅是在创造代码，也是在创造一种艺术，唯有接近于艺术家的程序员才具备了软件设计师的潜质。

作者 张素丰，转载请注明出处：http://www.cnblogs.com/zhangsufeng/archive/2010/09/03/1816612.html 

  废话少说，让我们通过mtk的优美代码来学校二分查找。

  对于mtk的开发者来说，对于设置菜单高亮的SetHiliteHandler函数可能已经熟悉的不得了了，在这个算法里，程序首先判断该menu是否已经高亮并存在于动态高亮表mmi_frm_int_hilite_hdlr_table中，如果存在则更换该menu的高亮函数，不存在则插入该menu并设置高亮。这个查找就使用了一个极其简约的二分查找，看代码：

mtk二分查找代码   1 typedef struct 
  2 {
  3    U32 key;
  4    U32 data;
  5 }mmi_frm_pair_data_struct;
  6 
  7 typedef struct
  8 {
  9     U32     menu_id;
 10     FuncPtr hilite_hdlr;
 11 }mmi_frm_hilite_hdlr_struct;
 12 
 13 
 14 static mmi_frm_hilite_hdlr_struct mmi_frm_int_hilite_hdlr_table[MMI_FRM_MAX_HILITE_HDLR];
 15 /*****************************************************************************
 16  * FUNCTION
 17  *  SetHiliteHandler
 18  * DESCRIPTION
 19  *  This function is used for dynamcally register the handler for the menu item. If the 
 20  *  menu items are pre-definable, the applications use this function to dynamcally set 
 21  *  the highlight handlers. 
 22  *
 23  *  Note: (1) Please distinguish the function from RegisterHighlightHandler() 
 24  *        which is provided by UI layer. SetHiliteHandler() is for single 
 25  *        menu item; RegisterHighlightHandler() is global for all menu items.
 26  *        (2) When the screen switchs, the registred handler will invalid.
 27  * PARAMETERS
 28  *  itemid              [IN]  ID of the item for which highlight handler needs 
 29  *                            to be set.      
 30  *  hiliteFuncPtr       [IN]  Function to be executed whenever item with above
 31  *                            ID is highlighted.      
 32  * RETURNS
 33  *  void
 34  *****************************************************************************/
 35 void SetHiliteHandler(U16 itemid, FuncPtr hiliteFuncPtr)
 36 {
 37     /*----------------------------------------------------------------*/
 38     /* Local Variables                                                */
 39     /*----------------------------------------------------------------*/
 40     U32 index;
 41     MMI_BOOL result;
 42 
 43     /*----------------------------------------------------------------*/
 44     /* Code Body                                                      */
 45     /*----------------------------------------------------------------*/
 46     MMI_TRACE(MMI_FW_TRC_G1_FRM, TRC_MMI_FRM_EVENT_SETCURHILIHTE_HDLR, itemid, hiliteFuncPtr);
 47 
 48     MMI_ASSERT(mmi_frm_int_hilite_hdlr_count < MMI_FRM_MAX_HILITE_HDLR);
 49         
 50     result = mmi_frm_binary_search((U32)itemid, (mmi_frm_pair_data_struct*)mmi_frm_int_hilite_hdlr_table, 
 51                                    (U32)mmi_frm_int_hilite_hdlr_count, &index);
 52             
 53     if (result == MMI_FALSE)
 54     {
 55         if (mmi_frm_int_hilite_hdlr_count != 0)
 56         {
 57             memmove(&mmi_frm_int_hilite_hdlr_table[index+1], &mmi_frm_int_hilite_hdlr_table[index], 
 58                      (mmi_frm_int_hilite_hdlr_count - index)*sizeof(mmi_frm_hilite_hdlr_struct));
 59         }
 60         mmi_frm_int_hilite_hdlr_count++;        
 61     }      
 62 
 63     mmi_frm_int_hilite_hdlr_table[index].menu_id     = itemid;
 64     mmi_frm_int_hilite_hdlr_table[index].hilite_hdlr = hiliteFuncPtr;  
 65  }
 66 
 67 
 68 
 69 /*****************************************************************************
 70  * FUNCTION
 71  *  mmi_frm_binary_search
 72  * DESCRIPTION
 73  *  Performs a binary search of a sorted array.
 74  * PARAMETERS
 75  *  key             [IN]    Object to search for. 
 76  *  search_table    [IN]    Pointer to base of search data.
 77  *  num             [IN]    Number of elements. 
 78  *  index           [OUT]   index to an occurrence of key in the search_table
 79  *                          array. 
 80  * RETURNS
 81  *  If key is found, the function returns MMI_TRUE, else returns MMI_FALSE.
 82  *****************************************************************************/
 83 MMI_BOOL mmi_frm_binary_search(U32 key, mmi_frm_pair_data_struct* search_table, U32 num, U32* index)
 84 {
 85     /*----------------------------------------------------------------*/
 86     /* Local Variables                                                */
 87     /*----------------------------------------------------------------*/
 88     S32 m =0, low = 0, high = num -1;
 89 
 90     /*----------------------------------------------------------------*/
 91     /* Code Body                                                      */
 92     /*----------------------------------------------------------------*/    
 93     while(low <= high)
 94     {
 95         m = (low + high)/2;
 96 
 97         if (key == search_table[m].key)
 98         {
 99             *index = m;
100             return MMI_TRUE;
101         }            
102         else if (key > search_table[m].key)
103         {
104             low = m + 1;
105         }
106         else
107         {
108             high = m - 1;
109         }
110     }
111 
112     *index = low;
113     return MMI_FALSE;    
114 }
115 复制代码

 

  代码写的不仅直观，而且优美，太简单了，我就不阐述了。

分类: MTK标签: 跨平台, MTK