Author: marek Date: 2010-01-10 02:37:27 +0100 (Sun, 10 Jan 2010) New Revision: 1545
Added: branches/batctl-0.2.x/hash.c branches/batctl-0.2.x/hash.h branches/batctl-0.2.x/list-batman.c branches/batctl-0.2.x/list-batman.h branches/batctl-0.2.x/packet.h Log: batctl: adding the real files
Since this maintenance branch has its own new location within the repository the links to other source code files are broken. We don't expect much development in this branch, so that the links can be replaced by copies of the real files.
Added: branches/batctl-0.2.x/hash.c =================================================================== --- branches/batctl-0.2.x/hash.c (rev 0) +++ branches/batctl-0.2.x/hash.c 2010-01-10 01:37:27 UTC (rev 1545) @@ -0,0 +1,319 @@ +/* + * Copyright (C) 2006-2009 B.A.T.M.A.N. contributors: + * + * Simon Wunderlich, Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + +#include <stdio.h> /* NULL */ +#include "hash.h" +#include "allocate.h" + + +/* clears the hash */ +void hash_init(struct hashtable_t *hash) +{ + int i; + + hash->elements = 0; + + for (i = 0; i < hash->size; i++) + hash->table[i] = NULL; +} + +/* remove the hash structure. if hashdata_free_cb != NULL, + * this function will be called to remove the elements inside of the hash. + * if you don't remove the elements, memory might be leaked. */ +void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb) +{ + struct element_t *bucket, *last_bucket; + int i; + + for (i = 0; i < hash->size; i++) { + + bucket = hash->table[i]; + while (bucket != NULL) { + + if (free_cb != NULL) + free_cb(bucket->data); + + last_bucket = bucket; + bucket = bucket->next; + debugFree(last_bucket, 1301); + + } + + } + + hash_destroy(hash); +} + +/* free only the hashtable and the hash itself. */ +void hash_destroy(struct hashtable_t *hash) +{ + debugFree(hash->table, 1302); + debugFree(hash, 1303); +} + +/* iterate though the hash. first element is selected with iter_in NULL. + * use the returned iterator to access the elements until hash_it_t returns NULL. */ +struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in) +{ + struct hash_it_t *iter; + + if (iter_in == NULL) { + iter = debugMalloc(sizeof(struct hash_it_t), 301); + iter->index = -1; + iter->bucket = NULL; + iter->prev_bucket = NULL; + } else + iter= iter_in; + + /* sanity checks first (if our bucket got deleted in the last iteration): */ + if (iter->bucket != NULL) { + if (iter->first_bucket != NULL) { + + /* we're on the first element and it got removed after the last iteration. */ + if ((*iter->first_bucket) != iter->bucket) { + + /* there are still other elements in the list */ + if ((*iter->first_bucket) != NULL) { + iter->prev_bucket = NULL; + iter->bucket = (*iter->first_bucket); + iter->first_bucket = &hash->table[iter->index]; + return iter; + } else { + iter->bucket = NULL; + } + + } + + } else if (iter->prev_bucket != NULL) { + + /* we're not on the first element, and the bucket got removed after the last iteration. + * the last bucket's next pointer is not pointing to our actual bucket anymore. + * select the next. */ + if (iter->prev_bucket->next != iter->bucket) + iter->bucket = iter->prev_bucket; + + } + + } + + /* now as we are sane, select the next one if there is some */ + if (iter->bucket != NULL) { + if (iter->bucket->next != NULL) { + iter->prev_bucket = iter->bucket; + iter->bucket = iter->bucket->next; + iter->first_bucket = NULL; + return iter; + } + } + /* if not returned yet, we've reached the last one on the index and have to search forward */ + + iter->index++; + /* go through the entries of the hash table */ + while (iter->index < hash->size) { + + if ((hash->table[iter->index]) == NULL) { + iter->index++; + continue; + } + + iter->prev_bucket = NULL; + iter->bucket = hash->table[iter->index]; + iter->first_bucket = &hash->table[iter->index]; + return iter; /* if this table entry is not null, return it */ + } + + /* nothing to iterate over anymore */ + debugFree(iter, 1304); + return NULL; +} + +/* allocates and clears the hash */ +struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose) +{ + struct hashtable_t *hash; + + hash = debugMalloc(sizeof(struct hashtable_t), 302); + if (!hash) + return NULL; + + hash->size= size; + hash->table= debugMalloc(sizeof(struct element_t *) * size, 303); + + if (!hash->table) { + debugFree(hash, 1305); + return NULL; + } + + hash_init(hash); + hash->compare = compare; + hash->choose = choose; + return hash; +} + +/* adds data to the hashtable. returns 0 on success, -1 on error */ +int hash_add(struct hashtable_t *hash, void *data) +{ + int index; + struct element_t *bucket, *prev_bucket = NULL; + + index = hash->choose(data, hash->size); + bucket = hash->table[index]; + + while (bucket != NULL) { + if (hash->compare(bucket->data, data)) + return -1; + + prev_bucket = bucket; + bucket= bucket->next; + } + + /* found the tail of the list, add new element */ + bucket = debugMalloc(sizeof(struct element_t),304); + + if (!bucket) + return -1; + + /* init the new bucket */ + bucket->data = data; + bucket->next = NULL; + + /* and link it */ + if (prev_bucket == NULL) { + hash->table[index] = bucket; + } else { + prev_bucket->next = bucket; + } + + hash->elements++; + return 0; +} + +/* finds data, based on the key in keydata. returns the found data on success, or NULL on error */ +void *hash_find(struct hashtable_t *hash, void *keydata) +{ + int index; + struct element_t *bucket; + + index = hash->choose(keydata , hash->size); + bucket = hash->table[index]; + + while (bucket != NULL) { + if (hash->compare(bucket->data, keydata)) + return bucket->data; + + bucket = bucket->next; + } + + return NULL; +} + +/* remove bucket (this might be used in hash_iterate() if you already found the bucket + * you want to delete and don't need the overhead to find it again with hash_remove(). + * But usually, you don't want to use this function, as it fiddles with hash-internals. */ +void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t) +{ + void *data_save; + + data_save = hash_it_t->bucket->data; /* save the pointer to the data */ + + if (hash_it_t->prev_bucket != NULL) { + hash_it_t->prev_bucket->next = hash_it_t->bucket->next; + } else if (hash_it_t->first_bucket != NULL) { + (*hash_it_t->first_bucket) = hash_it_t->bucket->next; + } + + debugFree(hash_it_t->bucket, 1306); + + hash->elements--; + return data_save; +} + +/* removes data from hash, if found. returns pointer do data on success, + * so you can remove the used structure yourself, or NULL on error . + * data could be the structure you use with just the key filled, + * we just need the key for comparing. */ +void *hash_remove(struct hashtable_t *hash, void *data) +{ + struct hash_it_t hash_it_t; + + hash_it_t.index = hash->choose(data, hash->size); + hash_it_t.bucket = hash->table[hash_it_t.index]; + hash_it_t.prev_bucket = NULL; + + while (hash_it_t.bucket != NULL) { + if (hash->compare(hash_it_t.bucket->data, data)) { + hash_it_t.first_bucket = (hash_it_t.bucket == hash->table[hash_it_t.index] ? &hash->table[ hash_it_t.index ] : NULL); + return hash_remove_bucket(hash, &hash_it_t); + } + + hash_it_t.prev_bucket = hash_it_t.bucket; + hash_it_t.bucket = hash_it_t.bucket->next; + } + + return NULL; +} + +/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success. */ +struct hashtable_t *hash_resize(struct hashtable_t *hash, int size) +{ + struct hashtable_t *new_hash; + struct element_t *bucket; + int i; + + /* initialize a new hash with the new size */ + new_hash = hash_new(size, hash->compare, hash->choose); + if (!new_hash) + return NULL; + + /* copy the elements */ + for (i = 0; i < hash->size; i++) { + bucket = hash->table[i]; + while (bucket != NULL) { + hash_add(new_hash, bucket->data); + bucket = bucket->next; + } + } + + hash_delete(hash, NULL); /* remove hash and eventual overflow buckets but not the content itself. */ + return new_hash; +} + +/* print the hash table for debugging */ +/* void hash_debug(struct hashtable_t *hash) { + int i; + struct element_t *bucket; + + for (i = 0; i < hash->size; i++) { + printf("[%d] ", i); + bucket = hash->table[i]; + + while (bucket) { + printf("-> [%10p] ", (void *)bucket); + bucket = bucket->next; + } + + printf("\n"); + + } + printf("\n"); +}*/ +
Added: branches/batctl-0.2.x/hash.h =================================================================== --- branches/batctl-0.2.x/hash.h (rev 0) +++ branches/batctl-0.2.x/hash.h 2010-01-10 01:37:27 UTC (rev 1545) @@ -0,0 +1,95 @@ +/* + * Copyright (C) 2006-2009 B.A.T.M.A.N. contributors: + * + * Simon Wunderlich, Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ +#ifndef _BATMAN_HASH_H +#define _BATMAN_HASH_H + + + +typedef int (*hashdata_compare_cb)(void *, void *); +typedef int (*hashdata_choose_cb)(void *, int); +typedef void (*hashdata_free_cb)(void *); + +struct element_t { + void *data; /* pointer to the data */ + struct element_t *next; /* overflow bucket pointer */ +}; + +struct hash_it_t { + int index; + struct element_t *bucket; + struct element_t *prev_bucket; + struct element_t **first_bucket; +}; + +struct hashtable_t { + struct element_t **table; /* the hashtable itself, with the buckets */ + int elements; /* number of elements registered */ + int size; /* size of hashtable */ + hashdata_compare_cb compare; /* callback to a compare function. + * should compare 2 element datas for their keys, + * return 0 if same and not 0 if not same */ + hashdata_choose_cb choose; /* the hashfunction, should return an index based + * on the key in the data of the first argument + * and the size the second */ +}; + +/* clears the hash */ +void hash_init(struct hashtable_t *hash); + +/* allocates and clears the hash */ +struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, hashdata_choose_cb choose); + +/* remove bucket (this might be used in hash_iterate() if you already found the bucket + * you want to delete and don't need the overhead to find it again with hash_remove(). + * But usually, you don't want to use this function, as it fiddles with hash-internals. */ +void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t); + +/* remove the hash structure. if hashdata_free_cb != NULL, + * this function will be called to remove the elements inside of the hash. + * if you don't remove the elements, memory might be leaked. */ +void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb); + +/* free only the hashtable and the hash itself. */ +void hash_destroy(struct hashtable_t *hash); + +/* adds data to the hashtable. returns 0 on success, -1 on error */ +int hash_add(struct hashtable_t *hash, void *data); + +/* removes data from hash, if found. returns pointer do data on success, + * so you can remove the used structure yourself, or NULL on error . + * data could be the structure you use with just the key filled, + * we just need the key for comparing. */ +void *hash_remove(struct hashtable_t *hash, void *data); + +/* finds data, based on the key in keydata. returns the found data on success, or NULL on error */ +void *hash_find(struct hashtable_t *hash, void *keydata); + +/* resize the hash, returns the pointer to the new hash or NULL on error. removes the old hash on success */ +struct hashtable_t *hash_resize(struct hashtable_t *hash, int size); + +/* print the hash table for debugging */ +void hash_debug( struct hashtable_t *hash); + +/* iterate though the hash. first element is selected with iter_in NULL. + * use the returned iterator to access the elements until hash_it_t returns NULL. */ +struct hash_it_t *hash_iterate(struct hashtable_t *hash, struct hash_it_t *iter_in); + +#endif
Added: branches/batctl-0.2.x/list-batman.c =================================================================== --- branches/batctl-0.2.x/list-batman.c (rev 0) +++ branches/batctl-0.2.x/list-batman.c 2010-01-10 01:37:27 UTC (rev 1545) @@ -0,0 +1,123 @@ +/* + * Copyright (C) 2006-2009 B.A.T.M.A.N. contributors: + * + * Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + + +#include "list-batman.h" + + + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the next entries already! + */ +static void __list_add( struct list_head *new, struct list_head *prev, struct list_head *next ) { + + new->next = next; + prev->next = new; + +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +void list_add( struct list_head *new, struct list_head_first *head ) { + + __list_add( new, (struct list_head *)head, head->next ); + + if ( head->prev == (struct list_head *)head ) + head->prev = new; + +} + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +void list_add_tail( struct list_head *new, struct list_head_first *head ) { + + __list_add( new, head->prev, (struct list_head *)head ); + + head->prev = new; + +} + +void list_add_before( struct list_head *prev_node, struct list_head *next_node, struct list_head *new_node ) { + + prev_node->next = new_node; + new_node->next = next_node; + +} + + + +/* + * Delete a list entry by making the next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the next entries already! + */ +static void __list_del( struct list_head *prev, struct list_head *next ) { + + prev->next = next; + +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty on entry does not return true after this, the entry is in an undefined state. + */ +void list_del( struct list_head *prev_entry, struct list_head *entry, struct list_head_first *head ) { + + if ( head->prev == entry ) + head->prev = prev_entry; + + __list_del( prev_entry, entry->next ); + + entry->next = (void *) 0; + +} + + + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +int list_empty( struct list_head_first *head ) { + + return head->next == (struct list_head *)head; + +} +
Added: branches/batctl-0.2.x/list-batman.h =================================================================== --- branches/batctl-0.2.x/list-batman.h (rev 0) +++ branches/batctl-0.2.x/list-batman.h 2010-01-10 01:37:27 UTC (rev 1545) @@ -0,0 +1,123 @@ +/* + * Copyright (C) 2006-2009 B.A.T.M.A.N. contributors: + * + * Marek Lindner + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + + +#include <stddef.h> /* offsetof() */ + +#ifndef _LINUX_LIST_H +#define _LINUX_LIST_H + +/* + * XXX: Resolve conflict between this file and <sys/queue.h> on BSD systems. + */ +#ifdef LIST_HEAD +#undef LIST_HEAD +#endif + +/* + * Simple linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +struct list_head { + struct list_head *next; +}; + +struct list_head_first { + struct list_head *next, *prev; +}; + + +void list_add( struct list_head *new, struct list_head_first *head ); +void list_add_tail( struct list_head *new, struct list_head_first *head ); +void list_add_before( struct list_head *prev_node, struct list_head *next_node, struct list_head *new_node ); +void list_del( struct list_head *prev_entry, struct list_head *entry, struct list_head_first *head ); +int list_empty( struct list_head_first *head ); + + + +#define INIT_LIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); \ +} while (0) + +#define INIT_LIST_HEAD_FIRST(ptr) \ + ptr.next = (struct list_head *)&ptr; ptr.prev = (struct list_head *)&ptr; \ + + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (struct list_head *)(head); \ + pos = pos->next) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop counter. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (struct list_head *)(head); \ + pos = n, n = pos->next) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (struct list_head *)(head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (struct list_head *)(head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + + +#endif
Added: branches/batctl-0.2.x/packet.h =================================================================== --- branches/batctl-0.2.x/packet.h (rev 0) +++ branches/batctl-0.2.x/packet.h 2010-01-10 01:37:27 UTC (rev 1545) @@ -0,0 +1,98 @@ +/* + * Copyright (C) 2007-2009 B.A.T.M.A.N. contributors: + * + * Marek Lindner, Simon Wunderlich + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA + * + */ + +#define ETH_P_BATMAN 0x4305 /* unofficial/not registered Ethertype */ + +#define BAT_PACKET 0x01 +#define BAT_ICMP 0x02 +#define BAT_UNICAST 0x03 +#define BAT_BCAST 0x04 +#define BAT_VIS 0x05 + +/* this file is included by batctl which needs these defines */ +#define COMPAT_VERSION 9 +#define DIRECTLINK 0x40 +#define VIS_SERVER 0x20 + +/* ICMP message types */ +#define ECHO_REPLY 0 +#define DESTINATION_UNREACHABLE 3 +#define ECHO_REQUEST 8 +#define TTL_EXCEEDED 11 +#define PARAMETER_PROBLEM 12 + +/* vis defines */ +#define VIS_TYPE_SERVER_SYNC 0 +#define VIS_TYPE_CLIENT_UPDATE 1 + +struct batman_packet { + uint8_t packet_type; + uint8_t version; /* batman version field */ + uint8_t flags; /* 0x40: DIRECTLINK flag, 0x20 VIS_SERVER flag... */ + uint8_t tq; + uint16_t seqno; + uint8_t orig[6]; + uint8_t prev_sender[6]; + uint8_t ttl; + uint8_t num_hna; + uint8_t gw_flags; /* flags related to gateway class */ + uint8_t align; +} __attribute__((packed)); + +#define BAT_PACKET_LEN sizeof(struct batman_packet) + +struct icmp_packet { + uint8_t packet_type; + uint8_t version; /* batman version field */ + uint8_t msg_type; /* see ICMP message types above */ + uint8_t ttl; + uint8_t dst[6]; + uint8_t orig[6]; + uint16_t seqno; + uint8_t uid; +} __attribute__((packed)); + +struct unicast_packet { + uint8_t packet_type; + uint8_t version; /* batman version field */ + uint8_t dest[6]; + uint8_t ttl; +} __attribute__((packed)); + +struct bcast_packet { + uint8_t packet_type; + uint8_t version; /* batman version field */ + uint8_t orig[6]; + uint16_t seqno; +} __attribute__((packed)); + +struct vis_packet { + uint8_t packet_type; + uint8_t version; /* batman version field */ + uint8_t vis_type; /* which type of vis-participant sent this? */ + uint8_t seqno; /* sequence number */ + uint8_t entries; /* number of entries behind this struct */ + uint8_t ttl; /* TTL */ + uint8_t vis_orig[6]; /* originator that informs about its + * neighbors */ + uint8_t target_orig[6]; /* who should receive this packet */ + uint8_t sender_orig[6]; /* who sent or rebroadcasted this packet */ +} __attribute__((packed));