Lấy từ tài liệu tuyệt vời này về linked list của trường Stanford mà tôi muốn khái lược lại bằng những đoạn mã trong đó. Danh sách liên kết (linked list) là một kiến thức rất cơ bản của cấu trúc dữ liệu và giải thuật. Hiểu được những ưu và khuyết điểm của nó sẽ giúp chúng ta hiểu các vấn đề về thời gian, không gian bộ nhớ và cấu trúc dữ liệu nói chung. Hơn thế nữa học về linked list là một cách rất tốt để hiểu về pointer. Những bài toán về linked list là sự kết hợp rất “đẹp” giữa giải thuật (algorithms) và các phép toán với con trỏ (pointer manipulation). Linked list là cách các lập trình viên luyện tập để thực sự hiểu về pointer và bạn sẽ thấy ngôn ngữ C “đẹp” vô cùng Hãy tham khảo thêm tài liệu của Stanford để hiểu kỹ thêm (Highly recommend!)

(more…)

StringTokenizer là một class thường được viết trong các dự án. Đó là một class dùng để xử lý chuỗi, chia tách chuỗi thành các chuỗi con (token) được phân cách bởi các ký tự định nghĩa trước (delimiter). Ví dụ:

“Hoang Tran:1982:Hanoi University of Technology” được phân cách bởi ký tự “:” để thu được thông tin tương ứng về tên, năm sinh và trường học.

Có rất nhiều cách thể hiện lớp StringTokenizer này ở các ngôn ngữ khác nhau (Java thì đã có trong JDK của nó rồi) Bạn có thể google để tìm tham khảo các cách viết đó. Dựa trên ý tưởng của java, chúng ta sẽ xây dựng một lớp StringTokenizer hữu dụng trong C++.

Trong nhiều cách viết lớp này ở trên mạng thì mình cũng nhận ra rằng cách viết ở dự án cũ là tối ưu, hay và dễ hiểu nhất Sử dụng deque làm storage data cho lớp StringTokenizer sẽ làm cho quá trình insert cũng như delete các beginning và end của container rất nhanh.

Đây là lớp StringTokenizer đã được thêm bớt chút ít sau khi đi chôm

(more…)

Nguồn: http://www.enderunix.org/docs/eng/daemon.php
Bài viết này bổ xung một số vấn đề chưa được trình bày trong bài viết “Viết daemon trên Linux (1)” của anh Hoàng.

1- Logging
Chúng ta có thể lựa chọn một trong hai cách ghi log như sau:
- Tự viết hàm ghi log:
Một hàm ghi log có dạng như sau:

void log_message( const char *fname, const char *msg )
{
  FILE *logfile = fopen( fname, “a” );
 
  if( ! logfile )
    return;
 
  fprintf( logfile, “%s\n”, msg );
 
  fclose( logfile );
 
}

- Dùng các hàm có sẵn trong thư viện: Standard C library có các hàm syslog(), openlog(), closelog() phục vụ việc ghi log.

2- Cơ chế loại trừ lẫn nhau
Tại một thời điểm thường chỉ có một thực thể của daemon đang chạy. Một thực thể của daemon sẽ cố gắng khóa một file (lock file). Nếu khóa thành công nghĩa là chưa có thực thể nào khác của daemon đó đang chạy. Khi đó, pid của thực thể sẽ được ghi vào lock file. Chúng ta sử dụng hàm chuẩn lockf() như sau:

lfp = open( "exampled.lock", O_RDWR | O_CREAT, 0640 );
 
if ( lfp < 0 ) /* không mở được lock file */
  exit( EXIT_FAILURE );
 
if ( lockf( lfp, F_TLOCK, 0 ) < 0 ) 
  /* không khóa được lock file, một thực thể khác đang chạy  */
  exit( EXIT_SUCCESS );
 
/* chưa có thực thể nào đang chạy, ghi pid vào lock file */
sprintf( str,"%d\n", getpid() );
write( lfp, str, strlen(str) );

3- Bắt các tín hiệu gửi đến
Sau các bước chuẩn bị nói trên, một daemon sẽ bắt đầu lắng nghe tín hiệu gửi đến từ người dùng hoặc từ các tiến trình khác. Chúng ta viết một hàm xử lí tín hiệu, sau đó gán hàm đó với các tín hiệu cụ thể nhờ hàm chuẩn signal(): (more…)

Hôm trước nhân lúc nhàn rỗi mình có giúp một “đồng nghiệp” viết một script nhỏ bằng ZShell phục vụ cho việc testing. Do công việc hàng ngày chỉ là viết các script đơn giản nên mình đã khá lúng túng trước yêu cầu phải lấy ra được một xâu con (substring) từ một xâu khác. Lên Google search thì thấy cũng có khá nhiều người gặp khó khăn trước vấn đề này và hóa ra xử lí xâu trong shell cũng là một vấn đề khá thú vị. Bài viết này tổng kết những phương pháp để lấy substring trong shell mà tác giả lượm lặt trên mạng. Chú ý rằng những phương pháp này có thể không áp dụng được với một số loại shell nhất định.

Những kĩ thuật dưới đây được áp dụng để giải quyết bài toán cụ thể là lấy ra xâu “substring” từ xâu “this is a substring test”. Bài toán này có ý nghĩa trong trường hợp substring là một biến có thể nhận nhiều giá trị khác nhau.

1- Sử dụng cú pháp substring=${string:starting_position:length}

string=”this is a substring test”
substring=${string:10:9}
echo $substring

substring

Chú ý rằng vị trí đầu tiên trong một xâu là 0. Nhược điểm của cách này là chỉ áp dụng khi xâu con cần lấy ra có độ dài cố định. Hơn nữa cách này không áp dụng được cho zshell, một loại shell được dùng phổ biến trên các hệ thống UNIX.

2- Sử dụng lệnh cut
Lệnh cut dùng để lấy ra một số kí tự trong một xâu. Dùng man cut để xem chi tiết về lệnh này. Trong bài toán cụ thể của chúng ta, trong xâu string thì xâu con “substring” bắt đầu từ vị trí 11 và kết thúc ở vị trí thứ 19. Bởi vậy có thể dùng lệnh sau đây để cắt ra “substring”

string=”this is a substring test”
echo $string | cut –c11-19

substring

Nhược điểm của cách làm này là chỉ áp dụng với xâu con có độ dài cố định. Chúng ta có thể sử dụng lệnh cut với các tham số sau đây đề khắc phục nhược điểm đó

string=”this is a substring test”
echo $string | cut –d’ ‘ –f4

substring

Lệnh trên lấy ra trường thứ 4 (f = field) của xâu string, mỗi trường cách nhau bởi kí tự space (d=delimeter).

3- Sử dụng các toán tử #, ##, % và %%

Toán tử # nghĩa là xóa bắt đầu từ bên trái xâu đầu tiên thỏa mãn mẫu (pattern) theo sau dấu #

(more…)

Phần này sẽ khái lược rất nhanh một vài điểm về các quy tắc sử dụng con trỏ. Để tham khảo toàn diện về con trỏ và bộ nhớ hãy xem tài liệu Pointers and Memory http://cslibrary.stanford.edu/102/).

- Pointer/Pointee: Một con trỏ “pointer” sẽ lưu một reference đến một biến khác được biết như là pointee của nó. Con trỏ có thể được thiết lập giá trị NULL có nghĩa là nó refer đến một pointee nào. (Trong C và C++, giá trị NULL có thể được sử dụng như là giá trị boolean false).

- Dereference: Toán tử dereference trên con trỏ cho phép truy nhập vào pointee của nó. Một pointer chỉ có thể bị dereference sau khi nó được thiết lập trỏ đến một pointee cụ thể. Một pointer mà không có pointee thì là bad pointer và không thể bị dereference.

- Bad pointer: Một pointer mà không được trỏ vào một pointee thì là “bad” và không thể dereference. Trong C và C++, việc dereference một bad pointer đôi khi gây xung đột ngay lập tức và làm hỏng bộ nhớ của chương trình đang chạy, gây nên “không biết đường nào mà lần”. Kiểu lỗi này rất khó để theo dõi. Trong C và C++, tất cả các pointer bắt đầu bằng bad values (những giá trị ngẫu nhiên), do đó rất dễ tình cờ sử dụng bad pointer. Những đoạn mã đúng sẽ thiết lập mỗi pointer có một good value trước khi sử dụng chúng. Chính vì vậy sử dụng bad pointer là một lỗi rất phổ biến trong C/C++. Với Java và các ngôn ngữ khác, các pointers được tự động bắt đầu với giá trị NULL, do đó quá trình dereference sẽ được dễ dàng detect nên các chương trình Java dễ gỡ lỗi này hơn nhiều.

- Pointer assignment: Một phép gán giữa hai con trỏ như p = q; sẽ làm cho hai pointer trỏ vào cùng một pointee. Nó sẽ không copy vùng nhớ của pointee. Sau phép gán thì cả hai pointer sẽ chỉ vào cùng một vùng nhớ của pointee.

- malloc(): malloc() là một hàm hệ thống mà cấp pháp một vùng nhớ trong “heap” và trả về con trỏ tới vùng nhớ mới đó. Prototype của malloc() và các hàm khác ở trong stdlib.h. Tham số của malloc() là một số nguyên là kích thước của vùng nhớ cần cấp phát tính theo bytes. Không giống như các biến cục bộ (“stack”), vùng nhớ heap không tự động giải phóng khi hàm tạo thoát ra. malloc() sẽ trả về NULL nếu nó không thế đáp ứng được yêu cầu cấp phát. Bạn nên kiểm tra trường hợp NULL với assert() nếu bạn mong nó an toàn. Hầu hết các hệ điều hành tiên tiến sẽ ném ra một exception hoặc làm việc bắt lỗi tự động trong việc cấp phát bộ nhớ của chúng, do đó không nhất thiết là trong đoạn mã của bạn phải kiểm tra việc cấp phát bộ nhớ thất bại.

- free(): free() thì ngược với malloc(). Gọi hàm free() trên vùng nhớ trên heap để chỉ ra rằng hệ thống đã thực hiện xong và giải phóng vùng nhớ đó. Tham số của free là một con trỏ tới vùng nhớ trên heap – con trỏ mà chúng ta đã có được thông qua lời gọi tới hàm malloc().

1. Daemon là gì?

Một daemon (hay service) là một background process được thiết kế để chạy độc lập, rất ít hoặc không có sự can thiệp của user. Daemon http của Apache web server là một ví dụ về daemon. Nó chạy ở dưới background, lắng nghe một số port xác định và cung cấp các pages hoặc processes scripts dựa vào kiểu request của user.

Để tạo một daemon trong Linux, chúng ta cần phải thực hiện một số bước theo thứ tự. Hiểu sâu bên trong cách một daemon hoạt động còn giúp chúng ta hiểu các hàm system call của kernel của Linux. Thực tế thì trong kernel module, có nhiều daemon quản lý các hardware device như là các mạch điều khiển ngoài, printer và PDAs. Chúng là một trong những khối cơ bản trên Linux mà nó cung cấp sự mềm dẻo và sức mạnh tuyệt vời.

Thông qua tài liệu này, chúng ta sẽ thể hiện một daemon rất đơn giản được viết bằng C. Như bạn có thể theo dõi từng bước, các đoạn mã sẽ được thêm vào chỉ ra thứ tự thực hiện các bước để thiết lập daemon và chạy nó.

2. Khởi đầu

Đầu tiên, bạn cần phải có những package sau được cài đặt trên Linux để phát triển các daemons:

- GCC 3.2.2 or higher

- Linux Development headers and libraries

Nếu hệ thống của bạn không có những package này bạn cần cài đặt nó. Để tìm version mà GCC bạn đang cài đặt, sử dụng lệnh:

gcc –-version

3. Thiết kế

3.1 Nó sẽ làm gì?

Một daemon sẽ làm một việc nào đó và cần làm nó tốt. Nó có thể phức tạp như phải quản lý hàng trăm mailbox với rất nhiều domains, hoặc là đơn giản như việc viết một report và gọi sendmail để gửi report đó đi.

Trong bất kỳ trường hợp nào, bạn cần phải lên kế hoạch xem daemon sẽ làm gì. Nếu nó cần tương tác với các daemon khác (có thể bạn chưa viết) thì đó sẽ là điều cần xem xét.

3.2 Tương tác như thế nào

Daemon không nên trao đổi trực tiếp với user thông qua terminal. Thực tế, một daemon hoàn toàn không nên tương tác trực tiếp với user. Tất cả sự trao đổi nên thông qua một dạng giạo diện mà nó có thể phức tạp như một GTK+ GUI hay đơn giản như là một tập các tín hiệu.

4. Cấu trúc cơ bản của daemon

Khi một daemon khởi động, nó phải thực hiện một vài công việc ở mức thấp (low-level) để sẵn sàng thực hiện các công việc thực sự. Nó sẽ cần thực hiện các bước sau:

(more…)

Một bài viết nhỏ để warm-up cái blog sau những ngày đông giá lạnh

Nguồn: http://www.gotw.ca/gotw/001.htm

Câu hỏi: Cho biết sự khác nhau của những dòng khởi tạo biến sau đây

SomeType t;
SomeType t();
SomeType t( u );
SomeType t = u;

Trả lời:

SomeType t;

Biến t được khởi tạo bởi default constructor SomeType::SomeType()

SomeType t();

Một dòng lệnh dễ gây nhầm lẫn! Thực ra đây là dòng khai báo một HÀM không có tham số và trả về một giá trị kiểu SomeType.

SomeType t( u );

Đây là dòng lệnh khởi tạo biến trực tiếp (direct initialization). Biến t được khởi tạo nhờ constructor SomeType::SomeType( u );

SomeType t = u;

Nhiều người nhầm lẫn rằng lệnh này gọi đến toán tử gán (assignment operator). Thực ra đây là một khởi tạo sao chép, trong đó t được khởi tạo nhờ copy constructor của lớp SomeType. Nếu u không thuộc kiểu SomeType thì constructor SomeType::SomeType( u ) sẽ được gọi để tạo ra một đối tượng tạm thời kiểu SomeType từ u, sau đó đối tượng này sẽ được sao chép sang t bởi copy constructor.

(more…)

Phần 2: Chương trình hiển thị nội dung file theo từng trang màn hình

1. Đặt vấn đề

Khi xem nội dung một file dài, chúng ta thường muốn nội dung file đó được hiển thị lần lượt theo từng trang màn hình. Hai lệnh phổ biến để xem nội dung file là cat và more không đáp ứng được nhu cầu này (chúng không có khả năng này, hoặc có nhưng không tiện dụng, “tác giả” cũng không biết rõ về tất cả các khả năng của hai lệnh này). Bởi vậy, chúng ta sẽ phát triển một chương trình tên là p làm nhiệm vụ in ra nội dung một file theo từng trang màn hình (screenful-at-a-time). Chương trình sẽ đợi người dùng ấn một phím để chuyển sang hiển thị trang tiếp theo. Giống như vis, p nhận dữ liệu vào từ cả file lẫn standard input. Ví dụ:

p nhận dữ liệu vào từ file

$ p vis.c

p nhận dữ liệu vào từ standard input

$ grep  ‘#define’  *.[ch]  |  p

Ở phiên bản đầu tiên, p sẽ hiển thị nội dung file theo từng khối, mỗi khối 22 dòng (phần lớn các terminal gồm 24 dòng văn bản). Một cách đơn giản để nhắc người dùng ấn một phím để tiếp tục là không in ra kí tự new line nằm cuối dòng thứ 22. Khi đó, con trỏ sẽ nằm ở cuối dòng thứ 22 thay vì đầu dòng thứ 23. Khi người dùng ấn phím enter, kí tự new line còn thiếu của dòng 22 sẽ được thêm vào, nhờ đó dòng tiếp theo (dòng 23) sẽ được in ra ở đúng vị trí của nó. Nếu người dùng ấn ctrl-d hay q thay vì enter, p sẽ kết thúc. Chúng ta sẽ không quan tâm đến các dòng quá dài. Ngoài ra, khi hiển thị nhiều file cùng lúc thì nội dung các file sẽ được in ra liên tục mà không có sự phân cách gì cả. Tức là, đầu ra của hai lệnh sau đây là như nhau

$ p file1 file2 …

và

$ cat file1 file2 …  |  p

Chú ý rằng lệnh cat in ra nội dung các file một cách liên tục mà không có sự phân cách gì cả. Nếu muốn nội dung các file được phân cách bởi tên file, chúng ta có thể dùng vòng lặp sau đây (ôn lại lập trình shell luôn :-D)

$ for i in filenames
> do
>      echo $i:
>      cat $i
> done  |  p

Có rất nhiều tính năng có thể được đưa vào chương trình p. Quan điểm của chúng ta là: Trước hết tạo ra một phiên bản đơn giản, sau đó dần dần thêm vào các tính năng phức tạp hơn khi cần thiết. Những tính năng được thêm vào phải là những cái mà người dùng thực sự muốn, chứ không phải những cái mà chúng ta nghĩ rằng họ muốn.

2. Phiên bản đầu tiên của p

Cấu trúc của p cũng tương tự như vis: Hàm main duyệt qua các file đầu vào và gọi một hàm tên là print để xử lí từng file. Dưới đây là hàm main

(more…)

Lời tựa

Dạo này đang thời kì nông nhàn nên quay lại với blog. Gần một tháng nay không có bài viết mới nào, có lẽ do các blogger đều đang bận bịu với những kế hoạch riêng của mình. Dạo này không thích những thứ loằng ngoằng phức tạp nữa, cũng chả thích mình là guru nữa, đau đầu lắm :-D. Bây giờ chỉ thích những thứ đơn giản nhưng đẹp đẽ. Ngẫm ra làm phần mềm cũng chẳng cần đến những thứ cao siêu hay phức tạp, vấn đề chỉ là kết hợp những thứ thật đơn giản thành một hệ thống lớn làm việc được mà thôi.

Đấy là lí do mà dạo này “tác giả” quay sang đọc cuốn “The Unix programming environment” của Brian W.Kernighan và Rob Pike. Công nhận hai bác này viết sách cực hay. Cuốn sách không chỉ trình bày các công cụ hay ngôn ngữ mà quan trọng hơn là nêu bật lên được triết lí của Unix: Viết các chương trình đơn giản, mỗi chương trình chỉ làm một nhiệm vụ nhưng có khả năng tương tác tốt với nhau để thực hiện những nhiệm vụ phức tạp hơn.

“Tác giả” bài viết này, trong thời gian tạm thời chưa bị phân tâm bởi việc fix bug nhàm chán thường nhật, muốn trích ra đây một số phần của cuốn sách, vừa để giải trí, vừa để ôn lại C và Unix, cũng vừa là để học tập tư duy lập trình trên Unix. Đồng thời, việc làm này cũng khôi phục lại phần nào tình cảm của “tác giả” đối với công việc lập trình, vốn đã bị phai nhạt khá nhiều sau một thời gian làm việc trong một dự án chán ngắt và không hề thể hiện được một chút gì gọi là “vẻ đẹp” của lập trình Unix.

Tác giả cũng khuyến cáo các độc giả (nếu có :-D) nên tìm đọc bản tiếng Anh của cuốn sách (tác giả cũng không có bản mềm, chỉ có bản cứng), bởi trình độ kĩ thuật và tiếng Anh của tác giả đều chỉ ở mức sơ cấp.

Loạt bài viết này trích ra từ các chương 6, 7, 8, 9 của cuốn “The Unix programming environment”. Các chương này trình bày quá trình phát triển một số chương trình đơn giản, qua đó làm nổi bật lên các kĩ thuật và các triết lí lập trình trên Unix. Các chương trình này, theo tác giả cuốn sách, đều là các chương trình nhỏ và không có mặt trong 7th Edition của Unix. Nếu hệ điều hành hiện thời của bạn cũng không có chúng, bạn sẽ thấy chúng rất có ích. Trong trường hợp ngược lại, việc so sánh thiết kế của những chương trình sẵn có với những chương trình trong sách cũng mang lại nhiều điều bổ ích.

Chúng ta cùng bắt đầu với các chương trình nhập xuất dữ liệu (I/O).

Phần 1 Chương trình in ra các kí tự đặc biệt: VIS

1. Standard input and output: vis

Rất nhiều chương trình đọc dữ liệu từ một đầu vào và ghi dữ liệu ra một đầu ra. Khi đó việc sử dụng các thao tác vào ra (I/O) đối với đầu vào chuẩn (standard input) và đầu ra chuẩn (standard output) là đủ đáp ứng yêu cầu của chương trình.
Chúng ta hãy bắt đầu xây dựng một chương trình đơn giản tên là vis (viết tắt của visible). vis sao chép dữ liệu từ standard input sang standard output, đồng thời hiển thị tất cả các kí tự vốn không thể in được (non-printing character) dưới dạng \nnn, trong đó nnn là giá trị octal của kí tự đó. Ví dụ: Chúng ta chuẩn bị file đầu vào x như sau:

$ cat x
abc<ctrl-a>
def<ctrl-b>
<ctrl-d>

Sử dụng vis để hiện thị x, kí tự ctrl-a sẽ được hiển thị là \001, kí tự ctrl-b sẽ được hiển thị là \002.

$ vis x
abc\001
def\002

Chương trình vis sẽ có ích trong việc phát hiện các kí tự lạ được ghi vào file vì một lí do nào đó. Chú ý rằng phiên bản đầu tiên của vis sẽ chỉ nhận dữ liệu vào từ standard input chứ chưa có khả năng đọc file. Khi cần in ra nội dung của nhiều file, chúng ta có thể nhờ đến lệnh cat như sau:

$ cat file1 file2 file3 … | vis

Chương trình vis của chúng ta sẽ có chức năng giống với lệnh sed sau đây:

$ sed –n l x
abc\01
def\02

Tuy nhiên trong một số trường hợp sed chỉ làm việc được với các file văn bản (text), bởi vậy việc viết mới chương trình vis vẫn là cần thiết.

Trong phiên bản đầu tiên của vis, chúng ta sử dụng hai hàm getchar và putchar. Hàm getchar đọc vào kí tự tiếp theo từ standard input (mặc định là terminal, cũng có thể là một file hay một pipeline, các chương trình không biết điều đó). Hàm putchar ghi một kí tự ra standard output, mặc định cũng là terminal.

Dưới đây là phiên bản đầu tiên của vis

(more…)

Nguồn: Tổng hợp từ cuốn sách “The Unix Programming Environment” của Brian W. Kernighan và Rob Pike.

Bài viết này giới thiệu những chức năng cơ bản nhất của sed, một chương trình xử lí văn bản cực mạnh trong Unix. Bài viết có sử dụng (mà không giải thích chi tiết) một số regular expression (cơ bản) và một số lệnh Unix (cũng cơ bản )

Cú pháp chung của sed

Cú pháp chung của một lệnh sed là

sed 'danh sách các lệnh'  'danh sách các file đầu vào'

sed sẽ đọc từng dòng của các file đầu vào và thực hiện từng lệnh trong danh sách các lệnh đối với các dòng đó. Sau đó, sed ghi dữ liệu ra vào thiết bị đầu ra chuẩn.

Chẳng hạn, chúng ta có thể thay tất cả các từ UNIX trong một file thành UNIX(TM) bằng câu lệnh sau:

sed 's/UNIX/UNIX(TM)/g' filename

Khi thực hiện lệnh này, sed sẽ:

- Đọc vào từng dòng của filename

- Đối với mỗi dòng đọc vào, sed sẽ thực hiện lệnh s/UNIX/UNIX(TM)/g, tức là thay thế (s = substitute) tất cả (g = global) các từ UNIX bởi UNIX(TM).

s (substitute) là một lệnh của ed, chương trình tiền thân của sed.

Chú ý: sed không thay đổi nội dung của file đầu vào.

Chúng ta luôn sử dụng dấu nháy đơn (single quote) để bao quanh các lệnh của sed nhằm tránh trường hợp các kí tự đặc biệt bị dịch thành ý nghĩa khác bởi shell.

Sau đây là 1 số lệnh sed thú vị!!!

(more…)