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 <string.h>
  38 #include <stdlib.h>
  39 #ifdef HAVE_STDINT_H
  40 # include <stdint.h>
  41 #endif
  42 #include "map.h"
  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*)((intptr_t)(p)&~1))
  58 #define NEGMAP(p)       (((intptr_t)(p))&1)
  59 #define POSMAP(p)       (!NEGMAP(p))
  60 #define NOT_MAP(mp)     ((struct map *) (((intptr_t)(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