Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/config/pack.c	Lines:	0	164	0.0 %
Date:	2017-11-13	Branches:	0	114	0.0 %


/*	$OpenBSD: pack.c,v 1.18 2015/01/16 06:40:16 deraadt Exp $	*/
/*	$NetBSD: pack.c,v 1.5 1996/08/31 21:15:11 mycroft Exp $	*/

/*
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This software was developed by the Computer Systems Engineering group
 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
 * contributed to Berkeley.
 *
 * All advertising materials mentioning features or use of this software
 * must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Lawrence Berkeley Laboratories.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	from: @(#)pack.c	8.1 (Berkeley) 6/6/93
 */

#include <stdlib.h>
#include <string.h>

#include "config.h"

/*
 * Packing.  We have three separate kinds of packing here.
 *
 * First, we pack device instances, to collapse things like
 *
 *	uba0 at sbi0 nexus ?
 *	uba0 at bi0 nexus ?
 *
 * into a single instance that is "at sbi0 or bi0".
 *
 * Second, we pack locators.  Given something like
 *
 *	hp0 at mba0 drive 0
 *	hp* at mba* drive ?
 *	ht0 at mba0 drive 0
 *	tu0 at ht0 slave 0
 *	ht* at mba* drive ?
 *	tu* at ht* slave ?
 *
 * (where the default drive and slave numbers are -1), we have three
 * locators whose value is 0 and three whose value is -1.  Rather than
 * emitting six integers, we emit just two.
 *
 * Finally, we pack parent vectors.  This is very much like packing
 * locators.  Unlike locators, however, parent vectors are always
 * terminated by -1 (rather like the way C strings always end with
 * a NUL).
 *
 * When packing locators, we would like to find sequences such as
 *	{1 2 3} {2 3 4} {3} {4 5}
 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
 * given by the appropriate offset (here 0, 1, 2, and 3 respectively).
 * When we pack parent vectors, overlap of this sort is impossible.
 * Non-overlapping packing is much easier, and so we use that here
 * and miss out on the chance to squeeze the locator sequence optimally.
 * (So it goes.)
 */

typedef int (*vec_cmp_func)(const void *, int, int);

#define	TAILHSIZE	128
#define	PVHASH(i)	((i) & (TAILHSIZE - 1))
#define	LOCHASH(l)	(((long)(l) >> 2) & (TAILHSIZE - 1))
struct tails {
	struct	tails *t_next;
	int	t_ends_at;
};

static struct tails *tails[TAILHSIZE];
static int locspace;
static int pvecspace;
static int longest_pvec;

static void packdevi(void);
static void packlocs(void);
static void packpvec(void);

static void addparents(struct devi *src, struct devi *dst);
static int nparents(struct devi **, struct devbase *, int);
static int sameas(struct devi *, struct devi *);
static int findvec(const void *, int, int, vec_cmp_func, int);
static int samelocs(const void *, int, int);
static int addlocs(const char **, int);
static int loclencmp(const void *, const void *);
static int samepv(const void *, int, int);
static int addpv(short *, int);
static int pvlencmp(const void *, const void *);
static void resettails(void);

void
pack(void)
{
	struct devi *i;
	int n;

	/* Pack instances and make parent vectors. */
	packdevi();

	/*
	 * Now that we know what we have, find upper limits on space
	 * needed for the loc[] and pv[] tables, and find the longest
	 * single pvec.  The loc and pv table sizes are bounded by
	 * what we would get if no packing occurred.
	 */
	locspace = pvecspace = 0;
	for (i = alldevi; i != NULL; i = i->i_next) {
		if (i->i_collapsed)
			continue;
		locspace += i->i_atattr->a_loclen;
		n = i->i_pvlen + 1;
		if (n > longest_pvec)
			longest_pvec = n;
		pvecspace += n;
	}

	/* Allocate and pack loc[]. */
	locators.vec = ereallocarray(NULL, locspace, sizeof(*locators.vec));
	locators.used = 0;
	packlocs();

	/* Allocate and pack pv[]. */
	parents.vec = ereallocarray(NULL, pvecspace, sizeof(*parents.vec));
	parents.used = 0;
	packpvec();
}

/*
 * Pack instances together wherever possible.  When everything is
 * packed, go back and set up the parents for each.  We must do this
 * on a second pass because during the first one, we do not know which,
 * if any, of the parents will collapse during packing.
 */
void
packdevi(void)
{
	struct devi *i, *l, *p;
	struct deva *d;
	int j, m, n;

	packed = ereallocarray(NULL, ndevi + 1, sizeof *packed);
	n = 0;
	for (d = alldevas; d != NULL; d = d->d_next) {
		/*
		 * For each instance of each attachment, add or collapse
		 * all its aliases.
		 */
		for (i = d->d_ihead; i != NULL; i = i->i_asame) {
			m = n;
			for (l = i; l != NULL; l = l->i_alias) {
				/* Skip if we already handled this one.  */
				if (l->i_cfindex >= 0)
					continue;
				l->i_pvlen = 0;
				l->i_pvoff = -1;
				l->i_locoff = -1;
				/* try to find an equivalent for l */
				for (j = m; j < n; j++) {
					p = packed[j];
					if (sameas(l, p)) {
						l->i_collapsed = 1;
						l->i_cfindex = p->i_cfindex;
						goto nextalias;
					}
				}
				/* could not find a suitable alias */
				l->i_collapsed = 0;
				l->i_cfindex = n;
				l->i_parents = emalloc(sizeof(*l->i_parents));
				l->i_parents[0] = NULL;
				packed[n++] = l;
			nextalias:;
			}
		}
	}
	npacked = n;
	packed[n] = NULL;
	for (i = alldevi; i != NULL; i = i->i_next)
		addparents(i, packed[i->i_cfindex]);
}

/*
 * Return true if two aliases are "the same".  In this case, they need
 * to attach via the same attribute, have the same config flags, and
 * have the same locators.
 */
static int
sameas(struct devi *i1, struct devi *i2)
{
	const char **p1, **p2;

	if (i1->i_atattr != i2->i_atattr)
		return (0);
	if (i1->i_cfflags != i2->i_cfflags)
		return (0);
	for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++)
		if (*p1++ == 0)
			return (1);
	return 0;
}

/*
 * Add the parents associated with "src" to the (presumably uncollapsed)
 * instance "dst".
 */
static void
addparents(struct devi *src, struct devi *dst)
{
	struct nvlist *nv;
	struct devi *i, **p, **q;
	int j, n, old, new, ndup;

	if (dst->i_collapsed)
		panic("addparents() i_collapsed");

	/* Collect up list of parents to add. */
	if (src->i_at == NULL)	/* none, because we are "at root" */
		return;
	if (src->i_atdev != NULL) {
		n = nparents(NULL, src->i_atdev, src->i_atunit);
		p = ereallocarray(NULL, n, sizeof *p);
		if (n == 0)
			return;
		(void)nparents(p, src->i_atdev, src->i_atunit);
	} else {
		n = 0;
		for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
			n += nparents(NULL, nv->nv_ptr, src->i_atunit);
		if (n == 0)
			return;
		p = ereallocarray(NULL, n, sizeof *p);
		n = 0;
		for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
			n += nparents(p + n, nv->nv_ptr, src->i_atunit);
	}
	/* Now elide duplicates. */
	ndup = 0;
	for (j = 0; j < n; j++) {
		i = p[j];
		for (q = dst->i_parents; *q != NULL; q++) {
			if (*q == i) {
				ndup++;
				p[j] = NULL;
				break;
			}
		}
	}
	/* Finally, add all the non-duplicates. */
	old = dst->i_pvlen;
	new = old + (n - ndup);
	if (old > new)
		panic("addparents() old > new");
	if (old == new) {
		free(p);
		return;
	}
	dst->i_parents = q = ereallocarray(dst->i_parents, new + 1, sizeof(*q));
	dst->i_pvlen = new;
	q[new] = NULL;
	q += old;
	for (j = 0; j < n; j++)
		if (p[j] != NULL)
			*q++ = p[j];
	free(p);
}

/*
 * Count up parents, and optionally store pointers to each.
 */
static int
nparents(struct devi **p, struct devbase *dev, int unit)
{
	struct devi *i, *l;
	int n;

	n = 0;
	/* for each instance ... */
	for (i = dev->d_ihead; i != NULL; i = i->i_bsame) {
		/* ... take each un-collapsed alias */
		for (l = i; l != NULL; l = l->i_alias) {
			if (!l->i_collapsed &&
			    (unit == WILD || unit == l->i_unit)) {
				if (p != NULL)
					*p++ = l;
				n++;
			}
		}
	}
	return (n);
}

static void
packlocs(void)
{
	struct devi **p, *i;
	int l, o;

	qsort(packed, npacked, sizeof *packed, loclencmp);
	for (p = packed; (i = *p) != NULL; p++) {
		if ((l = i->i_atattr->a_loclen) > 0) {
			o = findvec(i->i_locs, LOCHASH(i->i_locs[l - 1]), l,
				    samelocs, locators.used);
			i->i_locoff = o < 0 ? addlocs(i->i_locs, l) : o;
		} else
			i->i_locoff = -1;
	}
	resettails();
}

static void
packpvec(void)
{
	struct devi **p, *i, **par;
	int l, v, o;
	short *vec;

	vec = ereallocarray(NULL, longest_pvec, sizeof(*vec));
	qsort(packed, npacked, sizeof *packed, pvlencmp);
	for (p = packed; (i = *p) != NULL; p++) {
		l = i->i_pvlen;
		if (l > longest_pvec)
			panic("packpvec");
		par = i->i_parents;
		for (v = 0; v < l; v++)
			vec[v] = par[v]->i_cfindex;
		if (l == 0 || (o = findvec(vec, PVHASH(vec[l - 1]), l,
		    samepv, parents.used)) < 0)
			o = addpv(vec, l);
		i->i_pvoff = o;
	}
	free(vec);
	resettails();
}

/*
 * Return the index at which the given vector already exists, or -1
 * if it is not anywhere in the current set.  If we return -1, we assume
 * our caller will add it at the end of the current set, and we make
 * sure that next time, we will find it there.
 */
static int
findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
{
	struct tails *t, **hp;
	int off;

	hp = &tails[hash];
	for (t = *hp; t != NULL; t = t->t_next) {
		off = t->t_ends_at - len;
		if (off >= 0 && (*cmp)(ptr, off, len))
			return (off);
	}
	t = emalloc(sizeof(*t));
	t->t_next = *hp;
	*hp = t;
	t->t_ends_at = nextplace + len;
	return (-1);
}

/*
 * Comparison function for locators.
 */
static int
samelocs(const void *ptr, int off, int len)
{
	const char **p, **q;

	for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;)
		if (*p++ != *q++)
			return (0);	/* different */
	return (1);			/* same */
}

/*
 * Add the given locators at the end of the global loc[] table.
 */
static int
addlocs(const char **locs, int len)
{
	const char **p;
	int ret;

	ret = locators.used;
	if ((locators.used = ret + len) > locspace)
		panic("addlocs: overrun");
	for (p = &locators.vec[ret]; --len >= 0;)
		*p++ = *locs++;
	return (ret);
}

/*
 * Comparison function for qsort-by-locator-length, longest first.
 * We rashly assume that subtraction of these lengths does not overflow.
 */
static int
loclencmp(const void *a, const void *b)
{
	int l1, l2;

	l1 = (*(struct devi **)a)->i_atattr->a_loclen;
	l2 = (*(struct devi **)b)->i_atattr->a_loclen;
	return (l2 - l1);
}

/*
 * Comparison function for parent vectors.
 */
static int
samepv(const void *ptr, int off, int len)
{
	short *p, *q;

	for (p = &parents.vec[off], q = (short *)ptr; --len >= 0;)
		if (*p++ != *q++)
			return (0);	/* different */
	return (1);			/* same */
}

/*
 * Add the given parent vectors at the end of the global pv[] table.
 */
static int
addpv(short *pv, int len)
{
	short *p;
	int ret;
	static int firstend = -1;

	/*
	 * If the vector is empty, reuse the first -1.  It will be
	 * there if there are any nonempty vectors at all, since we
	 * do the longest first.  If there are no nonempty vectors,
	 * something is probably wrong, but we will ignore that here.
	 */
	if (len == 0 && firstend >= 0)
		return (firstend);
	len++;			/* account for trailing -1 */
	ret = parents.used;
	if ((parents.used = ret + len) > pvecspace)
		panic("addpv: overrun");
	for (p = &parents.vec[ret]; --len > 0;)
		*p++ = *pv++;
	*p = -1;
	if (firstend < 0)
		firstend = parents.used - 1;
	return (ret);
}

/*
 * Comparison function for qsort-by-parent-vector-length, longest first.
 * We rashly assume that subtraction of these lengths does not overflow.
 */
static int
pvlencmp(const void *a, const void *b)
{
	int l1, l2;

	l1 = (*(struct devi **)a)->i_pvlen;
	l2 = (*(struct devi **)b)->i_pvlen;
	return (l2 - l1);
}

static void
resettails(void)
{
	struct tails **p, *t, *next;
	int i;

	for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
		for (t = *p; t != NULL; t = next) {
			next = t->t_next;
			free(t);
		}
		*p = NULL;
	}
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: pack.c,v 1.18 2015/01/16 06:40:16 deraadt Exp $ */
2			/* $NetBSD: pack.c,v 1.5 1996/08/31 21:15:11 mycroft Exp $ */
3
4			/*
5			* Copyright (c) 1992, 1993
6			* The Regents of the University of California. All rights reserved.
7			*
8			* This software was developed by the Computer Systems Engineering group
9			* at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
10			* contributed to Berkeley.
11			*
12			* All advertising materials mentioning features or use of this software
13			* must display the following acknowledgement:
14			* This product includes software developed by the University of
15			* California, Lawrence Berkeley Laboratories.
16			*
17			* Redistribution and use in source and binary forms, with or without
18			* modification, are permitted provided that the following conditions
19			* are met:
20			* 1. Redistributions of source code must retain the above copyright
21			* notice, this list of conditions and the following disclaimer.
22			* 2. Redistributions in binary form must reproduce the above copyright
23			* notice, this list of conditions and the following disclaimer in the
24			* documentation and/or other materials provided with the distribution.
25			* 3. Neither the name of the University nor the names of its contributors
26			* may be used to endorse or promote products derived from this software
27			* without specific prior written permission.
28			*
29			* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32			* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39			* SUCH DAMAGE.
40			*
41			* from: @(#)pack.c 8.1 (Berkeley) 6/6/93
42			*/
43
44			#include <stdlib.h>
45			#include <string.h>
46
47			#include "config.h"
48
49			/*
50			* Packing. We have three separate kinds of packing here.
51			*
52			* First, we pack device instances, to collapse things like
53			*
54			* uba0 at sbi0 nexus ?
55			* uba0 at bi0 nexus ?
56			*
57			* into a single instance that is "at sbi0 or bi0".
58			*
59			* Second, we pack locators. Given something like
60			*
61			* hp0 at mba0 drive 0
62			* hp* at mba* drive ?
63			* ht0 at mba0 drive 0
64			* tu0 at ht0 slave 0
65			* ht* at mba* drive ?
66			* tu* at ht* slave ?
67			*
68			* (where the default drive and slave numbers are -1), we have three
69			* locators whose value is 0 and three whose value is -1. Rather than
70			* emitting six integers, we emit just two.
71			*
72			* Finally, we pack parent vectors. This is very much like packing
73			* locators. Unlike locators, however, parent vectors are always
74			* terminated by -1 (rather like the way C strings always end with
75			* a NUL).
76			*
77			* When packing locators, we would like to find sequences such as
78			* {1 2 3} {2 3 4} {3} {4 5}
79			* and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
80			* given by the appropriate offset (here 0, 1, 2, and 3 respectively).
81			* When we pack parent vectors, overlap of this sort is impossible.
82			* Non-overlapping packing is much easier, and so we use that here
83			* and miss out on the chance to squeeze the locator sequence optimally.
84			* (So it goes.)
85			*/
86
87			typedef int (vec_cmp_func)(const void , int, int);
88
89			#define TAILHSIZE 128
90			#define PVHASH(i) ((i) & (TAILHSIZE - 1))
91			#define LOCHASH(l) (((long)(l) >> 2) & (TAILHSIZE - 1))
92			struct tails {
93			struct tails *t_next;
94			int t_ends_at;
95			};
96
97			static struct tails *tails[TAILHSIZE];
98			static int locspace;
99			static int pvecspace;
100			static int longest_pvec;
101
102			static void packdevi(void);
103			static void packlocs(void);
104			static void packpvec(void);
105
106			static void addparents(struct devi src, struct devi dst);
107			static int nparents(struct devi *, struct devbase , int);
108			static int sameas(struct devi , struct devi );
109			static int findvec(const void *, int, int, vec_cmp_func, int);
110			static int samelocs(const void *, int, int);
111			static int addlocs(const char **, int);
112			static int loclencmp(const void , const void );
113			static int samepv(const void *, int, int);
114			static int addpv(short *, int);
115			static int pvlencmp(const void , const void );
116			static void resettails(void);
117
118			void
119			pack(void)
120			{
121			struct devi *i;
122			int n;
123
124			/* Pack instances and make parent vectors. */
125			packdevi();
126
127			/*
128			* Now that we know what we have, find upper limits on space
129			* needed for the loc[] and pv[] tables, and find the longest
130			* single pvec. The loc and pv table sizes are bounded by
131			* what we would get if no packing occurred.
132			*/
133			locspace = pvecspace = 0;
134			for (i = alldevi; i != NULL; i = i->i_next) {
135			if (i->i_collapsed)
136			continue;
137			locspace += i->i_atattr->a_loclen;
138			n = i->i_pvlen + 1;
139			if (n > longest_pvec)
140			longest_pvec = n;
141			pvecspace += n;
142			}
143
144			/* Allocate and pack loc[]. */
145			locators.vec = ereallocarray(NULL, locspace, sizeof(*locators.vec));
146			locators.used = 0;
147			packlocs();
148
149			/* Allocate and pack pv[]. */
150			parents.vec = ereallocarray(NULL, pvecspace, sizeof(*parents.vec));
151			parents.used = 0;
152			packpvec();
153			}
154
155			/*
156			* Pack instances together wherever possible. When everything is
157			* packed, go back and set up the parents for each. We must do this
158			* on a second pass because during the first one, we do not know which,
159			* if any, of the parents will collapse during packing.
160			*/
161			void
162			packdevi(void)
163			{
164			struct devi i, l, *p;
165			struct deva *d;
166			int j, m, n;
167
168			packed = ereallocarray(NULL, ndevi + 1, sizeof *packed);
169			n = 0;
170			for (d = alldevas; d != NULL; d = d->d_next) {
171			/*
172			* For each instance of each attachment, add or collapse
173			* all its aliases.
174			*/
175			for (i = d->d_ihead; i != NULL; i = i->i_asame) {
176			m = n;
177			for (l = i; l != NULL; l = l->i_alias) {
178			/* Skip if we already handled this one. */
179			if (l->i_cfindex >= 0)
180			continue;
181			l->i_pvlen = 0;
182			l->i_pvoff = -1;
183			l->i_locoff = -1;
184			/* try to find an equivalent for l */
185			for (j = m; j < n; j++) {
186			p = packed[j];
187			if (sameas(l, p)) {
188			l->i_collapsed = 1;
189			l->i_cfindex = p->i_cfindex;
190			goto nextalias;
191			}
192			}
193			/* could not find a suitable alias */
194			l->i_collapsed = 0;
195			l->i_cfindex = n;
196			l->i_parents = emalloc(sizeof(*l->i_parents));
197			l->i_parents[0] = NULL;
198			packed[n++] = l;
199			nextalias:;
200			}
201			}
202			}
203			npacked = n;
204			packed[n] = NULL;
205			for (i = alldevi; i != NULL; i = i->i_next)
206			addparents(i, packed[i->i_cfindex]);
207			}
208
209			/*
210			* Return true if two aliases are "the same". In this case, they need
211			* to attach via the same attribute, have the same config flags, and
212			* have the same locators.
213			*/
214			static int
215			sameas(struct devi i1, struct devi i2)
216			{
217			const char p1, p2;
218
219			if (i1->i_atattr != i2->i_atattr)
220			return (0);
221			if (i1->i_cfflags != i2->i_cfflags)
222			return (0);
223			for (p1 = i1->i_locs, p2 = i2->i_locs; p1 == p2; p2++)
224			if (*p1++ == 0)
225			return (1);
226			return 0;
227			}
228
229			/*
230			* Add the parents associated with "src" to the (presumably uncollapsed)
231			* instance "dst".
232			*/
233			static void
234			addparents(struct devi src, struct devi dst)
235			{
236			struct nvlist *nv;
237			struct devi i, p, *q;
238			int j, n, old, new, ndup;
239
240			if (dst->i_collapsed)
241			panic("addparents() i_collapsed");
242
243			/* Collect up list of parents to add. */
244			if (src->i_at == NULL) /* none, because we are "at root" */
245			return;
246			if (src->i_atdev != NULL) {
247			n = nparents(NULL, src->i_atdev, src->i_atunit);
248			p = ereallocarray(NULL, n, sizeof *p);
249			if (n == 0)
250			return;
251			(void)nparents(p, src->i_atdev, src->i_atunit);
252			} else {
253			n = 0;
254			for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
255			n += nparents(NULL, nv->nv_ptr, src->i_atunit);
256			if (n == 0)
257			return;
258			p = ereallocarray(NULL, n, sizeof *p);
259			n = 0;
260			for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
261			n += nparents(p + n, nv->nv_ptr, src->i_atunit);
262			}
263			/* Now elide duplicates. */
264			ndup = 0;
265			for (j = 0; j < n; j++) {
266			i = p[j];
267			for (q = dst->i_parents; *q != NULL; q++) {
268			if (*q == i) {
269			ndup++;
270			p[j] = NULL;
271			break;
272			}
273			}
274			}
275			/* Finally, add all the non-duplicates. */
276			old = dst->i_pvlen;
277			new = old + (n - ndup);
278			if (old > new)
279			panic("addparents() old > new");
280			if (old == new) {
281			free(p);
282			return;
283			}
284			dst->i_parents = q = ereallocarray(dst->i_parents, new + 1, sizeof(*q));
285			dst->i_pvlen = new;
286			q[new] = NULL;
287			q += old;
288			for (j = 0; j < n; j++)
289			if (p[j] != NULL)
290			*q++ = p[j];
291			free(p);
292			}
293
294			/*
295			* Count up parents, and optionally store pointers to each.
296			*/
297			static int
298			nparents(struct devi *p, struct devbase dev, int unit)
299			{
300			struct devi i, l;
301			int n;
302
303			n = 0;
304			/* for each instance ... */
305			for (i = dev->d_ihead; i != NULL; i = i->i_bsame) {
306			/* ... take each un-collapsed alias */
307			for (l = i; l != NULL; l = l->i_alias) {
308			if (!l->i_collapsed &&
309			(unit == WILD \|\| unit == l->i_unit)) {
310			if (p != NULL)
311			*p++ = l;
312			n++;
313			}
314			}
315			}
316			return (n);
317			}
318
319			static void
320			packlocs(void)
321			{
322			struct devi *p, i;
323			int l, o;
324
325			qsort(packed, npacked, sizeof *packed, loclencmp);
326			for (p = packed; (i = *p) != NULL; p++) {
327			if ((l = i->i_atattr->a_loclen) > 0) {
328			o = findvec(i->i_locs, LOCHASH(i->i_locs[l - 1]), l,
329			samelocs, locators.used);
330			i->i_locoff = o < 0 ? addlocs(i->i_locs, l) : o;
331			} else
332			i->i_locoff = -1;
333			}
334			resettails();
335			}
336
337			static void
338			packpvec(void)
339			{
340			struct devi *p, i, **par;
341			int l, v, o;
342			short *vec;
343
344			vec = ereallocarray(NULL, longest_pvec, sizeof(*vec));
345			qsort(packed, npacked, sizeof *packed, pvlencmp);
346			for (p = packed; (i = *p) != NULL; p++) {
347			l = i->i_pvlen;
348			if (l > longest_pvec)
349			panic("packpvec");
350			par = i->i_parents;
351			for (v = 0; v < l; v++)
352			vec[v] = par[v]->i_cfindex;
353			if (l == 0 \|\| (o = findvec(vec, PVHASH(vec[l - 1]), l,
354			samepv, parents.used)) < 0)
355			o = addpv(vec, l);
356			i->i_pvoff = o;
357			}
358			free(vec);
359			resettails();
360			}
361
362			/*
363			* Return the index at which the given vector already exists, or -1
364			* if it is not anywhere in the current set. If we return -1, we assume
365			* our caller will add it at the end of the current set, and we make
366			* sure that next time, we will find it there.
367			*/
368			static int
369			findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
370			{
371			struct tails t, *hp;
372			int off;
373
374			hp = &tails[hash];
375			for (t = *hp; t != NULL; t = t->t_next) {
376			off = t->t_ends_at - len;
377			if (off >= 0 && (*cmp)(ptr, off, len))
378			return (off);
379			}
380			t = emalloc(sizeof(*t));
381			t->t_next = *hp;
382			*hp = t;
383			t->t_ends_at = nextplace + len;
384			return (-1);
385			}
386
387			/*
388			* Comparison function for locators.
389			*/
390			static int
391			samelocs(const void *ptr, int off, int len)
392			{
393			const char p, q;
394
395			for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;)
396			if (p++ != q++)
397			return (0); /* different */
398			return (1); /* same */
399			}
400
401			/*
402			* Add the given locators at the end of the global loc[] table.
403			*/
404			static int
405			addlocs(const char **locs, int len)
406			{
407			const char **p;
408			int ret;
409
410			ret = locators.used;
411			if ((locators.used = ret + len) > locspace)
412			panic("addlocs: overrun");
413			for (p = &locators.vec[ret]; --len >= 0;)
414			p++ = locs++;
415			return (ret);
416			}
417
418			/*
419			* Comparison function for qsort-by-locator-length, longest first.
420			* We rashly assume that subtraction of these lengths does not overflow.
421			*/
422			static int
423			loclencmp(const void a, const void b)
424			{
425			int l1, l2;
426
427			l1 = ((struct devi *)a)->i_atattr->a_loclen;
428			l2 = ((struct devi *)b)->i_atattr->a_loclen;
429			return (l2 - l1);
430			}
431
432			/*
433			* Comparison function for parent vectors.
434			*/
435			static int
436			samepv(const void *ptr, int off, int len)
437			{
438			short p, q;
439
440			for (p = &parents.vec[off], q = (short *)ptr; --len >= 0;)
441			if (p++ != q++)
442			return (0); /* different */
443			return (1); /* same */
444			}
445
446			/*
447			* Add the given parent vectors at the end of the global pv[] table.
448			*/
449			static int
450			addpv(short *pv, int len)
451			{
452			short *p;
453			int ret;
454			static int firstend = -1;
455
456			/*
457			* If the vector is empty, reuse the first -1. It will be
458			* there if there are any nonempty vectors at all, since we
459			* do the longest first. If there are no nonempty vectors,
460			* something is probably wrong, but we will ignore that here.
461			*/
462			if (len == 0 && firstend >= 0)
463			return (firstend);
464			len++; /* account for trailing -1 */
465			ret = parents.used;
466			if ((parents.used = ret + len) > pvecspace)
467			panic("addpv: overrun");
468			for (p = &parents.vec[ret]; --len > 0;)
469			p++ = pv++;
470			*p = -1;
471			if (firstend < 0)
472			firstend = parents.used - 1;
473			return (ret);
474			}
475
476			/*
477			* Comparison function for qsort-by-parent-vector-length, longest first.
478			* We rashly assume that subtraction of these lengths does not overflow.
479			*/
480			static int
481			pvlencmp(const void a, const void b)
482			{
483			int l1, l2;
484
485			l1 = ((struct devi *)a)->i_pvlen;
486			l2 = ((struct devi *)b)->i_pvlen;
487			return (l2 - l1);
488			}
489
490			static void
491			resettails(void)
492			{
493			struct tails *p, t, *next;
494			int i;
495
496			for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
497			for (t = *p; t != NULL; t = next) {
498			next = t->t_next;
499			free(t);
500			}
501			*p = NULL;
502			}
503			}