WebSVN – Kolibri OS – Diff – /contrib/toolchain/binutils/include/partition.h


/* List implementation of a partition of consecutive integers.
   Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
   Contributed by CodeSourcery, LLC.
 
   This file is part of GCC.
 
   GCC 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.
 
   GCC 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 GCC; see the file COPYING.  If not, write to
   the Free Software Foundation, 51 Franklin Street - Fifth Floor,
   Boston, MA 02110-1301, USA.  */
 
/* This package implements a partition of consecutive integers.  The
   elements are partitioned into classes.  Each class is represented
   by one of its elements, the canonical element, which is chosen
   arbitrarily from elements in the class.  The principal operations
   on a partition are FIND, which takes an element, determines its
   class, and returns the canonical element for that class, and UNION,
   which unites the two classes that contain two given elements into a
   single class.
 
   The list implementation used here provides constant-time finds.  By
   storing the size of each class with the class's canonical element,
   it is able to perform unions over all the classes in the partition
   in O (N log N) time.  */
 
#ifndef _PARTITION_H
#define _PARTITION_H
 
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
 
#include "ansidecl.h"
#include 
 
struct partition_elem
{
 
 
 
  /* The next element in this class.  Elements in each class form a
     circular list.  */
  struct partition_elem* next;
  /* The canonical element that represents the class containing this
     element.  */
  int class_element;
  /* The number of elements in this class.  Valid only if this is the
     canonical element for its class.  */
  unsigned class_count;
};
 
typedef struct partition_def 
{
  /* The number of elements in this partition.  */
  int num_elements;
  /* The elements in the partition.  */
  struct partition_elem elements[1];
} *partition;
 
extern partition partition_new (int);
extern void partition_delete (partition);
extern int partition_union (partition, int, int);
extern void partition_print (partition,	FILE*);
 
/* Returns the canonical element corresponding to the class containing
   ELEMENT__ in PARTITION__.  */
 
#define partition_find(partition__, element__) \
    ((partition__)->elements[(element__)].class_element)
 
#ifdef __cplusplus
}
#endif /* __cplusplus */
 
#endif /* _PARTITION_H */

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

Subversion Repositories Kolibri OS

(root)/contrib/toolchain/binutils/include/partition.h – Rev 5191 → 6324