Lập trình tổng quát(Generic programming) trong C

1. Giới thiệu

Là phương pháp lập trình tạo ra các hàm tổng quát có thể sử dụng lại trong nhiều bài toán khác nhau.

Ví dụ hàm memcpy() trong thư viện string.h:

void* memcpy(void* region1, const void* region2, size_t n);

Chức năng chính của hàm:Tương tự như hàm strncpy, nhưng khi dùng memcpy thì sẽ kiểm soát bộ nhớ, tránh lỗi tràn bộ nhớ.

Hàm memcpy() bên trên được khai báo tổng quát bằng cách sử dụng các con trỏ void* . Điều này giúp cho hàm có thể sử dụng với nhiều kiểu dữ liệu khác nhau. Hay nói cách khác, để sao chép dữ liệu, ta chỉ cần địa chỉ và kích cỡ của chúng.

Ví dụ 1 cách cài đặt của hàm memcpy():

void* memcpy(void* region1, const void* region2, size_t n){
            const char* first = (const char*) region2;
            const char* last = ((const char*) region2) + n;
            char* result = (char*) region1;
            while (first != last) *result++ = *first++;
            return result;
}

2. Tạo Hàm tổng quát

Trong cách hàm tổng quát, dữ liệu được truyền vào 1 cách tổng quát thông qua địa chỉ và kích thước kiểu dữ liệu.Nếu như hàm yêu cầu 1 hàm khác để thực hiện 1 thao tác nào đấy(như so sánh 2 dữ liệu) thì dữ liệu thuật toán so sánh được truyền vào thông qua con trỏ hàm.

Ví dụ: hàm qsort() trong thư viện stdio.h yêu cầu truyền vào hàm so sánh 2 phần tử:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

(*compar)(const void *, const void*)) trong hàm ở trên chính là 1 con trỏ hàm !

1 hàm tổng quát được tạo ra bằng cách truyền các tham số cơ bản:

• void *bù: địa chỉ của phần tử đầu tiên của mảng
• int size: kích thước 1 phần tử trong mảng
• int total: số phần tử của mảng
• ….

 

Ví dụ 1 số hàm tổng quát :

• Tìm kiếm trên mảng:

int search( void* buf,
            int size,
            int l, int r,
            void * item,
            int (*compare)(void*, void*)) {
     if (r < l) return -1;
     i = (l + r)/2;
     res = compare( item, (char*)buf+(size*i) );
     if (res==0)    return i;
     else if (res < 0)   return search(buf, size, l, i-1, item, compare);
     else           return search(buf, size, i+1, r, item, compare);
 }

•  So sánh 2 phần tử:

int int_compare(void const* x, void const *y) {
 int m, n;
 m = *((int*)x);
 n = *((int*)y);
 if ( m == n ) return 0;
 return m > n ? 1: -1;
 }

3. Kiểu dữ liệu tổng quát

Tạo ra 1 kiểu dữ liệu tổng quát, nơi mà dữ liệu vừa có thể là số nguyên, số thực, kí tự thậm chí là bản ghi ? Thậm chí, kiểu dữ liệu tổng quát này phải thực sự hiệu quả để thực hiện các ADT như : linkedlist, queue, stack hay tree.
Kiểu hợp (Union) có thể là một cách hữu hiệu để thực thi một cấu trúc dữ liệu tổng quát:

 typedef union {
 int i;
 long l;
 float f;
 double d;
 void *v;
 char *s;
 char c;
 } Jval;

Kiểu jval trên có thể ứng dụng để lưu lại các dữ liệu khác nhau:

Jval a, b;
a.i = 5;
b.f = 3.14;

Để sử dụng đơn giản, 1 vài hàm khởi tạo được xây dựng:

• Jval new_jval_i(int);
• Jval new_jval_f(float);
• Jval new_jval_d(double);
• Jval new_jval_s(char *);

ví dụ về 1 vài cách cài đặt các hàm khởi tạo:

Jval new_jval_i(int i) { Jval j; j.i = i; return j; }
 Jval new_jval_l(long l) { Jval j; j.l = l; return j; }
 Jval new_jval_f(float f) { Jval j; j.f = f; return j; }
 Jval new_jval_d(double d) { Jval j; j.d = d; return j; }
 Jval new_jval_v(void *v) { Jval j; j.v = v; return j; }
 ....
 int jval_i(Jval j) { return j.i; }
 long jval_l(Jval j) { return j.l; }
 float jval_f(Jval j) { return j.f; }
 double jval_d(Jval j) { return j.d; }
 void *jval_v(Jval j) { return j.v; }
 ..
 

Luyện tập 1 chút: bạn đọc thử viết các hàm tổng quát ở phần 2 bằng cách sử dụng jval 😀