net/ipv6/mobile_ip6/sortedlist.c

   1 /**
   2  * Sorted list - linked list with sortkey.
   3  *
   4  * Authors:
   5  * Jaakko Laine <medved@iki.fi>
   6  *
   7  * $Id: s.sortedlist.c 1.11 03/04/10 13:09:54+03:00 anttit@jon.mipl.mediapoli.com $
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version
  12  * 2 of the License, or (at your option) any later version.
  13  */
  14
  15 #include <linux/list.h>
  16 #include <linux/slab.h>
  17 #include <linux/spinlock.h>
  18 #include <linux/string.h>
  19 #include <net/ipv6.h>
  20 #include "config.h"
  21
  22 struct mipv6_sorted_list_entry {
  23         struct list_head list;
  24         void *data;
  25         int datalen;
  26         unsigned long sortkey;
  27 };
  28
  29 /**
  30  * compare - compares two arbitrary data items
  31  * @data1: first data item
  32  * @data2: second data item
  33  * @datalen: length of data items in bits
  34  *
  35  * datalen is in bits!
  36  */
  37 int mipv6_bitwise_compare(const void *data1, const void *data2, int datalen)
  38 {
  39         int n = datalen;
  40         __u8 * ptr1 = (__u8 *)data1;
  41         __u8 * ptr2 = (__u8 *)data2;
  42
  43         for (; n>=0; n-=8, ptr1++, ptr2++) {
  44                 if (n >= 8) {
  45                         if (*ptr1 != *ptr2)
  46                                 return 0;
  47                 } else {
  48                         if ((*ptr1 ^ *ptr2) & ((~0) << (8 - n)))
  49                                 return 0;
  50                 }
  51         }
  52
  53         return 1;
  54 }
  55
  56 /**
  57  * mipv6_slist_add - add an entry to sorted list
  58  * @head: list_head of the sorted list
  59  * @data: item to store
  60  * @datalen: length of data (in bytes)
  61  * @key: sortkey of item
  62  *
  63  * Allocates memory for entry and data
  64  */
  65 int mipv6_slist_add(struct list_head *head, void *data, int datalen,
  66                     unsigned long sortkey)
  67 {
  68         struct list_head *pos;
  69         struct mipv6_sorted_list_entry *entry, *tmp, *next;
  70
  71         entry = kmalloc(sizeof(struct mipv6_sorted_list_entry), GFP_ATOMIC);
  72
  73         if (!entry)
  74                 return -1;
  75
  76         entry->data = kmalloc(datalen, GFP_ATOMIC);
  77
  78         if (!entry->data) {
  79                 kfree(entry);
  80                 return -1;
  81         }
  82
  83         memcpy(entry->data, data, datalen);
  84         entry->datalen = datalen;
  85         entry->sortkey = sortkey;
  86
  87         if ((pos = head->next) == head) {
  88                 list_add(&entry->list, head);
  89                 return 0;
  90         }
  91
  92         tmp = list_entry(pos, struct mipv6_sorted_list_entry, list);
  93         if (entry->sortkey < tmp->sortkey) {
  94                 list_add(&entry->list, head);
  95                 return 0;
  96         }
  97
  98         for (; pos != head; pos = pos->next) {
  99                 tmp = list_entry(pos, struct mipv6_sorted_list_entry, list);
 100                 if (pos->next == head) {
 101                         list_add(&entry->list, &tmp->list);
 102                         return 0;
 103                 }
 104                 next = list_entry(pos->next, struct mipv6_sorted_list_entry, list);
 105                 if (entry->sortkey >= tmp->sortkey && entry->sortkey < next->sortkey) {
 106                         list_add(&entry->list, &tmp->list);
 107                         return 0;
 108                 }
 109         }
 110
 111         /* never reached */
 112         return -1;
 113 }
 114
 115 /**
 116  * mipv6_slist_get_first - get the first data item in the list
 117  * @head: list_head of the sorted list
 118  *
 119  * Returns the actual data item, not copy, so don't kfree it
 120  */
 121 void *mipv6_slist_get_first(struct list_head *head)
 122 {
 123         struct mipv6_sorted_list_entry *entry;
 124
 125         if (list_empty(head))
 126                 return NULL;
 127
 128         entry = list_entry(head->next, struct mipv6_sorted_list_entry, list);
 129         return entry->data;
 130 }
 131
 132 /**
 133  * mipv6_slist_del_first - delete (and get) the first item in list
 134  * @head: list_head of the sorted list
 135  *
 136  * Remember to kfree the item
 137  */
 138 void *mipv6_slist_del_first(struct list_head *head)
 139 {
 140         void *tmp;
 141         struct mipv6_sorted_list_entry *entry;
 142
 143         if (list_empty(head))
 144                 return NULL;
 145
 146         entry = list_entry(head->next, struct mipv6_sorted_list_entry, list);
 147         tmp = entry->data;
 148
 149         list_del(head->next);
 150         kfree(entry);
 151
 152         return tmp;
 153 }
 154
 155 /**
 156  * mipv6_slist_del_item - delete entry
 157  * @head: list_head of the sorted list
 158  * @data: item to delete
 159  * @compare: function used for comparing the data items
 160  *
 161  * compare function needs to have prototype
 162  * int (*compare)(const void *data1, const void *data2, int datalen)
 163  */
 164 int mipv6_slist_del_item(struct list_head *head, void *data,
 165                          int (*compare)(const void *data1, const void *data2,
 166                                         int datalen))
 167 {
 168         struct list_head *pos;
 169         struct mipv6_sorted_list_entry *entry;
 170
 171         for(pos = head->next; pos != head; pos = pos->next) {
 172                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 173                 if (compare(data, entry->data, entry->datalen)) {
 174                         list_del(pos);
 175                         kfree(entry->data);
 176                         kfree(entry);
 177                         return 0;
 178                 }
 179         }
 180
 181         return -1;
 182 }
 183
 184 /**
 185  * mipv6_slist_get_first_key - get sortkey of the first item
 186  * @head: list_head of the sorted list
 187  */
 188 unsigned long mipv6_slist_get_first_key(struct list_head *head)
 189 {
 190         struct mipv6_sorted_list_entry *entry;
 191
 192         if (list_empty(head))
 193                 return 0;
 194
 195         entry = list_entry(head->next, struct mipv6_sorted_list_entry, list);
 196         return entry->sortkey;
 197 }
 198
 199 /**
 200  * mipv6_slist_get_key - get sortkey of the data item
 201  * @head: list_head of the sorted list
 202  * @data: the item to search for
 203  * @compare: function used for comparing the data items
 204  *
 205  * compare function needs to have prototype
 206  * int (*compare)(const void *data1, const void *data2, int datalen)
 207  */
 208 unsigned long mipv6_slist_get_key(struct list_head *head, void *data,
 209                                   int (*compare)(const void *data1,
 210                                                  const void *data2,
 211                                                  int datalen))
 212 {
 213         struct list_head *pos;
 214         struct mipv6_sorted_list_entry *entry;
 215
 216         for(pos = head->next; pos != head; pos = pos->next) {
 217                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 218                 if (compare(data, entry->data, entry->datalen))
 219                         return entry->sortkey;
 220         }
 221
 222         return 0;
 223 }
 224
 225 /**
 226  * mipv6_slist_get_data - get the data item identified by sortkey
 227  * @head: list_head of the sorted list
 228  * @key: sortkey of the item
 229  *
 230  * Returns the actual data item, not copy, so don't kfree it
 231  */
 232 void *mipv6_slist_get_data(struct list_head *head, unsigned long sortkey)
 233 {
 234         struct list_head *pos;
 235         struct mipv6_sorted_list_entry *entry;
 236
 237         list_for_each(pos, head) {
 238                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 239                 if (entry->sortkey == sortkey)
 240                         return entry->data;
 241         }
 242
 243         return NULL;
 244 }
 245
 246 /**
 247  * reorder_entry - move an entry to a new position according to sortkey
 248  * @head: list_head of the sorted list
 249  * @entry_pos: current place of the entry
 250  * @key: new sortkey
 251  */
 252 static void reorder_entry(struct list_head *head, struct list_head *entry_pos,
 253                           unsigned long sortkey)
 254 {
 255         struct list_head *pos;
 256         struct mipv6_sorted_list_entry *entry;
 257
 258         list_del(entry_pos);
 259
 260         for (pos = head->next; pos != head; pos = pos->next) {
 261                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 262                 if (sortkey >= entry->sortkey) {
 263                         list_add(entry_pos, &entry->list);
 264                         return;
 265                 }
 266         }
 267
 268         list_add(entry_pos, head);
 269 }
 270
 271 /**
 272  * mipv6_slist_modify - modify data item
 273  * @head: list_head of the sorted list
 274  * @data: item, whose sortkey is to be modified
 275  * @datalen: datalen in bytes
 276  * @new_key: new sortkey
 277  * @compare: function used for comparing the data items
 278  *
 279  * Compies the new data on top of the old one, if compare function returns
 280  * true. If there's no matching entry, new one will be created.
 281  * Compare function needs to have prototype
 282  * int (*compare)(const void *data1, const void *data2, int datalen)
 283  */
 284 int mipv6_slist_modify(struct list_head *head, void *data, int datalen,
 285                        unsigned long new_key,
 286                        int (*compare)(const void *data1, const void *data2,
 287                                       int datalen))
 288 {
 289         struct list_head *pos;
 290         struct mipv6_sorted_list_entry *entry;
 291
 292         for (pos = head->next; pos != head; pos = pos->next) {
 293                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 294                 if (compare(data, entry->data, datalen)) {
 295                         memcpy(entry->data, data, datalen);
 296                         entry->sortkey = new_key;
 297                         reorder_entry(head, &entry->list, new_key);
 298                         return 0;
 299                 }
 300         }
 301
 302         return mipv6_slist_add(head, data, datalen, new_key);
 303 }
 304
 305 /**
 306  * mipv6_slist_push_first - move the first entry to place indicated by new_key
 307  * @head: list_head of the sorted list
 308  * @new_key: new sortkey
 309  */
 310 int mipv6_slist_push_first(struct list_head *head, unsigned long new_key)
 311 {
 312         struct mipv6_sorted_list_entry *entry;
 313
 314         if (list_empty(head))
 315                 return -1;
 316
 317         entry = list_entry(head->next, struct mipv6_sorted_list_entry, list);
 318         entry->sortkey = new_key;
 319
 320         reorder_entry(head, head->next, new_key);
 321         return 0;
 322 }
 323
 324 /**
 325  * mipv6_slist_for_each - apply func to every item in list
 326  * @head: list_head of the sorted list
 327  * @args: args to pass to func
 328  * @func: function to use
 329  *
 330  * function must be of type
 331  * int (*func)(void *data, void *args, unsigned long sortkey)
 332  * List iteration will stop once func has been applied to every item
 333  * or when func returns true
 334  */
 335 int mipv6_slist_for_each(struct list_head *head, void *args,
 336                          int (*func)(void *data, void *args,
 337                                      unsigned long sortkey))
 338 {
 339         struct list_head *pos;
 340         struct mipv6_sorted_list_entry *entry;
 341
 342         list_for_each(pos, head) {
 343                 entry = list_entry(pos, struct mipv6_sorted_list_entry, list);
 344                 if (func(entry->data, args, entry->sortkey))
 345                         break;
 346         }
 347
 348         return 0;
 349 }
 350
 351 EXPORT_SYMBOL(mipv6_slist_for_each);
 352 EXPORT_SYMBOL(mipv6_slist_modify);
 353 EXPORT_SYMBOL(mipv6_slist_get_first_key);
 354 EXPORT_SYMBOL(mipv6_slist_add);
 355