src/ptserver/map.c

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