plist.c

大名鼎鼎的路由器源码。程序分ZEBRA、OSPFRIP等3个包。程序框架采用一个路由协议一个进程的方式

/* Prefix list functions.
 * Copyright (C) 1999 Kunihiro Ishiguro
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra 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 2, or (at your
 * option) any later version.
 *
 * GNU Zebra 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 GNU Zebra; see the file COPYING.  If not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include <zebra.h>

#include "prefix.h"
#include "command.h"
#include "memory.h"
#include "plist.h"
#include "sockunion.h"
#include "buffer.h"

/* Each prefix-list's entry. */
struct prefix_list_entry
{
  int seq;

  int le;
  int ge;

  enum prefix_list_type type;

  int any;
  struct prefix prefix;

  unsigned long refcnt;
  unsigned long hitcnt;

  struct prefix_list_entry *next;
  struct prefix_list_entry *prev;
};

/* List of struct prefix_list. */
struct prefix_list_list
{
  struct prefix_list *head;
  struct prefix_list *tail;
};

/* Master structure of prefix_list. */
struct prefix_master
{
  /* List of prefix_list which name is number. */
  struct prefix_list_list num;

  /* List of prefix_list which name is string. */
  struct prefix_list_list str;

  /* Whether sequential number is used. */
  int seqnum;

  /* The latest update. */
  struct prefix_list *recent;

  /* Hook function which is executed when new prefix_list is added. */
  void (*add_hook) ();

  /* Hook function which is executed when prefix_list is deleted. */
  void (*delete_hook) ();
};

/* Static structure of IPv4 prefix_list's master. */
static struct prefix_master prefix_master_ipv4 = 
{ 
  {NULL, NULL},
  {NULL, NULL},
  1,
  NULL,
  NULL,
};

#ifdef HAVE_IPV6
/* Static structure of IPv6 prefix-list's master. */
static struct prefix_master prefix_master_ipv6 = 
{ 
  {NULL, NULL},
  {NULL, NULL},
  1,
  NULL,
  NULL,
};
#endif /* HAVE_IPV6*/

/* Static structure of BGP ORF prefix_list's master. */
static struct prefix_master prefix_master_orf = 
{ 
  {NULL, NULL},
  {NULL, NULL},
  1,
  NULL,
  NULL,
};

struct prefix_master *
prefix_master_get (afi_t afi)
{
  if (afi == AFI_IP)
    return &prefix_master_ipv4;
#ifdef HAVE_IPV6
  else if (afi == AFI_IP6)
    return &prefix_master_ipv6;
#endif /* HAVE_IPV6 */
  else if (afi == AFI_ORF_PREFIX)
    return &prefix_master_orf;
  return NULL;
}

/* Lookup prefix_list from list of prefix_list by name. */
struct prefix_list *
prefix_list_lookup (afi_t afi, char *name)
{
  struct prefix_list *plist;
  struct prefix_master *master;

  if (name == NULL)
    return NULL;

  master = prefix_master_get (afi);
  if (master == NULL)
    return NULL;

  for (plist = master->num.head; plist; plist = plist->next)
    if (strcmp (plist->name, name) == 0)
      return plist;

  for (plist = master->str.head; plist; plist = plist->next)
    if (strcmp (plist->name, name) == 0)
      return plist;

  return NULL;
}

struct prefix_list *
prefix_list_new ()
{
  struct prefix_list *new;

  new = XCALLOC (MTYPE_PREFIX_LIST, sizeof (struct prefix_list));
  return new;
}

void
prefix_list_free (struct prefix_list *plist)
{
  XFREE (MTYPE_PREFIX_LIST, plist);
}

struct prefix_list_entry *
prefix_list_entry_new ()
{
  struct prefix_list_entry *new;

  new = XCALLOC (MTYPE_PREFIX_LIST_ENTRY, sizeof (struct prefix_list_entry));
  return new;
}

void
prefix_list_entry_free (struct prefix_list_entry *pentry)
{
  XFREE (MTYPE_PREFIX_LIST_ENTRY, pentry);
}

/* Insert new prefix list to list of prefix_list.  Each prefix_list
   is sorted by the name. */
struct prefix_list *
prefix_list_insert (afi_t afi, char *name)
{
  int i;
  long number;
  struct prefix_list *plist;
  struct prefix_list *point;
  struct prefix_list_list *list;
  struct prefix_master *master;

  master = prefix_master_get (afi);
  if (master == NULL)
    return NULL;

  /* Allocate new prefix_list and copy given name. */
  plist = prefix_list_new ();
  plist->name = XSTRDUP (MTYPE_PREFIX_LIST_STR, name);
  plist->master = master;

  /* If name is made by all digit character.  We treat it as
     number. */
  for (number = 0, i = 0; i < strlen (name); i++)
    {
      if (isdigit ((int) name[i]))
	number = (number * 10) + (name[i] - '0');
      else
	break;
    }

  /* In case of name is all digit character */
  if (i == strlen (name))
    {
      plist->type = PREFIX_TYPE_NUMBER;

      /* Set prefix_list to number list. */
      list = &master->num;

      for (point = list->head; point; point = point->next)
	if (atol (point->name) >= number)
	  break;
    }
  else
    {
      plist->type = PREFIX_TYPE_STRING;

      /* Set prefix_list to string list. */
      list = &master->str;
  
      /* Set point to insertion point. */
      for (point = list->head; point; point = point->next)
	if (strcmp (point->name, name) >= 0)
	  break;
    }

  /* In case of this is the first element of master. */
  if (list->head == NULL)
    {
      list->head = list->tail = plist;
      return plist;
    }

  /* In case of insertion is made at the tail of access_list. */
  if (point == NULL)
    {
      plist->prev = list->tail;
      list->tail->next = plist;
      list->tail = plist;
      return plist;
    }

  /* In case of insertion is made at the head of access_list. */
  if (point == list->head)
    {
      plist->next = list->head;
      list->head->prev = plist;
      list->head = plist;
      return plist;
    }

  /* Insertion is made at middle of the access_list. */
  plist->next = point;
  plist->prev = point->prev;

  if (point->prev)
    point->prev->next = plist;
  point->prev = plist;

  return plist;
}

struct prefix_list *
prefix_list_get (afi_t afi, char *name)
{
  struct prefix_list *plist;

  plist = prefix_list_lookup (afi, name);

  if (plist == NULL)
    plist = prefix_list_insert (afi, name);
  return plist;
}

/* Delete prefix-list from prefix_list_master and free it. */
void
prefix_list_delete (struct prefix_list *plist)
{
  struct prefix_list_list *list;
  struct prefix_master *master;
  struct prefix_list_entry *pentry;
  struct prefix_list_entry *next;

  /* If prefix-list contain prefix_list_entry free all of it. */
  for (pentry = plist->head; pentry; pentry = next)
    {
      next = pentry->next;
      prefix_list_entry_free (pentry);
      plist->count--;
    }

  master = plist->master;

  if (plist->type == PREFIX_TYPE_NUMBER)
    list = &master->num;
  else
    list = &master->str;

  if (plist->next)
    plist->next->prev = plist->prev;
  else
    list->tail = plist->prev;

  if (plist->prev)
    plist->prev->next = plist->next;
  else
    list->head = plist->next;

  if (plist->desc)
    XFREE (MTYPE_TMP, plist->desc);

  /* Make sure master's recent changed prefix-list information is
     cleared. */
  master->recent = NULL;

  if (plist->name)
    XFREE (MTYPE_PREFIX_LIST_STR, plist->name);

  prefix_list_free (plist);

  if (master->delete_hook)
    (*master->delete_hook) ();
}

struct prefix_list_entry *
prefix_list_entry_make (struct prefix *prefix, enum prefix_list_type type,
			int seq, int le, int ge, int any)
{
  struct prefix_list_entry *pentry;

  pentry = prefix_list_entry_new ();

  if (any)
    pentry->any = 1;

  prefix_copy (&pentry->prefix, prefix);
  pentry->type = type;
  pentry->seq = seq;
  pentry->le = le;
  pentry->ge = ge;

  return pentry;
}

/* Add hook function. */
void
prefix_list_add_hook (void (*func) (struct prefix_list *plist))
{
  prefix_master_ipv4.add_hook = func;
#ifdef HAVE_IPV6
  prefix_master_ipv6.add_hook = func;
#endif /* HAVE_IPV6 */
}

/* Delete hook function. */
void
prefix_list_delete_hook (void (*func) (struct prefix_list *plist))
{
  prefix_master_ipv4.delete_hook = func;
#ifdef HAVE_IPV6
  prefix_master_ipv6.delete_hook = func;
#endif /* HAVE_IPVt6 */
}

/* Calculate new sequential number. */
int
prefix_new_seq_get (struct prefix_list *plist)
{
  int maxseq;
  int newseq;
  struct prefix_list_entry *pentry;

  maxseq = newseq = 0;

  for (pentry = plist->head; pentry; pentry = pentry->next)
    {
      if (maxseq < pentry->seq)
	maxseq = pentry->seq;
    }

  newseq = ((maxseq / 5) * 5) + 5;
  
  return newseq;
}

/* Return prefix list entry which has same seq number. */
struct prefix_list_entry *
prefix_seq_check (struct prefix_list *plist, int seq)
{
  struct prefix_list_entry *pentry;

  for (pentry = plist->head; pentry; pentry = pentry->next)
    if (pentry->seq == seq)
      return pentry;
  return NULL;
}

struct prefix_list_entry *
prefix_list_entry_lookup (struct prefix_list *plist, struct prefix *prefix,
			  enum prefix_list_type type, int seq, int le, int ge)
{
  struct prefix_list_entry *pentry;

  for (pentry = plist->head; pentry; pentry = pentry->next)
    if (prefix_same (&pentry->prefix, prefix) && pentry->type == type)
      {
	if (seq >= 0 && pentry->seq != seq)
	  continue;

	if (pentry->le != le)
	  continue;
	if (pentry->ge != ge)
	  continue;

	return pentry;
      }

  return NULL;
}

void
prefix_list_entry_delete (struct prefix_list *plist, 
			  struct prefix_list_entry *pentry,
			  int update_list)
{
  if (plist == NULL || pentry == NULL)
    return;
  if (pentry->prev)
    pentry->prev->next = pentry->next;
  else
    plist->head = pentry->next;
  if (pentry->next)
    pentry->next->prev = pentry->prev;
  else
    plist->tail = pentry->prev;

  prefix_list_entry_free (pentry);

  plist->count--;

  if (update_list)
    {
      if (plist->master->delete_hook)
	(*plist->master->delete_hook) (plist);

      if (plist->head == NULL && plist->tail == NULL && plist->desc == NULL)
	prefix_list_delete (plist);
      else
	plist->master->recent = plist;
    }
}

void
prefix_list_entry_add (struct prefix_list *plist,
		       struct prefix_list_entry *pentry)
{
  struct prefix_list_entry *replace;
  struct prefix_list_entry *point;

  /* Automatic asignment of seq no. */
  if (pentry->seq == -1)
    pentry->seq = prefix_new_seq_get (plist);

  /* Is there any same seq prefix list entry? */
  replace = prefix_seq_check (plist, pentry->seq);
  if (replace)
    prefix_list_entry_delete (plist, replace, 0);

  /* Check insert point. */
  for (point = plist->head; point; point = point->next)
    if (point->seq >= pentry->seq)
      break;

  /* In case of this is the first element of the list. */
  pentry->next = point;

  if (point)
    {
      if (point->prev)
	point->prev->next = pentry;
      else
	plist->head = pentry;

      pentry->prev = point->prev;