From 55a2212feb5042e65fbf0ed8891c0cab55479621 Mon Sep 17 00:00:00 2001 From: Guillermo Ramos Date: Sat, 24 Sep 2011 18:13:15 +0200 Subject: Renamed map ADT to kmap --- kmap/Makefile | 8 +++ kmap/kmap.c | 154 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ kmap/kmap.h | 41 +++++++++++++++ kmap/test_kmap.c | 66 ++++++++++++++++++++++++ 4 files changed, 269 insertions(+) create mode 100644 kmap/Makefile create mode 100644 kmap/kmap.c create mode 100644 kmap/kmap.h create mode 100644 kmap/test_kmap.c (limited to 'kmap') diff --git a/kmap/Makefile b/kmap/Makefile new file mode 100644 index 0000000..62aa5c8 --- /dev/null +++ b/kmap/Makefile @@ -0,0 +1,8 @@ +obj-m += test.o +test-objs := kmap.o test_kmap.o + +all: + make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules + +clean: + make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean diff --git a/kmap/kmap.c b/kmap/kmap.c new file mode 100644 index 0000000..2db6b82 --- /dev/null +++ b/kmap/kmap.c @@ -0,0 +1,154 @@ +/* + * kmap - (Linux) kernel map implementation + * + * Copyright (c) 2011 Guillermo Ramos <0xwille@gmail.com> + * + * This file is part of kmap + * + * kmap is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * kmap is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with kmap. If not, see . + */ + +#include +#include +#include +#include "kmap.h" + +/* + * Returns the node with the value passed, or NULL in case it does not exist + */ +static inline struct kmap *kmap_search(struct kmap *head, int value) +{ + struct list_head *list; + struct kmap *node; + + list_for_each(list, &head->l) { + node = list_entry(list, struct kmap, l); + if (node->value == value) + return node; + } + + return NULL; +} + +/* + * Prints in klog a representation of all the nodes in the map + */ +void kmap_display(struct kmap *head) +{ + struct kmap *node; + struct list_head *list; + + printk(KERN_ALERT "Displaying..."); + list_for_each(list, &head->l) { + node = list_entry(list, struct kmap, l); + printk(KERN_ALERT " %p: v=%d d=%s\n", + node, node->value, (char*)node->data); + } +} + +/* + * Creates and returns a new head node + */ +inline struct kmap *kmap_create(void) +{ + struct kmap *head; + + head = kmalloc(sizeof(struct kmap), GFP_KERNEL); + if (unlikely(!head)) + return NULL; + + INIT_LIST_HEAD(&head->l); + + return head; +} + +/* + * Deletes the map and frees the memory used by its nodes + */ +void kmap_destroy(struct kmap *head) +{ + struct kmap *node; + struct list_head *list = head->l.next; + + while (list != &head->l) { + node = list_entry(list, struct kmap, l); + list = list->next; + kfree(node); + } + + kfree(head); +} + +/* + * Creates a new node with the given value and data, and adds it to the map head + */ +int kmap_insert(struct kmap *head, int value, void *data) +{ + struct kmap *new; + + // Key already exists + if (kmap_search(head, value)) + return -EINVAL; + + new = kmap_create(); + if (unlikely(!new)) + return -ENOMEM; + + new->value = value; + new->data = data; + list_add_tail(&new->l, &head->l); + + return 0; +} + +/* + * Removes from the map the node with the given value. + */ +int kmap_delete(struct kmap *head, int value) +{ + struct kmap *node = kmap_search(head, value); + + if (node) { + list_del(&node->l); + kfree(node); + return 0; + } else { + return -EINVAL; + } +} + +/* + * Returns the data mapped to the given value, or NULL if that value has no data + * associated to it + */ +void *kmap_get(struct kmap *head, int value) +{ + struct kmap *node = kmap_search(head, value); + + if (node) + return node->data; + else + return NULL; +} + +/* + * Associates the given value with new data, if the value was already in the map + */ +void kmap_set(struct kmap *head, int value, void *data) +{ + struct kmap *node = kmap_search(head, value); + + if (node) + node->data = data; +} diff --git a/kmap/kmap.h b/kmap/kmap.h new file mode 100644 index 0000000..7d6e8ad --- /dev/null +++ b/kmap/kmap.h @@ -0,0 +1,41 @@ +/* + * kmap - (Linux) kernel map implementation + * + * Copyright (c) 2011 Guillermo Ramos <0xwille@gmail.com> + * + * This file is part of kmap + * + * kmap is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * kmap is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with kmap. If not, see . + */ + +#include + +#ifndef KHM +#define KHM + +struct kmap { + struct list_head l; + int value; + void *data; +}; + +struct kmap *kmap_create(void); +void kmap_destroy(struct kmap *head); +int kmap_insert(struct kmap *head, int value, void *data); +int kmap_delete(struct kmap *head, int value); +void *kmap_get(struct kmap *head, int value); +void kmap_set(struct kmap *head, int value, void *data); +void kmap_display(struct kmap *head); + +#endif // KHM diff --git a/kmap/test_kmap.c b/kmap/test_kmap.c new file mode 100644 index 0000000..577eeb5 --- /dev/null +++ b/kmap/test_kmap.c @@ -0,0 +1,66 @@ +#include +#include +#include "kmap.h" + +#define Z_ASD 1 +#define Z_QWE 2 +#define Z_BLR 3 + +static struct kmap *km; + +static int __init test_init(void) +{ + char *values; + + km = kmap_create(); + + if ((values = (char*)kmap_get(km, Z_BLR))) + printk(KERN_ALERT "ERROR: Z_BLR exists: %s\n", values); + else + printk(KERN_ALERT "Z_BLR does not exist (good)\n"); + + if (kmap_insert(km, Z_ASD, "ASDF")) + goto insert_err; + if (kmap_insert(km, Z_QWE, "QWERTY")) + goto insert_err; + if (kmap_insert(km, Z_BLR, "BLRBLRBLR")) + goto insert_err; + + kmap_display(km); + kmap_delete(km, Z_QWE); + kmap_display(km); + kmap_set(km, Z_ASD, "ASDF NEW!!"); + kmap_display(km); + + if ((values = (char*)kmap_get(km, Z_ASD))) + printk(KERN_ALERT "Z_ASD: %s\n", values); + else + printk(KERN_ALERT "Z_ASD does not exist\n"); + if ((values = (char*)kmap_get(km, Z_QWE))) + printk(KERN_ALERT "Z_QWE: %s\n", values); + else + printk(KERN_ALERT "Z_QWE does not exist\n"); + if ((values = (char*)kmap_get(km, Z_BLR))) + printk(KERN_ALERT "Z_BLR: %s\n", values); + else + printk(KERN_ALERT "Z_BLR does not exist\n"); + + if (kmap_insert(km, Z_ASD, "REPEATED!!")) + goto insert_err; + + return 0; + +insert_err: + printk(KERN_ALERT "Error inserting (good)\n"); + return 0; +} + +static void __exit test_exit(void) +{ + kmap_destroy(km); +} + +module_init(test_init); +module_exit(test_exit); + +MODULE_LICENSE("GPL"); -- cgit v1.2.3