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