b28a479c265e4e3600f2c0d21a881f50bd697fd5
[openafs.git] / src / ptserver / map.c
1 /*
2  *      bit map routines (in-core).
3  */
4 /*
5  * Copyright (c) 1995, 1996, 2007 Marcus D. Watts  All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. The name of the developer may not be used to endorse or promote
16  *    products derived from this software without specific prior written
17  *    permission.
18  *
19  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
20  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
21  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
22  * MARCUS D. WATTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
24  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
25  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
27  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
28  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31 #include <afsconfig.h>
32 #include <afs/param.h>
33
34
35 #ifdef SUPERGROUPS
36 #include <errno.h>
37 #include "map.h"
38 #ifdef STDLIB_HAS_MALLOC_PROTOS
39 #include <stdlib.h>
40 #else
41 #include "malloc.h"
42 #endif
43
44 #undef PRINT_MAP_ERROR
45 /* #define MAP_DEBUG */
46 /* #define NEED_READ_WRITE */
47
48 #define LSHIFT 5
49 #define MSHIFT 8                /* XXX make this 8 in the production version... */
50 #define MDATA (1<<MSHIFT)
51 struct bitmap {
52     struct bitmap *m_next;
53     int m_page;
54     int m_data[MDATA];
55 };
56
57 #define MAP(p)  ((struct bitmap*)((int)(p)&~1))
58 #define NEGMAP(p)       (((int)(p))&1)
59 #define POSMAP(p)       (!NEGMAP(p))
60 #define NOT_MAP(mp)     ((struct map *) (((int)(mp)) ^ 1))
61
62 #define NUMBERTOBIT(n)  ((n) & ((1<<LSHIFT)-1))
63 #define NUMBERTOINDEX(n)        ((n>>LSHIFT) & ((1<<MSHIFT)-1))
64 #define NUMBERTOPAGE(n) ((n>>(LSHIFT+MSHIFT)))
65 #define TONUMBER(p,x,b) ((b) + ((x)<<LSHIFT) + ((p)<<((LSHIFT+MSHIFT))))
66
67 #define Mflag   (debug_mask & (1L<<('Y'-'@')))
68 #define Aflag   (debug_mask & (1L<<('Z'-'@')))
69 extern int debug_mask;
70
71 int
72 in_map(struct map *parm, int node)
73 {
74     struct bitmap *map;
75     int bit;
76     int x, page;
77     int result;
78
79 #ifdef MAP_DEBUG
80     if (Aflag) {
81         printf("in_map: is %d in [", node);
82         print_map(parm);
83         printf(" ]");
84     }
85 #endif
86     bit = NUMBERTOBIT(node);
87     x = NUMBERTOINDEX(node);
88     page = NUMBERTOPAGE(node);
89 #ifdef MAP_DEBUG
90     if (Aflag)
91         if (TONUMBER(page, x, bit) != node) {
92             printf
93                 ("bxp mixup: node=%d -> p=%d x=%d b=%d -> %d, %d, %d = %d\n",
94                  node, page, x, bit, TONUMBER(page, 0, 0), TONUMBER(0, x, 0),
95                  TONUMBER(0, 0, bit), TONUMBER(page, x, bit));
96         }
97 #endif
98     bit = 1L << bit;;
99
100     for (map = MAP(parm); map; map = map->m_next)
101         if (map->m_page == page)
102             return NEGMAP(parm) ^ (!!(map->m_data[x] & bit));
103     result = !POSMAP(parm);
104 #ifdef MAP_DEBUG
105     if (Aflag)
106         printf(" -> %s\n", result ? "yes" : "no");
107 #endif
108     return result;
109 }
110
111 void
112 free_map(struct map *parm)
113 {
114     struct bitmap *map, *next;
115 #ifdef MAP_DEBUG
116     if (Aflag) {
117         printf("Freeing map");
118         print_map(parm);
119         printf("\n");
120     }
121 #endif
122     map = MAP(parm);
123     while (map) {
124         next = map->m_next;
125         free(map);
126         map = next;
127     }
128 }
129
130 struct map *
131 add_map(struct map *parm, int node)
132 {
133     struct bitmap *map;
134     int bit;
135     int x, page;
136
137 #ifdef MAP_DEBUG
138     if (Aflag) {
139         printf("add_map: adding %d to [", node);
140         print_map(parm);
141         printf(" ] ");
142     }
143 #endif
144     bit = NUMBERTOBIT(node);
145     x = NUMBERTOINDEX(node);
146     page = NUMBERTOPAGE(node);
147
148     bit = 1L << bit;;
149
150     for (map = MAP(parm); map; map = map->m_next)
151         if (map->m_page == page)
152             break;
153     if (!map) {
154         map = (struct bitmap *)malloc(sizeof *map);
155         if (!map) {
156 #ifdef PRINT_MAP_ERROR
157             printf("No memory!\n");
158 #endif
159             free_map((struct map *)map);
160             return 0;
161         }
162         map->m_page = page;
163         memset( map->m_data, 0, sizeof map->m_data);
164         if (NEGMAP(parm)) {
165             int i;
166             for (i = 0; i < MDATA; ++i)
167                 map->m_data[i] = ~0;
168         }
169         map->m_next = MAP(parm);
170         if (POSMAP(parm))
171             parm = (struct map *)map;
172         else
173             parm = NOT_MAP(map);
174     }
175     if (POSMAP(parm))
176         map->m_data[x] |= bit;
177     else
178         map->m_data[x] &= ~bit;
179 #ifdef MAP_DEBUG
180     if (Aflag) {
181         printf(" ->");
182         print_map(parm);
183         printf("\n");
184     }
185 #endif
186     return (struct map *)parm;
187 }
188
189 struct bitmap *
190 simplify_bitmap(struct bitmap *map)
191 {
192     struct bitmap **mpp, *mp2;
193     int i;
194     for (mpp = &map; (mp2 = *mpp);) {
195         for (i = 0; i < MDATA; ++i)
196             if (mp2->m_data[i])
197                 break;
198         if (i == MDATA) {
199 #ifdef PRINT_MAP_ERROR
200             printf("simplify_bitmap: failed to eliminate zero page %d\n",
201                    mp2->m_page);
202 #endif
203             *mpp = mp2->m_next;
204             free((char *)mp2);
205         } else
206             mpp = &mp2->m_next;
207     }
208     return map;
209 }
210
211 struct bitmap *
212 or_bitmap(struct bitmap *left, struct bitmap *right)
213 {
214     struct bitmap **rightmp, *lmap, *rmap;
215     int i;
216     for (lmap = left; lmap; lmap = lmap->m_next) {
217         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
218             if (rmap->m_page == lmap->m_page) {
219                 for (i = 0; i < MDATA; ++i)
220                     lmap->m_data[i] |= rmap->m_data[i];
221                 *rightmp = rmap->m_next;
222                 free((char *)rmap);
223                 break;
224             }
225     }
226     for (rightmp = &left; *rightmp; rightmp = &(*rightmp)->m_next)
227         ;
228     *rightmp = right;
229     return left;
230 }
231
232 struct bitmap *
233 and_bitmap(struct bitmap *left, struct bitmap *right)
234 {
235     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
236     int i;
237     int sig;
238     for (leftmp = &left; (lmap = *leftmp);) {
239         sig = 0;
240         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
241             if (rmap->m_page == lmap->m_page) {
242                 for (i = 0; i < MDATA; ++i)
243                     sig |= (lmap->m_data[i] &= rmap->m_data[i]);
244                 *rightmp = rmap->m_next;
245                 free((char *)rmap);
246                 break;
247             }
248         if (rmap && sig) {
249             leftmp = &lmap->m_next;
250         } else {
251             *leftmp = lmap->m_next;
252             free((char *)lmap);
253         }
254     }
255     free_map((struct map *)right);
256     return simplify_bitmap(left);
257 }
258
259 /* bit set in left, but not in right */
260 struct bitmap *
261 bic_bitmap(struct bitmap *left, struct bitmap *right)
262 {
263     struct bitmap **rightmp, *lmap, *rmap, **leftmp;
264     int i;
265     int sig;
266 #ifdef MAP_DEBUG
267     if (Mflag) {
268         printf("bic_bitmap: left=%#lx right=%#lx\n", (long)left, (long)right);
269     }
270 #endif
271     for (leftmp = &left; (lmap = *leftmp);) {
272         sig = 0;
273         for (rightmp = &right; (rmap = *rightmp); rightmp = &rmap->m_next)
274             if (rmap->m_page == lmap->m_page) {
275                 for (i = 0; i < MDATA; ++i)
276                     sig |= (lmap->m_data[i] &= ~rmap->m_data[i]);
277                 *rightmp = rmap->m_next;
278                 free((char *)rmap);
279                 break;
280             }
281         if (!rmap || sig) {
282             leftmp = &lmap->m_next;
283         } else {
284             *leftmp = lmap->m_next;
285             free((char *)lmap);
286         }
287     }
288     free_map((struct map *)right);
289     left = simplify_bitmap(left);
290 #ifdef MAP_DEBUG
291     if (Mflag) {
292         printf("bic_bitmap: result=%#lx\n", (long) left);
293     }
294 #endif
295     return left;
296 }
297
298 struct map *
299 and_map(struct map *mp1, struct map *mp2)
300 {
301 #ifdef MAP_DEBUG
302     if (Mflag) {
303         printf("Anding maps");
304         print_map(mp1);
305         printf(" and");
306         print_map(mp2);
307     }
308 #endif
309     if (POSMAP(mp1))
310         if (POSMAP(mp2))
311             mp1 = (struct map *)and_bitmap((struct bitmap *) mp1,
312                 (struct bitmap *) mp2);
313         else
314             mp1 = (struct map *)bic_bitmap((struct bitmap *) mp1, MAP(mp2));
315     else if (POSMAP(mp2))
316         mp1 = (struct map *)bic_bitmap((struct bitmap *) mp2, MAP(mp1));
317     else
318         mp1 = NOT_MAP(or_bitmap(MAP(mp1), MAP(mp2)));
319 #ifdef MAP_DEBUG
320     if (Mflag) {
321         printf(" ->");
322         print_map(mp1);
323         printf("\n");
324     }
325 #endif
326     return mp1;
327 }
328
329 struct map *
330 or_map(struct map *mp1, struct map *mp2)
331 {
332 #ifdef MAP_DEBUG
333     if (Mflag) {
334         printf("Oring maps");
335         print_map(mp1);
336         printf(" and");
337         print_map(mp2);
338     }
339 #endif
340     if (POSMAP(mp1))
341         if (POSMAP(mp2))
342             mp1 = (struct map *)or_bitmap((struct bitmap *) mp1,
343                 (struct bitmap *) mp2);
344         else
345             mp1 = NOT_MAP(bic_bitmap(MAP(mp2), (struct bitmap *) mp1));
346     else if (POSMAP(mp2))
347         mp1 = NOT_MAP(bic_bitmap(MAP(mp1), (struct bitmap *) mp2));
348     else
349         mp1 = NOT_MAP(and_bitmap(MAP(mp1), MAP(mp2)));
350 #ifdef MAP_DEBUG
351     if (Mflag) {
352         printf(" ->");
353         print_map(mp1);
354         printf("\n");
355     }
356 #endif
357     return mp1;
358 }
359
360 struct map *
361 not_map(struct map *map)
362 {
363 #ifdef MAP_DEBUG
364     if (Mflag) {
365         printf("Notting map");
366         print_map(map);
367         printf("\n");
368     }
369 #endif
370     return NOT_MAP(map);
371 }
372
373 struct map *
374 copy_map(struct map *parm)
375 {
376     struct bitmap *result, **mpp, *map;
377 #ifdef MAP_DEBUG
378     if (Mflag) {
379         printf("copymap:");
380         print_map(parm);
381         printf("\n");
382     }
383 #endif
384     map = MAP(parm);
385     for (mpp = &result; (*mpp = 0), map; map = map->m_next) {
386         *mpp = (struct bitmap *)malloc(sizeof **mpp);
387         if (!*mpp) {
388 #ifdef MAP_DEBUG
389             if (Mflag)
390                 printf("copy_map: out of memory\n");
391 #endif
392             free_map((struct map *)result);
393             result = 0;
394             break;
395         }
396         **mpp = *map;
397         mpp = &(*mpp)->m_next;
398     }
399     if (NEGMAP(parm))
400         return NOT_MAP(result);
401     else
402         return (struct map *)result;
403 }
404
405 int
406 count_map(struct map *parm)
407 {
408     int nf;
409     struct bitmap *map;
410     int i, j;
411
412     nf = 0;
413     for (map = MAP(parm); map; map = map->m_next) {
414         for (i = 0; i < MDATA; ++i) {
415             if (!map->m_data[i])
416                 ;
417             else if (!~map->m_data[i])
418                 nf += (1 << LSHIFT);
419             else
420                 for (j = 0; j < (1L << LSHIFT); ++j)
421                     if (map->m_data[i] & (1L << j))
422                         ++nf;
423         }
424     }
425     if (NEGMAP(parm))
426         nf = ~nf;               /* note 1's complement */
427 #ifdef MAP_DEBUG
428     if (Mflag) {
429         printf("countmap:");
430         print_map(parm);
431         printf(" -> %d\n", nf);
432     }
433 #endif
434     return nf;
435 }
436
437 int
438 next_map(struct map *parm, int node)
439 {
440     struct bitmap *map, *lowest;
441     int bit, mask;
442     int x, page;
443     int best;
444     int i;
445     int bn;
446
447 #ifdef MAP_DEBUG
448     if (Aflag) {
449         printf("next_map: selecting next after %d from", node);
450         print_map(parm);
451     }
452 #endif
453     if (NEGMAP(parm)) {
454 #ifdef MAP_DEBUG
455         if (Aflag)
456             printf("next_map failed; negative map\n");
457 #endif
458         return -1;
459     }
460
461     ++node;
462     bit = NUMBERTOBIT(node);
463     x = NUMBERTOINDEX(node);
464     page = NUMBERTOPAGE(node);
465     bit = 1L << bit;
466     best = -1;
467     lowest = 0;
468     for (map = MAP(parm); map; map = map->m_next)
469         if (map->m_page >= page && (!lowest || lowest->m_page > map->m_page)) {
470             i = 0;
471             mask = ~0;
472             if (page == map->m_page)
473                 i = x, mask = -bit;
474             for (; i < MDATA; ++i, mask = ~0)
475                 if (map->m_data[i] & mask)
476                     break;
477             if (i < MDATA) {
478                 for (bn = 0; bn < (1 << LSHIFT); ++bn)
479                     if (map->m_data[i] & mask & (1L << bn)) {
480                         break;
481                     }
482 #ifdef MAP_DEBUG
483                 if (Aflag) {
484                     if (bn == (1 << LSHIFT)) {
485                         printf
486                             ("next_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
487                              map->m_page, i, map->m_data[i], mask, x, bit);
488                         continue;
489                     }
490                 }
491 #endif
492                 best = bn + ((i + ((map->m_page) << MSHIFT)
493                              ) << LSHIFT);
494                 lowest = map;
495             }
496         }
497 #ifdef MAP_DEBUG
498     if (Aflag) {
499         printf(" -> %d\n", best);
500         if (best >= 0 && !in_map(parm, best)) {
501             printf("next_map: botch; %d not in map\n", best);
502             return -1;
503         }
504     }
505 #endif
506     return best;
507 }
508
509 int
510 first_map(struct map *parm)
511 {
512     return next_map(parm, -9999);
513 }
514
515 int
516 prev_map(struct map *parm, int node)
517 {
518     struct bitmap *map, *lowest;
519     int bit, mask;
520     int x, page;
521     int best;
522     int i;
523     int bn;
524
525 #ifdef MAP_DEBUG
526     if (Aflag) {
527         printf("prev_map: selecting previous before %d from", node);
528         print_map(parm);
529     }
530 #endif
531     if (NEGMAP(parm)) {
532 #ifdef MAP_DEBUG
533         if (Aflag)
534             printf("prev_map failed; negative map\n");
535 #endif
536         return -1;
537     }
538
539     if (node < 0)
540         node = ((unsigned int)~0) >> 1;
541
542     --node;
543     bit = NUMBERTOBIT(node);
544     x = NUMBERTOINDEX(node);
545     page = NUMBERTOPAGE(node);
546     bit = 1L << bit;
547     best = -1;
548     lowest = 0;
549     for (map = MAP(parm); map; map = map->m_next)
550         if (map->m_page <= page && (!lowest || lowest->m_page < map->m_page)) {
551             i = MDATA - 1;
552             mask = ~0;
553             if (page == map->m_page)
554                 i = x, mask = (bit << 1) - 1;
555             for (; i >= 0; --i, mask = ~0)
556                 if (map->m_data[i] & mask)
557                     break;
558             if (i >= 0) {
559                 for (bn = (1 << LSHIFT) - 1; bn >= 0; --bn)
560                     if (map->m_data[i] & mask & (1L << bn)) {
561                         break;
562                     }
563 #ifdef MAP_DEBUG
564                 if (Aflag) {
565                     if (bn < 0) {
566                         printf
567                             ("prev_map: botch; pageno %d index %d data %#x mask %#x x,bit %d,%#x\n",
568                              map->m_page, i, map->m_data[i], mask, x, bit);
569                         continue;
570                     }
571                 }
572 #endif
573                 best = bn + ((i + ((map->m_page) << MSHIFT)
574                              ) << LSHIFT);
575                 lowest = map;
576             }
577         }
578 #ifdef MAP_DEBUG
579     if (Aflag) {
580         printf(" -> %d\n", best);
581         if (best >= 0 && !in_map(parm, best)) {
582             printf("prev_map: botch; %d not in map\n", best);
583             return -1;
584         }
585     }
586 #endif
587     return best;
588 }
589
590 int
591 last_map(struct map *parm)
592 {
593     return prev_map(parm, 0x7fffffff);
594 }
595
596 struct map *
597 negative_map(struct map *map)
598 {
599     return (struct map *)NEGMAP(map);
600 }
601
602 struct map *
603 bic_map(struct map *mp1, struct map *mp2)
604 {
605 #ifdef MAP_DEBUG
606     if (Mflag) {
607         printf("Bic maps");
608         print_map(mp1);
609         printf(" minus");
610         print_map(mp2);
611     }
612 #endif
613     mp1 = and_map(mp1, NOT_MAP(mp2));
614 #ifdef MAP_DEBUG
615     if (Mflag) {
616         printf(" ->");
617         print_map(mp1);
618         printf("\n");
619     }
620 #endif
621     return mp1;
622 }
623
624 #ifdef PRINT_MAP_ERROR
625 void 
626 print_map(struct map *parm)
627 {
628     struct bitmap *map;
629     int i, j;
630     int bitno, firstbitno, lastbitno;
631     if (NEGMAP(parm)) {
632         printf(" NOT");
633     }
634     map = MAP(parm);
635     if (!map)
636         printf(" nil(%lx)", (long)parm);
637     else
638         printf(" %lx", (long)parm);
639     lastbitno = -100;
640     firstbitno = -100;
641     for (; map; map = map->m_next)
642         for (i = 0; i < MDATA; ++i)
643             if (map->m_data[i])
644                 for (j = 0; j < (1 << LSHIFT); ++j) {
645                     bitno =
646                         j + (i << LSHIFT) +
647                         ((map->m_page) << (LSHIFT + MSHIFT));
648                     if (map->m_data[i] & (1 << j)) {
649                         if (bitno == lastbitno + 1) {
650                             ++lastbitno;
651                             continue;
652                         }
653                         if (bitno != (lastbitno + 1)) {
654                             if (firstbitno >= 0 && firstbitno != lastbitno)
655                                 printf("-%d", lastbitno);
656                             firstbitno = -100;
657                         }
658                         printf(" %d", bitno);
659                         firstbitno = lastbitno = bitno;
660                     } else {
661                         if (firstbitno >= 0 && firstbitno != lastbitno)
662                             printf("-%d", lastbitno);
663                         firstbitno = -100;
664                     }
665                 }
666     if (firstbitno >= 0 && firstbitno != lastbitno)
667         printf("-%d", lastbitno);
668 }
669 #endif
670
671 #ifdef NEED_READ_WRITE
672 struct map *
673 read_map(int (*f) (void *), char *arg)
674 {
675     struct bitmap *map, *result, **mp;
676     int page;
677     int bitno, lastno;
678     int data;
679
680 /* count, then startbitno, then bits. */
681     lastno = ((*f) (arg));
682     if (lastno == -1)
683         return 0;
684     if (lastno & ((1 << LSHIFT) - 1)) {
685 #ifdef PRINT_MAP_ERROR
686         printf("read_map: bad count\n");
687 #endif
688         return 0;
689     }
690     bitno = ((*f) (arg));
691     if (bitno & ((1 << LSHIFT) - 1)) {
692 #ifdef PRINT_MAP_ERROR
693         printf("read_map: bad start\n");
694 #endif
695         return 0;
696     }
697     lastno += bitno;
698     map = result = 0;
699     for (; bitno < lastno; bitno += (1 << LSHIFT)) {
700         data = (*f) (arg);
701         if (!data)
702             continue;
703         page = NUMBERTOPAGE(bitno);
704         if (!map || map->m_page != page)
705             for (mp = &result; (map = *mp); mp = &map->m_next)
706                 if (map->m_page == page)
707                     break;
708         if (!map) {
709             map = (struct bitmap *)malloc(sizeof *map);
710             if (!map) {
711 #ifdef PRINT_MAP_ERROR
712                 printf("No memory!\n");
713 #endif
714                 if (result)
715                     free_map((struct map *)result);
716                 return 0;
717             }
718             memset( map->m_data, 0, sizeof map->m_data);
719             map->m_page = page;
720             map->m_next = 0;
721             *mp = map;
722         }
723         map->m_data[NUMBERTOINDEX(bitno)] = data;
724     }
725     return (struct map *)result;
726 }
727
728 int 
729 write_map(struct map *parm, int (*f) (void *, int), char *arg)
730 {
731     struct bitmap *map;
732     int page;
733     int bitno, lastno, thisno, prevno;
734     int i, j;
735
736     bitno = first_map(parm);
737     bitno &= ~((1 << LSHIFT) - 1);
738
739     lastno = last_map(parm);
740     lastno -= bitno;
741     lastno += ((1 << LSHIFT));
742     lastno &= ~((1 << LSHIFT) - 1);
743 /* count, then startbitno, then bits. */
744     if ((*f) (arg, lastno) == -1)
745         return -1;
746     /* word: number of bits */
747     if ((*f) (arg, bitno) == -1)
748         return -1;
749     lastno += bitno;
750     prevno = bitno;
751     for (bitno = first_map(parm); bitno >= 0; bitno = next_map(parm, bitno)) {
752         page = NUMBERTOPAGE(bitno);
753         for (map = MAP(parm); map; map = map->m_next)
754             if (map->m_page == page)
755                 break;
756         if (!map) {
757 #ifdef PRINT_MAP_ERROR
758             printf("write_map: botch #1: can't find page %d\n", page);
759 #endif
760             continue;
761         }
762         for (i = 0; i < MDATA; ++i) {
763             if (!map->m_data[i])
764                 continue;
765             thisno = TONUMBER(page, i, 0);
766             for (j = thisno - prevno; j > 0; j -= (1 << LSHIFT))
767                 if ((*f) (arg, 0) == -1)
768                     return -1;
769             prevno = thisno;
770             for (;;) {
771                 if ((*f) (arg, map->m_data[i]) == -1)
772                     return -1;
773                 prevno += (1 << LSHIFT);
774                 ++i;
775                 if (i >= MDATA || !map->m_data[i])
776                     break;
777             }
778             --i;
779         }
780         bitno = TONUMBER(page, i, 0) - 1;
781     }
782 #ifdef PRINT_MAP_ERROR
783     if (prevno != lastno)
784         printf("write_map: botch #2: bitno=%d prevno=%d lastno=%d\n", bitno,
785                prevno, lastno);
786 #endif
787     return 0;
788 }
789 #endif
790
791 #endif