בהמשך למסע ב Kernel החלטתי להתמקד בקצרה על רשימות מקושרות, למי שלא מכיר או שהספיק לשכוח מדובר על דרך לחבר בין אובייקטים בעזרת מצביעים לאובייקטים אחרים בזיכרון, לכל אובייקט יש מצביע לאובייקט שלפניו ומצביע לאובייקט שאחריו כפי שניתן לראות בתמונה:
שימו לב!
- עבודה מול ה Kernel עלולה להזיק למחשב שלך, מומלץ לעבוד על תחנה וירטואלית.
- המאמר נכתב על Fedora 14.
מערכת ההפעלה נותנת כלים פנימיים שעוזרים לנהל את הרשימות במקום שנהל בעצמנו, קובץ list.h חושף מספר פונקציות ו Macros כפי שניתן לראות בדוגמה:
myList.c
//define module
#include <linux/module.h>
//we are in the kerenl
#include <linux/kernel.h>
//linked list header
#include <linux/list.h>
//example struct to be linked
struct element {
int id;
char name[15];
char description[50];
//creating header, next and previous pointers
struct list_head list;
};
//the list!
struct element elementsList;
void addElements(void)
{
struct element *tmp;
int listMax = 20;
int i = 0;
for(i = 0; i < listMax; i++)
{
//getting memory for the struct
tmp = kmalloc(sizeof(*tmp),GFP_KERNEL);
tmp->id = i;
strcpy(tmp->name, "Element");
strcpy(tmp->description, "just simple element inside the list");
//initializes pointers
INIT_LIST_HEAD(&tmp->list);
//add the element at the end of the list
list_add_tail(&(tmp->list), &(elementsList.list));
}
printk(KERN_INFO "load complete\n");
}
void deleteElements(void)
{
struct element *tmp, *node;
//if deleting elements better using this function,
//it preserve the pointer to the next element,preventing holes inside the list.
list_for_each_entry_safe(node, tmp, &elementsList.list, list){
//remove from the list
list_del(&node->list);
//release the memory
kfree(node);
}
}
void viewElements(void)
{
struct element *tmp;
//running through all elements
list_for_each_entry(tmp, &elementsList.list, list) {
printk(KERN_INFO "Element\n ID: %d; Name: %s;
Description: %s\n", tmp->id, tmp->name, tmp->description);
}
}
int c_module() {
//initializes the list
INIT_LIST_HEAD(&elementsList.list);
printk(KERN_INFO "initialize list complete\n");
addElements();
viewElements();
return 0;
}
void r_module()
{
printk(KERN_INFO "delete list\n");
deleteElements();
printk(KERN_INFO "remove module complete\n");
}
module_init(c_module);
module_exit(r_module);
מגדירים מבנה עם אובייקט מיוחד מסוג list_head שמכיל בתוכו את המצביעים, מייצרים מופע כללי של המבנה שמייצג את ראש הרשימה, בשלב טעינת ה Module נטענת הפונקציה addElements שמכניסה 20 אובייקטים לרשימה, היא מאפסת את המצביעים ושולחת כל מבנה לפונקציה (list_add_tail) שמוסיפה אותו לסוף הרשימה.
לסיום רצה הפונקציה viewElements שמציגה את הרשימה בעזרת המאקרו list_for_each_entry שדרכו ניתן לעבור על האלמנטים, בהסרת ה Module רצה הפונקציה deleteElements שמפעילה את המאקרו list_for_each_entry_safe שדואג להסרה בטוחה של אובייקטים מבלי שהיו חורים ברשימה.
סיכום
מדובר בכלי חזק אבל קצת מסורבל שעלול לגרום לכאב ראש לא קטן אם ננסה לממש אותו בעצמנו, Linux חוסכת את כל ההתעסקות הכואבת במצביעים ונותנת תשתית נוחה לבניה ולניהול רשימות מקושרות.
מידע נוסף
רשמת?
