"Fossies" - the Fresh Open Source Software Archive

Member "tesseract-5.2.0/src/ccutil/elst.cpp" (6 Jul 2022, 14649 Bytes) of package /linux/misc/tesseract-5.2.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "elst.cpp" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 5.0.0_vs_5.0.1.

    1 /**********************************************************************
    2  * File:        elst.cpp  (Formerly elist.c)
    3  * Description: Embedded list handling code which is not in the include file.
    4  * Author:      Phil Cheatle
    5  *
    6  * (C) Copyright 1991, Hewlett-Packard Ltd.
    7  ** Licensed under the Apache License, Version 2.0 (the "License");
    8  ** you may not use this file except in compliance with the License.
    9  ** You may obtain a copy of the License at
   10  ** http://www.apache.org/licenses/LICENSE-2.0
   11  ** Unless required by applicable law or agreed to in writing, software
   12  ** distributed under the License is distributed on an "AS IS" BASIS,
   13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   14  ** See the License for the specific language governing permissions and
   15  ** limitations under the License.
   16  *
   17  **********************************************************************/
   18 
   19 #include "elst.h"
   20 #include <cstdlib>
   21 
   22 namespace tesseract {
   23 
   24 /***********************************************************************
   25  *              ELIST::internal_clear
   26  *
   27  *  Used by the destructor and the "clear" member function of derived list
   28  *  classes to destroy all the elements on the list.
   29  *  The calling function passes a "zapper" function which can be called to
   30  *  delete each element of the list, regardless of its derived type.  This
   31  *  technique permits a generic clear function to destroy elements of
   32  *  different derived types correctly, without requiring virtual functions and
   33  *  the consequential memory overhead.
   34  **********************************************************************/
   35 
   36 void ELIST::internal_clear( // destroy all links
   37     void (*zapper)(void *)) {
   38   // ptr to zapper functn
   39   ELIST_LINK *ptr;
   40   ELIST_LINK *next;
   41 
   42   if (!empty()) {
   43     ptr = last->next;     // set to first
   44     last->next = nullptr; // break circle
   45     last = nullptr;       // set list empty
   46     while (ptr) {
   47       next = ptr->next;
   48       zapper(ptr);
   49       ptr = next;
   50     }
   51   }
   52 }
   53 
   54 /***********************************************************************
   55  *              ELIST::assign_to_sublist
   56  *
   57  *  The list is set to a sublist of another list.  "This" list must be empty
   58  *  before this function is invoked.  The two iterators passed must refer to
   59  *  the same list, different from "this" one.  The sublist removed is the
   60  *  inclusive list from start_it's current position to end_it's current
   61  *  position.  If this range passes over the end of the source list then the
   62  *  source list has its end set to the previous element of start_it.  The
   63  *  extracted sublist is unaffected by the end point of the source list, its
   64  *  end point is always the end_it position.
   65  **********************************************************************/
   66 
   67 void ELIST::assign_to_sublist( // to this list
   68     ELIST_ITERATOR *start_it,  // from list start
   69     ELIST_ITERATOR *end_it) {  // from list end
   70   constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist");
   71 
   72   if (!empty()) {
   73     LIST_NOT_EMPTY.error("ELIST.assign_to_sublist", ABORT);
   74   }
   75 
   76   last = start_it->extract_sublist(end_it);
   77 }
   78 
   79 /***********************************************************************
   80  *              ELIST::sort
   81  *
   82  *  Sort elements on list
   83  *  NB If you don't like the const declarations in the comparator, coerce yours:
   84  *   ( int (*)(const void *, const void *)
   85  **********************************************************************/
   86 
   87 void ELIST::sort(   // sort elements
   88     int comparator( // comparison routine
   89         const void *, const void *)) {
   90   // Allocate an array of pointers, one per list element.
   91   auto count = length();
   92 
   93   if (count > 0) {
   94     // ptr array to sort
   95     std::vector<ELIST_LINK *> base;
   96     base.reserve(count);
   97 
   98     ELIST_ITERATOR it(this);
   99 
  100     // Extract all elements, putting the pointers in the array.
  101     for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
  102       base.push_back(it.extract());
  103     }
  104 
  105     // Sort the pointer array.
  106     qsort(&base[0], count, sizeof(base[0]), comparator);
  107 
  108     // Rebuild the list from the sorted pointers.
  109     for (auto current : base) {
  110       it.add_to_end(current);
  111     }
  112   }
  113 }
  114 
  115 // Assuming list has been sorted already, insert new_link to
  116 // keep the list sorted according to the same comparison function.
  117 // Comparison function is the same as used by sort, i.e. uses double
  118 // indirection. Time is O(1) to add to beginning or end.
  119 // Time is linear to add pre-sorted items to an empty list.
  120 // If unique is set to true and comparator() returns 0 (an entry with the
  121 // same information as the one contained in new_link is already in the
  122 // list) - new_link is not added to the list and the function returns the
  123 // pointer to the identical entry that already exists in the list
  124 // (otherwise the function returns new_link).
  125 ELIST_LINK *ELIST::add_sorted_and_find(int comparator(const void *, const void *), bool unique,
  126                                        ELIST_LINK *new_link) {
  127   // Check for adding at the end.
  128   if (last == nullptr || comparator(&last, &new_link) < 0) {
  129     if (last == nullptr) {
  130       new_link->next = new_link;
  131     } else {
  132       new_link->next = last->next;
  133       last->next = new_link;
  134     }
  135     last = new_link;
  136   } else {
  137     // Need to use an iterator.
  138     ELIST_ITERATOR it(this);
  139     for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
  140       ELIST_LINK *link = it.data();
  141       int compare = comparator(&link, &new_link);
  142       if (compare > 0) {
  143         break;
  144       } else if (unique && compare == 0) {
  145         return link;
  146       }
  147     }
  148     if (it.cycled_list()) {
  149       it.add_to_end(new_link);
  150     } else {
  151       it.add_before_then_move(new_link);
  152     }
  153   }
  154   return new_link;
  155 }
  156 
  157 /***********************************************************************
  158  *  MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR
  159  *  =========================================
  160  **********************************************************************/
  161 
  162 /***********************************************************************
  163  *              ELIST_ITERATOR::forward
  164  *
  165  *  Move the iterator to the next element of the list.
  166  *  REMEMBER: ALL LISTS ARE CIRCULAR.
  167  **********************************************************************/
  168 
  169 ELIST_LINK *ELIST_ITERATOR::forward() {
  170 #ifndef NDEBUG
  171   if (!list)
  172     NO_LIST.error("ELIST_ITERATOR::forward", ABORT);
  173 #endif
  174   if (list->empty()) {
  175     return nullptr;
  176   }
  177 
  178   if (current) { // not removed so
  179                  // set previous
  180     prev = current;
  181     started_cycling = true;
  182     // In case next is deleted by another iterator, get next from current.
  183     current = current->next;
  184   } else {
  185     if (ex_current_was_cycle_pt) {
  186       cycle_pt = next;
  187     }
  188     current = next;
  189   }
  190 #ifndef NDEBUG
  191   if (!current)
  192     NULL_DATA.error("ELIST_ITERATOR::forward", ABORT);
  193 #endif
  194   next = current->next;
  195 
  196 #ifndef NDEBUG
  197   if (!next) {
  198     NULL_NEXT.error("ELIST_ITERATOR::forward", ABORT,
  199                     "This is: %p  Current is: %p",
  200                     static_cast<void *>(this),
  201                     static_cast<void *>(current));
  202   }
  203 #endif
  204   return current;
  205 }
  206 
  207 /***********************************************************************
  208  *              ELIST_ITERATOR::data_relative
  209  *
  210  *  Return the data pointer to the element "offset" elements from current.
  211  *  "offset" must not be less than -1.
  212  *  (This function can't be INLINEd because it contains a loop)
  213  **********************************************************************/
  214 
  215 ELIST_LINK *ELIST_ITERATOR::data_relative( // get data + or - ...
  216     int8_t offset) {                       // offset from current
  217   ELIST_LINK *ptr;
  218 
  219 #ifndef NDEBUG
  220   if (!list)
  221     NO_LIST.error("ELIST_ITERATOR::data_relative", ABORT);
  222   if (list->empty())
  223     EMPTY_LIST.error("ELIST_ITERATOR::data_relative", ABORT);
  224   if (offset < -1)
  225     BAD_PARAMETER.error("ELIST_ITERATOR::data_relative", ABORT, "offset < -l");
  226 #endif
  227 
  228   if (offset == -1) {
  229     ptr = prev;
  230   } else {
  231     for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
  232       ;
  233     }
  234   }
  235 
  236 #ifndef NDEBUG
  237   if (!ptr)
  238     NULL_DATA.error("ELIST_ITERATOR::data_relative", ABORT);
  239 #endif
  240 
  241   return ptr;
  242 }
  243 
  244 /***********************************************************************
  245  *              ELIST_ITERATOR::move_to_last()
  246  *
  247  *  Move current so that it is set to the end of the list.
  248  *  Return data just in case anyone wants it.
  249  *  (This function can't be INLINEd because it contains a loop)
  250  **********************************************************************/
  251 
  252 ELIST_LINK *ELIST_ITERATOR::move_to_last() {
  253 #ifndef NDEBUG
  254   if (!list)
  255     NO_LIST.error("ELIST_ITERATOR::move_to_last", ABORT);
  256 #endif
  257 
  258   while (current != list->last) {
  259     forward();
  260   }
  261 
  262   return current;
  263 }
  264 
  265 /***********************************************************************
  266  *              ELIST_ITERATOR::exchange()
  267  *
  268  *  Given another iterator, whose current element is a different element on
  269  *  the same list list OR an element of another list, exchange the two current
  270  *  elements.  On return, each iterator points to the element which was the
  271  *  other iterators current on entry.
  272  *  (This function hasn't been in-lined because its a bit big!)
  273  **********************************************************************/
  274 
  275 void ELIST_ITERATOR::exchange(  // positions of 2 links
  276     ELIST_ITERATOR *other_it) { // other iterator
  277   constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists");
  278 
  279   ELIST_LINK *old_current;
  280 
  281 #ifndef NDEBUG
  282   if (!list)
  283     NO_LIST.error("ELIST_ITERATOR::exchange", ABORT);
  284   if (!other_it)
  285     BAD_PARAMETER.error("ELIST_ITERATOR::exchange", ABORT, "other_it nullptr");
  286   if (!(other_it->list))
  287     NO_LIST.error("ELIST_ITERATOR::exchange", ABORT, "other_it");
  288 #endif
  289 
  290   /* Do nothing if either list is empty or if both iterators reference the same
  291 link */
  292 
  293   if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) {
  294     return;
  295   }
  296 
  297   /* Error if either current element is deleted */
  298 
  299   if (!current || !other_it->current) {
  300     DONT_EXCHANGE_DELETED.error("ELIST_ITERATOR.exchange", ABORT);
  301   }
  302 
  303   /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
  304 (other before this); non-doubleton adjacent elements (this before other);
  305 non-adjacent elements. */
  306 
  307   // adjacent links
  308   if ((next == other_it->current) || (other_it->next == current)) {
  309     // doubleton list
  310     if ((next == other_it->current) && (other_it->next == current)) {
  311       prev = next = current;
  312       other_it->prev = other_it->next = other_it->current;
  313     } else { // non-doubleton with
  314              // adjacent links
  315              // other before this
  316       if (other_it->next == current) {
  317         other_it->prev->next = current;
  318         other_it->current->next = next;
  319         current->next = other_it->current;
  320         other_it->next = other_it->current;
  321         prev = current;
  322       } else { // this before other
  323         prev->next = other_it->current;
  324         current->next = other_it->next;
  325         other_it->current->next = current;
  326         next = current;
  327         other_it->prev = other_it->current;
  328       }
  329     }
  330   } else { // no overlap
  331     prev->next = other_it->current;
  332     current->next = other_it->next;
  333     other_it->prev->next = current;
  334     other_it->current->next = next;
  335   }
  336 
  337   /* update end of list pointer when necessary (remember that the 2 iterators
  338   may iterate over different lists!) */
  339 
  340   if (list->last == current) {
  341     list->last = other_it->current;
  342   }
  343   if (other_it->list->last == other_it->current) {
  344     other_it->list->last = current;
  345   }
  346 
  347   if (current == cycle_pt) {
  348     cycle_pt = other_it->cycle_pt;
  349   }
  350   if (other_it->current == other_it->cycle_pt) {
  351     other_it->cycle_pt = cycle_pt;
  352   }
  353 
  354   /* The actual exchange - in all cases*/
  355 
  356   old_current = current;
  357   current = other_it->current;
  358   other_it->current = old_current;
  359 }
  360 
  361 /***********************************************************************
  362  *              ELIST_ITERATOR::extract_sublist()
  363  *
  364  *  This is a private member, used only by ELIST::assign_to_sublist.
  365  *  Given another iterator for the same list, extract the links from THIS to
  366  *  OTHER inclusive, link them into a new circular list, and return a
  367  *  pointer to the last element.
  368  *  (Can't inline this function because it contains a loop)
  369  **********************************************************************/
  370 
  371 ELIST_LINK *ELIST_ITERATOR::extract_sublist( // from this current
  372     ELIST_ITERATOR *other_it) {              // to other current
  373 #ifndef NDEBUG
  374   constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists");
  375   constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points");
  376 #endif
  377   constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
  378 
  379   ELIST_ITERATOR temp_it = *this;
  380   ELIST_LINK *end_of_new_list;
  381 
  382 #ifndef NDEBUG
  383   if (!other_it)
  384     BAD_PARAMETER.error("ELIST_ITERATOR::extract_sublist", ABORT, "other_it nullptr");
  385   if (!list)
  386     NO_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT);
  387   if (list != other_it->list)
  388     BAD_EXTRACTION_PTS.error("ELIST_ITERATOR.extract_sublist", ABORT);
  389   if (list->empty())
  390     EMPTY_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT);
  391 
  392   if (!current || !other_it->current)
  393     DONT_EXTRACT_DELETED.error("ELIST_ITERATOR.extract_sublist", ABORT);
  394 #endif
  395 
  396   ex_current_was_last = other_it->ex_current_was_last = false;
  397   ex_current_was_cycle_pt = false;
  398   other_it->ex_current_was_cycle_pt = false;
  399 
  400   temp_it.mark_cycle_pt();
  401   do {                         // walk sublist
  402     if (temp_it.cycled_list()) { // can't find end pt
  403       BAD_SUBLIST.error("ELIST_ITERATOR.extract_sublist", ABORT);
  404     }
  405 
  406     if (temp_it.at_last()) {
  407       list->last = prev;
  408       ex_current_was_last = other_it->ex_current_was_last = true;
  409     }
  410 
  411     if (temp_it.current == cycle_pt) {
  412       ex_current_was_cycle_pt = true;
  413     }
  414 
  415     if (temp_it.current == other_it->cycle_pt) {
  416       other_it->ex_current_was_cycle_pt = true;
  417     }
  418 
  419     temp_it.forward();
  420   } while (temp_it.prev != other_it->current);
  421 
  422   // circularise sublist
  423   other_it->current->next = current;
  424   end_of_new_list = other_it->current;
  425 
  426   // sublist = whole list
  427   if (prev == other_it->current) {
  428     list->last = nullptr;
  429     prev = current = next = nullptr;
  430     other_it->prev = other_it->current = other_it->next = nullptr;
  431   } else {
  432     prev->next = other_it->next;
  433     current = other_it->current = nullptr;
  434     next = other_it->next;
  435     other_it->prev = prev;
  436   }
  437   return end_of_new_list;
  438 }
  439 
  440 } // namespace tesseract