home *** CD-ROM | disk | FTP | other *** search
/ Large Pack of OldSkool DOS MOD Trackers / goattracker_2.65.zip / src / asm / vec.c < prev    next >
C/C++ Source or Header  |  2006-03-24  |  4KB  |  201 lines
  1. /*
  2.  * Copyright (c) 2003 - 2005 Magnus Lind.
  3.  *
  4.  * This software is provided 'as-is', without any express or implied warranty.
  5.  * In no event will the authors be held liable for any damages arising from
  6.  * the use of this software.
  7.  *
  8.  * Permission is granted to anyone to use this software, alter it and re-
  9.  * distribute it freely for any non-commercial, non-profit purpose subject to
  10.  * the following restrictions:
  11.  *
  12.  *   1. The origin of this software must not be misrepresented; you must not
  13.  *   claim that you wrote the original software. If you use this software in a
  14.  *   product, an acknowledgment in the product documentation would be
  15.  *   appreciated but is not required.
  16.  *
  17.  *   2. Altered source versions must be plainly marked as such, and must not
  18.  *   be misrepresented as being the original software.
  19.  *
  20.  *   3. This notice may not be removed or altered from any distribution.
  21.  *
  22.  *   4. The names of this software and/or it's copyright holders may not be
  23.  *   used to endorse or promote products derived from this software without
  24.  *   specific prior written permission.
  25.  *
  26.  */
  27.  
  28. #include "vec.h"
  29. #include <stdlib.h>
  30.  
  31.  
  32. #define VEC_FLAG_SORTED 1
  33.  
  34. void vec_init(struct vec *p, size_t elsize)
  35. {
  36.     p->elsize = elsize;
  37.     membuf_init(&p->buf);
  38.     p->flags = VEC_FLAG_SORTED;
  39. }
  40.  
  41. void vec_clear(struct vec *p, cb_free * f)
  42. {
  43.     struct vec_iterator i;
  44.     void *d;
  45.  
  46.     vec_get_iterator(p, &i);
  47.  
  48.     if (f != NULL)
  49.     {
  50.         while ((d = vec_iterator_next(&i)) != NULL)
  51.         {
  52.             f(d);
  53.         }
  54.     }
  55.     membuf_clear(&p->buf);
  56.     p->flags = VEC_FLAG_SORTED;
  57. }
  58.  
  59. void vec_free(struct vec *p, cb_free * f)
  60. {
  61.     vec_clear(p, f);
  62.     membuf_free(&p->buf);
  63. }
  64.  
  65. int vec_count(struct vec *p)
  66. {
  67.     int count;
  68.     count = membuf_memlen(&p->buf) / p->elsize;
  69.     return count;
  70. }
  71.  
  72. void *vec_get(struct vec *p, int index)
  73. {
  74.     char *buf;
  75.  
  76.     buf = (char *) membuf_get(&p->buf);
  77.     buf += index * p->elsize;
  78.  
  79.     return (void *)buf;
  80. }
  81.  
  82. void *vec_insert(struct vec *p, int index, const void *in)
  83. {
  84.     void *buf;
  85.  
  86.     buf = membuf_insert(&p->buf, index * p->elsize, in, p->elsize);
  87.  
  88.     return buf;
  89. }
  90.  
  91. void *vec_push(struct vec *p, const void *in)
  92. {
  93.     void *out;
  94.     out = membuf_append(&p->buf, in, p->elsize);
  95.     p->flags &= ~VEC_FLAG_SORTED;
  96.  
  97.     return out;
  98. }
  99.  
  100. int vec_find(struct vec *p, cb_cmp * f, const void *in)
  101. {
  102.     int lo;
  103.  
  104.     lo = -1;
  105.     if(p->flags & VEC_FLAG_SORTED)
  106.     {
  107.         int hi;
  108.         lo = 0;
  109.         hi = vec_count(p) - 1;
  110.         while(lo <= hi)
  111.         {
  112.             int next;
  113.             int val;
  114.  
  115.             next = (lo + hi) / 2;
  116.             val = f(in, vec_get(p, next));
  117.             if(val == 0)
  118.             {
  119.                 /* match */
  120.                 lo = -(next + 2);
  121.                 break;
  122.             }
  123.             else if(val < 0)
  124.             {
  125.                 hi = next - 1;
  126.             }
  127.             else
  128.             {
  129.                 lo = next + 1;
  130.             }
  131.         }
  132.     }
  133.     return -(lo + 2);
  134. }
  135.  
  136. void *vec_find2(struct vec *p, cb_cmp * f, const void *key)
  137. {
  138.     void *out = NULL;
  139.     int pos = vec_find(p, f, key);
  140.     if(pos >= 0)
  141.     {
  142.         out = vec_get(p, pos);
  143.     }
  144.     return out;
  145. }
  146.  
  147. int vec_insert_uniq(struct vec *p, cb_cmp * f, const void *in, void **outp)
  148. {
  149.     int val = 0;
  150.     void *out;
  151.  
  152.     val = vec_find(p, f, in);
  153.     if(val != -1)
  154.     {
  155.         if(val < 0)
  156.         {
  157.             /* not there */
  158.             out = vec_insert(p, -(val + 2), in);
  159.             val = 1;
  160.         }
  161.         else
  162.         {
  163.             out = vec_get(p, val);
  164.             val = 0;
  165.         }
  166.  
  167.         if(outp != NULL)
  168.         {
  169.             *outp = out;
  170.         }
  171.     }
  172.  
  173.     return val;
  174. }
  175.  
  176. void vec_sort(struct vec *p, cb_cmp * f)
  177. {
  178.     qsort(membuf_get(&p->buf), vec_count(p), p->elsize, f);
  179.     p->flags |= VEC_FLAG_SORTED;
  180. }
  181.  
  182.  
  183. void vec_get_iterator(struct vec *p, struct vec_iterator *i)
  184. {
  185.     i->vec = p;
  186.     i->pos = 0;
  187. }
  188.  
  189. void *vec_iterator_next(struct vec_iterator *i)
  190. {
  191.     void *out;
  192.     int count = vec_count(i->vec);
  193.     if (i->pos >= count)
  194.     {
  195.         return NULL;
  196.     }
  197.     out = vec_get(i->vec, i->pos);
  198.     i->pos += 1;
  199.     return out;
  200. }
  201.