cde/lib/tt/lib/util/tt_object_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 //%%  (c) Copyright 1993, 1994 Hewlett-Packard Company
  24 //%%  (c) Copyright 1993, 1994 International Business Machines Corp.
  25 //%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
  26 //%%  (c) Copyright 1993, 1994 Novell, Inc.
  27 //%%  $XConsortium: tt_object_list.C /main/3 1995/10/23 10:42:37 rswiston $
  28 /* @(#)tt_object_list.C 1.17 93/07/30
  29  *
  30  * tt_object_list.cc
  31  *
  32  * Copyright (c) 1991, 1992, 1993 by Sun Microsystems, Inc.
  33  *
  34  * This is the list package.
  35  */
  36
  37 #include "util/tt_object_list.h"
  38 #include "util/tt_assert.h"
  39 #include "util/tt_iostream.h"
  40
  41 /*
  42  * Construct a new empty list.
  43  */
  44 _Tt_object_list::
  45 _Tt_object_list()
  46 {
  47         first = 0;
  48         last =  0;
  49         _count = 0;
  50 }
  51
  52 /*
  53  * Copy a list.  Sort of expensive, since elements aren't refcounted.
  54  * Should be used sparingly.
  55  */
  56 _Tt_object_list::
  57 _Tt_object_list(const _Tt_object_list &t)
  58 {
  59         _Tt_object_list_element *p, *n;
  60
  61         first = 0;
  62         last = 0;
  63         p = t.first;
  64         while (p != 0) {
  65                 n = new _Tt_object_list_element;
  66                 n->data = p->data;
  67                 n->prev = last;
  68                 n->next = 0;
  69                 if (!first) {
  70                         first = n;
  71                 }
  72                 if (last) {
  73                         last->next = n;
  74                 }
  75                 last = n;
  76                 p = p->next;
  77         }
  78         _count = t._count;
  79 }
  80
  81 /*
  82  * Destroy list, freeing all the elements.
  83  */
  84 _Tt_object_list::
  85 ~_Tt_object_list()
  86 {
  87         _Tt_object_list_element *p, *q;
  88         p = first;
  89         while (p != 0) {
  90                 q = p->next;
  91                 delete p;
  92                 p = q;
  93         }
  94 }
  95
  96 /*
  97  *  Freeing all the elements, and reset.
  98  */
  99 void _Tt_object_list::
 100 flush()
 101 {
 102         _Tt_object_list_element *p, *q;
 103         p = first;
 104         while (p != 0) {
 105                 q = p->next;
 106                 delete p;
 107                 p = q;
 108         }
 109         first = 0;
 110         last =  0;
 111         _count = 0;
 112 }
 113
 114 /*
 115  * push: put a new element on the top of the list.
 116  */
 117 _Tt_object_list& _Tt_object_list::
 118 push(const _Tt_object_ptr &e)
 119 {
 120         _Tt_object_list_element *n = new _Tt_object_list_element;
 121
 122         _count++;
 123         n->data = e;
 124         n->next = first;        /* n->prev is nulled in constructor */
 125         if (0==first)
 126           last = n;
 127         else
 128           first->prev = n;
 129         first = n;
 130         return *this;
 131 }
 132
 133 /*
 134  * pop: remove the element from the top of the list.
 135  */
 136 _Tt_object_list& _Tt_object_list::
 137 pop()
 138 {
 139         _Tt_object_list_element *n;
 140
 141         ASSERT(first,"Pop of empty list");
 142         _count--;
 143         n = first->next;
 144         if (0==n) {
 145                 last = 0;
 146         } else {
 147                 n->prev = 0;
 148         }
 149         delete first;
 150         first = n;
 151         return *this;
 152 }
 153
 154 /*
 155  * append: put a new element at the bottom of the list
 156  */
 157 _Tt_object_list& _Tt_object_list::
 158 append(const _Tt_object_ptr &e)
 159 {
 160         _Tt_object_list_element *n = new _Tt_object_list_element;
 161
 162         _count++;
 163         n->data = e;
 164         n->prev = last;         /* n->next is nulled in constructor */
 165         if (0==last)
 166           first = n;
 167         else
 168           last->next = n;
 169         last = n;
 170         return *this;
 171 }
 172
 173 /*
 174  * Create a new list which is the current list appended to the given list.
 175  */
 176 _Tt_object_list& _Tt_object_list::
 177 append(_Tt_object_list_ptr l)
 178 {
 179         _Tt_object_list_ptr nl = new _Tt_object_list(*l);
 180         append_destructive(nl);
 181         return *this;
 182 }
 183
 184 /*
 185  * append_destructive: append all elements of supplied list to the list.
 186  * as a side effect, empty the supplied list! This somewhat-surprising
 187  * side effect lets us do the append very cheaply by reusing all the
 188  * _Tt_object_list_element instances.
 189  */
 190 _Tt_object_list& _Tt_object_list::
 191 append_destructive(_Tt_object_list_ptr l)
 192 {
 193         if (0==l->first) {
 194                 /* second list is empty, append does nothing */
 195                 return *this;
 196         } else if (0==first) {
 197                 /* first list is null */
 198                 first = l->first;
 199         last = l->last;
 200                 _count = l->_count;
 201         } else {
 202                 /* real work to do */
 203                 l->first->prev = last;
 204                 last->next = l->first;
 205                 last = l->last;
 206                 _count += l->_count;
 207         }
 208         /* empty the second list */
 209         l->first = 0;
 210         l->last = 0;
 211         l->_count = 0;
 212         return *this;
 213 }
 214 /*
 215  * dequeue: remove the element from the bottom of the list.
 216  */
 217 _Tt_object_list& _Tt_object_list::
 218 dequeue()
 219 {
 220         _Tt_object_list_element *n;
 221
 222         ASSERT(last,"Dequeue from empty list");
 223
 224         _count--;
 225         n = last->prev;
 226         if (0==n) {
 227                 first = 0;
 228         } else {
 229                 n->next = 0;
 230         }
 231         delete last;
 232         last = n;
 233         return *this;
 234 }
 235
 236 /*
 237  * Return a pointer to the contents of the element on the top of the list
 238  */
 239 _Tt_object_ptr &_Tt_object_list::
 240 top() const
 241 {
 242         ASSERT(first,"top of empty list");
 243         return first->data;
 244 }
 245
 246 /*
 247  * Return a pointer to the contents of the element on the bottom of the list
 248  */
 249 _Tt_object_ptr &_Tt_object_list::
 250 bot() const
 251 {
 252         ASSERT(last,"bottom of empty list");
 253         return last->data;
 254 }
 255
 256 /*
 257  * Return a pointer to the contents of the n-th element on the list
 258  *
 259  * Note: this implementation could be very slow for large lists.
 260  * The API routines use it heavily.  It's likely the API accesses would be
 261  * sequential, so an improvment would be to have a "cache pointer" to the
 262  * last retrieved element along with its index; then sequential accesses
 263  * could be very fast.
 264  */
 265 _Tt_object_ptr &_Tt_object_list::
 266 operator[](int n) const
 267 {
 268         ASSERT(0<=n && n<=count(),"subscript out of range");
 269         _Tt_object_list_element *p;
 270         p = first;
 271         while(n--) p = p->next;
 272         return p->data;
 273 }
 274
 275 /*
 276  * Predicate that returns 1 iff list is empty, else returns 0
 277  */
 278 int _Tt_object_list::
 279 is_empty() const
 280 {
 281         return first==0;
 282 }
 283
 284 /*
 285  * return number of elements in the list
 286  */
 287 /*
 288  * int _Tt_object_list::
 289  * count() const
 290  * {
 291  *      return _count;
 292  * }
 293  */
 294 /*
 295  *  XDR encoding and decoding function for lists
 296  */
 297 bool_t _Tt_object_list::
 298 xdr(XDR *xdrs, _Tt_new_xdrfn xdrfn, _Tt_object *(*make_new)())
 299 {
 300         if (! xdr_int(xdrs, &_count)) {
 301                 return(0);
 302         }
 303         if (xdrs->x_op == XDR_ENCODE) {
 304                 _Tt_object_list_cursor  cursor(this);
 305                 _Tt_object_ptr          optr;
 306
 307                 while (cursor.next()) {
 308                         optr = *cursor;
 309                         if (optr.is_null()) {
 310                                 continue;
 311                         }
 312                         if (! (*xdrfn)(xdrs, optr.c_pointer())) {
 313                                 return(0);
 314                         }
 315                 }
 316         } else {
 317                 int                     i;
 318                 int                     len;
 319                 _Tt_object_ptr          ptr;
 320
 321                 len = _count;
 322                 flush();
 323                 for (i=len; i > 0; --i) {
 324                         ptr = (*make_new)();
 325                         if (! (*xdrfn)(xdrs, ptr.c_pointer())) {
 326                                 return(0);
 327                         } else {
 328                                 append(ptr);
 329                         }
 330                 }
 331         }
 332
 333         return(1);
 334 }
 335
 336
 337 void _Tt_object_list::
 338 print(_Tt_object_printfn print_elt, const _Tt_ostream &os) const
 339 {
 340         _Tt_object_list_element *cur;
 341         cur = first;
 342         while (cur) {
 343                 (*print_elt)(os, (cur->data).c_pointer());
 344                 os << " ";
 345                 cur = cur->next;
 346         }
 347 }
 348
 349 // verify that an object list is OK.  Since lists are so generic, about all
 350 // we can do is ensure that back pointers do point back, and that every
 351 // element points to a object with a reasonable refcount. Here "reasonable"
 352 // is greater than zero (a must) and less than 1,000,000 (an arbitrarily
 353 // chosen upper bound.)  We also allow the user to pass in a pointer to a
 354 // predicate function which can verify the objects on the list.  We call
 355 // that with each object in turn.  if it returns zero (false) there is a bad
 356 // object on the list.
 357 int _Tt_object_list::
 358 verify(int (*verifier)(const _Tt_object *))
 359 {
 360         _Tt_object_list_element *cur;
 361         int n = 0;
 362         cur = first;
 363         while (cur) {
 364                 if (0==cur->prev && cur!=first) {
 365                         fprintf(stderr,
 366                                 "_Tt_object_list::verify: "
 367                                 "bad null prev at element %d\n",
 368                                 n);
 369                         return 0;
 370                 }
 371                 if (0!=cur->next && cur->next->prev!=cur) {
 372                         fprintf(stderr,
 373                                 "_Tt_object_list::verify: "
 374                                 "bad next->prev at element %d\n",
 375                                 n);
 376                         return 0;
 377                 }
 378                 if (0==cur->next && cur!=last) {
 379                         fprintf(stderr,
 380                                 "_Tt_object_list::verify: "
 381                                 "bad null next at element %d\n",
 382                                 n);
 383                         return 0;
 384                 }
 385                 if (cur->data.is_null()) {
 386                         fprintf(stderr,
 387                                 "_Tt_object_list::verify: "
 388                                 "null data pointer at element %d\n",
 389                                 n);
 390                         return 0;
 391                 }
 392                 if (cur->data->verify_refcount(1000000) < 0) {
 393                         fprintf(stderr,
 394                                 "_Tt_object_list::verify: "
 395                                 "nonpositive _refcount_ at element %d\n",
 396                                 n);
 397                         return 0;
 398                 }
 399                 if (cur->data->verify_refcount(1000000) > 0)  {
 400                         fprintf(stderr,
 401                                 "_Tt_object_list::verify: "
 402                                 "absurdly large _refcount_ at element %d\n",
 403                                 n);
 404                         return 0;
 405                 }
 406                 if (0 != verifier &&
 407                     0 == (*verifier)(cur->data.c_pointer())) {
 408                         fprintf(stderr,
 409                                 "_Tt_object_list::verify: "
 410                                 "verifier rejected object at element %d\n",
 411                                 n);
 412                         return 0;
 413                 }
 414
 415                 cur = cur->next;
 416                 ++n;
 417         }
 418         return 1;
 419 }
 420
 421
 422
 423
 424 /*
 425  * Constructor for list elements
 426  */
 427 _Tt_object_list_element::
 428 _Tt_object_list_element()
 429 {
 430         next = 0;
 431         prev = 0;
 432 }
 433
 434 _Tt_object_list_element::
 435 ~_Tt_object_list_element()
 436 {
 437 }
 438
 439 /*
 440  * The _Tt_object_list_cursor methods implement an iterator which
 441  * provides for convenient stepping along the list.
 442  */
 443 /*
 444  * The simple constructor for a cursor creates a cursor which
 445  * points nowhere. reset(_Tt_object_list_ptr l) must be done before doing
 446  * anything else with the cursor.
 447  */
 448 _Tt_object_list_cursor::
 449 _Tt_object_list_cursor()
 450 {
 451         current = 0;
 452         flags = 0;
 453 }
 454
 455 /*
 456  * The copy constructor for a cursor replicates the current position.
 457  * Note that if two cursors point to the same element and one deletes
 458  * it, the other cursor is hosed.
 459  */
 460 _Tt_object_list_cursor::
 461 _Tt_object_list_cursor(const _Tt_object_list_cursor &c)
 462 {
 463         current = c.current;
 464         listhdr = c.listhdr;
 465         flags = c.flags;
 466 }
 467
 468 /*
 469  * The usual constructor for a cursor supplies a list.  The cursor
 470  * is set before the first element in the list (as if reset(list) had
 471  * been done.)
 472  */
 473 _Tt_object_list_cursor::
 474 _Tt_object_list_cursor(const _Tt_object_list_ptr &l)
 475 {
 476         current = 0;
 477         listhdr = l;
 478         flags = 1<<INIT;
 479         flags &= ~(1<<DELETED);
 480 }
 481
 482 _Tt_object_list_cursor::
 483 ~_Tt_object_list_cursor()
 484 {
 485 }
 486
 487 /*
 488  * reset() moves a cursor back before the start of its list.
 489  */
 490 _Tt_object_list_cursor& _Tt_object_list_cursor::
 491 reset()
 492 {
 493         ASSERT(flags&(1<<INIT),"Attempt to reset an unset cursor.");
 494         current = 0;
 495         flags &= ~(1<<DELETED);
 496         return *this;
 497 }
 498
 499 /*
 500  * reset(_Tt_object_list_ptr l) resets the cursor to a new list, positioned
 501  * before the first element.
 502  */
 503 _Tt_object_list_cursor& _Tt_object_list_cursor::
 504 reset(const _Tt_object_list_ptr &l)
 505 {
 506         current = 0;
 507         listhdr = _Tt_object_list_ptr(l);
 508         flags |= 1<<INIT;
 509         return *this;
 510 }
 511
 512 /*
 513  * operator * returns a ref_counted pointer to the object under the cursor.
 514  */
 515 _Tt_object_ptr &_Tt_object_list_cursor::
 516 operator * () const
 517 {
 518         if (current != 0) {
 519                 return current->data;
 520         } else {
 521                 return _Tt_object::null_ptr();
 522         }
 523 }
 524
 525 /*
 526  * operator -> returns a ref-counted pointer to the object under the cursor,
 527  * which c++ will then apply the _Tt_object_PTR::operator-> to.
 528  */
 529 _Tt_object_ptr &_Tt_object_list_cursor::
 530 operator -> () const
 531 {
 532         return current->data;
 533 }
 534
 535 /*
 536  * next() moves the cursor to the next element in the list and returns 1
 537  * unless there is no next element, in which case it returns 0.
 538  */
 539 int _Tt_object_list_cursor::
 540 next()
 541 {
 542         flags &= ~(1<<DELETED);
 543         if (current!=0) {
 544                 current = current->next;
 545         } else {
 546                 if (listhdr.is_null()) {
 547                         return 0;
 548                 } else {
 549                         current = listhdr->first;
 550                 }
 551         }
 552         return current!=0;
 553 }
 554
 555 /*
 556  * prev() moves the cursor to the prev element in the list and returns 1
 557  * unless there is no prev element, in which case it returns 0.
 558  */
 559 int _Tt_object_list_cursor::
 560 prev()
 561 {
 562         if (flags&(1<<DELETED)) {
 563                 /* already on prev element */
 564                 flags &= ~(1<<DELETED);
 565         } else if (current!=0) {
 566                 current = current->prev;
 567         } else {
 568                 current = listhdr->last;
 569         }
 570         return current!=0;
 571 }
 572
 573 /*
 574  * insert(_Tt_object_ptr p) inserts a new element after the current one.
 575  * inserting right after a delete puts the new element where the
 576  * old deleted one was.  inserting into a reset cursor puts the
 577  * new element first. The cursor points to the new element after insert.
 578  */
 579 _Tt_object_list_cursor& _Tt_object_list_cursor::
 580 insert(const _Tt_object_ptr &p)
 581 {
 582         flags &= ~(1<<DELETED);
 583         if (current == 0) {     /* reset cursor */
 584                 listhdr->push(p);
 585                 current = listhdr->first;
 586         } else {
 587                 _Tt_object_list_element *n = new _Tt_object_list_element;
 588                 listhdr->_count++;
 589                 if (current->next != 0)
 590                   current->next->prev = n;
 591                 else
 592                   listhdr->last = n;
 593                 n->next = current->next;
 594                 n->prev = current;
 595                 n->data = _Tt_object_ptr(p);
 596                 current->next = n;
 597                 current = n;
 598         }
 599         return *this;
 600 }
 601
 602 /*
 603  * remove() deletes the element under the cursor. The cursor is set up
 604  * so that next() after remove() will get the element after the one
 605  * that was removed, and  prev() after remove() will get the element before
 606  * the one that was removed.
 607  */
 608 _Tt_object_list_cursor& _Tt_object_list_cursor::
 609 remove()
 610 {
 611         ASSERT(current,"No current element to delete");
 612         register _Tt_object_list_element *p = current;
 613         listhdr->_count--;
 614         if (p->next != 0)
 615           p->next->prev = p->prev;
 616         else
 617           listhdr->last = p->prev;
 618         if (p->prev != 0)
 619           p->prev->next = p->next;
 620         else
 621           listhdr->first = p->next;
 622         flags |= 1<<DELETED;
 623         current = p->prev;
 624         delete p;
 625         return *this;
 626 }
 627 /*
 628  * is_valid returns 1 if there is an element under the cursor, else 0
 629  */
 630 int _Tt_object_list_cursor::
 631 is_valid() const
 632 {
 633         return 0!=current;
 634 }
 635
 636 implement_ptr_to(_Tt_object)
 637 implement_ptr_to(_Tt_object_list)