Seminář 7

S pomocí pointerů na funkce lze v omezené míře pracovat s funkcemi vyššího řádu. Pointer na funkci je adresa, kde je funkce uložena v paměti. S pomocí této adresy lze funkci volat. Podobně jako u polí, jméno funkce degeneruje na pointer na funkci.

Pointer na funkci sebou nese i typové informace: typ návratové hodnoty a počet a typy argumentů. Zápis tohoto typu podobný jako zápis hlavičky funkce bez jmen argument, pouze jméno funkce nahradíme (*).

int (*)(int*, int)   // typ pointer na fci, ktera vraci int, 
                     // jeji argumentu jsou typu int* a int.

int (*fce_ptr)(int*, int);   // definice pointeru

typedef int (*p_fun)(int* , int); // typ se jmenuje p_fun
p_fun ptr;   // definice promenne

S pointery na funkce nelze provádět aritmetiku, ani aplikovat operátory adresy a dereference (resp, tyto operátory nedělají nic). Můžeme ovšem funkci volat, syntax volání je přitom stejná jako u běžného volání funkce.

typedef int (*p_fun)(int* , int);

int array_sum(int *array, int n) {
    int r = 0;
    for (int i = 0; i < n; i += 1) {
        ret += i;
    }
    return ret;
}

int array_product(int *array, int n) {
    int ret = 1;
    for (int i = 0; i < n; i += 1) {
        ret += i;
    }
    return ret; 
}

int main() {
    int a[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(a)/sizeof(*a);
    
    p_fun reduce = array_sum;      // reduce ukazuje na funkci array_sum
    printf("%i\n", reduce(a, m));   // vytiskne 15, vola array_sum
    reduce = array_product;
    printf("%i\n", reduce(a, m));   // vytiskne 120, vola array_product
    return 0;
}

S pointery na funkce lze pracovat jako s jinými typy v C. Lze tvořit jejich pole, předávat je do funkcí jako argumenty, mohou být návratovými hodnotami funkcí atd.

Pointer na funkci může být neplatný, v tom případě vede pokus o volání k nedefinovanému chování. Pointeru na funkci je možné přiřadit 0.

Jedno z využití pointerů na funkce je tvorba analogii generických funkcí známých z jiných jazyků. Ideou je, že funkci naprogramujeme jednou a ona poté pracuje pro více typů. Ukážeme si to na příkladu binárního vyhledávání.

typedef int compare_fn(void *, void *);  // argumenty jsou void*, aby byla funkce obecna

int compare_int(void *a, void *b) { 
  int *aa = a; // tuto funkci budeme volat pouze s int*,
  int *bb = b; // muzeme bezpecne pretypovat

  if (*aa < *bb) return -1;
  if (*bb < *aa) return 1;

  return 0;
}

int compare_long(void *a, void *b) {
  long* aa = a;  
  long* bb = b;

  if (*aa < *bb) return -1;
  if (*bb < *aa) return 1;

  return 0;
}

//
//  genericka funkce pro binarni vyhledavani
//

int binary_search(void *array,              // pole, ve kterem vyhledavame
                  void *key,                // ukazatel na hodnotu klice
                  size_t n,                 // pocet prvku pole
                  size_t element_size,      // velikost jednoho prvku v bajtech
                  compare_fn* cmp)          // funkce pro porovnani dvou prvku
{
    unsigned char* bytes = array;

    int l = 0;
    int p = n-1;

    while (l <= p) {
        int s = (l + p) / 2;

        unsigned char* s_ptr = bytes + s * element_size;  // tady spocitame prvni bajt prvku na indexu s
        int cmp_result = cmp(key, s_ptr);                 // zjistime vysledek porovnani

        if (!cmp_result) {
            return s;
        }
        else if (cmp_result > 0) { // klic je vetsi
            l = s + 1;
        }
        else {
            p = s - 1;
        }
    }

    return -1;
}

//
//  pro jednotlive typy vytvorem funkce tvorici rozhrani
//
int binary_search_int(int* array, int key, size_t n) {
    return binary_search(array, &key, n, sizeof(int), compare_int);
}

int binary_search_long(long* array, long key, size_t n) {
    return binary_search(array, &key, n, sizeof(long), compare_long);
}

int main() {
    int array_int[20];
    long array_long[20];

    for(int i = 0; i < 20; i += 1) {
        array_int[i] = i;
        array_long[i] = i;
    }

    int key_int_ok = 10;
    int key_int_fail = 30;

    long key_long_ok = 5;
    long key_long_fail = -3;

    printf("index of %i in array_int is %i\n",
            key_int_ok,
            binary_search_int(array_int, key_int_ok, 20));

    printf("index of %i in array_int is %i\n",
           key_int_fail,
           binary_search_int(array_int, key_int_fail, 20));

    printf("index of %li in array_long is %i\n",
           key_long_ok,
           binary_search_long(array_long, key_long_ok, 20));

    printf("index of %li in array_long is %i\n",
           key_long_fail,
           binary_search_long(array_long, key_long_fail, 20));
         
    return 0;
}

Seminář 7

Pointery na funkce

Úkoly