git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/dix/colormap.c

   1 /***********************************************************
   2
   3 Copyright (c) 1987  X Consortium
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a copy
   6 of this software and associated documentation files (the "Software"), to deal
   7 in the Software without restriction, including without limitation the rights
   8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 copies of the Software, and to permit persons to whom the Software is
  10 furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21
  22 Except as contained in this notice, the name of the X Consortium shall not be
  23 used in advertising or otherwise to promote the sale, use or other dealings
  24 in this Software without prior written authorization from the X Consortium.
  25
  26
  27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
  28
  29                         All Rights Reserved
  30
  31 Permission to use, copy, modify, and distribute this software and its
  32 documentation for any purpose and without fee is hereby granted,
  33 provided that the above copyright notice appear in all copies and that
  34 both that copyright notice and this permission notice appear in
  35 supporting documentation, and that the name of Digital not be
  36 used in advertising or publicity pertaining to distribution of the
  37 software without specific, written prior permission.
  38
  39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  45 SOFTWARE.
  46
  47 ******************************************************************/
  48
  49 /* $XConsortium: colormap.c /main/71 1996/06/17 11:01:33 mor $ */
  50 /* $XFree86: xc/programs/Xserver/dix/colormap.c,v 3.1 1996/12/23 06:29:34 dawes Exp $ */
  51
  52 #include "X.h"
  53 #define NEED_EVENTS
  54 #include "Xproto.h"
  55 #include "misc.h"
  56 #include "dix.h"
  57 #include "colormapst.h"
  58 #include "os.h"
  59 #include "scrnintstr.h"
  60 #include "resource.h"
  61 #include "windowstr.h"
  62
  63 extern XID clientErrorValue;
  64
  65 static Pixel FindBestPixel(
  66 #if NeedFunctionPrototypes
  67     EntryPtr /*pentFirst*/,
  68     int /*size*/,
  69     xrgb * /*prgb*/,
  70     int /*channel*/
  71 #endif
  72 );
  73
  74 static int AllComp(
  75 #if NeedFunctionPrototypes
  76     EntryPtr /*pent*/,
  77     xrgb * /*prgb*/
  78 #endif
  79 );
  80
  81 static int RedComp(
  82 #if NeedFunctionPrototypes
  83     EntryPtr /*pent*/,
  84     xrgb * /*prgb*/
  85 #endif
  86 );
  87
  88 static int GreenComp(
  89 #if NeedFunctionPrototypes
  90     EntryPtr /*pent*/,
  91     xrgb * /*prgb*/
  92 #endif
  93 );
  94
  95 static int BlueComp(
  96 #if NeedFunctionPrototypes
  97     EntryPtr /*pent*/,
  98     xrgb * /*prgb*/
  99 #endif
 100 );
 101
 102 static void FreePixels(
 103 #if NeedFunctionPrototypes
 104     register ColormapPtr /*pmap*/,
 105     register int /*client*/
 106 #endif
 107 );
 108
 109 static void CopyFree(
 110 #if NeedFunctionPrototypes
 111     int /*channel*/,
 112     int /*client*/,
 113     ColormapPtr /*pmapSrc*/,
 114     ColormapPtr /*pmapDst*/
 115 #endif
 116 );
 117
 118 static void FreeCell(
 119 #if NeedFunctionPrototypes
 120     ColormapPtr /*pmap*/,
 121     Pixel /*i*/,
 122     int /*channel*/
 123 #endif
 124 );
 125
 126 static void UpdateColors(
 127 #if NeedFunctionPrototypes
 128     ColormapPtr /*pmap*/
 129 #endif
 130 );
 131
 132 static int AllocDirect(
 133 #if NeedFunctionPrototypes
 134     int /*client*/,
 135     ColormapPtr /*pmap*/,
 136     int /*c*/,
 137     int /*r*/,
 138     int /*g*/,
 139     int /*b*/,
 140     Bool /*contig*/,
 141     Pixel * /*pixels*/,
 142     Pixel * /*prmask*/,
 143     Pixel * /*pgmask*/,
 144     Pixel * /*pbmask*/
 145 #endif
 146 );
 147
 148 static int AllocPseudo(
 149 #if NeedFunctionPrototypes
 150     int /*client*/,
 151     ColormapPtr /*pmap*/,
 152     int /*c*/,
 153     int /*r*/,
 154     Bool /*contig*/,
 155     Pixel * /*pixels*/,
 156     Pixel * /*pmask*/,
 157     Pixel ** /*pppixFirst*/
 158 #endif
 159 );
 160
 161 static Bool AllocCP(
 162 #if NeedFunctionPrototypes
 163     ColormapPtr /*pmap*/,
 164     EntryPtr /*pentFirst*/,
 165     int /*count*/,
 166     int /*planes*/,
 167     Bool /*contig*/,
 168     Pixel * /*pixels*/,
 169     Pixel * /*pMask*/
 170 #endif
 171 );
 172
 173 static Bool AllocShared(
 174 #if NeedFunctionPrototypes
 175     ColormapPtr /*pmap*/,
 176     Pixel * /*ppix*/,
 177     int /*c*/,
 178     int /*r*/,
 179     int /*g*/,
 180     int /*b*/,
 181     Pixel /*rmask*/,
 182     Pixel /*gmask*/,
 183     Pixel /*bmask*/,
 184     Pixel * /*ppixFirst*/
 185 #endif
 186 );
 187
 188 static int FreeCo(
 189 #if NeedFunctionPrototypes
 190     ColormapPtr /*pmap*/,
 191     int /*client*/,
 192     int /*color*/,
 193     int /*npixIn*/,
 194     Pixel * /*ppixIn*/,
 195     Pixel /*mask*/
 196 #endif
 197 );
 198
 199 static int   TellNoMap(
 200 #if NeedFunctionPrototypes
 201     WindowPtr   /*pwin*/,
 202     Colormap    * /*pmid*/
 203 #endif
 204 );
 205
 206 #define NUMRED(vis) ((vis->redMask >> vis->offsetRed) + 1)
 207 #define NUMGREEN(vis) ((vis->greenMask >> vis->offsetGreen) + 1)
 208 #define NUMBLUE(vis) ((vis->blueMask >> vis->offsetBlue) + 1)
 209 #define RGBMASK(vis) (vis->redMask | vis->greenMask | vis->blueMask)
 210
 211 /* GetNextBitsOrBreak(bits, mask, base)  --
 212  * (Suggestion: First read the macro, then read this explanation.
 213  *
 214  * Either generate the next value to OR in to a pixel or break out of this
 215  * while loop
 216  *
 217  * This macro is used when we're trying to generate all 2^n combinations of
 218  * bits in mask.  What we're doing here is counting in binary, except that
 219  * the bits we use to count may not be contiguous.  This macro will be
 220  * called 2^n times, returning a different value in bits each time. Then
 221  * it will cause us to break out of a surrounding loop. (It will always be
 222  * called from within a while loop.)
 223  * On call: mask is the value we want to find all the combinations for
 224  * base has 1 bit set where the least significant bit of mask is set
 225  *
 226  * For example,if mask is 01010, base should be 0010 and we count like this:
 227  * 00010 (see this isn't so hard),
 228  *     then we add base to bits and get 0100. (bits & ~mask) is (0100 & 0100) so
 229  *      we add that to bits getting (0100 + 0100) =
 230  * 01000 for our next value.
 231  *      then we add 0010 to get
 232  * 01010 and we're done (easy as 1, 2, 3)
 233  */
 234 #define GetNextBitsOrBreak(bits, mask, base)    \
 235             if((bits) == (mask))                \
 236                 break;                          \
 237             (bits) += (base);                   \
 238             while((bits) & ~(mask))             \
 239                 (bits) += ((bits) & ~(mask));
 240 /* ID of server as client */
 241 #define SERVER_ID       0
 242
 243 typedef struct _colorResource
 244 {
 245         Colormap        mid;
 246         int             client;
 247 } colorResource;
 248
 249 /* Invariants:
 250  * refcnt == 0 means entry is empty
 251  * refcnt > 0 means entry is useable by many clients, so it can't be changed
 252  * refcnt == AllocPrivate means entry owned by one client only
 253  * fShared should only be set if refcnt == AllocPrivate, and only in red map
 254  */
 255
 256
 257 /* Create and initialize the color map */
 258 int
 259 CreateColormap (mid, pScreen, pVisual, ppcmap, alloc, client)
 260     Colormap    mid;            /* resource to use for this colormap */
 261     ScreenPtr   pScreen;
 262     VisualPtr   pVisual;
 263     ColormapPtr *ppcmap;
 264     int         alloc;          /* 1 iff all entries are allocated writeable */
 265     int         client;
 266 {
 267     int         class, size;
 268     unsigned long sizebytes;
 269     ColormapPtr pmap;
 270     register    EntryPtr        pent;
 271     int         i;
 272     register    Pixel   *ppix, **pptr;
 273     extern int colormapPrivateCount;
 274
 275     class = pVisual->class;
 276     if(!(class & DynamicClass) && (alloc != AllocNone) && (client != SERVER_ID))
 277         return (BadMatch);
 278
 279     size = pVisual->ColormapEntries;
 280     sizebytes = (size * sizeof(Entry)) +
 281                 (MAXCLIENTS * sizeof(Pixel *)) +
 282                 (MAXCLIENTS * sizeof(int));
 283     if ((class | DynamicClass) == DirectColor)
 284         sizebytes *= 3;
 285     sizebytes += sizeof(ColormapRec);
 286     pmap = (ColormapPtr) xalloc(sizebytes);
 287     if (!pmap)
 288         return (BadAlloc);
 289     pmap->red = (EntryPtr)((char *)pmap + sizeof(ColormapRec));
 290     sizebytes = size * sizeof(Entry);
 291     pmap->clientPixelsRed = (Pixel **)((char *)pmap->red + sizebytes);
 292     pmap->numPixelsRed = (int *)((char *)pmap->clientPixelsRed +
 293                                  (MAXCLIENTS * sizeof(Pixel *)));
 294     pmap->mid = mid;
 295     pmap->flags = 0;    /* start out with all flags clear */
 296     if(mid == pScreen->defColormap)
 297         pmap->flags |= IsDefault;
 298     pmap->pScreen = pScreen;
 299     pmap->pVisual = pVisual;
 300     pmap->class = class;
 301     if ((class | DynamicClass) == DirectColor)
 302         size = NUMRED(pVisual);
 303     pmap->freeRed = size;
 304     bzero ((char *) pmap->red, (int)sizebytes);
 305     bzero((char *) pmap->numPixelsRed, MAXCLIENTS * sizeof(int));
 306     for (pptr = &pmap->clientPixelsRed[MAXCLIENTS]; --pptr >= pmap->clientPixelsRed; )
 307         *pptr = (Pixel *)NULL;
 308     if (alloc == AllocAll)
 309     {
 310         if (class & DynamicClass)
 311             pmap->flags |= AllAllocated;
 312         for (pent = &pmap->red[size - 1]; pent >= pmap->red; pent--)
 313             pent->refcnt = AllocPrivate;
 314         pmap->freeRed = 0;
 315         ppix = (Pixel *)xalloc(size * sizeof(Pixel));
 316         if (!ppix)
 317         {
 318             xfree(pmap);
 319             return (BadAlloc);
 320         }
 321         pmap->clientPixelsRed[client] = ppix;
 322         for(i = 0; i < size; i++)
 323             ppix[i] = i;
 324         pmap->numPixelsRed[client] = size;
 325     }
 326
 327     if ((class | DynamicClass) == DirectColor)
 328     {
 329         pmap->freeGreen = NUMGREEN(pVisual);
 330         pmap->green = (EntryPtr)((char *)pmap->numPixelsRed +
 331                                  (MAXCLIENTS * sizeof(int)));
 332         pmap->clientPixelsGreen = (Pixel **)((char *)pmap->green + sizebytes);
 333         pmap->numPixelsGreen = (int *)((char *)pmap->clientPixelsGreen +
 334                                        (MAXCLIENTS * sizeof(Pixel *)));
 335         pmap->freeBlue = NUMBLUE(pVisual);
 336         pmap->blue = (EntryPtr)((char *)pmap->numPixelsGreen +
 337                                 (MAXCLIENTS * sizeof(int)));
 338         pmap->clientPixelsBlue = (Pixel **)((char *)pmap->blue + sizebytes);
 339         pmap->numPixelsBlue = (int *)((char *)pmap->clientPixelsBlue +
 340                                       (MAXCLIENTS * sizeof(Pixel *)));
 341
 342         bzero ((char *) pmap->green, (int)sizebytes);
 343         bzero ((char *) pmap->blue, (int)sizebytes);
 344
 345         memmove((char *) pmap->clientPixelsGreen,
 346                 (char *) pmap->clientPixelsRed,
 347               MAXCLIENTS * sizeof(Pixel *));
 348         memmove((char *) pmap->clientPixelsBlue,
 349                 (char *) pmap->clientPixelsRed,
 350               MAXCLIENTS * sizeof(Pixel *));
 351         bzero((char *) pmap->numPixelsGreen, MAXCLIENTS * sizeof(int));
 352         bzero((char *) pmap->numPixelsBlue, MAXCLIENTS * sizeof(int));
 353
 354         /* If every cell is allocated, mark its refcnt */
 355         if (alloc == AllocAll)
 356         {
 357             size = pmap->freeGreen;
 358             for(pent = &pmap->green[size-1]; pent >= pmap->green; pent--)
 359                 pent->refcnt = AllocPrivate;
 360             pmap->freeGreen = 0;
 361             ppix = (Pixel *) xalloc(size * sizeof(Pixel));
 362             if (!ppix)
 363             {
 364                 xfree(pmap->clientPixelsRed[client]);
 365                 xfree(pmap);
 366                 return(BadAlloc);
 367             }
 368             pmap->clientPixelsGreen[client] = ppix;
 369             for(i = 0; i < size; i++)
 370                 ppix[i] = i;
 371             pmap->numPixelsGreen[client] = size;
 372
 373             size = pmap->freeBlue;
 374             for(pent = &pmap->blue[size-1]; pent >= pmap->blue; pent--)
 375                 pent->refcnt = AllocPrivate;
 376             pmap->freeBlue = 0;
 377             ppix = (Pixel *) xalloc(size * sizeof(Pixel));
 378             if (!ppix)
 379             {
 380                 xfree(pmap->clientPixelsGreen[client]);
 381                 xfree(pmap->clientPixelsRed[client]);
 382                 xfree(pmap);
 383                 return(BadAlloc);
 384             }
 385             pmap->clientPixelsBlue[client] = ppix;
 386             for(i = 0; i < size; i++)
 387                 ppix[i] = i;
 388             pmap->numPixelsBlue[client] = size;
 389         }
 390     }
 391     if (!AddResource(mid, RT_COLORMAP, (pointer)pmap))
 392         return (BadAlloc);
 393     /* If the device wants a chance to initialize the colormap in any way,
 394      * this is it.  In specific, if this is a Static colormap, this is the
 395      * time to fill in the colormap's values */
 396     pmap->flags |= BeingCreated;
 397
 398
 399     /*
 400      * Allocate the array of devPrivate's for this colormap.
 401      */
 402
 403     if (colormapPrivateCount == 0)
 404         pmap->devPrivates = NULL;
 405     else
 406     {
 407         pmap->devPrivates = (DevUnion *) xalloc (
 408             colormapPrivateCount * sizeof(DevUnion));
 409
 410         if (!pmap->devPrivates)
 411         {
 412             FreeResource (mid, RT_NONE);
 413             return BadAlloc;
 414         }
 415     }
 416
 417     if (!(*pScreen->CreateColormap)(pmap))
 418     {
 419         FreeResource (mid, RT_NONE);
 420         return BadAlloc;
 421     }
 422     pmap->flags &= ~BeingCreated;
 423     *ppcmap = pmap;
 424     return (Success);
 425 }
 426
 427 int
 428 FreeColormap (value, mid)
 429     pointer     value; /* must conform to DeleteType */
 430     XID         mid;
 431 {
 432     int         i;
 433     register EntryPtr pent;
 434     ColormapPtr pmap = (ColormapPtr)value;
 435
 436     if(CLIENT_ID(mid) != SERVER_ID)
 437     {
 438         (*pmap->pScreen->UninstallColormap) (pmap);
 439         WalkTree(pmap->pScreen, (VisitWindowProcPtr)TellNoMap, (pointer) &mid);
 440     }
 441
 442     /* This is the device's chance to undo anything it needs to, especially
 443      * to free any storage it allocated */
 444     (*pmap->pScreen->DestroyColormap)(pmap);
 445
 446     if(pmap->clientPixelsRed)
 447     {
 448         for(i = 0; i < MAXCLIENTS; i++)
 449             xfree(pmap->clientPixelsRed[i]);
 450     }
 451
 452     if ((pmap->class == PseudoColor) || (pmap->class == GrayScale))
 453     {
 454         for(pent = &pmap->red[pmap->pVisual->ColormapEntries - 1];
 455             pent >= pmap->red;
 456             pent--)
 457         {
 458             if(pent->fShared)
 459             {
 460                 if (--pent->co.shco.red->refcnt == 0)
 461                     xfree(pent->co.shco.red);
 462                 if (--pent->co.shco.green->refcnt == 0)
 463                     xfree(pent->co.shco.green);
 464                 if (--pent->co.shco.blue->refcnt == 0)
 465                     xfree(pent->co.shco.blue);
 466             }
 467         }
 468     }
 469     if((pmap->class | DynamicClass) == DirectColor)
 470     {
 471         for(i = 0; i < MAXCLIENTS; i++)
 472         {
 473             xfree(pmap->clientPixelsGreen[i]);
 474             xfree(pmap->clientPixelsBlue[i]);
 475         }
 476     }
 477
 478     if (pmap->devPrivates)
 479         xfree(pmap->devPrivates);
 480
 481     xfree(pmap);
 482     return(Success);
 483 }
 484
 485 /* Tell window that pmid has disappeared */
 486 static int
 487 TellNoMap (pwin, pmid)
 488     WindowPtr   pwin;
 489     Colormap    *pmid;
 490 {
 491     xEvent      xE;
 492     if (wColormap(pwin) == *pmid)
 493     {
 494         /* This should be call to DeliverEvent */
 495         xE.u.u.type = ColormapNotify;
 496         xE.u.colormap.window = pwin->drawable.id;
 497         xE.u.colormap.colormap = None;
 498         xE.u.colormap.new = TRUE;
 499         xE.u.colormap.state = ColormapUninstalled;
 500         DeliverEvents(pwin, &xE, 1, (WindowPtr)NULL);
 501         if (pwin->optional) {
 502             pwin->optional->colormap = None;
 503             CheckWindowOptionalNeed (pwin);
 504         }
 505     }
 506
 507     return (WT_WALKCHILDREN);
 508 }
 509
 510 /* Tell window that pmid got uninstalled */
 511 int
 512 TellLostMap (pwin, value)
 513     WindowPtr   pwin;
 514     pointer     value;
 515 {
 516     Colormap    *pmid = (Colormap *)value;
 517     xEvent      xE;
 518     if (wColormap(pwin) == *pmid)
 519     {
 520         /* This should be call to DeliverEvent */
 521         xE.u.u.type = ColormapNotify;
 522         xE.u.colormap.window = pwin->drawable.id;
 523         xE.u.colormap.colormap = *pmid;
 524         xE.u.colormap.new = FALSE;
 525         xE.u.colormap.state = ColormapUninstalled;
 526         DeliverEvents(pwin, &xE, 1, (WindowPtr)NULL);
 527     }
 528
 529     return (WT_WALKCHILDREN);
 530 }
 531
 532 /* Tell window that pmid got installed */
 533 int
 534 TellGainedMap (pwin, value)
 535     WindowPtr   pwin;
 536     pointer     value;
 537 {
 538     Colormap    *pmid = (Colormap *)value;
 539     xEvent      xE;
 540     if (wColormap (pwin) == *pmid)
 541     {
 542         /* This should be call to DeliverEvent */
 543         xE.u.u.type = ColormapNotify;
 544         xE.u.colormap.window = pwin->drawable.id;
 545         xE.u.colormap.colormap = *pmid;
 546         xE.u.colormap.new = FALSE;
 547         xE.u.colormap.state = ColormapInstalled;
 548         DeliverEvents(pwin, &xE, 1, (WindowPtr)NULL);
 549     }
 550
 551     return (WT_WALKCHILDREN);
 552 }
 553
 554
 555 int
 556 CopyColormapAndFree (mid, pSrc, client)
 557     Colormap    mid;
 558     ColormapPtr pSrc;
 559     int         client;
 560 {
 561     ColormapPtr pmap = (ColormapPtr) NULL;
 562     int         result, alloc, size;
 563     Colormap    midSrc;
 564     ScreenPtr   pScreen;
 565     VisualPtr   pVisual;
 566
 567     pScreen = pSrc->pScreen;
 568     pVisual = pSrc->pVisual;
 569     midSrc = pSrc->mid;
 570     alloc = ((pSrc->flags & AllAllocated) && CLIENT_ID(midSrc) == client) ?
 571             AllocAll : AllocNone;
 572     size = pVisual->ColormapEntries;
 573
 574     /* If the create returns non-0, it failed */
 575     result = CreateColormap (mid, pScreen, pVisual, &pmap, alloc, client);
 576     if(result != Success)
 577         return(result);
 578     if(alloc == AllocAll)
 579     {
 580         memmove((char *)pmap->red, (char *)pSrc->red, size * sizeof(Entry));
 581         if((pmap->class | DynamicClass) == DirectColor)
 582         {
 583             memmove((char *)pmap->green, (char *)pSrc->green, size * sizeof(Entry));
 584             memmove((char *)pmap->blue, (char *)pSrc->blue, size * sizeof(Entry));
 585         }
 586         pSrc->flags &= ~AllAllocated;
 587         FreePixels(pSrc, client);
 588         UpdateColors(pmap);
 589         return(Success);
 590     }
 591
 592     CopyFree(REDMAP, client, pSrc, pmap);
 593     if ((pmap->class | DynamicClass) == DirectColor)
 594     {
 595         CopyFree(GREENMAP, client, pSrc, pmap);
 596         CopyFree(BLUEMAP, client, pSrc, pmap);
 597     }
 598     if (pmap->class & DynamicClass)
 599         UpdateColors(pmap);
 600     /* XXX should worry about removing any RT_CMAPENTRY resource */
 601     return(Success);
 602 }
 603
 604 /* Helper routine for freeing large numbers of cells from a map */
 605 static void
 606 CopyFree (channel, client, pmapSrc, pmapDst)
 607     int         channel, client;
 608     ColormapPtr pmapSrc, pmapDst;
 609 {
 610     int         z, npix, oldFree;
 611     EntryPtr    pentSrcFirst, pentDstFirst;
 612     EntryPtr    pentSrc, pentDst;
 613     Pixel       *ppix;
 614     int         nalloc;
 615
 616     switch(channel)
 617     {
 618       default:  /* so compiler can see that everything gets initialized */
 619       case REDMAP:
 620         ppix = (pmapSrc->clientPixelsRed)[client];
 621         npix = (pmapSrc->numPixelsRed)[client];
 622         pentSrcFirst = pmapSrc->red;
 623         pentDstFirst = pmapDst->red;
 624         oldFree = pmapSrc->freeRed;
 625         break;
 626       case GREENMAP:
 627         ppix = (pmapSrc->clientPixelsGreen)[client];
 628         npix = (pmapSrc->numPixelsGreen)[client];
 629         pentSrcFirst = pmapSrc->green;
 630         pentDstFirst = pmapDst->green;
 631         oldFree = pmapSrc->freeGreen;
 632         break;
 633       case BLUEMAP:
 634         ppix = (pmapSrc->clientPixelsBlue)[client];
 635         npix = (pmapSrc->numPixelsBlue)[client];
 636         pentSrcFirst = pmapSrc->blue;
 637         pentDstFirst = pmapDst->blue;
 638         oldFree = pmapSrc->freeBlue;
 639         break;
 640     }
 641     nalloc = 0;
 642     if (pmapSrc->class & DynamicClass)
 643     {
 644         for(z = npix; --z >= 0; ppix++)
 645         {
 646             /* Copy entries */
 647             pentSrc = pentSrcFirst + *ppix;
 648             pentDst = pentDstFirst + *ppix;
 649             if (pentDst->refcnt > 0)
 650             {
 651                 pentDst->refcnt++;
 652             }
 653             else
 654             {
 655                 *pentDst = *pentSrc;
 656                 nalloc++;
 657                 if (pentSrc->refcnt > 0)
 658                     pentDst->refcnt = 1;
 659                 else
 660                     pentSrc->fShared = FALSE;
 661             }
 662             FreeCell(pmapSrc, *ppix, channel);
 663         }
 664     }
 665
 666     /* Note that FreeCell has already fixed pmapSrc->free{Color} */
 667     switch(channel)
 668     {
 669       case REDMAP:
 670         pmapDst->freeRed -= nalloc;
 671         (pmapDst->clientPixelsRed)[client] =
 672             (pmapSrc->clientPixelsRed)[client];
 673         (pmapSrc->clientPixelsRed)[client] = (Pixel *) NULL;
 674         (pmapDst->numPixelsRed)[client] = (pmapSrc->numPixelsRed)[client];
 675         (pmapSrc->numPixelsRed)[client] = 0;
 676         break;
 677       case GREENMAP:
 678         pmapDst->freeGreen -= nalloc;
 679         (pmapDst->clientPixelsGreen)[client] =
 680             (pmapSrc->clientPixelsGreen)[client];
 681         (pmapSrc->clientPixelsGreen)[client] = (Pixel *) NULL;
 682         (pmapDst->numPixelsGreen)[client] = (pmapSrc->numPixelsGreen)[client];
 683         (pmapSrc->numPixelsGreen)[client] = 0;
 684         break;
 685       case BLUEMAP:
 686         pmapDst->freeBlue -= nalloc;
 687         pmapDst->clientPixelsBlue[client] = pmapSrc->clientPixelsBlue[client];
 688         pmapSrc->clientPixelsBlue[client] = (Pixel *) NULL;
 689         pmapDst->numPixelsBlue[client] = pmapSrc->numPixelsBlue[client];
 690         pmapSrc->numPixelsBlue[client] = 0;
 691         break;
 692     }
 693 }
 694
 695 /* Free the ith entry in a color map.  Must handle freeing of
 696  * colors allocated through AllocColorPlanes */
 697 static void
 698 FreeCell (pmap, i, channel)
 699     ColormapPtr pmap;
 700     Pixel i;
 701     int channel;
 702 {
 703     EntryPtr pent;
 704     int *pCount;
 705
 706
 707     switch (channel)
 708     {
 709       default:  /* so compiler can see that everything gets initialized */
 710       case PSEUDOMAP:
 711       case REDMAP:
 712           pent = (EntryPtr) &pmap->red[i];
 713           pCount = &pmap->freeRed;
 714           break;
 715       case GREENMAP:
 716           pent = (EntryPtr) &pmap->green[i];
 717           pCount = &pmap->freeGreen;
 718           break;
 719       case BLUEMAP:
 720           pent = (EntryPtr) &pmap->blue[i];
 721           pCount = &pmap->freeBlue;
 722           break;
 723     }
 724     /* If it's not privately allocated and it's not time to free it, just
 725      * decrement the count */
 726     if (pent->refcnt > 1)
 727         pent->refcnt--;
 728     else
 729     {
 730         /* If the color type is shared, find the sharedcolor. If decremented
 731          * refcnt is 0, free the shared cell. */
 732         if (pent->fShared)
 733         {
 734             if(--pent->co.shco.red->refcnt == 0)
 735                 xfree(pent->co.shco.red);
 736             if(--pent->co.shco.green->refcnt == 0)
 737                 xfree(pent->co.shco.green);
 738             if(--pent->co.shco.blue->refcnt == 0)
 739                 xfree(pent->co.shco.blue);
 740             pent->fShared = FALSE;
 741         }
 742         pent->refcnt = 0;
 743         *pCount += 1;
 744     }
 745 }
 746
 747 static void
 748 UpdateColors (pmap)
 749     ColormapPtr pmap;
 750 {
 751     xColorItem          *defs;
 752     register xColorItem *pdef;
 753     register EntryPtr   pent;
 754     register VisualPtr  pVisual;
 755     int                 i, n, size;
 756
 757     pVisual = pmap->pVisual;
 758     size = pVisual->ColormapEntries;
 759     defs = (xColorItem *)ALLOCATE_LOCAL(size * sizeof(xColorItem));
 760     if (!defs)
 761         return;
 762     n = 0;
 763     pdef = defs;
 764     if (pmap->class == DirectColor)
 765     {
 766         for (i = 0; i < size; i++)
 767         {
 768             if (!pmap->red[i].refcnt &&
 769                 !pmap->green[i].refcnt &&
 770                 !pmap->blue[i].refcnt)
 771                 continue;
 772             pdef->pixel = ((Pixel)i << pVisual->offsetRed) |
 773                           ((Pixel)i << pVisual->offsetGreen) |
 774                           ((Pixel)i << pVisual->offsetBlue);
 775             pdef->red = pmap->red[i].co.local.red;
 776             pdef->green = pmap->green[i].co.local.green;
 777             pdef->blue = pmap->blue[i].co.local.blue;
 778             pdef->flags = DoRed|DoGreen|DoBlue;
 779             pdef++;
 780             n++;
 781         }
 782     }
 783     else
 784     {
 785         for (i = 0, pent = pmap->red; i < size; i++, pent++)
 786         {
 787             if (!pent->refcnt)
 788                 continue;
 789             pdef->pixel = i;
 790             if(pent->fShared)
 791             {
 792                 pdef->red = pent->co.shco.red->color;
 793                 pdef->green = pent->co.shco.green->color;
 794                 pdef->blue = pent->co.shco.blue->color;
 795             }
 796             else
 797             {
 798                 pdef->red = pent->co.local.red;
 799                 pdef->green = pent->co.local.green;
 800                 pdef->blue = pent->co.local.blue;
 801             }
 802             pdef->flags = DoRed|DoGreen|DoBlue;
 803             pdef++;
 804             n++;
 805         }
 806     }
 807     if (n)
 808         (*pmap->pScreen->StoreColors)(pmap, n, defs);
 809     DEALLOCATE_LOCAL(defs);
 810 }
 811
 812 /* Get a read-only color from a ColorMap (probably slow for large maps)
 813  * Returns by changing the value in pred, pgreen, pblue and pPix
 814  */
 815 int
 816 AllocColor (pmap, pred, pgreen, pblue, pPix, client)
 817     ColormapPtr         pmap;
 818     unsigned short      *pred, *pgreen, *pblue;
 819     Pixel               *pPix;
 820     int                 client;
 821 {
 822     Pixel       pixR, pixG, pixB;
 823     int         entries;
 824     xrgb        rgb;
 825     int         class;
 826     VisualPtr   pVisual;
 827     int         npix;
 828     Pixel       *ppix;
 829
 830     pVisual = pmap->pVisual;
 831     (*pmap->pScreen->ResolveColor) (pred, pgreen, pblue, pVisual);
 832     rgb.red = *pred;
 833     rgb.green = *pgreen;
 834     rgb.blue = *pblue;
 835     class = pmap->class;
 836     entries = pVisual->ColormapEntries;
 837
 838     /* If the colormap is being created, then we want to be able to change
 839      * the colormap, even if it's a static type. Otherwise, we'd never be
 840      * able to initialize static colormaps
 841      */
 842     if(pmap->flags & BeingCreated)
 843         class |= DynamicClass;
 844
 845     /* If this is one of the static storage classes, and we're not initializing
 846      * it, the best we can do is to find the closest color entry to the
 847      * requested one and return that.
 848      */
 849     switch (class) {
 850     case StaticColor:
 851     case StaticGray:
 852         /* Look up all three components in the same pmap */
 853         *pPix = pixR = FindBestPixel(pmap->red, entries, &rgb, PSEUDOMAP);
 854         *pred = pmap->red[pixR].co.local.red;
 855         *pgreen = pmap->red[pixR].co.local.green;
 856         *pblue = pmap->red[pixR].co.local.blue;
 857         npix = pmap->numPixelsRed[client];
 858         ppix = (Pixel *) xrealloc(pmap->clientPixelsRed[client],
 859                                   (npix + 1) * sizeof(Pixel));
 860         if (!ppix)
 861             return (BadAlloc);
 862         ppix[npix] = pixR;
 863         pmap->clientPixelsRed[client] = ppix;
 864         pmap->numPixelsRed[client]++;
 865         break;
 866
 867     case TrueColor:
 868         /* Look up each component in its own map, then OR them together */
 869         pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP);
 870         pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb, GREENMAP);
 871         pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP);
 872         *pPix = (pixR << pVisual->offsetRed) |
 873                 (pixG << pVisual->offsetGreen) |
 874                 (pixB << pVisual->offsetBlue);
 875         *pred = pmap->red[pixR].co.local.red;
 876         *pgreen = pmap->green[pixG].co.local.green;
 877         *pblue = pmap->blue[pixB].co.local.blue;
 878         npix = pmap->numPixelsRed[client];
 879         ppix = (Pixel *) xrealloc(pmap->clientPixelsRed[client],
 880                                   (npix + 1) * sizeof(Pixel));
 881         if (!ppix)
 882             return (BadAlloc);
 883         ppix[npix] = pixR;
 884         pmap->clientPixelsRed[client] = ppix;
 885         npix = pmap->numPixelsGreen[client];
 886         ppix = (Pixel *) xrealloc(pmap->clientPixelsGreen[client],
 887                                   (npix + 1) * sizeof(Pixel));
 888         if (!ppix)
 889             return (BadAlloc);
 890         ppix[npix] = pixG;
 891         pmap->clientPixelsGreen[client] = ppix;
 892         npix = pmap->numPixelsBlue[client];
 893         ppix = (Pixel *) xrealloc(pmap->clientPixelsBlue[client],
 894                                   (npix + 1) * sizeof(Pixel));
 895         if (!ppix)
 896             return (BadAlloc);
 897         ppix[npix] = pixB;
 898         pmap->clientPixelsBlue[client] = ppix;
 899         pmap->numPixelsRed[client]++;
 900         pmap->numPixelsGreen[client]++;
 901         pmap->numPixelsBlue[client]++;
 902         break;
 903
 904     case GrayScale:
 905     case PseudoColor:
 906         if (FindColor(pmap, pmap->red, entries, &rgb, pPix, PSEUDOMAP,
 907                       client, AllComp) != Success)
 908             return (BadAlloc);
 909         break;
 910
 911     case DirectColor:
 912         pixR = (*pPix & pVisual->redMask) >> pVisual->offsetRed;
 913         if (FindColor(pmap, pmap->red, NUMRED(pVisual), &rgb, &pixR, REDMAP,
 914                       client, RedComp) != Success)
 915             return (BadAlloc);
 916         pixG = (*pPix & pVisual->greenMask) >> pVisual->offsetGreen;
 917         if (FindColor(pmap, pmap->green, NUMGREEN(pVisual), &rgb, &pixG,
 918                       GREENMAP, client, GreenComp) != Success)
 919         {
 920             (void)FreeCo(pmap, client, REDMAP, 1, &pixR, (Pixel)0);
 921             return (BadAlloc);
 922         }
 923         pixB = (*pPix & pVisual->blueMask) >> pVisual->offsetBlue;
 924         if (FindColor(pmap, pmap->blue, NUMBLUE(pVisual), &rgb, &pixB, BLUEMAP,
 925                       client, BlueComp) != Success)
 926         {
 927             (void)FreeCo(pmap, client, GREENMAP, 1, &pixG, (Pixel)0);
 928             (void)FreeCo(pmap, client, REDMAP, 1, &pixR, (Pixel)0);
 929             return (BadAlloc);
 930         }
 931         *pPix = pixR | pixG | pixB;
 932         break;
 933     }
 934
 935     /* if this is the client's first pixel in this colormap, tell the
 936      * resource manager that the client has pixels in this colormap which
 937      * should be freed when the client dies */
 938     if ((pmap->numPixelsRed[client] == 1) &&
 939         (CLIENT_ID(pmap->mid) != client) &&
 940         !(pmap->flags & BeingCreated))
 941     {
 942         colorResource   *pcr;
 943
 944         pcr = (colorResource *) xalloc(sizeof(colorResource));
 945         if (!pcr)
 946         {
 947             (void)FreeColors(pmap, client, 1, pPix, (Pixel)0);
 948             return (BadAlloc);
 949         }
 950         pcr->mid = pmap->mid;
 951         pcr->client = client;
 952         if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (pointer)pcr))
 953             return (BadAlloc);
 954     }
 955     return (Success);
 956 }
 957
 958 /*
 959  * FakeAllocColor -- fake an AllocColor request by
 960  * returning a free pixel if availible, otherwise returning
 961  * the closest matching pixel.  This is used by the mi
 962  * software sprite code to recolor cursors.  A nice side-effect
 963  * is that this routine will never return failure.
 964  */
 965
 966 void
 967 FakeAllocColor (pmap, item)
 968     register ColormapPtr pmap;
 969     register xColorItem  *item;
 970 {
 971     Pixel       pixR, pixG, pixB;
 972     Pixel       temp;
 973     int         entries;
 974     xrgb        rgb;
 975     int         class;
 976     register VisualPtr  pVisual;
 977
 978     pVisual = pmap->pVisual;
 979     rgb.red = item->red;
 980     rgb.green = item->green;
 981     rgb.blue = item->blue;
 982     (*pmap->pScreen->ResolveColor) (&rgb.red, &rgb.green, &rgb.blue, pVisual);
 983     class = pmap->class;
 984     entries = pVisual->ColormapEntries;
 985
 986     switch (class) {
 987     case GrayScale:
 988     case PseudoColor:
 989         item->pixel = 0;
 990         if (FindColor(pmap, pmap->red, entries, &rgb, &temp, PSEUDOMAP,
 991                       -1, AllComp) == Success) {
 992             item->pixel = temp;
 993             break;
 994         }
 995         /* fall through ... */
 996     case StaticColor:
 997     case StaticGray:
 998         item->pixel = FindBestPixel(pmap->red, entries, &rgb, PSEUDOMAP);
 999         break;
1000
1001     case DirectColor:
1002         /* Look up each component in its own map, then OR them together */
1003         pixR = (item->pixel & pVisual->redMask) >> pVisual->offsetRed;
1004         pixG = (item->pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1005         pixB = (item->pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1006         if (FindColor(pmap, pmap->red, NUMRED(pVisual), &rgb, &pixR, REDMAP,
1007                       -1, RedComp) != Success)
1008             pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP)
1009                         << pVisual->offsetRed;
1010         if (FindColor(pmap, pmap->green, NUMGREEN(pVisual), &rgb, &pixG,
1011                       GREENMAP, -1, GreenComp) != Success)
1012             pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb,
1013                                  GREENMAP) << pVisual->offsetGreen;
1014         if (FindColor(pmap, pmap->blue, NUMBLUE(pVisual), &rgb, &pixB, BLUEMAP,
1015                       -1, BlueComp) != Success)
1016             pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP)
1017                         << pVisual->offsetBlue;
1018         item->pixel = pixR | pixG | pixB;
1019         break;
1020
1021     case TrueColor:
1022         /* Look up each component in its own map, then OR them together */
1023         pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP);
1024         pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb, GREENMAP);
1025         pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP);
1026         item->pixel = (pixR << pVisual->offsetRed) |
1027                       (pixG << pVisual->offsetGreen) |
1028                       (pixB << pVisual->offsetBlue);
1029         break;
1030     }
1031 }
1032
1033 /* free a pixel value obtained from FakeAllocColor */
1034 void
1035 FakeFreeColor(pmap, pixel)
1036     register ColormapPtr pmap;
1037     Pixel pixel;
1038 {
1039     register VisualPtr pVisual;
1040     Pixel pixR, pixG, pixB;
1041
1042     switch (pmap->class) {
1043     case GrayScale:
1044     case PseudoColor:
1045         if (pmap->red[pixel].refcnt == AllocTemporary)
1046             pmap->red[pixel].refcnt = 0;
1047         break;
1048     case DirectColor:
1049         pVisual = pmap->pVisual;
1050         pixR = (pixel & pVisual->redMask) >> pVisual->offsetRed;
1051         pixG = (pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1052         pixB = (pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1053         if (pmap->red[pixR].refcnt == AllocTemporary)
1054             pmap->red[pixR].refcnt = 0;
1055         if (pmap->green[pixG].refcnt == AllocTemporary)
1056             pmap->green[pixG].refcnt = 0;
1057         if (pmap->blue[pixB].refcnt == AllocTemporary)
1058             pmap->blue[pixB].refcnt = 0;
1059         break;
1060     }
1061 }
1062
1063 typedef unsigned short  BigNumUpper;
1064 typedef unsigned long   BigNumLower;
1065
1066 #define BIGNUMLOWERBITS 24
1067 #define BIGNUMUPPERBITS 16
1068 #define BIGNUMLOWER (1 << BIGNUMLOWERBITS)
1069 #define BIGNUMUPPER (1 << BIGNUMUPPERBITS)
1070 #define UPPERPART(i)    ((i) >> BIGNUMLOWERBITS)
1071 #define LOWERPART(i)    ((i) & (BIGNUMLOWER - 1))
1072
1073 typedef struct _bignum {
1074     BigNumUpper upper;
1075     BigNumLower lower;
1076 } BigNumRec, *BigNumPtr;
1077
1078 #define BigNumGreater(x,y) (((x)->upper > (y)->upper) ||\
1079                             ((x)->upper == (y)->upper && (x)->lower > (y)->lower))
1080
1081 #define UnsignedToBigNum(u,r)   (((r)->upper = UPPERPART(u)), \
1082                                  ((r)->lower = LOWERPART(u)))
1083
1084 #define MaxBigNum(r)            (((r)->upper = BIGNUMUPPER-1), \
1085                                  ((r)->lower = BIGNUMLOWER-1))
1086
1087 static void
1088 #if NeedFunctionPrototypes
1089 BigNumAdd (BigNumPtr x, BigNumPtr y, BigNumPtr r)
1090 #else
1091 BigNumAdd (x, y, r)
1092     BigNumPtr   x, y, r;
1093 #endif
1094 {
1095     BigNumLower lower, carry = 0;
1096
1097     lower = x->lower + y->lower;
1098     if (lower >= BIGNUMLOWER) {
1099         lower -= BIGNUMLOWER;
1100         carry = 1;
1101     }
1102     r->lower = lower;
1103     r->upper = x->upper + y->upper + carry;
1104 }
1105
1106 static Pixel
1107 FindBestPixel(pentFirst, size, prgb, channel)
1108     EntryPtr    pentFirst;
1109     int         size;
1110     xrgb        *prgb;
1111     int         channel;
1112 {
1113     EntryPtr    pent;
1114     Pixel       pixel, final;
1115     long        dr, dg, db;
1116     unsigned long   sq;
1117     BigNumRec   minval, sum, temp;
1118
1119     final = 0;
1120     MaxBigNum(&minval);
1121     /* look for the minimal difference */
1122     for (pent = pentFirst, pixel = 0; pixel < size; pent++, pixel++)
1123     {
1124         dr = dg = db = 0;
1125         switch(channel)
1126         {
1127           case PSEUDOMAP:
1128               dg = pent->co.local.green - prgb->green;
1129               db = pent->co.local.blue - prgb->blue;
1130           case REDMAP:
1131               dr = pent->co.local.red - prgb->red;
1132               break;
1133           case GREENMAP:
1134               dg = pent->co.local.green - prgb->green;
1135               break;
1136           case BLUEMAP:
1137               db = pent->co.local.blue - prgb->blue;
1138               break;
1139         }
1140         sq = dr * dr;
1141         UnsignedToBigNum (sq, &sum);
1142         sq = dg * dg;
1143         UnsignedToBigNum (sq, &temp);
1144         BigNumAdd (&sum, &temp, &sum);
1145         sq = db * db;
1146         UnsignedToBigNum (sq, &temp);
1147         BigNumAdd (&sum, &temp, &sum);
1148         if (BigNumGreater (&minval, &sum))
1149         {
1150             final = pixel;
1151             minval = sum;
1152         }
1153     }
1154     return(final);
1155 }
1156
1157 /* Tries to find a color in pmap that exactly matches the one requested in prgb
1158  * if it can't it allocates one.
1159  * Starts looking at pentFirst + *pPixel, so if you want a specific pixel,
1160  * load *pPixel with that value, otherwise set it to 0
1161  */
1162 int
1163 FindColor (pmap, pentFirst, size, prgb, pPixel, channel, client, comp)
1164     ColormapPtr pmap;
1165     EntryPtr    pentFirst;
1166     int         size;
1167     xrgb        *prgb;
1168     Pixel       *pPixel;
1169     int         channel;
1170     int         client;
1171     ColorCompareProcPtr comp;
1172 {
1173     EntryPtr    pent;
1174     Bool        foundFree;
1175     Pixel       pixel, Free;
1176     int         npix, count, *nump;
1177     Pixel       **pixp, *ppix;
1178     xColorItem  def;
1179
1180     foundFree = FALSE;
1181
1182     if((pixel = *pPixel) >= size)
1183         pixel = 0;
1184     /* see if there is a match, and also look for a free entry */
1185     for (pent = pentFirst + pixel, count = size; --count >= 0; )
1186     {
1187         if (pent->refcnt > 0)
1188         {
1189             if ((*comp) (pent, prgb))
1190             {
1191                 if (client >= 0)
1192                     pent->refcnt++;
1193                 *pPixel = pixel;
1194                 switch(channel)
1195                 {
1196                   case REDMAP:
1197                     *pPixel <<= pmap->pVisual->offsetRed;
1198                   case PSEUDOMAP:
1199                     break;
1200                   case GREENMAP:
1201                     *pPixel <<= pmap->pVisual->offsetGreen;
1202                     break;
1203                   case BLUEMAP:
1204                     *pPixel <<= pmap->pVisual->offsetBlue;
1205                     break;
1206                 }
1207                 goto gotit;
1208             }
1209         }
1210         else if (!foundFree && pent->refcnt == 0)
1211         {
1212             Free = pixel;
1213             foundFree = TRUE;
1214             /* If we're initializing the colormap, then we are looking for
1215              * the first free cell we can find, not to minimize the number
1216              * of entries we use.  So don't look any further. */
1217             if(pmap->flags & BeingCreated)
1218                 break;
1219         }
1220         pixel++;
1221         if(pixel >= size)
1222         {
1223             pent = pentFirst;
1224             pixel = 0;
1225         }
1226         else
1227             pent++;
1228     }
1229
1230     /* If we got here, we didn't find a match.  If we also didn't find
1231      * a free entry, we're out of luck.  Otherwise, we'll usurp a free
1232      * entry and fill it in */
1233     if (!foundFree)
1234         return (BadAlloc);
1235     pent = pentFirst + Free;
1236     pent->fShared = FALSE;
1237     pent->refcnt = (client >= 0) ? 1 : AllocTemporary;
1238
1239     switch (channel)
1240     {
1241       case PSEUDOMAP:
1242         pent->co.local.red = prgb->red;
1243         pent->co.local.green = prgb->green;
1244         pent->co.local.blue = prgb->blue;
1245         def.red = prgb->red;
1246         def.green = prgb->green;
1247         def.blue = prgb->blue;
1248         def.flags = (DoRed|DoGreen|DoBlue);
1249         if (client >= 0)
1250             pmap->freeRed--;
1251         def.pixel = Free;
1252         break;
1253
1254       case REDMAP:
1255         pent->co.local.red = prgb->red;
1256         def.red = prgb->red;
1257         def.green = pmap->green[0].co.local.green;
1258         def.blue = pmap->blue[0].co.local.blue;
1259         def.flags = DoRed;
1260         if (client >= 0)
1261             pmap->freeRed--;
1262         def.pixel = Free << pmap->pVisual->offsetRed;
1263         break;
1264
1265       case GREENMAP:
1266         pent->co.local.green = prgb->green;
1267         def.red = pmap->red[0].co.local.red;
1268         def.green = prgb->green;
1269         def.blue = pmap->blue[0].co.local.blue;
1270         def.flags = DoGreen;
1271         if (client >= 0)
1272             pmap->freeGreen--;
1273         def.pixel = Free << pmap->pVisual->offsetGreen;
1274         break;
1275
1276       case BLUEMAP:
1277         pent->co.local.blue = prgb->blue;
1278         def.red = pmap->red[0].co.local.red;
1279         def.green = pmap->green[0].co.local.green;
1280         def.blue = prgb->blue;
1281         def.flags = DoBlue;
1282         if (client >= 0)
1283             pmap->freeBlue--;
1284         def.pixel = Free << pmap->pVisual->offsetBlue;
1285         break;
1286     }
1287     (*pmap->pScreen->StoreColors) (pmap, 1, &def);
1288     pixel = Free;
1289     *pPixel = def.pixel;
1290
1291 gotit:
1292     if (pmap->flags & BeingCreated || client == -1)
1293         return(Success);
1294     /* Now remember the pixel, for freeing later */
1295     switch (channel)
1296     {
1297       case PSEUDOMAP:
1298       case REDMAP:
1299         nump = pmap->numPixelsRed;
1300         pixp = pmap->clientPixelsRed;
1301         break;
1302
1303       case GREENMAP:
1304         nump = pmap->numPixelsGreen;
1305         pixp = pmap->clientPixelsGreen;
1306         break;
1307
1308       case BLUEMAP:
1309         nump = pmap->numPixelsBlue;
1310         pixp = pmap->clientPixelsBlue;
1311         break;
1312     }
1313     npix = nump[client];
1314     ppix = (Pixel *) xrealloc (pixp[client], (npix + 1) * sizeof(Pixel));
1315     if (!ppix)
1316     {
1317         pent->refcnt--;
1318         if (!pent->fShared)
1319             switch (channel)
1320             {
1321               case PSEUDOMAP:
1322               case REDMAP:
1323                 pmap->freeRed++;
1324                 break;
1325               case GREENMAP:
1326                 pmap->freeGreen++;
1327                 break;
1328               case BLUEMAP:
1329                 pmap->freeBlue++;
1330                 break;
1331             }
1332         return(BadAlloc);
1333     }
1334     ppix[npix] = pixel;
1335     pixp[client] = ppix;
1336     nump[client]++;
1337
1338     return(Success);
1339 }
1340
1341 /* Comparison functions -- passed to FindColor to determine if an
1342  * entry is already the color we're looking for or not */
1343 static int
1344 AllComp (pent, prgb)
1345     EntryPtr    pent;
1346     xrgb        *prgb;
1347 {
1348     if((pent->co.local.red == prgb->red) &&
1349        (pent->co.local.green == prgb->green) &&
1350        (pent->co.local.blue == prgb->blue) )
1351        return (1);
1352     return (0);
1353 }
1354
1355 static int
1356 RedComp (pent, prgb)
1357     EntryPtr    pent;
1358     xrgb        *prgb;
1359 {
1360     if (pent->co.local.red == prgb->red)
1361         return (1);
1362     return (0);
1363 }
1364
1365 static int
1366 GreenComp (pent, prgb)
1367     EntryPtr    pent;
1368     xrgb        *prgb;
1369 {
1370     if (pent->co.local.green == prgb->green)
1371         return (1);
1372     return (0);
1373 }
1374
1375 static int
1376 BlueComp (pent, prgb)
1377     EntryPtr    pent;
1378     xrgb        *prgb;
1379 {
1380     if (pent->co.local.blue == prgb->blue)
1381         return (1);
1382     return (0);
1383 }
1384
1385
1386 /* Read the color value of a cell */
1387
1388 int
1389 QueryColors (pmap, count, ppixIn, prgbList)
1390     ColormapPtr pmap;
1391     int         count;
1392     Pixel       *ppixIn;
1393     xrgb        *prgbList;
1394 {
1395     Pixel       *ppix, pixel;
1396     xrgb        *prgb;
1397     VisualPtr   pVisual;
1398     EntryPtr    pent;
1399     Pixel       i;
1400     int         errVal = Success;
1401
1402     pVisual = pmap->pVisual;
1403     if ((pmap->class | DynamicClass) == DirectColor)
1404     {
1405         int numred, numgreen, numblue;
1406         Pixel rgbbad;
1407
1408         numred = NUMRED(pVisual);
1409         numgreen = NUMGREEN(pVisual);
1410         numblue = NUMBLUE(pVisual);
1411         rgbbad = ~RGBMASK(pVisual);
1412         for( ppix = ppixIn, prgb = prgbList; --count >= 0; ppix++, prgb++)
1413         {
1414             pixel = *ppix;
1415             if (pixel & rgbbad) {
1416                 clientErrorValue = pixel;
1417                 errVal =  BadValue;
1418                 continue;
1419             }
1420             i  = (pixel & pVisual->redMask) >> pVisual->offsetRed;
1421             if (i >= numred)
1422             {
1423                 clientErrorValue = pixel;
1424                 errVal =  BadValue;
1425                 continue;
1426             }
1427             prgb->red = pmap->red[i].co.local.red;
1428             i  = (pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1429             if (i >= numgreen)
1430             {
1431                 clientErrorValue = pixel;
1432                 errVal =  BadValue;
1433                 continue;
1434             }
1435             prgb->green = pmap->green[i].co.local.green;
1436             i  = (pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1437             if (i >= numblue)
1438             {
1439                 clientErrorValue = pixel;
1440                 errVal =  BadValue;
1441                 continue;
1442             }
1443             prgb->blue = pmap->blue[i].co.local.blue;
1444         }
1445     }
1446     else
1447     {
1448         for( ppix = ppixIn, prgb = prgbList; --count >= 0; ppix++, prgb++)
1449         {
1450             pixel = *ppix;
1451             if (pixel >= pVisual->ColormapEntries)
1452             {
1453                 clientErrorValue = pixel;
1454                 errVal = BadValue;
1455             }
1456             else
1457             {
1458                 pent = (EntryPtr)&pmap->red[pixel];
1459                 if (pent->fShared)
1460                 {
1461                     prgb->red = pent->co.shco.red->color;
1462                     prgb->green = pent->co.shco.green->color;
1463                     prgb->blue = pent->co.shco.blue->color;
1464                 }
1465                 else
1466                 {
1467                     prgb->red = pent->co.local.red;
1468                     prgb->green = pent->co.local.green;
1469                     prgb->blue = pent->co.local.blue;
1470                 }
1471             }
1472         }
1473     }
1474     return (errVal);
1475 }
1476
1477 static void
1478 FreePixels(pmap, client)
1479     register ColormapPtr        pmap;
1480     register int                client;
1481 {
1482     register Pixel              *ppix, *ppixStart;
1483     register int                n;
1484     int                         class;
1485 #ifdef LBX
1486     Bool                        grabbed;
1487     Bool                        zeroRefCount;
1488     Bool                        anyRefCountReachedZero = 0;
1489 #endif
1490
1491     class = pmap->class;
1492     ppixStart = pmap->clientPixelsRed[client];
1493     if (class & DynamicClass)
1494     {
1495         n = pmap->numPixelsRed[client];
1496 #ifdef LBX
1497         grabbed = LbxCheckCmapGrabbed (pmap);
1498         if (grabbed)
1499         {
1500             /*
1501              * If the colormap is grabbed by a proxy, the server must
1502              * notify the proxy of all cells that are freed (the refcount
1503              * has reached zero on these cells).
1504              */
1505
1506             LbxBeginFreeCellsEvent (pmap);
1507             LbxSortPixelList (ppixStart, n);
1508         }
1509 #endif
1510         for (ppix = ppixStart; --n >= 0; )
1511         {
1512             FreeCell(pmap, *ppix, REDMAP);
1513 #ifdef LBX
1514             /*
1515              * Only PSEUDO colormaps are grabbed by LBX proxies.
1516              * Check if the ref count reached zero on this pixel.
1517              */
1518
1519             zeroRefCount = pmap->red[*ppix].refcnt == 0;
1520             if (zeroRefCount)
1521                 anyRefCountReachedZero = 1;
1522
1523             if (grabbed && zeroRefCount)
1524                 LbxAddFreeCellToEvent (pmap, *ppix);
1525 #endif
1526             ppix++;
1527         }
1528 #ifdef LBX
1529         if (grabbed)
1530             LbxEndFreeCellsEvent (pmap);
1531         else if (anyRefCountReachedZero)
1532         {
1533             /*
1534              * We only send LbxFreeCell events to a proxy that has the colormap
1535              * grabbed.  If the colormap is not grabbed, the proxy that last
1536              * had the colormap grabbed will not be able to do a smart grab
1537              * in the future.  A smart grab can only occur if the proxy is kept
1538              * up to date on every alloc/free change in the colormap.
1539              */
1540
1541             LbxDisableSmartGrab (pmap);
1542         }
1543 #endif
1544     }
1545
1546     xfree(ppixStart);
1547     pmap->clientPixelsRed[client] = (Pixel *) NULL;
1548     pmap->numPixelsRed[client] = 0;
1549     if ((class | DynamicClass) == DirectColor)
1550     {
1551         ppixStart = pmap->clientPixelsGreen[client];
1552         if (class & DynamicClass)
1553             for (ppix = ppixStart, n = pmap->numPixelsGreen[client]; --n >= 0;)
1554                 FreeCell(pmap, *ppix++, GREENMAP);
1555         xfree(ppixStart);
1556         pmap->clientPixelsGreen[client] = (Pixel *) NULL;
1557         pmap->numPixelsGreen[client] = 0;
1558
1559         ppixStart = pmap->clientPixelsBlue[client];
1560         if (class & DynamicClass)
1561             for (ppix = ppixStart, n = pmap->numPixelsBlue[client]; --n >= 0; )
1562                 FreeCell(pmap, *ppix++, BLUEMAP);
1563         xfree(ppixStart);
1564         pmap->clientPixelsBlue[client] = (Pixel *) NULL;
1565         pmap->numPixelsBlue[client] = 0;
1566     }
1567 }
1568
1569 /* Free all of a client's colors and cells */
1570 /*ARGSUSED*/
1571 int
1572 FreeClientPixels (value, fakeid)
1573     pointer value;  /* must conform to DeleteType */
1574     XID fakeid;
1575 {
1576     ColormapPtr pmap;
1577     colorResource *pcr = (colorResource *)value;
1578
1579     pmap = (ColormapPtr) LookupIDByType(pcr->mid, RT_COLORMAP);
1580     if (pmap)
1581         FreePixels(pmap, pcr->client);
1582     xfree(pcr);
1583     return Success;
1584 }
1585
1586 int
1587 AllocColorCells (client, pmap, colors, planes, contig, ppix, masks)
1588     int         client;
1589     ColormapPtr pmap;
1590     int         colors, planes;
1591     Bool        contig;
1592     Pixel       *ppix;
1593     Pixel       *masks;
1594 {
1595     Pixel       rmask, gmask, bmask, *ppixFirst, r, g, b;
1596     int         n, class;
1597     int         ok;
1598     int         oldcount;
1599     colorResource *pcr = (colorResource *)NULL;
1600
1601     class = pmap->class;
1602     if (!(class & DynamicClass))
1603         return (BadAlloc); /* Shouldn't try on this type */
1604     oldcount = pmap->numPixelsRed[client];
1605     if (pmap->class == DirectColor)
1606         oldcount += pmap->numPixelsGreen[client] + pmap->numPixelsBlue[client];
1607     if (!oldcount && (CLIENT_ID(pmap->mid) != client))
1608     {
1609         pcr = (colorResource *) xalloc(sizeof(colorResource));
1610         if (!pcr)
1611             return (BadAlloc);
1612     }
1613
1614     if (pmap->class == DirectColor)
1615     {
1616         ok = AllocDirect (client, pmap, colors, planes, planes, planes,
1617                           contig, ppix, &rmask, &gmask, &bmask);
1618         if(ok == Success)
1619         {
1620             for (r = g = b = 1, n = planes; --n >= 0; r += r, g += g, b += b)
1621             {
1622                 while(!(rmask & r))
1623                     r += r;
1624                 while(!(gmask & g))
1625                     g += g;
1626                 while(!(bmask & b))
1627                     b += b;
1628                 *masks++ = r | g | b;
1629             }
1630         }
1631     }
1632     else
1633     {
1634         ok = AllocPseudo (client, pmap, colors, planes, contig, ppix, &rmask,
1635                           &ppixFirst);
1636         if(ok == Success)
1637         {
1638             for (r = 1, n = planes; --n >= 0; r += r)
1639             {
1640                 while(!(rmask & r))
1641                     r += r;
1642                 *masks++ = r;
1643             }
1644         }
1645     }
1646
1647     /* if this is the client's first pixels in this colormap, tell the
1648      * resource manager that the client has pixels in this colormap which
1649      * should be freed when the client dies */
1650     if ((ok == Success) && pcr)
1651     {
1652         pcr->mid = pmap->mid;
1653         pcr->client = client;
1654         if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (pointer)pcr))
1655             ok = BadAlloc;
1656     } else if (pcr)
1657         xfree(pcr);
1658
1659     return (ok);
1660 }
1661
1662
1663 int
1664 AllocColorPlanes (client, pmap, colors, r, g, b, contig, pixels,
1665                   prmask, pgmask, pbmask)
1666     int         client;
1667     ColormapPtr pmap;
1668     int         colors, r, g, b;
1669     Bool        contig;
1670     Pixel       *pixels;
1671     Pixel       *prmask, *pgmask, *pbmask;
1672 {
1673     int         ok;
1674     Pixel       mask, *ppixFirst;
1675     register Pixel shift;
1676     register int i;
1677     int         class;
1678     int         oldcount;
1679     colorResource *pcr = (colorResource *)NULL;
1680
1681     class = pmap->class;
1682     if (!(class & DynamicClass))
1683         return (BadAlloc); /* Shouldn't try on this type */
1684     oldcount = pmap->numPixelsRed[client];
1685     if (class == DirectColor)
1686         oldcount += pmap->numPixelsGreen[client] + pmap->numPixelsBlue[client];
1687     if (!oldcount && (CLIENT_ID(pmap->mid) != client))
1688     {
1689         pcr = (colorResource *) xalloc(sizeof(colorResource));
1690         if (!pcr)
1691             return (BadAlloc);
1692     }
1693
1694     if (class == DirectColor)
1695     {
1696         ok = AllocDirect (client, pmap, colors, r, g, b, contig, pixels,
1697                           prmask, pgmask, pbmask);
1698     }
1699     else
1700     {
1701         /* Allocate the proper pixels */
1702         /* XXX This is sort of bad, because of contig is set, we force all
1703          * r + g + b bits to be contiguous.  Should only force contiguity
1704          * per mask
1705          */
1706         ok = AllocPseudo (client, pmap, colors, r + g + b, contig, pixels,
1707                           &mask, &ppixFirst);
1708
1709         if(ok == Success)
1710         {
1711             /* now split that mask into three */
1712             *prmask = *pgmask = *pbmask = 0;
1713             shift = 1;
1714             for (i = r; --i >= 0; shift += shift)
1715             {
1716                 while (!(mask & shift))
1717                     shift += shift;
1718                 *prmask |= shift;
1719             }
1720             for (i = g; --i >= 0; shift += shift)
1721             {
1722                 while (!(mask & shift))
1723                     shift += shift;
1724                 *pgmask |= shift;
1725             }
1726             for (i = b; --i >= 0; shift += shift)
1727             {
1728                 while (!(mask & shift))
1729                     shift += shift;
1730                 *pbmask |= shift;
1731             }
1732
1733             /* set up the shared color cells */
1734             if (!AllocShared(pmap, pixels, colors, r, g, b,
1735                              *prmask, *pgmask, *pbmask, ppixFirst))
1736             {
1737                 (void)FreeColors(pmap, client, colors, pixels, mask);
1738                 ok = BadAlloc;
1739             }
1740         }
1741     }
1742
1743     /* if this is the client's first pixels in this colormap, tell the
1744      * resource manager that the client has pixels in this colormap which
1745      * should be freed when the client dies */
1746     if ((ok == Success) && pcr)
1747     {
1748         pcr->mid = pmap->mid;
1749         pcr->client = client;
1750         if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (pointer)pcr))
1751             ok = BadAlloc;
1752     } else if (pcr)
1753         xfree(pcr);
1754
1755     return (ok);
1756 }
1757
1758 static int
1759 AllocDirect (client, pmap, c, r, g, b, contig, pixels, prmask, pgmask, pbmask)
1760     int         client;
1761     ColormapPtr pmap;
1762     int         c, r, g, b;
1763     Bool        contig;
1764     Pixel       *pixels;
1765     Pixel       *prmask, *pgmask, *pbmask;
1766 {
1767     Pixel       *ppixRed, *ppixGreen, *ppixBlue;
1768     Pixel       *ppix, *pDst, *p;
1769     int         npix, npixR, npixG, npixB;
1770     Bool        okR, okG, okB;
1771     Pixel       *rpix = 0, *gpix = 0, *bpix = 0;
1772
1773     npixR = c << r;
1774     npixG = c << g;
1775     npixB = c << b;
1776     if ((r >= 32) || (g >= 32) || (b >= 32) ||
1777         (npixR > pmap->freeRed) || (npixR < c) ||
1778         (npixG > pmap->freeGreen) || (npixG < c) ||
1779         (npixB > pmap->freeBlue) || (npixB < c))
1780         return BadAlloc;
1781
1782     /* start out with empty pixels */
1783     for(p = pixels; p < pixels + c; p++)
1784         *p = 0;
1785
1786     ppixRed = (Pixel *)ALLOCATE_LOCAL(npixR * sizeof(Pixel));
1787     ppixGreen = (Pixel *)ALLOCATE_LOCAL(npixG * sizeof(Pixel));
1788     ppixBlue = (Pixel *)ALLOCATE_LOCAL(npixB * sizeof(Pixel));
1789     if (!ppixRed || !ppixGreen || !ppixBlue)
1790     {
1791         if (ppixBlue) DEALLOCATE_LOCAL(ppixBlue);
1792         if (ppixGreen) DEALLOCATE_LOCAL(ppixGreen);
1793         if (ppixRed) DEALLOCATE_LOCAL(ppixRed);
1794         return(BadAlloc);
1795     }
1796
1797     okR = AllocCP(pmap, pmap->red, c, r, contig, ppixRed, prmask);
1798     okG = AllocCP(pmap, pmap->green, c, g, contig, ppixGreen, pgmask);
1799     okB = AllocCP(pmap, pmap->blue, c, b, contig, ppixBlue, pbmask);
1800
1801     if (okR && okG && okB)
1802     {
1803         rpix = (Pixel *) xrealloc(pmap->clientPixelsRed[client],
1804                                   (pmap->numPixelsRed[client] + (c << r)) *
1805                                   sizeof(Pixel));
1806         if (rpix)
1807             pmap->clientPixelsRed[client] = rpix;
1808         gpix = (Pixel *) xrealloc(pmap->clientPixelsGreen[client],
1809                                   (pmap->numPixelsGreen[client] + (c << g)) *
1810                                   sizeof(Pixel));
1811         if (gpix)
1812             pmap->clientPixelsGreen[client] = gpix;
1813         bpix = (Pixel *) xrealloc(pmap->clientPixelsBlue[client],
1814                                   (pmap->numPixelsBlue[client] + (c << b)) *
1815                                   sizeof(Pixel));
1816         if (bpix)
1817             pmap->clientPixelsBlue[client] = bpix;
1818     }
1819
1820     if (!okR || !okG || !okB || !rpix || !gpix || !bpix)
1821     {
1822         if (okR)
1823             for(ppix = ppixRed, npix = npixR; --npix >= 0; ppix++)
1824                 pmap->red[*ppix].refcnt = 0;
1825         if (okG)
1826             for(ppix = ppixGreen, npix = npixG; --npix >= 0; ppix++)
1827                 pmap->green[*ppix].refcnt = 0;
1828         if (okB)
1829             for(ppix = ppixBlue, npix = npixB; --npix >= 0; ppix++)
1830                 pmap->blue[*ppix].refcnt = 0;
1831         DEALLOCATE_LOCAL(ppixBlue);
1832         DEALLOCATE_LOCAL(ppixGreen);
1833         DEALLOCATE_LOCAL(ppixRed);
1834         return(BadAlloc);
1835     }
1836
1837     *prmask <<= pmap->pVisual->offsetRed;
1838     *pgmask <<= pmap->pVisual->offsetGreen;
1839     *pbmask <<= pmap->pVisual->offsetBlue;
1840
1841     ppix = rpix + pmap->numPixelsRed[client];
1842     for (pDst = pixels, p = ppixRed; p < ppixRed + npixR; p++)
1843     {
1844         *ppix++ = *p;
1845         if(p < ppixRed + c)
1846             *pDst++ |= *p << pmap->pVisual->offsetRed;
1847     }
1848     pmap->numPixelsRed[client] += npixR;
1849     pmap->freeRed -= npixR;
1850
1851     ppix = gpix + pmap->numPixelsGreen[client];
1852     for (pDst = pixels, p = ppixGreen; p < ppixGreen + npixG; p++)
1853     {
1854         *ppix++ = *p;
1855         if(p < ppixGreen + c)
1856             *pDst++ |= *p << pmap->pVisual->offsetGreen;
1857     }
1858     pmap->numPixelsGreen[client] += npixG;
1859     pmap->freeGreen -= npixG;
1860
1861     ppix = bpix + pmap->numPixelsBlue[client];
1862     for (pDst = pixels, p = ppixBlue; p < ppixBlue + npixB; p++)
1863     {
1864         *ppix++ = *p;
1865         if(p < ppixBlue + c)
1866             *pDst++ |= *p << pmap->pVisual->offsetBlue;
1867     }
1868     pmap->numPixelsBlue[client] += npixB;
1869     pmap->freeBlue -= npixB;
1870
1871     DEALLOCATE_LOCAL(ppixBlue);
1872     DEALLOCATE_LOCAL(ppixGreen);
1873     DEALLOCATE_LOCAL(ppixRed);
1874
1875     return (Success);
1876 }
1877
1878 static int
1879 AllocPseudo (client, pmap, c, r, contig, pixels, pmask, pppixFirst)
1880     int         client;
1881     ColormapPtr pmap;
1882     int         c, r;
1883     Bool        contig;
1884     Pixel       *pixels;
1885     Pixel       *pmask;
1886     Pixel       **pppixFirst;
1887 {
1888     Pixel       *ppix, *p, *pDst, *ppixTemp;
1889     int         npix;
1890     Bool        ok;
1891
1892     npix = c << r;
1893     if ((r >= 32) || (npix > pmap->freeRed) || (npix < c))
1894         return(BadAlloc);
1895     if(!(ppixTemp = (Pixel *)ALLOCATE_LOCAL(npix * sizeof(Pixel))))
1896         return(BadAlloc);
1897     ok = AllocCP(pmap, pmap->red, c, r, contig, ppixTemp, pmask);
1898
1899     if (ok)
1900     {
1901
1902         /* all the allocated pixels are added to the client pixel list,
1903          * but only the unique ones are returned to the client */
1904         ppix = (Pixel *)xrealloc(pmap->clientPixelsRed[client],
1905                          (pmap->numPixelsRed[client] + npix) * sizeof(Pixel));
1906         if (!ppix)
1907         {
1908             for (p = ppixTemp; p < ppixTemp + npix; p++)
1909                 pmap->red[*p].refcnt = 0;
1910             return (BadAlloc);
1911         }
1912         pmap->clientPixelsRed[client] = ppix;
1913         ppix += pmap->numPixelsRed[client];
1914         *pppixFirst = ppix;
1915         pDst = pixels;
1916         for (p = ppixTemp; p < ppixTemp + npix; p++)
1917         {
1918             *ppix++ = *p;
1919             if(p < ppixTemp + c)
1920                 *pDst++ = *p;
1921         }
1922         pmap->numPixelsRed[client] += npix;
1923         pmap->freeRed -= npix;
1924     }
1925     DEALLOCATE_LOCAL(ppixTemp);
1926     return (ok ? Success : BadAlloc);
1927 }
1928
1929 /* Allocates count << planes pixels from colormap pmap for client. If
1930  * contig, then the plane mask is made of consecutive bits.  Returns
1931  * all count << pixels in the array pixels. The first count of those
1932  * pixels are the unique pixels.  *pMask has the mask to Or with the
1933  * unique pixels to get the rest of them.
1934  *
1935  * Returns True iff all pixels could be allocated
1936  * All cells allocated will have refcnt set to AllocPrivate and shared to FALSE
1937  * (see AllocShared for why we care)
1938  */
1939 static Bool
1940 AllocCP (pmap, pentFirst, count, planes, contig, pixels, pMask)
1941     ColormapPtr pmap;
1942     EntryPtr    pentFirst;
1943     int         count, planes;
1944     Bool        contig;
1945     Pixel       *pixels, *pMask;
1946
1947 {
1948     EntryPtr    ent;
1949     Pixel       pixel, base, entries, maxp, save;
1950     int         dplanes, found;
1951     Pixel       *ppix;
1952     Pixel       mask;
1953     Pixel       finalmask;
1954
1955     dplanes = pmap->pVisual->nplanes;
1956
1957     /* Easy case.  Allocate pixels only */
1958     if (planes == 0)
1959     {
1960         /* allocate writable entries */
1961         ppix = pixels;
1962         ent = pentFirst;
1963         pixel = 0;
1964         while (--count >= 0)
1965         {
1966             /* Just find count unallocated cells */
1967             while (ent->refcnt)
1968             {
1969                 ent++;
1970                 pixel++;
1971             }
1972             ent->refcnt = AllocPrivate;
1973             *ppix++ = pixel;
1974             ent->fShared = FALSE;
1975         }
1976         *pMask = 0;
1977         return (TRUE);
1978     }
1979     else if (planes > dplanes)
1980     {
1981         return (FALSE);
1982     }
1983
1984     /* General case count pixels * 2 ^ planes cells to be allocated */
1985
1986     /* make room for new pixels */
1987     ent = pentFirst;
1988
1989     /* first try for contiguous planes, since it's fastest */
1990     for (mask = (((Pixel)1) << planes) - 1, base = 1, dplanes -= (planes - 1);
1991          --dplanes >= 0;
1992          mask += mask, base += base)
1993     {
1994         ppix = pixels;
1995         found = 0;
1996         pixel = 0;
1997         entries = pmap->pVisual->ColormapEntries - mask;
1998         while (pixel < entries)
1999         {
2000             save = pixel;
2001             maxp = pixel + mask + base;
2002             /* check if all are free */
2003             while (pixel != maxp && ent[pixel].refcnt == 0)
2004                 pixel += base;
2005             if (pixel == maxp)
2006                 {
2007                     /* this one works */
2008                     *ppix++ = save;
2009                     found++;
2010                     if (found == count)
2011                     {
2012                         /* found enough, allocate them all */
2013                         while (--count >= 0)
2014                         {
2015                             pixel = pixels[count];
2016                             maxp = pixel + mask;
2017                             while (1)
2018                             {
2019                                 ent[pixel].refcnt = AllocPrivate;
2020                                 ent[pixel].fShared = FALSE;
2021                                 if (pixel == maxp)
2022                                     break;
2023                                 pixel += base;
2024                                 *ppix++ = pixel;
2025                             }
2026                         }
2027                         *pMask = mask;
2028                         return (TRUE);
2029                     }
2030                 }
2031             pixel = save + 1;
2032             if (pixel & mask)
2033                 pixel += mask;
2034         }
2035     }
2036
2037     dplanes = pmap->pVisual->nplanes;
2038     if (contig || planes == 1 || dplanes < 3)
2039         return (FALSE);
2040
2041     /* this will be very slow for large maps, need a better algorithm */
2042
2043     /*
2044        we can generate the smallest and largest numbers that fits in dplanes
2045        bits and contain exactly planes bits set as follows. First, we need to
2046        check that it is possible to generate such a mask at all.
2047        (Non-contiguous masks need one more bit than contiguous masks). Then
2048        the smallest such mask consists of the rightmost planes-1 bits set, then
2049        a zero, then a one in position planes + 1. The formula is
2050          (3 << (planes-1)) -1
2051        The largest such masks consists of the leftmost planes-1 bits set, then
2052        a zero, then a one bit in position dplanes-planes-1. If dplanes is
2053        smaller than 32 (the number of bits in a word) then the formula is:
2054          (1<<dplanes) - (1<<(dplanes-planes+1) + (1<<dplanes-planes-1)
2055        If dplanes = 32, then we can't calculate (1<<dplanes) and we have
2056        to use:
2057          ( (1<<(planes-1)) - 1) << (dplanes-planes+1) + (1<<(dplanes-planes-1))
2058
2059           << Thank you, Loretta>>>
2060
2061     */
2062
2063     finalmask =
2064         (((((Pixel)1)<<(planes-1)) - 1) << (dplanes-planes+1)) +
2065           (((Pixel)1)<<(dplanes-planes-1));
2066     for (mask = (((Pixel)3) << (planes -1)) - 1; mask <= finalmask; mask++)
2067     {
2068         /* next 3 magic statements count number of ones (HAKMEM #169) */
2069         pixel = (mask >> 1) & 033333333333;
2070         pixel = mask - pixel - ((pixel >> 1) & 033333333333);
2071         if ((((pixel + (pixel >> 3)) & 030707070707) % 077) != planes)
2072             continue;
2073         ppix = pixels;
2074         found = 0;
2075         entries = pmap->pVisual->ColormapEntries - mask;
2076         base = lowbit (mask);
2077         for (pixel = 0; pixel < entries; pixel++)
2078         {
2079             if (pixel & mask)
2080                 continue;
2081             maxp = 0;
2082             /* check if all are free */
2083             while (ent[pixel + maxp].refcnt == 0)
2084             {
2085                 GetNextBitsOrBreak(maxp, mask, base);
2086             }
2087             if ((maxp < mask) || (ent[pixel + mask].refcnt != 0))
2088                 continue;
2089             /* this one works */
2090             *ppix++ = pixel;
2091             found++;
2092             if (found < count)
2093                 continue;
2094             /* found enough, allocate them all */
2095             while (--count >= 0)
2096             {
2097                 pixel = (pixels)[count];
2098                 maxp = 0;
2099                 while (1)
2100                 {
2101                     ent[pixel + maxp].refcnt = AllocPrivate;
2102                     ent[pixel + maxp].fShared = FALSE;
2103                     GetNextBitsOrBreak(maxp, mask, base);
2104                     *ppix++ = pixel + maxp;
2105                 }
2106             }
2107
2108             *pMask = mask;
2109             return (TRUE);
2110         }
2111     }
2112     return (FALSE);
2113 }
2114
2115 static Bool
2116 AllocShared (pmap, ppix, c, r, g, b, rmask, gmask, bmask, ppixFirst)
2117     ColormapPtr pmap;
2118     Pixel       *ppix;
2119     int         c, r, g, b;
2120     Pixel       rmask, gmask, bmask;
2121     Pixel       *ppixFirst;     /* First of the client's new pixels */
2122 {
2123     Pixel       *pptr, *cptr;
2124     int         npix, z, npixClientNew, npixShared;
2125     Pixel       basemask, base, bits, common;
2126     SHAREDCOLOR *pshared, **ppshared, **psharedList;
2127
2128     npixClientNew = c << (r + g + b);
2129     npixShared = (c << r) + (c << g) + (c << b);
2130     psharedList = (SHAREDCOLOR **)ALLOCATE_LOCAL(npixShared *
2131                                                  sizeof(SHAREDCOLOR *));
2132     if (!psharedList)
2133         return FALSE;
2134     ppshared = psharedList;
2135     for (z = npixShared; --z >= 0; )
2136     {
2137         if (!(ppshared[z] = (SHAREDCOLOR *)xalloc(sizeof(SHAREDCOLOR))))
2138         {
2139             for (z++ ; z < npixShared; z++)
2140                 xfree(ppshared[z]);
2141             return FALSE;
2142         }
2143     }
2144     for(pptr = ppix, npix = c; --npix >= 0; pptr++)
2145     {
2146         basemask = ~(gmask | bmask);
2147         common = *pptr & basemask;
2148         if (rmask)
2149         {
2150             bits = 0;
2151             base = lowbit (rmask);
2152             while(1)
2153             {
2154                 pshared = *ppshared++;
2155                 pshared->refcnt = 1 << (g + b);
2156                 for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2157                 {
2158                     if ((*cptr & basemask) == (common | bits))
2159                     {
2160                         pmap->red[*cptr].fShared = TRUE;
2161                         pmap->red[*cptr].co.shco.red = pshared;
2162                     }
2163                 }
2164                 GetNextBitsOrBreak(bits, rmask, base);
2165             }
2166         }
2167         else
2168         {
2169             pshared = *ppshared++;
2170             pshared->refcnt = 1 << (g + b);
2171             for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2172             {
2173                 if ((*cptr & basemask) == common)
2174                 {
2175                     pmap->red[*cptr].fShared = TRUE;
2176                     pmap->red[*cptr].co.shco.red = pshared;
2177                 }
2178             }
2179         }
2180         basemask = ~(rmask | bmask);
2181         common = *pptr & basemask;
2182         if (gmask)
2183         {
2184             bits = 0;
2185             base = lowbit (gmask);
2186             while(1)
2187             {
2188                 pshared = *ppshared++;
2189                 pshared->refcnt = 1 << (r + b);
2190                 for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2191                 {
2192                     if ((*cptr & basemask) == (common | bits))
2193                     {
2194                         pmap->red[*cptr].co.shco.green = pshared;
2195                     }
2196                 }
2197                 GetNextBitsOrBreak(bits, gmask, base);
2198             }
2199         }
2200         else
2201         {
2202             pshared = *ppshared++;
2203             pshared->refcnt = 1 << (g + b);
2204             for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2205             {
2206                 if ((*cptr & basemask) == common)
2207                 {
2208                     pmap->red[*cptr].co.shco.green = pshared;
2209                 }
2210             }
2211         }
2212         basemask = ~(rmask | gmask);
2213         common = *pptr & basemask;
2214         if (bmask)
2215         {
2216             bits = 0;
2217             base = lowbit (bmask);
2218             while(1)
2219             {
2220                 pshared = *ppshared++;
2221                 pshared->refcnt = 1 << (r + g);
2222                 for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2223                 {
2224                     if ((*cptr & basemask) == (common | bits))
2225                     {
2226                         pmap->red[*cptr].co.shco.blue = pshared;
2227                     }
2228                 }
2229                 GetNextBitsOrBreak(bits, bmask, base);
2230             }
2231         }
2232         else
2233         {
2234             pshared = *ppshared++;
2235             pshared->refcnt = 1 << (g + b);
2236             for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++)
2237             {
2238                 if ((*cptr & basemask) == common)
2239                 {
2240                     pmap->red[*cptr].co.shco.blue = pshared;
2241                 }
2242             }
2243         }
2244     }
2245     DEALLOCATE_LOCAL(psharedList);
2246     return TRUE;
2247 }
2248
2249
2250 /* Free colors and/or cells (probably slow for large numbers) */
2251
2252 int
2253 FreeColors (pmap, client, count, pixels, mask)
2254     ColormapPtr pmap;
2255     int         client, count;
2256     Pixel       *pixels;
2257     Pixel       mask;
2258 {
2259     int         rval, result, class;
2260     Pixel       rmask;
2261
2262     class = pmap->class;
2263     if (pmap->flags & AllAllocated)
2264         return(BadAccess);
2265     if ((class | DynamicClass) == DirectColor)
2266     {
2267         rmask = mask & RGBMASK(pmap->pVisual);
2268         result = FreeCo(pmap, client, REDMAP, count, pixels,
2269                         mask & pmap->pVisual->redMask);
2270         /* If any of the three calls fails, we must report that, if more
2271          * than one fails, it's ok that we report the last one */
2272         rval = FreeCo(pmap, client, GREENMAP, count, pixels,
2273                       mask & pmap->pVisual->greenMask);
2274         if(rval != Success)
2275             result = rval;
2276         rval = FreeCo(pmap, client, BLUEMAP, count, pixels,
2277                       mask & pmap->pVisual->blueMask);
2278         if(rval != Success)
2279             result = rval;
2280     }
2281     else
2282     {
2283         rmask = mask & ((((Pixel)1) << pmap->pVisual->nplanes) - 1);
2284         result = FreeCo(pmap, client, PSEUDOMAP, count, pixels, rmask);
2285     }
2286     if ((mask != rmask) && count)
2287     {
2288         clientErrorValue = *pixels | mask;
2289         result = BadValue;
2290     }
2291     /* XXX should worry about removing any RT_CMAPENTRY resource */
2292     return (result);
2293 }
2294
2295 /* Helper for FreeColors -- frees all combinations of *newpixels and mask bits
2296  * which the client has allocated in channel colormap cells of pmap.
2297  * doesn't change newpixels if it doesn't need to */
2298 static int
2299 FreeCo (pmap, client, color, npixIn, ppixIn, mask)
2300     ColormapPtr pmap;           /* which colormap head */
2301     int         client;
2302     int         color;          /* which sub-map, eg RED, BLUE, PSEUDO */
2303     int         npixIn;         /* number of pixels passed in */
2304     Pixel       *ppixIn;        /* list of base pixels */
2305     Pixel       mask;           /* mask client gave us */
2306 {
2307
2308     Pixel       *ppixClient, pixTest;
2309     int         npixClient, npixNew, npix;
2310     Pixel       bits, base, cmask, rgbbad;
2311     Pixel       *pptr, *cptr;
2312     int         n, zapped;
2313     int         errVal = Success;
2314     int         offset, numents;
2315 #ifdef LBX
2316     Bool        grabbed;
2317     Bool        zeroRefCount;
2318     Bool        anyRefCountReachedZero = 0;
2319 #endif
2320
2321     if (npixIn == 0)
2322         return (errVal);
2323     bits = 0;
2324     zapped = 0;
2325     base = lowbit (mask);
2326
2327     switch(color)
2328     {
2329       case REDMAP:
2330         cmask = pmap->pVisual->redMask;
2331         rgbbad = ~RGBMASK(pmap->pVisual);
2332         offset = pmap->pVisual->offsetRed;
2333         numents = (cmask >> offset) + 1;
2334         ppixClient = pmap->clientPixelsRed[client];
2335         npixClient = pmap->numPixelsRed[client];
2336         break;
2337       case GREENMAP:
2338         cmask = pmap->pVisual->greenMask;
2339         rgbbad = ~RGBMASK(pmap->pVisual);
2340         offset = pmap->pVisual->offsetGreen;
2341         numents = (cmask >> offset) + 1;
2342         ppixClient = pmap->clientPixelsGreen[client];
2343         npixClient = pmap->numPixelsGreen[client];
2344         break;
2345       case BLUEMAP:
2346         cmask = pmap->pVisual->blueMask;
2347         rgbbad = ~RGBMASK(pmap->pVisual);
2348         offset = pmap->pVisual->offsetBlue;
2349         numents = (cmask >> offset) + 1;
2350         ppixClient = pmap->clientPixelsBlue[client];
2351         npixClient = pmap->numPixelsBlue[client];
2352         break;
2353       default:  /* so compiler can see that everything gets initialized */
2354       case PSEUDOMAP:
2355         cmask = ~((Pixel)0);
2356         rgbbad = 0;
2357         offset = 0;
2358         numents = pmap->pVisual->ColormapEntries;
2359         ppixClient = pmap->clientPixelsRed[client];
2360         npixClient = pmap->numPixelsRed[client];
2361         break;
2362     }
2363
2364 #ifdef LBX
2365     grabbed = LbxCheckCmapGrabbed (pmap);
2366
2367     if (grabbed)
2368     {
2369         /*
2370          * If the colormap is grabbed by a proxy, the server must
2371          * notify the proxy of all cells that are freed (the refcount
2372          * has reached zero on these cells).
2373          */
2374
2375         LbxBeginFreeCellsEvent (pmap);
2376         LbxSortPixelList (ppixIn, npixIn);
2377     }
2378 #endif
2379
2380     /* zap all pixels which match */
2381     while (1)
2382     {
2383         /* go through pixel list */
2384         for (pptr = ppixIn, n = npixIn; --n >= 0; pptr++)
2385         {
2386             pixTest = ((*pptr | bits) & cmask) >> offset;
2387             if ((pixTest >= numents) || (*pptr & rgbbad))
2388             {
2389                 clientErrorValue = *pptr | bits;
2390                 errVal = BadValue;
2391                 continue;
2392             }
2393
2394             /* find match in client list */
2395             for (cptr = ppixClient, npix = npixClient;
2396                  --npix >= 0 && *cptr != pixTest;
2397                  cptr++) ;
2398
2399             if (npix >= 0)
2400             {
2401                 if (pmap->class & DynamicClass)
2402                 {
2403                     FreeCell(pmap, pixTest, color);
2404 #ifdef LBX
2405                     /*
2406                      * Only PSEUDO colormaps are grabbed by LBX proxies.
2407                      * Check if the ref count reached zero on this pixel.
2408                      */
2409
2410                     zeroRefCount = pmap->red[pixTest].refcnt == 0;
2411                     if (zeroRefCount)
2412                         anyRefCountReachedZero = 1;
2413
2414                     if (grabbed && zeroRefCount)
2415                         LbxAddFreeCellToEvent (pmap, pixTest);
2416 #endif
2417                 }
2418                 *cptr = ~((Pixel)0);
2419                 zapped++;
2420             }
2421             else
2422                 errVal = BadAccess;
2423         }
2424         /* generate next bits value */
2425         GetNextBitsOrBreak(bits, mask, base);
2426     }
2427
2428 #ifdef LBX
2429     if (grabbed)
2430         LbxEndFreeCellsEvent (pmap);
2431     else if (anyRefCountReachedZero)
2432     {
2433         /*
2434          * We only send LbxFreeCell events to a proxy that has the colormap
2435          * grabbed.  If the colormap is not grabbed, the proxy that last
2436          * had the colormap grabbed will not be able to do a smart grab
2437          * in the future.  A smart grab can only occur if the proxy is kept
2438          * up to date on every alloc/free change in the colormap.
2439          */
2440
2441         LbxDisableSmartGrab (pmap);
2442     }
2443 #endif
2444
2445     /* delete freed pixels from client pixel list */
2446     if (zapped)
2447     {
2448         npixNew = npixClient - zapped;
2449         if (npixNew)
2450         {
2451             /* Since the list can only get smaller, we can do a copy in
2452              * place and then realloc to a smaller size */
2453             pptr = cptr = ppixClient;
2454
2455             /* If we have all the new pixels, we don't have to examine the
2456              * rest of the old ones */
2457             for(npix = 0; npix < npixNew; cptr++)
2458             {
2459                 if (*cptr != ~((Pixel)0))
2460                 {
2461                     *pptr++ = *cptr;
2462                     npix++;
2463                 }
2464             }
2465             pptr = (Pixel *)xrealloc(ppixClient, npixNew * sizeof(Pixel));
2466             if (pptr)
2467                 ppixClient = pptr;
2468             npixClient = npixNew;
2469         }
2470         else
2471         {
2472             npixClient = 0;
2473             xfree(ppixClient);
2474             ppixClient = (Pixel *)NULL;
2475         }
2476         switch(color)
2477         {
2478           case PSEUDOMAP:
2479           case REDMAP:
2480             pmap->clientPixelsRed[client] = ppixClient;
2481             pmap->numPixelsRed[client] = npixClient;
2482             break;
2483           case GREENMAP:
2484             pmap->clientPixelsGreen[client] = ppixClient;
2485             pmap->numPixelsGreen[client] = npixClient;
2486             break;
2487           case BLUEMAP:
2488             pmap->clientPixelsBlue[client] = ppixClient;
2489             pmap->numPixelsBlue[client] = npixClient;
2490             break;
2491         }
2492     }
2493     return (errVal);
2494 }
2495
2496
2497
2498 /* Redefine color values */
2499 int
2500 StoreColors (pmap, count, defs)
2501     ColormapPtr pmap;
2502     int         count;
2503     xColorItem  *defs;
2504 {
2505     register Pixel      pix;
2506     register xColorItem *pdef;
2507     register EntryPtr   pent, pentT, pentLast;
2508     register VisualPtr  pVisual;
2509     SHAREDCOLOR         *pred, *pgreen, *pblue;
2510     int                 n, ChgRed, ChgGreen, ChgBlue, idef;
2511     int                 class, errVal = Success;
2512     int                 ok;
2513
2514
2515     class = pmap->class;
2516     if(!(class & DynamicClass) && !(pmap->flags & BeingCreated))
2517     {
2518         return(BadAccess);
2519     }
2520     pVisual = pmap->pVisual;
2521
2522     idef = 0;
2523     if((class | DynamicClass) == DirectColor)
2524     {
2525         int numred, numgreen, numblue;
2526         Pixel rgbbad;
2527
2528         numred = NUMRED(pVisual);
2529         numgreen = NUMGREEN(pVisual);
2530         numblue = NUMBLUE(pVisual);
2531         rgbbad = ~RGBMASK(pVisual);
2532         for (pdef = defs, n = 0; n < count; pdef++, n++)
2533         {
2534             ok = TRUE;
2535             (*pmap->pScreen->ResolveColor)
2536                 (&pdef->red, &pdef->green, &pdef->blue, pmap->pVisual);
2537
2538             if (pdef->pixel & rgbbad)
2539             {
2540                 errVal = BadValue;
2541                 clientErrorValue = pdef->pixel;
2542                 continue;
2543             }
2544             pix = (pdef->pixel & pVisual->redMask) >> pVisual->offsetRed;
2545             if (pix >= numred)
2546             {
2547                 errVal = BadValue;
2548                 ok = FALSE;
2549             }
2550             else if (pmap->red[pix].refcnt != AllocPrivate)
2551             {
2552                 errVal = BadAccess;
2553                 ok = FALSE;
2554             }
2555             else if (pdef->flags & DoRed)
2556             {
2557                 pmap->red[pix].co.local.red = pdef->red;
2558             }
2559             else
2560             {
2561                 pdef->red = pmap->red[pix].co.local.red;
2562             }
2563
2564             pix = (pdef->pixel & pVisual->greenMask) >> pVisual->offsetGreen;
2565             if (pix >= numgreen)
2566             {
2567                 errVal = BadValue;
2568                 ok = FALSE;
2569             }
2570             else if (pmap->green[pix].refcnt != AllocPrivate)
2571             {
2572                 errVal = BadAccess;
2573                 ok = FALSE;
2574             }
2575             else if (pdef->flags & DoGreen)
2576             {
2577                 pmap->green[pix].co.local.green = pdef->green;
2578             }
2579             else
2580             {
2581                 pdef->green = pmap->green[pix].co.local.green;
2582             }
2583
2584             pix = (pdef->pixel & pVisual->blueMask) >> pVisual->offsetBlue;
2585             if (pix >= numblue)
2586             {
2587                 errVal = BadValue;
2588                 ok = FALSE;
2589             }
2590             else if (pmap->blue[pix].refcnt != AllocPrivate)
2591             {
2592                 errVal = BadAccess;
2593                 ok = FALSE;
2594             }
2595             else if (pdef->flags & DoBlue)
2596             {
2597                 pmap->blue[pix].co.local.blue = pdef->blue;
2598             }
2599             else
2600             {
2601                 pdef->blue = pmap->blue[pix].co.local.blue;
2602             }
2603             /* If this is an o.k. entry, then it gets added to the list
2604              * to be sent to the hardware.  If not, skip it.  Once we've
2605              * skipped one, we have to copy all the others.
2606              */
2607             if(ok)
2608             {
2609                 if(idef != n)
2610                     defs[idef] = defs[n];
2611                 idef++;
2612             } else
2613                 clientErrorValue = pdef->pixel;
2614         }
2615     }
2616     else
2617     {
2618         for (pdef = defs, n = 0; n < count; pdef++, n++)
2619         {
2620
2621             ok = TRUE;
2622             if (pdef->pixel >= pVisual->ColormapEntries)
2623             {
2624                 clientErrorValue = pdef->pixel;
2625                 errVal = BadValue;
2626                 ok = FALSE;
2627             }
2628             else if (pmap->red[pdef->pixel].refcnt != AllocPrivate)
2629             {
2630                 errVal = BadAccess;
2631                 ok = FALSE;
2632             }
2633
2634             /* If this is an o.k. entry, then it gets added to the list
2635              * to be sent to the hardware.  If not, skip it.  Once we've
2636              * skipped one, we have to copy all the others.
2637              */
2638             if(ok)
2639             {
2640                 if(idef != n)
2641                     defs[idef] = defs[n];
2642                 idef++;
2643             }
2644             else
2645                 continue;
2646
2647             (*pmap->pScreen->ResolveColor)
2648                 (&pdef->red, &pdef->green, &pdef->blue, pmap->pVisual);
2649
2650             pent = &pmap->red[pdef->pixel];
2651
2652             if(pdef->flags & DoRed)
2653             {
2654                 if(pent->fShared)
2655                 {
2656                     pent->co.shco.red->color = pdef->red;
2657                     if (pent->co.shco.red->refcnt > 1)
2658                         ok = FALSE;
2659                 }
2660                 else
2661                     pent->co.local.red = pdef->red;
2662             }
2663             else
2664             {
2665                 if(pent->fShared)
2666                     pdef->red = pent->co.shco.red->color;
2667                 else
2668                     pdef->red = pent->co.local.red;
2669             }
2670             if(pdef->flags & DoGreen)
2671             {
2672                 if(pent->fShared)
2673                 {
2674                     pent->co.shco.green->color = pdef->green;
2675                     if (pent->co.shco.green->refcnt > 1)
2676                         ok = FALSE;
2677                 }
2678                 else
2679                     pent->co.local.green = pdef->green;
2680             }
2681             else
2682             {
2683                 if(pent->fShared)
2684                     pdef->green = pent->co.shco.green->color;
2685                 else
2686                     pdef->green = pent->co.local.green;
2687             }
2688             if(pdef->flags & DoBlue)
2689             {
2690                 if(pent->fShared)
2691                 {
2692                     pent->co.shco.blue->color = pdef->blue;
2693                     if (pent->co.shco.blue->refcnt > 1)
2694                         ok = FALSE;
2695                 }
2696                 else
2697                     pent->co.local.blue = pdef->blue;
2698             }
2699             else
2700             {
2701                 if(pent->fShared)
2702                     pdef->blue = pent->co.shco.blue->color;
2703                 else
2704                     pdef->blue = pent->co.local.blue;
2705             }
2706
2707             if(!ok)
2708             {
2709                 /* have to run through the colormap and change anybody who
2710                  * shares this value */
2711                 pred = pent->co.shco.red;
2712                 pgreen = pent->co.shco.green;
2713                 pblue = pent->co.shco.blue;
2714                 ChgRed = pdef->flags & DoRed;
2715                 ChgGreen = pdef->flags & DoGreen;
2716                 ChgBlue = pdef->flags & DoBlue;
2717                 pentLast = pmap->red + pVisual->ColormapEntries;
2718
2719                 for(pentT = pmap->red; pentT < pentLast; pentT++)
2720                 {
2721                     if(pentT->fShared && (pentT != pent))
2722                     {
2723                         xColorItem      defChg;
2724
2725                         /* There are, alas, devices in this world too dumb
2726                          * to read their own hardware colormaps.  Sick, but
2727                          * true.  So we're going to be really nice and load
2728                          * the xColorItem with the proper value for all the
2729                          * fields.  We will only set the flags for those
2730                          * fields that actually change.  Smart devices can
2731                          * arrange to change only those fields.  Dumb devices
2732                          * can rest assured that we have provided for them,
2733                          * and can change all three fields */
2734
2735                         defChg.flags = 0;
2736                         if(ChgRed && pentT->co.shco.red == pred)
2737                         {
2738                             defChg.flags |= DoRed;
2739                         }
2740                         if(ChgGreen && pentT->co.shco.green == pgreen)
2741                         {
2742                             defChg.flags |= DoGreen;
2743                         }
2744                         if(ChgBlue && pentT->co.shco.blue == pblue)
2745                         {
2746                             defChg.flags |= DoBlue;
2747                         }
2748                         if(defChg.flags != 0)
2749                         {
2750                             defChg.pixel = pentT - pmap->red;
2751                             defChg.red = pentT->co.shco.red->color;
2752                             defChg.green = pentT->co.shco.green->color;
2753                             defChg.blue = pentT->co.shco.blue->color;
2754                             (*pmap->pScreen->StoreColors) (pmap, 1, &defChg);
2755                         }
2756                     }
2757                 }
2758
2759             }
2760         }
2761     }
2762     /* Note that we use idef, the count of acceptable entries, and not
2763      * count, the count of proposed entries */
2764     if (idef != 0)
2765         ( *pmap->pScreen->StoreColors) (pmap, idef, defs);
2766     return (errVal);
2767 }
2768
2769 int
2770 IsMapInstalled(map, pWin)
2771     Colormap    map;
2772     WindowPtr   pWin;
2773 {
2774     Colormap    *pmaps;
2775     int         imap, nummaps, found;
2776
2777     pmaps = (Colormap *) ALLOCATE_LOCAL(
2778              pWin->drawable.pScreen->maxInstalledCmaps * sizeof(Colormap));
2779     if(!pmaps)
2780         return(FALSE);
2781     nummaps = (*pWin->drawable.pScreen->ListInstalledColormaps)
2782         (pWin->drawable.pScreen, pmaps);
2783     found = FALSE;
2784     for(imap = 0; imap < nummaps; imap++)
2785     {
2786         if(pmaps[imap] == map)
2787         {
2788             found = TRUE;
2789             break;
2790         }
2791     }
2792     DEALLOCATE_LOCAL(pmaps);
2793     return (found);
2794 }