2 * misc.c: miscellaneous useful items
9 return s
+ 1 + strlen(s
);
21 s
= snew(struct stackTag
);
29 void stk_free(stack s
) {
34 void stk_push(stack s
, void *item
) {
35 if (s
->size
<= s
->sp
) {
37 s
->data
= sresize(s
->data
, s
->size
, void *);
39 s
->data
[s
->sp
++] = item
;
42 void *stk_pop(stack s
) {
44 return s
->data
[--s
->sp
];
49 void *stk_top(stack s
) {
51 return s
->data
[s
->sp
-1];
57 * Small routines to amalgamate a string from an input source.
59 const rdstring empty_rdstring
= {0, 0, NULL
};
60 const rdstringc empty_rdstringc
= {0, 0, NULL
};
62 void rdadd(rdstring
*rs
, wchar_t c
) {
63 if (rs
->pos
>= rs
->size
-1) {
64 rs
->size
= rs
->pos
+ 128;
65 rs
->text
= sresize(rs
->text
, rs
->size
, wchar_t);
67 rs
->text
[rs
->pos
++] = c
;
68 rs
->text
[rs
->pos
] = 0;
70 void rdadds(rdstring
*rs
, wchar_t const *p
) {
72 if (rs
->pos
>= rs
->size
- len
) {
73 rs
->size
= rs
->pos
+ len
+ 128;
74 rs
->text
= sresize(rs
->text
, rs
->size
, wchar_t);
76 ustrcpy(rs
->text
+ rs
->pos
, p
);
79 wchar_t *rdtrim(rdstring
*rs
) {
80 rs
->text
= sresize(rs
->text
, rs
->pos
+ 1, wchar_t);
84 void rdaddc(rdstringc
*rs
, char c
) {
85 if (rs
->pos
>= rs
->size
-1) {
86 rs
->size
= rs
->pos
+ 128;
87 rs
->text
= sresize(rs
->text
, rs
->size
, char);
89 rs
->text
[rs
->pos
++] = c
;
90 rs
->text
[rs
->pos
] = 0;
92 void rdaddsc(rdstringc
*rs
, char const *p
) {
94 if (rs
->pos
>= rs
->size
- len
) {
95 rs
->size
= rs
->pos
+ len
+ 128;
96 rs
->text
= sresize(rs
->text
, rs
->size
, char);
98 strcpy(rs
->text
+ rs
->pos
, p
);
101 char *rdtrimc(rdstringc
*rs
) {
102 rs
->text
= sresize(rs
->text
, rs
->pos
+ 1, char);
106 static int compare_wordlists_literally(word
*a
, word
*b
) {
109 if (a
->type
!= b
->type
)
110 return (a
->type
< b
->type ?
-1 : +1); /* FIXME? */
112 if ((t
!= word_Normal
&& t
!= word_Code
&&
113 t
!= word_WeakCode
&& t
!= word_Emph
) ||
116 if (a
->text
&& b
->text
) {
117 c
= ustricmp(a
->text
, b
->text
);
121 c
= compare_wordlists_literally(a
->alt
, b
->alt
);
127 wchar_t *ap
= a
->text
, *bp
= b
->text
;
129 wchar_t ac
= *ap
, bc
= *bp
;
131 return (ac
< bc ?
-1 : +1);
132 if (!*++ap
&& a
->next
&& a
->next
->type
== t
&& !a
->next
->alt
)
133 a
= a
->next
, ap
= a
->text
;
134 if (!*++bp
&& b
->next
&& b
->next
->type
== t
&& !b
->next
->alt
)
135 b
= b
->next
, bp
= b
->text
;
138 return (*ap ?
+1 : -1);
145 return (a ?
+1 : -1);
150 int compare_wordlists(word
*a
, word
*b
) {
152 * First we compare only the alphabetic content of the word
153 * lists, with case not a factor. If that comes out equal,
154 * _then_ we compare the word lists literally.
164 pos
[0].i
= pos
[1].i
= 0;
168 * Find the next alphabetic character in each word list.
172 for (k
= 0; k
< 2; k
++) {
174 * Advance until we hit either an alphabetic character
175 * or the end of the word list.
179 /* End of word list. */
182 } else if (!pos
[k
].w
->text
|| !pos
[k
].w
->text
[pos
[k
].i
]) {
183 /* No characters remaining in this word; move on. */
184 pos
[k
].w
= pos
[k
].w
->next
;
186 } else if (!uisalpha(pos
[k
].w
->text
[pos
[k
].i
])) {
187 /* This character isn't alphabetic; move on. */
190 /* We have an alphabetic! Lowercase it and continue. */
191 pos
[k
].c
= utolower(pos
[k
].w
->text
[pos
[k
].i
]);
211 if (pos
[0].c
< pos
[1].c
)
213 else if (pos
[0].c
> pos
[1].c
)
218 break; /* they're equal */
225 * If we reach here, the strings were alphabetically equal, so
226 * compare in more detail.
228 return compare_wordlists_literally(a
, b
);
231 void mark_attr_ends(word
*words
)
236 for (w
= words
; w
; w
= w
->next
) {
237 if (isattr(w
->type
)) {
238 int before
= (wp
&& isattr(wp
->type
) &&
239 sameattr(wp
->type
, w
->type
));
240 int after
= (w
->next
&& isattr(w
->next
->type
) &&
241 sameattr(w
->next
->type
, w
->type
));
243 (after ? attr_Always
: attr_Last
) :
244 (after ? attr_First
: attr_Only
));
251 * This function implements the optimal paragraph wrapping
252 * algorithm, pretty much as used in TeX. A cost function is
253 * defined for each line of the wrapped paragraph (typically some
254 * convex function of the difference between the line's length and
255 * its desired length), and a dynamic programming approach is used
256 * to optimise globally across all possible layouts of the
257 * paragraph to find the one with the minimum total cost.
259 * The function as implemented here gives a choice of two options
260 * for the cost function:
262 * - If `natural_space' is zero, then the algorithm attempts to
263 * make each line the maximum possible width (either `width' or
264 * `subsequentwidth' depending on whether it's the first line of
265 * the paragraph or not), and the cost function is simply the
266 * square of the unused space at the end of each line. This is a
267 * simple mechanism suitable for use in fixed-pitch environments
268 * such as plain text displayed on a terminal.
270 * - However, if `natural_space' is positive, the algorithm
271 * assumes the medium is fully graphical and that the width of
272 * space characters can be adjusted finely, and it attempts to
273 * make each _space character_ the width given in
274 * `natural_space'. (The provided width function should return
275 * the _minimum_ acceptable width of a space character in this
276 * case.) Therefore, the cost function for a line is dependent
277 * on the number of spaces on that line as well as the amount by
278 * which the line width differs from the optimum.
280 wrappedline
*wrap_para(word
*text
, int width
, int subsequentwidth
,
281 int (*widthfn
)(void *, word
*), void *ctx
,
283 wrappedline
*head
= NULL
, **ptr
= &head
;
284 int nwords
, wordsize
;
295 * Break the line up into wrappable components.
297 nwords
= wordsize
= 0;
300 if (nwords
>= wordsize
) {
301 wordsize
= nwords
+ 64;
302 wrapwords
= srealloc(wrapwords
, wordsize
* sizeof(*wrapwords
));
304 wrapwords
[nwords
].width
= 0;
305 wrapwords
[nwords
].begin
= text
;
307 wrapwords
[nwords
].width
+= widthfn(ctx
, text
);
308 wrapwords
[nwords
].end
= text
->next
;
309 if (text
->next
&& (text
->next
->type
== word_WhiteSpace
||
310 text
->next
->type
== word_EmphSpace
||
315 if (text
&& text
->next
&& (text
->next
->type
== word_WhiteSpace
||
316 text
->next
->type
== word_EmphSpace
)) {
317 wrapwords
[nwords
].spacewidth
= widthfn(ctx
, text
->next
);
320 wrapwords
[nwords
].spacewidth
= 0;
328 * Perform the dynamic wrapping algorithm: work backwards from
329 * nwords-1, determining the optimal wrapping for each terminal
330 * subsequence of the paragraph.
332 for (i
= nwords
; i
-- ;) {
336 int linelen
= 0, spacewidth
= 0, minspacewidth
= 0;
338 int thiswidth
= (i
== 0 ? width
: subsequentwidth
);
342 while (i
+j
< nwords
) {
344 * See what happens if we put j+1 words on this line.
348 minspacewidth
= spacewidth
;
350 linelen
+= spacewidth
+ wrapwords
[i
+j
].width
;
351 spacewidth
= wrapwords
[i
+j
].spacewidth
;
353 if (linelen
> thiswidth
) {
355 * If we're over the width limit, abandon ship,
356 * _unless_ there is no best-effort yet (which will
357 * only happen if the first word is too long all by
365 * Compute the cost of this line. The method of doing
366 * this differs hugely depending on whether
367 * natural_space is nonzero or not.
370 if (!nspaces
&& linelen
> thiswidth
) {
372 * Special case: if there are no spaces at all
373 * on the line because one single word is too
374 * long for its line, cost is zero because
375 * there's nothing we can do about it anyway.
379 int shortfall
= thiswidth
- linelen
;
380 int spaceextra
= shortfall
/ (nspaces ? nspaces
: 1);
381 int spaceshortfall
= natural_space
-
382 (minspacewidth
+ spaceextra
);
384 if (i
+j
== nwords
&& spaceshortfall
< 0) {
386 * Special case: on the very last line of
387 * the paragraph, we don't score penalty
388 * points for having to _stretch_ the line,
389 * since we won't stretch it anyway.
390 * However, we score penalties as normal
391 * for having to squeeze it.
396 * Squaring this number is tricky since
397 * it's liable to be quite big. Let's
398 * divide it through by 256.
400 int x
= spaceshortfall
>> 8;
401 int xf
= spaceshortfall
& 0xFF;
404 * Not counting strange variable-fixed-
405 * point oddities, we are computing
407 * (x+xf)^2 = x^2 + 2*x*xf + xf*xf
409 * except that _our_ xf is 256 times the
414 cost
+= (2 * x
* xf
) >> 8;
420 * Special case: if we're at the very end of the
421 * paragraph, we don't score penalty points for the
422 * white space left on the line.
426 cost
= (thiswidth
-linelen
) * (thiswidth
-linelen
);
431 * Add in the cost of wrapping all lines after this
435 cost
+= wrapwords
[i
+j
].cost
;
438 * We compare bestcost >= cost, not bestcost > cost,
439 * because in cases where the costs are identical we
440 * want to try to look like the greedy algorithm,
441 * because readers are likely to have spent a lot of
442 * time looking at greedy-wrapped paragraphs and
443 * there's no point violating the Principle of Least
444 * Surprise if it doesn't actually gain anything.
446 if (best
< 0 || bestcost
>= cost
) {
452 * Now we know the optimal answer for this terminal
453 * subsequence, so put it in wrapwords.
455 wrapwords
[i
].cost
= bestcost
;
456 wrapwords
[i
].nwords
= best
;
460 * We've wrapped the paragraph. Now build the output
461 * `wrappedline' list.
465 wrappedline
*w
= snew(wrappedline
);
470 n
= wrapwords
[i
].nwords
;
471 w
->begin
= wrapwords
[i
].begin
;
472 w
->end
= wrapwords
[i
+n
-1].end
;
475 * Count along the words to find nspaces and shortfall.
478 w
->shortfall
= width
;
479 for (j
= 0; j
< n
; j
++) {
480 w
->shortfall
-= wrapwords
[i
+j
].width
;
481 if (j
< n
-1 && wrapwords
[i
+j
].spacewidth
) {
483 w
->shortfall
-= wrapwords
[i
+j
].spacewidth
;
494 void wrap_free(wrappedline
*w
) {
496 wrappedline
*t
= w
->next
;
502 void cmdline_cfg_add(paragraph
*cfg
, char *string
)
505 int upos
, ulen
, pos
, len
;
508 while (cfg
->keyword
[ulen
])
509 ulen
+= 1 + ustrlen(cfg
->keyword
+ulen
);
511 while (cfg
->origkeyword
[len
])
512 len
+= 1 + strlen(cfg
->origkeyword
+len
);
514 ustring
= ufroma_locale_dup(string
);
517 ulen
+= 2 + ustrlen(ustring
);
518 cfg
->keyword
= sresize(cfg
->keyword
, ulen
, wchar_t);
519 ustrcpy(cfg
->keyword
+upos
, ustring
);
520 cfg
->keyword
[ulen
-1] = L
'\0';
523 len
+= 2 + strlen(string
);
524 cfg
->origkeyword
= sresize(cfg
->origkeyword
, len
, char);
525 strcpy(cfg
->origkeyword
+pos
, string
);
526 cfg
->origkeyword
[len
-1] = '\0';
531 paragraph
*cmdline_cfg_new(void)
536 memset(p
, 0, sizeof(*p
));
537 p
->type
= para_Config
;
539 p
->fpos
.filename
= "<command line>";
540 p
->fpos
.line
= p
->fpos
.col
= -1;
541 p
->keyword
= ustrdup(L
"\0");
542 p
->origkeyword
= dupstr("\0");
547 paragraph
*cmdline_cfg_simple(char *string
, ...)
553 p
= cmdline_cfg_new();
554 cmdline_cfg_add(p
, string
);
556 va_start(ap
, string
);
557 while ((s
= va_arg(ap
, char *)) != NULL
)
558 cmdline_cfg_add(p
, s
);