uspace/lib/c/generic/gsort.c

   1 /*
   2  * Copyright (c) 2005 Sergey Bondari
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup libc
  30  * @{
  31  */
  32
  33 /**
  34  * @file
  35  * @brief Gnome Sort.
  36  *
  37  * This file contains an implementation of gnome sort
  38  *
  39  */
  40
  41 #include <gsort.h>
  42 #include <inttypes.h>
  43 #include <mem.h>
  44 #include <stdlib.h>
  45
  46 /** Immediate buffer size.
  47  *
  48  * For small buffer sizes avoid doing malloc()
  49  * and use the stack.
  50  *
  51  */
  52 #define IBUF_SIZE  32
  53
  54 /** Array accessor.
  55  *
  56  */
  57 #define INDEX(buf, i, elem_size)  ((buf) + (i) * (elem_size))
  58
  59 /** Gnome sort
  60  *
  61  * Apply generic gnome sort algorithm on supplied data,
  62  * using pre-allocated buffer.
  63  *
  64  * @param data      Pointer to data to be sorted.
  65  * @param cnt       Number of elements to be sorted.
  66  * @param elem_size Size of one element.
  67  * @param cmp       Comparator function.
  68  * @param arg       3rd argument passed to cmp.
  69  * @param slot      Pointer to scratch memory buffer
  70  *                  elem_size bytes long.
  71  *
  72  */
  73 static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
  74     void *arg, void *slot)
  75 {
  76         size_t i = 0;
  77
  78         while (i < cnt) {
  79                 if ((i != 0) &&
  80                     (cmp(INDEX(data, i, elem_size),
  81                     INDEX(data, i - 1, elem_size), arg) < 0)) {
  82                         memcpy(slot, INDEX(data, i, elem_size), elem_size);
  83                         memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size),
  84                             elem_size);
  85                         memcpy(INDEX(data, i - 1, elem_size), slot, elem_size);
  86                         i--;
  87                 } else
  88                         i++;
  89         }
  90 }
  91
  92 /** Gnome sort wrapper
  93  *
  94  * This is only a wrapper that takes care of memory
  95  * allocations for storing the slot element for generic
  96  * gnome sort algorithm.
  97  *
  98  * @param data      Pointer to data to be sorted.
  99  * @param cnt       Number of elements to be sorted.
 100  * @param elem_size Size of one element.
 101  * @param cmp       Comparator function.
 102  * @param arg       3rd argument passed to cmp.
 103  *
 104  * @return True if sorting succeeded.
 105  *
 106  */
 107 bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
 108 {
 109         uint8_t ibuf_slot[IBUF_SIZE];
 110         void *slot;
 111
 112         if (elem_size > IBUF_SIZE) {
 113                 slot = (void *) malloc(elem_size);
 114                 if (!slot)
 115                         return false;
 116         } else
 117                 slot = (void *) ibuf_slot;
 118
 119         _gsort(data, cnt, elem_size, cmp, arg, slot);
 120
 121         if (elem_size > IBUF_SIZE)
 122                 free(slot);
 123
 124         return true;
 125 }
 126
 127 /** @}
 128  */