home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso / altsrc / articles / 11108 / iphash.c < prev    next >
C/C++ Source or Header  |  1994-08-11  |  6KB  |  198 lines
  1. /* Routines for maintaining a totally encapsulated table of IP addresses
  2.  * and their associated hardware addresses, indexed by IP address.  The
  3.  * hash function is extremely simple--the fourth octet of the IP address
  4.  * becomes the index into a 256-cell array of linked lists.  This seems
  5.  * fast and simple enough for most applications, without being restrictive.
  6.  *
  7.  * To facilitate the common application of proxy-arping entire networks,
  8.  * I've added lookup tables for Class B and Class C networks we proxy-arp.
  9.  * The overhead associated with searching these should be a lot less than
  10.  * the overhead of, say, adding 65,536 hash table entries for a Class B.
  11.  *
  12.  * See proxyarpd.h and iphash.h for type definitions.
  13.  *
  14.  * Written by Matt Kimmel, kimmel@cs.umass.edu, 8/94.
  15.  * Copyright (c) 1994, University of Massachusetts.  This program may be
  16.  * freely distributed, modified, or incorporated into other programs
  17.  * provided that the following conditions are met: 1) This copyright
  18.  * remains unmodified and is included in any derivative works; and 2)
  19.  * No profit is made through the sale of this program or derivative
  20.  * works.
  21.  */
  22. #include <stdio.h>
  23. #include <string.h>
  24. #include "proxyarpd.h"
  25. #include "iphash.h"
  26.  
  27. /* Global variables */
  28. static struct iphash_node *iphash_table[256];  /* The hash table */
  29. static struct iphash_node *iphash_classb; /* List of Class B's we proxy-arp */
  30. static struct iphash_node *iphash_classc; /* List of Class C's we proxy-arp */
  31.  
  32. /* Function prototypes */
  33. void iphash_init();
  34. int iphash_add(ipaddr,etheraddr *);
  35. int iphash_add_classb(char *,etheraddr *);
  36. int iphash_add_classc(char *,etheraddr *);
  37. etheraddr *iphash_retrieve(ipaddr);
  38.  
  39. /* This function initializes the hash table.  It should be called before
  40.  * any data is added to the hash table.  It will re-initialize the table
  41.  * if it's already been used, but it will NOT free up the space allocated
  42.  * to the records, so it should not be used for this purpose.
  43.  */
  44. void iphash_init()
  45. {
  46.   int i;
  47.  
  48.   for(i=0;i<256;i++)
  49.     iphash_table[i] = NULL;
  50.   iphash_classb = NULL;
  51.   iphash_classc = NULL;
  52. }
  53.  
  54. /* This function adds an IP address/ethernet address pair to the hash
  55.  * table.  Returns 0 on success, non-zero on failure.
  56.  */
  57. int iphash_add(ipaddr ip,etheraddr *ether)
  58. {
  59.   struct iphash_node *newnode;
  60.   int hash;
  61.  
  62.   /* First, hash the IP address */
  63.   hash = iphash_hashfunc(ip);
  64.  
  65.   /* Now, create a new node to store the information. */
  66.   if((newnode = (struct iphash_node *)malloc(sizeof(struct iphash_node))) == NULL)
  67.     return(-1);
  68.   newnode->ip = ip;
  69.   memcpy(newnode->ether.ether_octet,ether->ether_octet,6);
  70.  
  71.   /* Finally, add the node to the appropriate slot in the hash table. */
  72.   newnode->next = iphash_table[hash];
  73.   iphash_table[hash] = newnode;
  74.  
  75.   return(0);
  76. }
  77.  
  78. /* This function adds a network to the list of Class B networks.  It expects
  79.  * the network number to be represented in a string of the form "xxx.xxx".
  80.  * Returns nonzero on failure, 0 on success.
  81.  */
  82. int iphash_add_classb(char *network,etheraddr *ether)
  83. {
  84.   struct iphash_node *newnode;
  85.   int o1, o2;
  86.   char *s, n[20];
  87.  
  88.   /* Parse the address */
  89.   strcpy(n,network);
  90.   s = strchr(n,'.');
  91.   if(s == NULL)
  92.     return(-1);
  93.   *s = '\0';
  94.   s++;
  95.   o1 = atoi(n);
  96.   o2 = atoi(s);
  97.  
  98.   /* Allocate and fill in a new node */
  99.   if((newnode = (struct iphash_node *)malloc(sizeof(struct iphash_node))) == NULL)
  100.     return(-1);
  101.   newnode->ip = (((o2 << 8) & 0xff00) | (o1 & 0xff)) & 0xffff;
  102.   memcpy(newnode->ether.ether_octet,ether->ether_octet,6);
  103.  
  104.   /* And add it. */
  105.   newnode->next = iphash_classb;
  106.   iphash_classb = newnode;
  107.  
  108.   return(0);
  109. }
  110.  
  111. /* This function adds a network to the list of Class C networks.  It expects
  112.  * the network number to be represented in a string of the form "xxx.xxx.xxx".
  113.  * Returns nonzero on failure, 0 on success.
  114.  */
  115. int iphash_add_classc(char *network,etheraddr *ether)
  116. {
  117.   struct iphash_node *newnode;
  118.   int o1, o2, o3;
  119.   char *s, *s2, n[20];
  120.  
  121.   /* Parse the address */
  122.   strcpy(n,network);
  123.   s = strchr(n,'.');
  124.   if(s == NULL)
  125.     return(-1);
  126.   *s = '\0';
  127.   s++;
  128.   s2 = strchr(s,'.');
  129.   if(s2 == NULL)
  130.     return(-1);
  131.   *s2 = '\0';
  132.   s2++;
  133.   o1 = atoi(n);
  134.   o2 = atoi(s);
  135.   o3 = atoi(s2);
  136.  
  137.   /* Allocate and fill in a new node */
  138.   if((newnode = (struct iphash_node *)malloc(sizeof(struct iphash_node))) == NULL)
  139.     return(-1);
  140.   newnode->ip = ((((o3 << 16) & 0xff0000) | ((o2 << 8) & 0xff00)) | (o1 & 0xff)) & 0xffffff;
  141.   memcpy(newnode->ether.ether_octet,ether->ether_octet,6);
  142.  
  143.   /* And add it. */
  144.   newnode->next = iphash_classc;
  145.   iphash_classc = newnode;
  146.  
  147.   return(0);
  148. }
  149.  
  150. /* This function retrieves the ethernet address associated with the
  151.  * specified IP number and returns a pointer to the etheraddr structure.
  152.  * It returns NULL if the IP number cannot be found.
  153.  */
  154. etheraddr *iphash_retrieve(ipaddr ip)
  155. {
  156.   int hash;
  157.   struct iphash_node *p;
  158.  
  159. #ifdef DEBUG
  160.   printf("Looking up %d.%d.%d.%d\n",
  161.      (ip & 0xff),
  162.      ((ip >> 8) & 0xff),
  163.      ((ip >> 16) & 0xff),
  164.      ((ip >> 24) & 0xff));
  165. #endif
  166.  
  167.   /* Hash the IP address */
  168.   hash = iphash_hashfunc(ip);
  169.  
  170.   /* Now search the appropriate linked list. */
  171.   p = iphash_table[hash];
  172.   while(p != NULL)
  173.     if(p->ip == ip) /* A match! */
  174.       return(&(p->ether));
  175.     else
  176.       p = p->next;
  177.  
  178.   /* After accessing the hash table, see if this address is in any of the
  179.    * Class B or Class C networks we're proxy-arping.
  180.    */
  181.   p = iphash_classc;
  182.   while(p != NULL) {
  183.     if((ip & 0x00ffffff) == (p->ip & 0x00ffffff)) /* A match! */
  184.       return(&(p->ether));
  185.     p = p->next;
  186.   }
  187.  
  188.   p = iphash_classb;
  189.   while(p != NULL) {
  190.     if((ip & 0x0000ffff) == (p->ip & 0x0000ffff)) /* A match! */
  191.       return(&(p->ether));
  192.     p = p->next;
  193.   }
  194.  
  195.   /* If we make it here, there was no match. */
  196.   return(NULL);
  197. }
  198.