1 /****************************************************************************
2  * Copyright 2018-2020,2021 Thomas E. Dickey                                *
3  * Copyright 2017 Free Software Foundation, Inc.                            *
4  *                                                                          *
5  * Permission is hereby granted, free of charge, to any person obtaining a  *
6  * copy of this software and associated documentation files (the            *
7  * "Software"), to deal in the Software without restriction, including      *
8  * without limitation the rights to use, copy, modify, merge, publish,      *
9  * distribute, distribute with modifications, sublicense, and/or sell       *
10  * copies of the Software, and to permit persons to whom the Software is    *
11  * furnished to do so, subject to the following conditions:                 *
12  *                                                                          *
13  * The above copyright notice and this permission notice shall be included  *
14  * in all copies or substantial portions of the Software.                   *
15  *                                                                          *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
19  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
20  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
21  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
22  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
23  *                                                                          *
24  * Except as contained in this notice, the name(s) of the above copyright   *
25  * holders shall not be used in advertising or otherwise to promote the     *
26  * sale, use or other dealings in this Software without prior written       *
27  * authorization.                                                           *
28  ****************************************************************************/
29 
30 /****************************************************************************
31  *  Author: Thomas E. Dickey                                                *
32  ****************************************************************************/
33 
34 /* new_pair.c
35  *
36  * New color-pair functions, alloc_pair and free_pair
37  */
38 
39 #define NEW_PAIR_INTERNAL 1
40 #include <curses.priv.h>
41 
42 #ifndef CUR
43 #define CUR SP_TERMTYPE
44 #endif
45 
46 #ifdef USE_TERM_DRIVER
47 #define MaxColors      InfoOf(SP_PARM).maxcolors
48 #else
49 #define MaxColors      max_colors
50 #endif
51 
52 #if NCURSES_EXT_COLORS
53 
54 /* fix redefinition versys tic.h */
55 #undef entry
56 #define entry my_entry
57 #undef ENTRY
58 #define ENTRY my_ENTRY
59 
60 #include <search.h>
61 
62 #endif
63 
64 MODULE_ID("$Id: new_pair.c,v 1.21 2021/02/14 00:17:09 tom Exp $")
65 
66 #if NCURSES_EXT_COLORS
67 
68 #ifdef NEW_PAIR_DEBUG
69 
70 static int
71 prev_len(SCREEN *sp, int pair)
72 {
73     int result = 1;
74     int base = pair;
75     colorpair_t *list = sp->_color_pairs;
76     while (list[pair].prev != base) {
77 	result++;
78 	pair = list[pair].prev;
79     }
80     return result;
81 }
82 
83 static int
84 next_len(SCREEN *sp, int pair)
85 {
86     int result = 1;
87     int base = pair;
88     colorpair_t *list = sp->_color_pairs;
89     while (list[pair].next != base) {
90 	result++;
91 	pair = list[pair].next;
92     }
93     return result;
94 }
95 
96 /*
97  * Trace the contents of LRU color-pairs.
98  */
99 static void
100 dumpit(SCREEN *sp, int pair, const char *tag)
101 {
102     colorpair_t *list = sp->_color_pairs;
103     char bigbuf[256 * 20];
104     char *p = bigbuf;
105     int n;
106     size_t have = sizeof(bigbuf);
107 
108     _nc_STRCPY(p, tag, have);
109     for (n = 0; n < sp->_pair_limit; ++n) {
110 	if (list[n].mode != cpFREE) {
111 	    p += strlen(p);
112 	    if ((size_t) (p - bigbuf) + 50 > have)
113 		break;
114 	    _nc_SPRINTF(p, _nc_SLIMIT(have - (p - bigbuf))
115 			" %d%c(%d,%d)",
116 			n, n == pair ? '@' : ':', list[n].next, list[n].prev);
117 	}
118     }
119     T(("(%d/%d) %ld - %s",
120        next_len(sp, 0),
121        prev_len(sp, 0),
122        strlen(bigbuf), bigbuf));
123 
124     if (next_len(sp, 0) != prev_len(sp, 0)) {
125 	endwin();
126 	ExitProgram(EXIT_FAILURE);
127     }
128 }
129 #else
130 #define dumpit(sp, pair, tag)	/* nothing */
131 #endif
132 
133 static int
134 compare_data(const void *a, const void *b)
135 {
136     const colorpair_t *p = (const colorpair_t *) a;
137     const colorpair_t *q = (const colorpair_t *) b;
138     return ((p->fg == q->fg)
139 	    ? (p->bg - q->bg)
140 	    : (p->fg - q->fg));
141 }
142 
143 static int
144 _nc_find_color_pair(SCREEN *sp, int fg, int bg)
145 {
146     colorpair_t find;
147     int result = -1;
148 
149     find.fg = fg;
150     find.bg = bg;
151     if (sp != 0) {
152 	void *pp;
153 	if ((pp = tfind(&find, &sp->_ordered_pairs, compare_data)) != 0) {
154 	    colorpair_t *temp = *(colorpair_t **) pp;
155 	    result = (int) (temp - sp->_color_pairs);
156 	}
157     }
158     return result;
159 }
160 
161 static void
162 delink_color_pair(SCREEN *sp, int pair)
163 {
164     colorpair_t *list = sp->_color_pairs;
165     int prev = list[pair].prev;
166     int next = list[pair].next;
167 
168     /* delink this from its current location */
169     if (list[prev].next == pair &&
170 	list[next].prev == pair) {
171 	list[prev].next = next;
172 	list[next].prev = prev;
173 	dumpit(sp, pair, "delinked");
174     }
175 }
176 
177 /*
178  * Discard all nodes in the fast-index.
179  */
180 NCURSES_EXPORT(void)
181 _nc_free_ordered_pairs(SCREEN *sp)
182 {
183     if (sp && sp->_ordered_pairs && sp->_pair_alloc) {
184 	int n;
185 	for (n = 0; n < sp->_pair_alloc; ++n) {
186 	    tdelete(&sp->_color_pairs[n], &sp->_ordered_pairs, compare_data);
187 	}
188     }
189 }
190 
191 /*
192  * Use this call to update the fast-index when modifying an entry in the color
193  * pair table.
194  */
195 NCURSES_EXPORT(void)
196 _nc_reset_color_pair(SCREEN *sp, int pair, colorpair_t * next)
197 {
198     colorpair_t *last;
199 
200     if (ValidPair(sp, pair)) {
201 	bool used;
202 
203 	ReservePairs(sp, pair);
204 	last = &(sp->_color_pairs[pair]);
205 	delink_color_pair(sp, pair);
206 	if (last->mode > cpFREE &&
207 	    (last->fg != next->fg || last->bg != next->bg)) {
208 	    /* remove the old entry from fast index */
209 	    tdelete(last, &sp->_ordered_pairs, compare_data);
210 	    used = FALSE;
211 	} else {
212 	    used = (last->mode != cpFREE);
213 	}
214 	if (!used) {
215 	    /* create a new entry in fast index */
216 	    *last = *next;
217 	    tsearch(last, &sp->_ordered_pairs, compare_data);
218 	}
219     }
220 }
221 
222 /*
223  * Use this call to relink the newest pair to the front of the list, keeping
224  * "0" first.
225  */
226 NCURSES_EXPORT(void)
227 _nc_set_color_pair(SCREEN *sp, int pair, int mode)
228 {
229     if (ValidPair(sp, pair)) {
230 	colorpair_t *list = sp->_color_pairs;
231 	dumpit(sp, pair, "SET_PAIR");
232 	list[0].mode = cpKEEP;
233 	if (list[pair].mode <= cpFREE)
234 	    sp->_pairs_used++;
235 	list[pair].mode = mode;
236 	if (list[0].next != pair) {
237 	    /* link it at the front of the list */
238 	    list[pair].next = list[0].next;
239 	    list[list[pair].next].prev = pair;
240 	    list[pair].prev = 0;
241 	    list[0].next = pair;
242 	}
243 	dumpit(sp, pair, "...after");
244     }
245 }
246 
247 /*
248  * If we reallocate the color-pair array, we have to adjust the fast-index.
249  */
250 NCURSES_EXPORT(void)
251 _nc_copy_pairs(SCREEN *sp, colorpair_t * target, colorpair_t * source, int length)
252 {
253     int n;
254     for (n = 0; n < length; ++n) {
255 	void *find = tfind(source + n, &sp->_ordered_pairs, compare_data);
256 	if (find != 0) {
257 	    tdelete(source + n, &sp->_ordered_pairs, compare_data);
258 	    tsearch(target + n, &sp->_ordered_pairs, compare_data);
259 	}
260     }
261 }
262 
263 NCURSES_EXPORT(int)
264 NCURSES_SP_NAME(alloc_pair) (NCURSES_SP_DCLx int fg, int bg)
265 {
266     int pair;
267 
268     T((T_CALLED("alloc_pair(%d,%d)"), fg, bg));
269     if (SP_PARM == 0) {
270 	pair = -1;
271     } else if ((pair = _nc_find_color_pair(SP_PARM, fg, bg)) < 0) {
272 	/*
273 	 * Check if all of the slots have been used.  If not, find one and
274 	 * use that.
275 	 */
276 	if (SP_PARM->_pairs_used + 1 < SP_PARM->_pair_limit) {
277 	    bool found = FALSE;
278 	    int hint = SP_PARM->_recent_pair;
279 
280 	    /*
281 	     * The linear search is done to allow mixing calls to init_pair()
282 	     * and alloc_pair().  The former can make gaps...
283 	     */
284 	    for (pair = hint + 1; pair < SP_PARM->_pair_alloc; pair++) {
285 		if (SP_PARM->_color_pairs[pair].mode == cpFREE) {
286 		    T(("found gap %d", pair));
287 		    found = TRUE;
288 		    break;
289 		}
290 	    }
291 	    if (!found && (SP_PARM->_pair_alloc < SP_PARM->_pair_limit)) {
292 		pair = SP_PARM->_pair_alloc;
293 		ReservePairs(SP_PARM, pair);
294 		if (SP_PARM->_color_pairs == 0) {
295 		    pair = -1;
296 		} else {
297 		    found = TRUE;
298 		}
299 	    }
300 	    if (!found) {
301 		for (pair = 1; pair <= hint; pair++) {
302 		    if (SP_PARM->_color_pairs[pair].mode == cpFREE) {
303 			T(("found gap %d", pair));
304 			found = TRUE;
305 			break;
306 		    }
307 		}
308 	    }
309 	    if (found) {
310 		SP_PARM->_recent_pair = pair;
311 	    } else {
312 		pair = ERR;
313 	    }
314 	} else {
315 	    /* reuse the oldest one */
316 	    pair = SP_PARM->_color_pairs[0].prev;
317 	    T(("reusing %d", pair));
318 	}
319 
320 	if (_nc_init_pair(SP_PARM, pair, fg, bg) == ERR)
321 	    pair = ERR;
322     }
323     returnCode(pair);
324 }
325 
326 NCURSES_EXPORT(int)
327 NCURSES_SP_NAME(find_pair) (NCURSES_SP_DCLx int fg, int bg)
328 {
329     int pair;
330 
331     T((T_CALLED("find_pair(%d,%d)"), fg, bg));
332     pair = _nc_find_color_pair(SP_PARM, fg, bg);
333     returnCode(pair);
334 }
335 
336 NCURSES_EXPORT(int)
337 NCURSES_SP_NAME(free_pair) (NCURSES_SP_DCLx int pair)
338 {
339     int result = ERR;
340     T((T_CALLED("free_pair(%d)"), pair));
341     if (ValidPair(SP_PARM, pair) && pair < SP_PARM->_pair_alloc) {
342 	colorpair_t *cp = &(SP_PARM->_color_pairs[pair]);
343 	if (pair != 0) {
344 	    _nc_change_pair(SP_PARM, pair);
345 	    delink_color_pair(SP_PARM, pair);
346 	    tdelete(cp, &SP_PARM->_ordered_pairs, compare_data);
347 	    cp->mode = cpFREE;
348 	    result = OK;
349 	    SP_PARM->_pairs_used--;
350 	}
351     }
352     returnCode(result);
353 }
354 
355 #if NCURSES_SP_FUNCS
356 NCURSES_EXPORT(int)
357 alloc_pair(int f, int b)
358 {
359     return NCURSES_SP_NAME(alloc_pair) (CURRENT_SCREEN, f, b);
360 }
361 
362 NCURSES_EXPORT(int)
363 find_pair(int f, int b)
364 {
365     return NCURSES_SP_NAME(find_pair) (CURRENT_SCREEN, f, b);
366 }
367 
368 NCURSES_EXPORT(int)
369 free_pair(int pair)
370 {
371     return NCURSES_SP_NAME(free_pair) (CURRENT_SCREEN, pair);
372 }
373 #endif
374 
375 #if NO_LEAKS
376 NCURSES_EXPORT(void)
377 _nc_new_pair_leaks(SCREEN *sp)
378 {
379     if (sp->_color_pairs) {
380 	while (sp->_color_pairs[0].next) {
381 	    free_pair(sp->_color_pairs[0].next);
382 	}
383     }
384 }
385 #endif
386 
387 #else
388 void _nc_new_pair(void);
389 void
390 _nc_new_pair(void)
391 {
392 }
393 #endif /* NCURSES_EXT_COLORS */
394