cde/programs/dtappbuilder/src/libABobj/obj_list.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23
  24 /*
  25  *      $XConsortium: obj_list.c /main/4 1996/10/02 16:09:05 drk $
  26  *
  27  * @(#)obj_list.c       1.8 03 Feb 1995 cde_app_builder/src/libAButil
  28  *
  29  *      RESTRICTED CONFIDENTIAL INFORMATION:
  30  *
  31  *      The information in this document is subject to special
  32  *      restrictions in a confidential disclosure agreement between
  33  *      HP, IBM, Sun, USL, SCO and Univel.  Do not dobjibute this
  34  *      document outside HP, IBM, Sun, USL, SCO, or Univel without
  35  *      Sun's specific written approval.  This document and all copies
  36  *      and derivative works thereof must be returned or destroyed at
  37  *      Sun's request.
  38  *
  39  *      Copyright 1993 Sun Microsystems, Inc.  All rights reserved.
  40  *
  41  */
  42
  43
  44 /*
  45  * File: objlist.c
  46  */
  47
  48 #ifdef _POSIX_SOURCE
  49 #define _POSIX_SOURCE 1
  50 #endif
  51
  52 #include <unistd.h>
  53 #include <stdlib.h>
  54 #include <string.h>
  55 #include <ab_private/obj_list.h>
  56
  57 /*****************************************************************
  58  **                                                             **
  59  **             ABObjList                                       **
  60  **                                                             **
  61  *****************************************************************/
  62
  63 static int objlistP_grow_array(ABObjList list, int sizeDiff);
  64 static int objlistP_shrink_array(ABObjList list, int sizeDiff);
  65 static int objlistP_build_user_data_array(
  66                         ABObjList list,
  67                         int index,
  68                         void *data
  69             );
  70
  71
  72 /*
  73 #define objlistP_add_user_data(_list,_index,_data) \
  74     ((((_list)->user_datas == NULL) && ((_data) != NULL))? \
  75         objlistP_build_user_data_array(_list, _index, _data) \
  76     : \
  77         ((long)((_list)->user_datas[(_index)] = (_data))) \
  78     )
  79 */
  80
  81 #define objlistP_add_user_data(_list,_index,_data) \
  82     (((_list)->user_datas == NULL)? \
  83         (((_data) == NULL)? \
  84             0 \
  85         : \
  86             objlistP_build_user_data_array(_list, _index, _data)) \
  87     : \
  88         ((long)((_list)->user_datas[(_index)] = (_data))) \
  89     )
  90
  91 #define objlistP_get_user_data(_list,_index) \
  92             (((_list)->user_datas) == NULL? \
  93                 NULL:((_list)->user_datas[(_index)]))
  94
  95 ABObjList
  96 objlist_create(void)
  97 {
  98     ABObjList          list = (ABObjList) util_malloc(sizeof(ABObjListRec));
  99     if (list == NULL)
 100     {
 101         return NULL;
 102     }
 103     objlist_construct(list);
 104     return list;
 105 }
 106
 107
 108 int
 109 objlist_construct(ABObjList list)
 110 {
 111     list->num_objs = 0;
 112     list->objs_size = 0;
 113     list->objs = NULL;
 114     list->user_datas = NULL;
 115     list->unique = TRUE;
 116     list->sort_order = OBJLIST_SORT_CLIENT_DEF;
 117     list->indexes_dirty = TRUE;
 118     return 0;
 119 }
 120
 121
 122 /*
 123  * Frees the obj list and all it's associated memory.
 124  */
 125 int
 126 objlist_destroy_impl(ABObjList *listInOut)
 127 {
 128     ABObjList   list = (*listInOut);
 129     if (list != NULL)
 130     {
 131         objlist_destruct(list);
 132         util_free(list);
 133     }
 134     (*listInOut) = list;
 135     return 0;
 136 }
 137
 138
 139 int
 140 objlist_destruct(ABObjList list)
 141 {
 142     return objlist_make_empty(list);
 143 }
 144
 145
 146 OBJLIST_SORT_ORDER
 147 objlist_get_sort_order(ABObjList list)
 148 {
 149     return list->sort_order;
 150 }
 151
 152
 153 int
 154 objlist_set_sort_order(ABObjList list, OBJLIST_SORT_ORDER new_order)
 155 {
 156     int         return_value = 0;
 157
 158     if (list->sort_order != new_order)
 159     {
 160         list->indexes_dirty = TRUE;
 161     }
 162
 163     return 0;
 164 }
 165
 166
 167 int
 168 objlist_make_empty(ABObjList list)
 169 {
 170     int         return_value = 0;
 171
 172     if (list->objs != NULL)
 173     {
 174         return_value = objlistP_shrink_array(list, list->objs_size);
 175     }
 176
 177     return return_value;
 178 }
 179
 180
 181 int
 182 objlist_is_empty(ABObjList list)
 183 {
 184     return (list->num_objs < 1);
 185 }
 186
 187
 188 int
 189 objlist_set_is_unique(ABObjList list, BOOL unique)
 190 {
 191     list->unique = unique;
 192     return 0;
 193 }
 194
 195
 196 BOOL
 197 objlist_get_is_unique(ABObjList list)
 198 {
 199     return list->unique;
 200 }
 201
 202
 203 /*
 204  * Searches the list for a match.
 205  *
 206  * returns:     true, if the obj exists. false, if it isn't in the lisT
 207  */
 208 BOOL
 209 objlist_obj_exists(ABObjList list, ABObj obj)
 210 {
 211     return (objlist_get_obj_index(list, obj) >= 0);
 212 }
 213
 214
 215 void *
 216 objlist_get_obj_data(ABObjList list, ABObj obj)
 217 {
 218     int         index = objlist_get_obj_index(list, obj);
 219     return objlistP_get_user_data(list, index);
 220 }
 221
 222
 223 /*
 224  * Returns the index of the given obj, or -1 if it doesn't exist
 225  */
 226 int
 227 objlist_get_obj_index(ABObjList list, ABObj obj)
 228 {
 229     int                 index = -1;
 230     int                 i = 0;
 231     int                 num_objs = list->num_objs;
 232
 233     for (i = 0; i < num_objs; ++i)
 234     {
 235         if (list->objs[i] == obj)
 236         {
 237             index = i;
 238             break;
 239         }
 240     }
 241
 242     return index;
 243 }
 244
 245
 246 /*
 247  * Add an obj
 248  *
 249  * returns:     0 if item added successfully
 250  *              ERR_DUPLICATE_KEY if item is already in list
 251  */
 252 int
 253 objlist_add_obj(ABObjList list, ABObj obj, void *clientData)
 254 {
 255     int                 return_value = 0;
 256     int                 rc = 0;
 257
 258     /*
 259      * look for it
 260      */
 261     if (list->unique)
 262     {
 263         long index = objlist_get_obj_index(list, obj);
 264         if (index >= 0)
 265         {
 266             objlistP_add_user_data(list, index, clientData);
 267             return 0;
 268         }
 269     }
 270
 271     /*
 272      * Allocate more space
 273      */
 274     if (list->num_objs >= list->objs_size)
 275     {
 276         /* grow the array by 50% (the "opposite" of a binary search) */
 277         int     new_size = (list->objs_size * 3)/2;
 278         int     size_inc = new_size - list->objs_size;
 279         size_inc = util_max(5,size_inc);
 280         rc = objlistP_grow_array(list, size_inc);
 281         if (rc < 0)
 282         {
 283             return_value = rc;
 284             goto epilogue;
 285         }
 286     }
 287
 288
 289     /*
 290      * save the obj (and data)
 291      */
 292     list->objs[list->num_objs] = obj;
 293     objlistP_add_user_data(list, list->num_objs, clientData);
 294     ++(list->num_objs);
 295
 296 epilogue:
 297     return return_value;
 298 }
 299
 300
 301 int
 302 objlist_remove_obj(ABObjList list, ABObj obj)
 303 {
 304     int         index = objlist_get_obj_index(list, obj);
 305     if (index < 0)
 306     {
 307         return 0;
 308     }
 309     return objlist_remove_index(list, index);
 310 }
 311
 312
 313 int
 314 objlist_remove_index(ABObjList list, int doomedIndex)
 315 {
 316 #define num_objs (list->num_objs)
 317     ABObj       *objs = list->objs;
 318     void        **user_datas = list->user_datas;
 319     int         index = 0;
 320     int         numToMove = 0;
 321
 322     if ((doomedIndex < 0) || (doomedIndex >= num_objs))
 323     {
 324         return -1;
 325     }
 326
 327     numToMove = (num_objs - doomedIndex - 1);
 328
 329     /*
 330      * Remove this obj and collapse the list
 331      */
 332     objs[doomedIndex] = NULL;
 333     if (numToMove > 0)
 334     {
 335         memmove((void *)(&(objs[doomedIndex])),
 336                     (void *)&(objs[doomedIndex+1]),
 337                     sizeof(ABObj) * numToMove);
 338         objs[num_objs-1] = NULL;
 339     }
 340
 341     /*
 342      * Destroy user data and collapse list
 343      */
 344     if (user_datas != NULL)
 345     {
 346         user_datas[doomedIndex] = NULL;
 347         if (numToMove > 0)
 348         {
 349             memmove((void *)(&(user_datas[doomedIndex])),
 350                     (void *)&(user_datas[doomedIndex+1]),
 351                     sizeof(void*) * numToMove);
 352             user_datas[num_objs-1] = NULL;
 353         }
 354     }
 355
 356     /*
 357      * Actually shorten list
 358      */
 359     --num_objs;
 360
 361     return 0;
 362 #undef num_objs
 363 }
 364
 365
 366 int
 367 objlist_get_num_objs(ABObjList list)
 368 {
 369     if (list == NULL)
 370     {
 371         return 0;
 372     }
 373     return list->num_objs;
 374 }
 375
 376
 377 ABObj
 378 objlist_get_obj(ABObjList list, int whichObj, void **clientDataOut)
 379 {
 380     if ((list == NULL) || (whichObj >= list->num_objs) ||
 381         (whichObj < 0))
 382     {
 383         return NULL;
 384     }
 385     if (clientDataOut != NULL)
 386     {
 387         *clientDataOut = objlistP_get_user_data(list, whichObj);
 388     }
 389     return list->objs[whichObj];
 390 }
 391
 392
 393 /*
 394  * Only "soft" limit is supported, now
 395  */
 396 BOOL
 397 objlist_max_size_is_soft(ABObjList list)
 398 {
 399     list = list;                /* avoid cc warning */
 400     return TRUE;
 401 }
 402
 403
 404 int
 405 objlist_set_max_size_soft(ABObjList list, int maxSize)
 406 {
 407     int         return_value = 0;
 408     int         sizeDiff = (maxSize - list->objs_size);
 409
 410     if (sizeDiff < 0)
 411     {
 412         return_value = objlistP_shrink_array(list, -1 * sizeDiff);
 413     }
 414     else if (sizeDiff > 0)
 415     {
 416         return_value = objlistP_grow_array(list, sizeDiff);
 417     }
 418
 419     return return_value;
 420 }
 421
 422
 423 int
 424 objlist_get_max_size(ABObjList list)
 425 {
 426     return list->objs_size;
 427 }
 428
 429
 430 /*
 431  * Frees any extra memory that may not be needed (multiple obj ptrs are
 432  * allocated at once, to reduce the number of realloc calls).
 433  */
 434 int
 435 objlist_shrink_mem_to_fit(ABObjList list)
 436 {
 437     int         return_value = 0;
 438     int         diff = list->objs_size - list->num_objs;
 439
 440     if (diff > 0)
 441     {
 442         return_value = objlistP_shrink_array(list, diff);
 443     }
 444
 445     return return_value;
 446 }
 447
 448
 449 int
 450 objlist_iterate(
 451     ABObjList       list,
 452     ABObjListIterFn fn
 453 )
 454 {
 455     int         i;
 456
 457     if (!list)
 458         return -1;
 459
 460     for (i=0; i<list->num_objs; i++)
 461     {
 462         (*fn)(list->objs[i]);
 463     }
 464     return 0;
 465 }
 466
 467
 468 ABObjList
 469 objlist_dup(ABObjList list)
 470 {
 471     int         i;
 472     ABObjList   new_list = NULL;
 473
 474     new_list = objlist_create();
 475     new_list->unique = list->unique;
 476     new_list->sort_order = list->sort_order;
 477     new_list->indexes_dirty = list->indexes_dirty;
 478     for (i=0; i<list->num_objs; i++)
 479     {
 480         objlist_add_obj(
 481             new_list, list->objs[i], objlistP_get_user_data(list,i));
 482     }
 483     return(new_list);
 484 }
 485
 486 /*************************************************************************
 487 **                                                                      **
 488 **              PRIVATE FUNCTIONS                                       **
 489 **                                                                      **
 490 **************************************************************************/
 491
 492
 493 objlistP_shrink_array(ABObjList list, int sizeDiff)
 494 {
 495     int         return_value = 0;
 496     int         new_objs_size = util_max(0, list->objs_size - sizeDiff);
 497     ABObj       *new_objs = NULL;
 498     void        **new_user_datas = NULL;
 499     int         i = 0;
 500
 501     for (i= new_objs_size; i < list->objs_size; ++i)
 502     {
 503         list->objs[i] = NULL;
 504         if (list->user_datas != NULL)
 505         {
 506             list->user_datas[i] = NULL;
 507         }
 508     }
 509
 510     if (new_objs_size > 0)
 511     {
 512         new_objs = (ABObj*) realloc(
 513                           list->objs, new_objs_size * sizeof(ABObj));
 514         if (new_user_datas != NULL)
 515         {
 516             new_user_datas = (void **) realloc(
 517                   list->user_datas, new_objs_size * sizeof(void*));
 518         }
 519     }
 520     else
 521     {
 522         util_free(list->objs); list->objs = NULL;
 523         util_free(list->user_datas); list->user_datas= NULL;
 524     }
 525
 526     if (   (new_objs_size > 0)
 527         && ((new_objs == NULL) || (new_user_datas == NULL)) )
 528     {
 529         return_value = ERR_NO_MEMORY;
 530         goto epilogue;
 531     }
 532     else
 533     {
 534         list->objs = new_objs;
 535         list->user_datas = new_user_datas;
 536         list->objs_size = new_objs_size;
 537         if (list->num_objs > list->objs_size)
 538         {
 539             list->num_objs = util_max(0, list->objs_size);
 540         }
 541     }
 542
 543 epilogue:
 544     return return_value;
 545 }
 546
 547
 548 static int
 549 objlistP_grow_array(ABObjList list, int sizeDiff)
 550 {
 551     int         return_value = 0;
 552     int         old_objs_size = list->objs_size;
 553     int         new_objs_size = list->objs_size + sizeDiff;
 554     ABObj       *new_objs = NULL;
 555     void        **new_user_datas = NULL;
 556     int         i = 0;
 557     BOOL        user_datas_valid = (list->user_datas != NULL);
 558
 559     new_objs = (ABObj*)realloc(
 560                         list->objs, new_objs_size * sizeof(ABObj));
 561     if (user_datas_valid)
 562     {
 563         new_user_datas = (void **)realloc(
 564                         list->user_datas, new_objs_size * sizeof(void *));
 565     }
 566     if (   (new_objs == NULL)
 567         || (user_datas_valid && (new_user_datas == NULL)) )
 568     {
 569         free(new_objs);
 570         free(new_user_datas);
 571         return_value = ERR_NO_MEMORY;
 572         goto epilogue;
 573     }
 574     else
 575     {
 576         list->objs = new_objs;
 577         list->user_datas = new_user_datas;
 578         list->objs_size = new_objs_size;
 579     }
 580
 581     /*
 582      * Init the new entries to NULL;
 583      */
 584     for (i = old_objs_size; i < new_objs_size; ++i)
 585     {
 586         list->objs[i] = NULL;
 587         if (user_datas_valid)
 588         {
 589             list->user_datas[i] = NULL;
 590         }
 591     }
 592
 593 epilogue:
 594     return return_value;
 595 }
 596
 597
 598 static int
 599 objlistP_build_user_data_array(ABObjList list, int index, void *data)
 600 {
 601     if (list->user_datas != NULL)
 602     {
 603         return -1;
 604     }
 605     list->user_datas = (void **)calloc(sizeof(void*), list->objs_size);
 606     if (list->user_datas == NULL)
 607     {
 608         return -1;
 609     }
 610     list->user_datas[index] = data;
 611     return 0;
 612 }
 613
 614
 615 #ifdef DEBUG
 616 /*************************************************************************
 617  **                                                                     **
 618  **                                                                     **
 619  **             DEBUGGING ROUTINES                                      **
 620  **                                                                     **
 621  **                                                                     **
 622  *************************************************************************/
 623
 624 #include <stdio.h>      /* needed only for debug output */
 625
 626 /*
 627  * debugging output
 628  */
 629 int
 630 objlist_dump(ABObjList list)
 631 {
 632     int i = 0;
 633     ABObj       obj = NULL;
 634     BOOL        entryUsed = FALSE;
 635     BOOL        entryValid = FALSE;
 636     char        objName[1024];
 637     *objName = 0;
 638
 639     if (list == NULL)
 640     {
 641         util_printf(0, "NULL obj list\n");
 642         return 0;
 643     }
 644     if (list->objs_size == 0)
 645     {
 646         util_dprintf(0, "empty obj list\n");
 647         return 0;
 648     }
 649
 650     for (i= 0; i < list->objs_size; ++i)
 651     {
 652         entryUsed = (i < list->num_objs);
 653         entryValid = FALSE;
 654
 655         if (entryUsed)
 656         {
 657             obj = list->objs[i];
 658             entryValid = (obj_verify(obj) >= 0);
 659
 660             if (entryValid)
 661             {
 662                 objName[0] = '\'';
 663                 obj_get_safe_name(obj, objName+1, 1023);
 664                 strcat(objName, "'");
 665             }
 666             else
 667             {
 668                 strcpy(objName, "** Invalid ABObj **");
 669             }
 670         }
 671         else
 672         {
 673             strcpy(objName, "** Unused Entry **");
 674         }
 675
 676         util_dprintf(0, "%d[%s]: %s",
 677                 i,
 678                 (i >= list->num_objs? " ":"X"),
 679                 objName);
 680
 681         if (list->user_datas != NULL)
 682         {
 683             util_dprintf(0, " 0x%08lx", objlistP_get_user_data(list,i));
 684         }
 685         util_dprintf(0, "\n");
 686     }
 687     util_dprintf(0, "\n");
 688     return 0;
 689 }
 690
 691 #endif /* DEBUG */
 692