CEP/C/mod_list.c

   1 /*
   2  * mod_list: Implements linked list module for cep-browser.
   3  *
   4  * The mod_list should be used for basic tests because its
   5  * main operations (insert() and lookup()) are quite slow and
   6  * expansive.
   7  *
   8  * Licensed under the GPLv2 license.
   9  *
  10  * Luiz Fernando N. Capitulino
  11  * <lcapitulino@gmail.com>
  12  */
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <stdlib.h>
  16
  17 #include "misc.h"
  18 #include "module.h"
  19 #include "mod_list.h"
  20
  21 /* list node */
  22 struct node {
  23         void *data;
  24         struct node *next;
  25 };
  26
  27 /* list data */
  28 struct list {
  29         size_t size;
  30         struct node *head;
  31         struct node *tail;
  32         int (*compare)(const void *key1, const void *key2);
  33         void (*destroy)(void *data);
  34         void (*dump)(const void *data);
  35 };
  36
  37 static struct list cep_list;
  38
  39 static struct node *list_node_alloc(void *data, struct node *next)
  40 {
  41         struct node *new;
  42
  43         new = malloc(sizeof(*new));
  44         if (!new)
  45                 fatal("Could not allocate memory");
  46
  47         new->data = data;
  48         new->next = next;
  49
  50         return new;
  51 }
  52
  53 static void list_init(int (*compare)(const void *key1, const void *key2),
  54                       void (*destroy)(void *data),
  55                       void (*dump)(const void *data))
  56 {
  57         struct node *p;
  58
  59         p = list_node_alloc(NULL, NULL);
  60
  61         cep_list.head = cep_list.tail = p;
  62         cep_list.compare = compare;
  63         cep_list.destroy = destroy;
  64         cep_list.dump = dump;
  65         cep_list.size = 0;
  66 }
  67
  68 static void list_destroy(void)
  69 {
  70         struct node *p, *tmp;
  71
  72         /* free place holder */
  73         tmp = cep_list.head->next;
  74         free(cep_list.head);
  75
  76         for (p = tmp; p != NULL;) {
  77                 tmp = p->next;
  78
  79                 cep_list.destroy(p->data);
  80                 free(p);
  81
  82                 p = tmp;
  83         }
  84 }
  85
  86 static size_t list_size(void)
  87 {
  88         return cep_list.size;
  89 }
  90
  91 static void list_insert(void *data)
  92 {
  93         struct node *new;
  94
  95         /*
  96          * XXX: Accept duplicated entries
  97          *
  98          * Insertions would be considerably slower if we
  99          * call list_lookup() to catch duplicated
 100          * insertions.
 101          *
 102          * Instead, we just ignore duplicates and
 103          * inserts new nodes in the tail of the list.
 104          */
 105
 106         new = list_node_alloc(data, NULL);
 107
 108         cep_list.tail->next = new;
 109         cep_list.tail = new;
 110         cep_list.size++;
 111 }
 112
 113 static void list_dump(void)
 114 {
 115         struct node *p;
 116
 117         for (p = cep_list.head->next; p != NULL; p = p->next)
 118                 cep_list.dump(p->data);
 119 }
 120
 121 static void *list_lookup(const void *data)
 122 {
 123         int ret;
 124         struct node *p;
 125
 126         for (p = cep_list.head->next; p != NULL; p = p->next) {
 127                 ret = cep_list.compare(p->data, data);
 128                 if (ret == 0)
 129                         return p->data;
 130         }
 131
 132         return NULL;
 133 }
 134
 135 struct module list_module = {
 136         .mod_name    = "LIST",
 137         .mod_init    = list_init,
 138         .mod_destroy = list_destroy,
 139         .mod_insert  = list_insert,
 140         .mod_lookup  = list_lookup,
 141         .mod_dump    = list_dump,
 142         .mod_size    = list_size,
 143 };