1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* MISCELLANEOUS UTILITY ROUTINES */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* Written by: Applegate, Bixby, Chvatal, and Cook */
23 /* Date: October 12, 1995 */
24 /* Date: September 28, 1997 */
25 /* April 7, 2003 (bico) */
26 /* */
27 /* EXPORTED FUNCTIONS: */
28 /* */
29 /* unsigned int CCutil_nextprime (unsigned int x) */
30 /* FINDS the smallest positive prime >= x */
31 /* */
32 /* int CCutil_our_gcd (int a, int b) */
33 /* COMPUTES gcd(a,b) */
34 /* -gcd(a,b) is always >= 0 */
35 /* -a and b can be negative, positive, or zero */
36 /* */
37 /* int CCutil_our_lcm (int a, int b) */
38 /* COMPUTES lcm(a,b) */
39 /* -lcm(a,b) is always >= 0 */
40 /* -a and b can be negative, positive, or zero */
41 /* */
42 /* char *CCutil_strchr (char *s, int c) */
43 /* RETURNS a pointer to the first occurrence of c in s, or NULL if c */
44 /* does not occur in s */
45 /* */
46 /* char *CCutil_strrchr (char *s, int c) */
47 /* RETURNS a pointer to the last occurrence of c in s, or NULL if c */
48 /* does not occur in s */
49 /* */
50 /* const char *CCutil_strchr_c (const char *s, int c) */
51 /* RETURNS a pointer to the first occurrence of c in s, or NULL if c */
52 /* does not occur in s. A variant for const strings. */
53 /* */
54 /* const char *CCutil_strrchr_c (const char *s, int c) */
55 /* RETURNS a pointer to the last occurrence of c in s, or NULL if c */
56 /* does not occur in s. A variant for const strings. */
57 /* */
58 /* char *CCutil_strdup (const char *s) */
59 /* RETURNS a pointer to a copy of s, allocated with CC_SAFE_MALLOC, */
60 /* or NULL if unable to allocate space for the string */
61 /* */
62 /* char *CCutil_strdup2 (const char *s) */
63 /* RETURNS a pointer to a copy of s up until the first whitespace, */
64 /* allocated with CC_SAFE_MALLOC, or NULL if unable to allocate space */
65 /* for the string. */
66 /* */
67 /* void CCutil_readstr (FILE *f, char *s, int len) */
68 /* READS a string from f into s. The string is terminated by a */
69 /* whitespace character (space, tab, newline) or EOF. The entire */
70 /* string including the terminating character is read, but only at */
71 /* most len characters are stored in s, including the terminating */
72 /* NULL. */
73 /* */
74 /* void CCutil_printlabel (void) */
75 /* PRINTS information identifying a machine */
76 /* */
77 /* int CCutil_print_command (int ac, char **av) */
78 /* PRINTS the command line */
79 /* */
80 /****************************************************************************/
81
82 #include "machdefs.h"
83 #include "macrorus.h"
84 #include "util.h"
85
86
87 static int
88 isprime (unsigned int x);
89
90
CCutil_nextprime(unsigned int x)91 unsigned int CCutil_nextprime (unsigned int x)
92 {
93 if (x < 3) return 3;
94 x |= 1;
95 while (!isprime (x)) x += 2;
96 return x;
97 }
98
isprime(unsigned int p)99 static int isprime (unsigned int p)
100 {
101 unsigned int i;
102
103 if ((p&1) == 0) return 0;
104 for (i=3; i*i<=p; i+=2) {
105 if (p%i == 0) return 0;
106 }
107 return 1;
108 }
109
CCutil_our_gcd(int a,int b)110 int CCutil_our_gcd (int a, int b)
111 {
112 int c;
113
114 if (a < 0) a = -a;
115 if (b < 0) b = -b;
116 if (a > b) CC_SWAP (a, b, c);
117
118 while (a) {
119 c = b % a;
120 b = a;
121 a = c;
122 }
123 return b;
124 }
125
CCutil_our_lcm(int a,int b)126 int CCutil_our_lcm (int a, int b)
127 {
128 int c;
129
130 if (a < 0) a = -a;
131 if (b < 0) b = -b;
132
133 c = CCutil_our_gcd (a, b);
134
135 return (a/c) * b;
136 }
137
CCutil_strchr(char * s,int c)138 char *CCutil_strchr (char *s, int c)
139 {
140 while (*s) {
141 if (*s == c) return s;
142 s++;
143 }
144 return (char *) NULL;
145 }
146
CCutil_strchr_c(const char * s,int c)147 const char *CCutil_strchr_c (const char *s, int c)
148 {
149 while (*s) {
150 if (*s == c) return s;
151 s++;
152 }
153 return (char *) NULL;
154 }
155
CCutil_strrchr(char * s,int c)156 char *CCutil_strrchr (char *s, int c)
157 {
158 char *l = (char *) NULL;
159
160 while (*s) {
161 if (*s == c) l = s;
162 s++;
163 }
164 return l;
165 }
166
CCutil_strrchr_c(const char * s,int c)167 const char *CCutil_strrchr_c (const char *s, int c)
168 {
169 const char *l = (char *) NULL;
170
171 while (*s) {
172 if (*s == c) l = s;
173 s++;
174 }
175 return l;
176 }
177
CCutil_strdup(const char * s)178 char *CCutil_strdup (const char *s)
179 {
180 char *p = CC_SAFE_MALLOC (strlen(s)+1, char);
181
182 if (p == (char *) NULL) {
183 fprintf (stderr, "Out of memory in CCutil_strdup\n");
184 return (char *) NULL;
185 }
186 strcpy (p, s);
187 return p;
188 }
189
CCutil_strdup2(const char * s)190 char *CCutil_strdup2 (const char *s)
191 {
192 char *p;
193 int len;
194
195 for (len = 0; s[len]; len++) {
196 if (s[len] == ' ' || s[len] == '\r' || s[len] == '\t' ||
197 s[len] == '\n') {
198 break;
199 }
200 }
201
202 p = CC_SAFE_MALLOC (len+1, char);
203
204 if (p == (char *) NULL) {
205 fprintf (stderr, "Out of memory in CCutil_strdup2\n");
206 return (char *) NULL;
207 }
208 strncpy (p, s, len);
209 p[len] = '\0';
210
211 return p;
212 }
213
CCutil_readstr(FILE * f,char * s,int len)214 void CCutil_readstr (FILE *f, char *s, int len)
215 {
216 int c;
217
218 while ((c = getc (f)) != EOF && c != ' ' && c != '\t' && c != '\r' &&
219 c != '\n') {
220 if (len > 1) {
221 *s++ = c;
222 len--;
223 }
224 }
225 *s = '\0';
226 }
227
CCutil_printlabel(void)228 void CCutil_printlabel (void)
229 {
230 #ifdef CC_NETREADY
231 char buf[1024];
232
233 gethostname (buf, 1024);
234 printf ("Host: %s Current process id: %d\n", buf, (int) getpid());
235 fflush (stdout);
236 #else
237 printf ("No label - need function to non-NETREADY machines\n");
238 fflush (stdout);
239 #endif
240 }
241
CCutil_print_command(int ac,char ** av)242 int CCutil_print_command (int ac, char **av)
243 {
244 int rval = 0;
245 int i, cmdlen = 0;
246 char *cmdout = (char *) NULL;
247
248 for (i=0; i<ac; i++) {
249 cmdlen += strlen(av[i]) + 1;
250 }
251 cmdout = CC_SAFE_MALLOC (cmdlen, char);
252 CCcheck_NULL (cmdout, "out of memory in print_command");
253
254 cmdlen = 0;
255 for (i=0; i<ac; i++) {
256 strcpy (cmdout + cmdlen, av[i]);
257 cmdlen += strlen(av[i]);
258 cmdout[cmdlen] = ' ';
259 cmdlen++;
260 }
261 cmdout[cmdlen-1] = '\0';
262 printf ("%s\n", cmdout); fflush (stdout);
263
264 CLEANUP:
265
266 CC_IFFREE (cmdout, char);
267 return rval;
268 }
269
270