1 /* $Id: ordvst.c,v 1.21 2020-10-13 04:47:53 phil Exp $ */
2
3 /*
4 * ordvst.c
5 * Martin. D. Waller July 28th, 1994
6 *
7 * ORDVST is used by the SNOBOL4 system to sort the variables
8 * into alphabetical order prior to dumping. It does this by
9 * working down the chained list or string structures saving the
10 * address of each descriptor found. Once complete the list is
11 * sorted and the chain list of string structures re-written.
12 *
13 * Integrated, simplified, 8/1/94 -phil
14 *
15 */
16
17 #ifdef HAVE_CONFIG_H
18 #include "config.h"
19 #endif /* HAVE_CONFIG_H defined */
20
21 #include <stdlib.h> /* for malloc */
22 #include <stdio.h>
23
24 #include "h.h"
25 #include "snotypes.h"
26 #include "macros.h"
27 #include "lib.h"
28 #include "str.h"
29
30 #include "equ.h"
31 #include "res.h"
32 #include "data.h"
33
34 #ifdef ORDVST_DEBUG
35 /* PLB: dump a descriptor */
36 static void
dump_descr(struct descr * vp)37 dump_descr(struct descr *vp)
38 {
39 printf("0x%08x v: 0x%08x f: 0x%02x t: 0x%06x\n",
40 vp, D_A(vp), D_F(vp), D_V(vp));
41 }
42
43 /*
44 * ordvst_dnv(nv)
45 *
46 * This routine is callable to dump a natural variable. It is intended
47 * as a pure aid to debugging and nothing more.
48 *
49 */
50 static void
ordvst_dnv(nv)51 ordvst_dnv(nv)
52 struct descr *nv;
53 {
54 struct descr *vd; /* Value field descriptor */
55 struct descr *ad; /* Attribute field descriptor */
56 struct descr *ld; /* Link field descriptor */
57 char *n;
58
59 vd = nv + 1; /* Set up the value descriptor */
60 ad = nv + ATTRIB/DESCR; /* Set up the attribute descriptor */
61 ld = nv + LNKFLD/DESCR; /* Set up the link descriptor */
62 n = ((char *) nv) + BCDFLD; /* Pointer to the name itself */
63 printf("**** Natural Variable -> %.*s\n",D_V(nv),n);
64 printf("**** nv @"); dump_descr(nv);
65 printf("**** value @"); dump_descr(vd);
66 printf("**** attrib @"); dump_descr(ad);
67 printf("**** link @"); dump_descr(ld);
68 printf("\n");
69 }
70 #endif /* ORDVST_DEBUG defined */
71
72 /*
73 * ordvst_strcmp(s1,l1,s2,l2)
74 *
75 * This routine is called to compare two strings passed by reference
76 * along with a length argument. It will return -1, 0, +1 to indicate
77 * if s1 < s2, s1 = s2, or s1 > s2.
78 */
79 static int
ordvst_strcmp(char * s1,int l1,char * s2,int l2)80 ordvst_strcmp(char *s1, int l1, char *s2, int l2) {
81 int i;
82
83 i = l1;
84 if (l2 < i)
85 i = l2;
86
87 while (i-- > 0) { /* for common portion */
88 if (*s1 != *s2) /* If the characters are different */
89 return (*s1 - *s2); /* Return the difference */
90 s1++;
91 s2++;
92 }
93
94 /* strings are identical, or one is a prefix of the other */
95 return l1 - l2; /* shorter string is "less" */
96 }
97
98 /*
99 * ordvst_cmp(d1,d2)
100 *
101 * This routine is callable by qsort to compare the two descriptors.
102 * It will return the result of ordvst_strcmp defined above.
103 *
104 */
105 static int
ordvst_cmp(const void * v1,const void * v2)106 ordvst_cmp(const void *v1, const void *v2) {
107 int l1,l2; /* Length variables */
108 char *n1, *n2; /* Name pointers */
109 const struct descr **d1 = (const struct descr **)v1;
110 const struct descr **d2 = (const struct descr **)v2;
111
112 l1 = D_V(*d1); /* Set the first length */
113 l2 = D_V(*d2); /* Set the second length */
114 n1 = ((char *) *d1) + BCDFLD; /* Set the first name pointer */
115 n2 = ((char *) *d2) + BCDFLD; /* Set the second name pointer */
116
117 return (ordvst_strcmp(n1,l1,n2,l2)); /* Compare the two */
118 }
119
120 /*
121 * ORDVST()
122 *
123 * This is the main entry point from the SNOBOL4 system. It will sort
124 * the string structures into order. Should the sort fail due to a lack
125 * of dynamic memory then the sort is not performed and the original
126 * list of string structures will be left unchanged.
127 */
128 void
ordvst(void)129 ordvst(void) {
130 int bc; /* Bin count */
131 int i; /* Looping variable */
132 struct descr *bd; /* Descriptor from the bins */
133 struct descr *lnkd; /* Link field descriptor */
134 struct descr **vars; /* array of var ptrs */
135 struct descr **vp; /* pointer to next stry to fill */
136 int nvars;
137
138 bd = (struct descr *) OBSTRT; /* Locate the first bin */
139 #ifdef ORDVST_DEBUG
140 printf("**** OBSTRT @ %#08x, %d buckets\n", bd, OBSIZ);
141 #endif /* ORDVST_DEBUG defined */
142
143 /* first pass; count number of vars to allocate pointers for */
144 nvars = 0;
145 for (bc = 0; bc < OBSIZ; bc++, bd++) { /* For all the bins we have */
146 struct descr *nvcd; /* Natural variable chain */
147 struct descr *vd; /* Value field descriptor */
148
149 /* Pick up the start of the chain */
150 nvcd = (struct descr *) D_A(bd);
151
152 #ifdef ORDVST_DEBUG
153 if (nvcd != NULL) {
154 printf("**** OBSTRT[%d] @", bc); dump_descr(bd);
155 }
156 #endif /* ORDVST_DEBUG defined */
157 while (nvcd != NULL) { /* Until the end of the chain */
158 vd = nvcd + 1; /* Set up the value descriptor */
159
160 /* don't count strings that aren't natural variables!! */
161 if (D_V(vd) != S || D_F(vd) != 0) {
162 #ifdef ORDVST_DEBUG
163 ordvst_dnv(nvcd); /* Dump the natural variable */
164 #endif /* ORDVST_DEBUG defined */
165 nvars++;
166 }
167 /* Pick up the link descriptor */
168 nvcd = (struct descr *) D_A(nvcd + LNKFLD/DESCR);
169 } /* while nvcd */
170 } /* for each bucket */
171
172 if (nvars == 0) /* bloody unlikely */
173 return;
174
175 /* allocate array of pointers to variables */
176 vars = (struct descr **) malloc( nvars * sizeof(struct descr *) );
177 if (vars == NULL)
178 return;
179 vp = vars; /* set up pointer to array */
180
181 /* pass two; fill in array */
182 bd = (struct descr *) OBSTRT; /* Locate the first bin */
183 for (bc = 0; bc < OBSIZ; bc++, bd++) { /* For all the bins we have */
184 struct descr *nvcd; /* Natural variable chain */
185 struct descr *vd; /* Value field descriptor */
186
187 /* Pick up the start of the chain */
188 nvcd = (struct descr *) D_A(bd);
189
190 while (nvcd != 0) { /* Until the end of the chain */
191 vd = nvcd + 1; /* Set up the value descriptor */
192
193 /* don't save strings that aren't natural variables!! */
194 if (D_V(vd) != S || D_F(vd) != 0) {
195 *vp++ = nvcd; /* append to array */
196 }
197 lnkd = nvcd + LNKFLD/DESCR; /* Pick up the link descriptor */
198 nvcd = (struct descr *) D_A(lnkd); /* Move down the chain */
199 } /* while nvcd */
200 } /* for each bucket */
201
202 #ifdef ORDVST_DEBUG
203 printf("**** Sorting\n"); /* Say that we are sorting */
204 #endif /* ORDVST_DEBUG defined */
205
206 qsort((void *) vars, nvars, sizeof(struct descr *), ordvst_cmp);
207
208 #ifdef ORDVST_DEBUG
209 printf("**** After Sorting\n\n");
210 for (i = 0, vp = vars; i < nvars; i++, vp++) { /* for all entries */
211 ordvst_dnv(*vp);
212 }
213 #endif /* ORDVST_DEBUG defined */
214
215 /* null out entire hash table */
216 bzero( OBSTRT, OBSIZ * DESCR );
217
218 /* link variables together in sorted order */
219 vp = vars;
220 for (i = nvars; i-- > 0; ) {
221 lnkd = *vp++ + LNKFLD/DESCR; /* point to var link field */
222
223 if (i > 0)
224 D_A(lnkd) = (int_t) *vp; /* point to next var */
225 else
226 D_A(lnkd) = 0; /* End of the list */
227 } /* for all entries */
228
229 /* set up first bin to point to sorted list */
230 D_A(OBSTRT) = (int_t) vars[0];
231
232 free(vars);
233 }
234
235
236