OpenCores
URL https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk

Subversion Repositories openrisc_2011-10-31

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [include/] [partition.h] - Blame information for rev 497

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 267 jeremybenn
/* List implementation of a partition of consecutive integers.
2
   Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
3
   Contributed by CodeSourcery, LLC.
4
 
5
   This file is part of GCC.
6
 
7
   GCC is free software; you can redistribute it and/or modify
8
   it under the terms of the GNU General Public License as published by
9
   the Free Software Foundation; either version 2, or (at your option)
10
   any later version.
11
 
12
   GCC is distributed in the hope that it will be useful,
13
   but WITHOUT ANY WARRANTY; without even the implied warranty of
14
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
   GNU General Public License for more details.
16
 
17
   You should have received a copy of the GNU General Public License
18
   along with GCC; see the file COPYING.  If not, write to
19
   the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20
   Boston, MA 02110-1301, USA.  */
21
 
22
/* This package implements a partition of consecutive integers.  The
23
   elements are partitioned into classes.  Each class is represented
24
   by one of its elements, the canonical element, which is chosen
25
   arbitrarily from elements in the class.  The principal operations
26
   on a partition are FIND, which takes an element, determines its
27
   class, and returns the canonical element for that class, and UNION,
28
   which unites the two classes that contain two given elements into a
29
   single class.
30
 
31
   The list implementation used here provides constant-time finds.  By
32
   storing the size of each class with the class's canonical element,
33
   it is able to perform unions over all the classes in the partition
34
   in O (N log N) time.  */
35
 
36
#ifndef _PARTITION_H
37
#define _PARTITION_H
38
 
39
#ifdef __cplusplus
40
extern "C" {
41
#endif /* __cplusplus */
42
 
43
#include "ansidecl.h"
44
#include <stdio.h>
45
 
46
struct partition_elem
47
{
48
  /* The canonical element that represents the class containing this
49
     element.  */
50
  int class_element;
51
  /* The next element in this class.  Elements in each class form a
52
     circular list.  */
53
  struct partition_elem* next;
54
  /* The number of elements in this class.  Valid only if this is the
55
     canonical element for its class.  */
56
  unsigned class_count;
57
};
58
 
59
typedef struct partition_def
60
{
61
  /* The number of elements in this partition.  */
62
  int num_elements;
63
  /* The elements in the partition.  */
64
  struct partition_elem elements[1];
65
} *partition;
66
 
67
extern partition partition_new (int);
68
extern void partition_delete (partition);
69
extern int partition_union (partition, int, int);
70
extern void partition_print (partition, FILE*);
71
 
72
/* Returns the canonical element corresponding to the class containing
73
   ELEMENT__ in PARTITION__.  */
74
 
75
#define partition_find(partition__, element__) \
76
    ((partition__)->elements[(element__)].class_element)
77
 
78
#ifdef __cplusplus
79
}
80
#endif /* __cplusplus */
81
 
82
#endif /* _PARTITION_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.