cde/programs/dtappbuilder/src/libAButil/strlist.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: strlist.c /main/5 1996/10/02 16:53:22 drk $
  26  *
  27  * @(#)strlist.c        1.8 14 Oct 1994 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 distribute 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: strlist.c
  46  */
  47
  48 #include <string.h>
  49 #include <ab_private/AB.h>
  50 #include <ab_private/istr.h>
  51 #include <ab_private/strlist.h>
  52
  53 /*****************************************************************
  54  **                                                             **
  55  **             STRING LIST                                     **
  56  **                                                             **
  57  *****************************************************************/
  58
  59 static int strlistP_grow_array(StringList list, int sizeDiff);
  60 static int strlistP_shrink_array(StringList list, int sizeDiff);
  61 static int strlistP_build_user_data_array(
  62                         StringList list,
  63                         int index,
  64                         void *data
  65             );
  66
  67
  68 #define strlistP_add_user_data(_list,_index,_data) \
  69     ((((_list)->user_datas == NULL) && ((_data) != NULL))? \
  70         strlistP_build_user_data_array(_list, _index, _data) \
  71     : \
  72         ((int)((_list)->user_datas[(_index)] = (_data))) \
  73     )
  74
  75
  76 StringList
  77 strlist_create(void)
  78 {
  79     StringList          list = (StringList) util_malloc(sizeof(StringListRec));
  80     if (list == NULL)
  81     {
  82         return NULL;
  83     }
  84     strlist_construct(list);
  85     return list;
  86 }
  87
  88
  89 int
  90 strlist_construct(StringList list)
  91 {
  92     list->num_strings = 0;
  93     list->strings_size = 0;
  94     list->strings = NULL;
  95     list->user_datas = NULL;
  96     list->unique = TRUE;
  97     list->sort_order = STRLIST_SORT_CLIENT_DEF;
  98     list->indexes_dirty = TRUE;
  99     return 0;
 100 }
 101
 102
 103 /*
 104  * Frees the string list and all it's associated memory.
 105  */
 106 int
 107 strlist_destroy(StringList list)
 108 {
 109     strlist_destruct(list);
 110     free(list);
 111     return 0;
 112 }
 113
 114
 115 int
 116 strlist_destruct(StringList list)
 117 {
 118     return strlist_make_empty(list);
 119 }
 120
 121
 122 STRLIST_SORT_ORDER
 123 strlist_get_sort_order(StringList list)
 124 {
 125     return list->sort_order;
 126 }
 127
 128
 129 int
 130 strlist_set_sort_order(StringList list, STRLIST_SORT_ORDER new_order)
 131 {
 132     int         return_value = 0;
 133
 134     if (list->sort_order != new_order)
 135     {
 136         list->indexes_dirty = TRUE;
 137     }
 138
 139     return 0;
 140 }
 141
 142
 143 int
 144 strlist_make_empty(StringList list)
 145 {
 146     int         return_value = 0;
 147
 148     if (list->strings != NULL)
 149     {
 150         return_value = strlistP_shrink_array(list, list->strings_size);
 151     }
 152
 153     return return_value;
 154 }
 155
 156
 157 int
 158 strlist_is_empty(StringList list)
 159 {
 160     return (list->num_strings < 1);
 161 }
 162
 163
 164 int
 165 strlist_set_is_unique(StringList list, BOOL unique)
 166 {
 167     list->unique = unique;
 168     return 0;
 169 }
 170
 171
 172 BOOL
 173 strlist_get_is_unique(StringList list)
 174 {
 175     return list->unique;
 176 }
 177
 178
 179 /*
 180  * Searches the string list for a match.
 181  *
 182  * returns:     true, if the string exists. false, if the string doesn't
 183  * exist.
 184  */
 185 BOOL
 186 strlist_istr_exists(StringList list, ISTRING istring)
 187 {
 188     return (strlist_get_istr_index(list, istring) >= 0);
 189 }
 190
 191
 192 int
 193 strlist_set_istr_data(StringList list, ISTRING istring, void *data)
 194 {
 195     int         index = strlist_get_istr_index(list, istring);
 196     if (index < 0)
 197     {
 198         return index;
 199     }
 200
 201     strlistP_add_user_data(list,index,data);
 202     return 0;
 203 }
 204
 205
 206
 207 void *
 208 strlist_get_istr_data(StringList list, ISTRING istring)
 209 {
 210     int         index = strlist_get_istr_index(list, istring);
 211     return (index < 0)? NULL:list->user_datas[index];
 212 }
 213
 214
 215 /*
 216  * Returns the index of the given string, or -1 if it doesn't exist
 217  */
 218 int
 219 strlist_get_istr_index(StringList list, ISTRING string)
 220 {
 221     int                 index = -1;
 222     int                 i = 0;
 223     int                 num_strings = list->num_strings;
 224
 225     for (i = 0; i < num_strings; ++i)
 226     {
 227         if (istr_equal(list->strings[i], string))
 228         {
 229             index = i;
 230             break;
 231         }
 232     }
 233
 234 epilogue:
 235     return index;
 236 }
 237
 238
 239 /*
 240  * Add a string to a string list.
 241  *
 242  * Duplicates the string
 243  *
 244  * returns:     0 if item added successfully ERR_DUPLICATE_KEY if item is
 245  * already in list
 246  */
 247 int
 248 strlist_add_istr(StringList list, ISTRING istring, void *clientData)
 249 {
 250     int                 return_value = 0;
 251     int                 rc = 0;
 252
 253     /*
 254      * look for it
 255      */
 256     if (list->unique)
 257     {
 258         int index = strlist_get_istr_index(list, istring);
 259         if (index >= 0)
 260         {
 261             strlistP_add_user_data(list, index, clientData);
 262             return 0;
 263         }
 264     }
 265
 266     /*
 267      * Allocate more space
 268      */
 269     if (list->num_strings >= list->strings_size)
 270     {
 271         /* grow the array by 50% (the "opposite" of a binary search) */
 272         int     new_size = (list->strings_size * 3)/2;
 273         int     size_inc = new_size - list->strings_size;
 274         size_inc = util_max(5,size_inc);
 275         rc = strlistP_grow_array(list, size_inc);
 276         if (rc < 0)
 277         {
 278             return_value = rc;
 279             goto epilogue;
 280         }
 281     }
 282
 283
 284     /*
 285      * save the string (and data)
 286      */
 287     list->strings[list->num_strings] = istr_dup(istring);
 288     strlistP_add_user_data(list, list->num_strings, clientData);
 289     ++(list->num_strings);
 290
 291 epilogue:
 292     return return_value;
 293 }
 294
 295
 296 int
 297 strlist_remove_istr(StringList list, ISTRING istring)
 298 {
 299     int         index = strlist_get_istr_index(list, istring);
 300     if (index < 0)
 301     {
 302         return 0;
 303     }
 304     return strlist_remove_index(list, index);
 305 }
 306
 307
 308 int
 309 strlist_remove_index(StringList list, int doomedIndex)
 310 {
 311 #define num_strings (list->num_strings)
 312     ISTRING     *strings = list->strings;
 313     void        **user_datas = list->user_datas;
 314     int         index = 0;
 315     int         numToMove = 0;
 316
 317     if ((doomedIndex < 0) || (doomedIndex >= num_strings))
 318     {
 319         return -1;
 320     }
 321
 322     numToMove = (num_strings - doomedIndex - 1);
 323
 324     /*
 325      * Destroy this string and collapse the list
 326      */
 327     istr_destroy(strings[doomedIndex]);
 328     if (numToMove > 0)
 329     {
 330         memmove((void *)(&(strings[doomedIndex])),
 331                     (void *)&(strings[doomedIndex+1]),
 332                     sizeof(ISTRING) * numToMove);
 333         strings[num_strings-1] = NULL;
 334     }
 335
 336     /*
 337      * Destroy user data and collapse list
 338      */
 339     if (user_datas != NULL)
 340     {
 341         user_datas[doomedIndex] = NULL;
 342         if (numToMove > 0)
 343         {
 344             memmove((void *)(&(user_datas[doomedIndex])),
 345                     (void *)&(user_datas[doomedIndex+1]),
 346                     sizeof(void*) * numToMove);
 347             user_datas[num_strings-1] = NULL;
 348         }
 349     }
 350
 351     /*
 352      * Actually shorten list
 353      */
 354     --num_strings;
 355
 356     return 0;
 357 #undef num_strings
 358 }
 359
 360
 361 int
 362 strlist_get_num_strs(StringList list)
 363 {
 364     if (list == NULL)
 365     {
 366         return 0;
 367     }
 368     return list->num_strings;
 369 }
 370
 371
 372 ISTRING
 373 strlist_get_istr(StringList list, int whichString, void **clientDataOut)
 374 {
 375     if ((list == NULL) || (whichString >= list->num_strings) ||
 376         (whichString < 0))
 377     {
 378         return NULL;
 379     }
 380     if (clientDataOut != NULL)
 381     {
 382         *clientDataOut =
 383             (list->user_datas == NULL? NULL:list->user_datas[whichString]);
 384     }
 385     return list->strings[whichString];
 386 }
 387
 388
 389 /*
 390  * Only "soft" limit is supported, now
 391  */
 392 BOOL
 393 strlist_max_size_is_soft(StringList list)
 394 {
 395     return TRUE;
 396 }
 397
 398
 399 int
 400 strlist_set_max_size_soft(StringList list, int maxSize)
 401 {
 402     int         return_value = 0;
 403     int         sizeDiff = (maxSize - list->strings_size);
 404
 405     if (sizeDiff < 0)
 406     {
 407         return_value = strlistP_shrink_array(list, -1 * sizeDiff);
 408     }
 409     else if (sizeDiff > 0)
 410     {
 411         return_value = strlistP_grow_array(list, sizeDiff);
 412     }
 413
 414     return return_value;
 415 }
 416
 417
 418 int
 419 strlist_get_max_size(StringList list)
 420 {
 421     return list->strings_size;
 422 }
 423
 424
 425 /*
 426  * Frees any extra memory that may not be needed (multiple strings are
 427  * allocated at once, to reduce the number of realloc calls).
 428  */
 429 int
 430 strlist_shrink_mem_to_fit(StringList list)
 431 {
 432     int         return_value = 0;
 433     int         diff = list->strings_size - list->num_strings;
 434
 435     if (diff > 0)
 436     {
 437         return_value = strlistP_shrink_array(list, diff);
 438     }
 439
 440     return return_value;
 441 }
 442
 443
 444 /*************************************************************************
 445 **                                                                      **
 446 **              STRING interface                                        **
 447 **                                                                      **
 448 **************************************************************************/
 449
 450 int
 451 strlist_add_str(StringList list, STRING string, void *clientData)
 452 {
 453     int         return_value = 0;
 454     ISTRING     istring = istr_create(string);
 455     return_value = strlist_add_istr(list, istring, clientData);
 456     istr_destroy(istring);
 457     return return_value;
 458 }
 459
 460
 461 #ifdef UNIMPLEMENTED
 462 int
 463 strlist_add_index_str(StringList list, int index, STRING string, void *clientData)
 464 {
 465     int         return_value = 0;
 466     ISTRING     istring = istr_create(string);
 467     return_value = strlist_add_index_istr(list, index, istring, clientData);
 468     istr_destroy(istring);
 469     return return_value;
 470 }
 471 #endif /* UNIMPLEMENTED */
 472
 473
 474 BOOL
 475 strlist_str_exists(StringList list, STRING string)
 476 {
 477     BOOL        doesIt = FALSE;
 478     ISTRING     istring = istr_dup_existing(string);
 479     if (istring != NULL)
 480     {
 481         doesIt = strlist_istr_exists(list, istring);
 482         istr_destroy(istring);
 483     }
 484     return doesIt;
 485 }
 486
 487
 488 int
 489 strlist_get_str_index(StringList list, STRING string)
 490 {
 491     int         index = -1;
 492     ISTRING     istring = istr_create(string);
 493     if (istring != NULL)
 494     {
 495         index = strlist_get_istr_index(list, istring);
 496         istr_destroy(istring);
 497     }
 498     return index;
 499 }
 500
 501
 502 STRING
 503 strlist_get_str(StringList list, int whichString, void **clientDataOut)
 504 {
 505     return istr_string(strlist_get_istr(list, whichString, clientDataOut));
 506 }
 507
 508
 509 int
 510 strlist_remove_str(StringList list, STRING string)
 511 {
 512     int         return_value = 0;
 513     ISTRING     istring = istr_dup_existing(string);
 514     if (istring != NULL)
 515     {
 516         return_value = strlist_remove_istr(list, istring);
 517         istr_destroy(istring);
 518     }
 519     return return_value;
 520 }
 521
 522
 523 int
 524 strlist_set_str_data(StringList list, STRING string, void *data)
 525 {
 526     int         return_value = 0;
 527     ISTRING     istring = istr_dup_existing(string);
 528     if (istring != NULL)
 529     {
 530         return_value = strlist_set_istr_data(list, istring, data);
 531         istr_destroy(istring);
 532     }
 533     return return_value;
 534 }
 535
 536
 537 void *
 538 strlist_get_str_data(StringList list, STRING string)
 539 {
 540     void        *clientData = NULL;
 541     ISTRING     istring = istr_dup_existing(string);
 542     if (istring != NULL)
 543     {
 544         clientData = strlist_get_istr_data(list, istring);
 545         istr_destroy(istring);
 546     }
 547     return clientData;
 548 }
 549
 550 StringList
 551 strlist_dup(StringList list)
 552 {
 553     int         i;
 554     StringList  new_list = NULL;
 555
 556     new_list = strlist_create();
 557     new_list->unique = list->unique;
 558     new_list->sort_order = list->sort_order;
 559     new_list->indexes_dirty = list->indexes_dirty;
 560     for (i=0; i<list->num_strings; i++)
 561     {
 562         strlist_add_istr(new_list, list->strings[i], list->user_datas[i]);
 563     }
 564     return(new_list);
 565 }
 566
 567 /*************************************************************************
 568 **                                                                      **
 569 **              PRIVATE FUNCTIONS                                       **
 570 **                                                                      **
 571 **************************************************************************/
 572
 573
 574 strlistP_shrink_array(StringList list, int sizeDiff)
 575 {
 576     int         return_value = 0;
 577     int         new_strings_size = util_max(0, list->strings_size - sizeDiff);
 578     ISTRING     *new_strings = NULL;
 579     void        **new_user_datas = NULL;
 580     int         i = 0;
 581
 582     for (i= new_strings_size; i < list->strings_size; ++i)
 583     {
 584         if (list->strings[i] != NULL)
 585         {
 586             istr_destroy(list->strings[i]);
 587         }
 588         list->user_datas[i] = NULL;
 589     }
 590
 591     if (new_strings_size > 0)
 592     {
 593         new_strings = (ISTRING *) realloc(
 594                           list->strings, new_strings_size * sizeof(ISTRING));
 595         new_user_datas = (void **) realloc(
 596                           list->user_datas, new_strings_size * sizeof(void*));
 597     }
 598     else
 599     {
 600         util_free(list->strings); list->strings = NULL;
 601         util_free(list->user_datas); list->user_datas= NULL;
 602     }
 603
 604     if (   (new_strings_size > 0)
 605         && ((new_strings == NULL) || (new_user_datas == NULL)) )
 606     {
 607         return_value = -1;
 608         goto epilogue;
 609     }
 610     else
 611     {
 612         list->strings = new_strings;
 613         list->user_datas = new_user_datas;
 614         list->strings_size = new_strings_size;
 615         if (list->num_strings > list->strings_size)
 616         {
 617             list->num_strings = util_max(0, list->strings_size);
 618         }
 619     }
 620
 621 epilogue:
 622     return return_value;
 623 }
 624
 625
 626 static int
 627 strlistP_grow_array(StringList list, int sizeDiff)
 628 {
 629     int         return_value = 0;
 630     int         old_strings_size = list->strings_size;
 631     int         new_strings_size = list->strings_size + sizeDiff;
 632     ISTRING     *new_strings = NULL;
 633     void        **new_user_datas = NULL;
 634     int         i = 0;
 635
 636     new_strings = (ISTRING *)realloc(
 637                         list->strings, new_strings_size * sizeof(ISTRING));
 638     new_user_datas = (void **)realloc(
 639                         list->user_datas, new_strings_size * sizeof(void *));
 640     if ((new_strings == NULL) || (new_user_datas == NULL))
 641     {
 642         return_value = -1;
 643         goto epilogue;
 644     }
 645     else
 646     {
 647         list->strings = new_strings;
 648         list->user_datas = new_user_datas;
 649         list->strings_size = new_strings_size;
 650     }
 651
 652     /*
 653      * Init the new entries to NULL;
 654      */
 655     for (i = old_strings_size; i < new_strings_size; ++i)
 656     {
 657         list->strings[i] = NULL;
 658         list->user_datas[i] = NULL;
 659     }
 660
 661 epilogue:
 662     return return_value;
 663 }
 664
 665
 666 static int
 667 strlistP_build_user_data_array(StringList list, int index, void *data)
 668 {
 669     if (list->user_datas != NULL)
 670     {
 671         return -1;
 672     }
 673     list->user_datas = (void **)calloc(sizeof(void*), list->strings_size);
 674     if (list->user_datas == NULL)
 675     {
 676         return -1;
 677     }
 678     list->user_datas[index] = data;
 679     return 0;
 680 }
 681
 682
 683 /*
 684  * debugging output
 685  */
 686 int
 687 strlist_dump(StringList list)
 688 {
 689     int i = 0;
 690     ISTRING     istring = NULL;
 691     STRING      string = NULL;
 692
 693     if (list == NULL)
 694     {
 695         util_printf(0, "NULL string list\n");
 696         return 0;
 697     }
 698     if (list->strings_size == 0)
 699     {
 700         util_dprintf(0, "empty string list\n");
 701         return 0;
 702     }
 703
 704     for (i= 0; i < list->strings_size; ++i)
 705     {
 706         istring= list->strings[i];
 707         if (istr_verify(istring) < 0)
 708         {
 709             string = "** Invalid ISTRING **";
 710         }
 711         else
 712         {
 713             string = util_strsafe(istr_string(istring));
 714         }
 715
 716         util_dprintf(0, "%d[%s]: '%s'",
 717                 i,
 718                 (i >= list->num_strings? " ":"X"),
 719                 string);
 720
 721         if (list->user_datas != NULL)
 722         {
 723             util_dprintf(0, " 0x%08lx", list->user_datas[i]);
 724         }
 725         util_dprintf(0, "\n");
 726     }
 727     util_dprintf(0, "\n");
 728     return 0;
 729 }
 730