2017-03-09 183 views
1

我必須爲具有比較函數作爲參數的任何數據類型編寫抽象二進制搜索函數。我不知道如何處理void,因爲使用指針運算是不可能的。然後我看到了標準的qsort函數,並且做到了這一點。問題是發生從void*char*轉換時發生了什麼?它爲什麼有效?Casting void * to char * in C

void *bin_srch(void *a, size_t n, size_t bs, void *x, int (*cmp)(const void *a, const void *b)) 
{ 
    size_t f = 0, l = n; 

    if(!n) return NULL; 

    while (f < l) 
    { 
     size_t m = f/2 + l/2; 
     char *mid = (char*)a + m*bs; 

     if (cmp(x, mid) <= 0) 
      l = m; 
     else 
      f = m + 1; 
    } 

    char *t = (char*)a + l*bs; 

    if (!cmp(t, x)) 
     return t; 
    else 
     return NULL; 
} 
+0

你不需要將任何東西轉換爲char *' - 函數中的所有指針都應該是void *' –

+0

@Someprogrammerdude那麼,爲什麼它是UB? 'char *'可以用來訪問任何其他類型,不是嗎? –

+1

@ChrisTurner *函數中的所有指針都應該是'void *'*如何對'void *'指針做指針運算? –

回答

3

它的工作原理,因爲,char *可以別名任何其他類型。

C11引用,章§6.3.2.3

[....當一個指向對象轉換爲一個指向字符類型, 結果點到最低尋址字節的對象。 結果的連續增量,直到對象的大小,產生指向對象剩餘字節的指針。

使用此屬性,鑄造到char *可以使用(鑄造)指針作爲操作數執行指針運算。

由於在同規格中提到(與我的重點),章§6.5.6/ P2

對於另外,無論是兩個操作數應具有算術類型,或一個操作數應該是一個 指向完整對象類型的指針,另一個應具有整數類型。 (遞增是 相當於增加1)

和,P3

對於減法,以下中的一個應當持有:

  • 兩個操作數具有算術類型;

  • 這兩個操作數都是指向合格或不合格版本的兼容完整對象類型的指針;或

  • 左操作數是一個指針將完整的對象類型和右操作數已 整數類型。

這就需要將指針操作數是一個指針到完整的類型,這void是不是和char是。

最後,參照章§6.2.5/ P19

void類型包括一個空的一組值;它是不完整的對象類型, 無法完成。

0

你基本上自己回答你的問題。這個代碼包含轉換到char *的唯一原因是使用基於字節的指針運算表達式像

char *mid = (char*)a + m*bs; 

即來計算按索引m指定的數組元素的位置以及元素bs的字節大小。當您轉換爲char *時,生成的指針指向與原始指針void *相同的位置,但現在可以將指針arithemtic應用於該指針。