Array.c++
上传用户:weiyuanprp
上传日期:2020-05-20
资源大小:1169k
文件大小:8k
源码类别:

传真(Fax)编程

开发平台:

C/C++

  1. /* $Id: Array.c++,v 1.1.1.1 2005/11/11 21:32:03 faxguy Exp $ */
  2. /*
  3.  * Copyright (c) 1990-1996 Sam Leffler
  4.  * Copyright (c) 1991-1996 Silicon Graphics, Inc.
  5.  * HylaFAX is a trademark of Silicon Graphics
  6.  *
  7.  * Permission to use, copy, modify, distribute, and sell this software and 
  8.  * its documentation for any purpose is hereby granted without fee, provided
  9.  * that (i) the above copyright notices and this permission notice appear in
  10.  * all copies of the software and related documentation, and (ii) the names of
  11.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  12.  * publicity relating to the software without the specific, prior written
  13.  * permission of Sam Leffler and Silicon Graphics.
  14.  * 
  15.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  16.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  17.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  18.  * 
  19.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  20.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  21.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  22.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  23.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  24.  * OF THIS SOFTWARE.
  25.  */
  26. #include "Array.h"
  27. #include <stdlib.h>
  28. #define that (*this)
  29. fxArray::fxArray(u_short esize, u_int initlength)
  30. {
  31.     num = maxi = initlength * esize;
  32.     elementsize = esize;
  33.     if (maxi != 0)
  34. data = malloc((u_int) maxi);
  35.     else
  36. data = 0;
  37.     // Don't create the elements because the subclass will do that, because
  38.     // we can't call a virtual from within this constructor.
  39. }
  40. fxArray::fxArray(const fxArray & other)
  41. {
  42.     num = other.num;
  43.     maxi = other.num;
  44.     elementsize = other.elementsize;
  45.     data = 0;
  46.     getmem();
  47.     copyElements(other.data,data,num);
  48. }
  49. fxArray::fxArray(u_int esize, u_int n, void * d)
  50. {
  51.     elementsize=esize;
  52.     num=maxi=n;
  53.     data=d;
  54. }
  55. fxArray::~fxArray()
  56. {
  57.     if (data)
  58. free((void*) data);
  59. }
  60. void
  61. fxArray::destroy()
  62. {
  63.     if (num != 0) destroyElements(data,num);
  64. }
  65. u_int fxArray::length() const { return num/elementsize; }
  66. void
  67. fxArray::append(void const * item) {
  68.     assert(num<=maxi);
  69.     if (num == maxi) expand();
  70.     copyElements(item, data + num, elementsize);
  71.     num += elementsize;
  72. }
  73. void
  74. fxArray::append(const fxArray & a) {
  75.     assert(elementsize == a.elementsize);
  76.     u_int length = a.num;
  77.     if (length > 0) {
  78. if (num + length > maxi) {
  79.     maxi = num + length;
  80.     getmem();
  81. }
  82. copyElements(a.data, data+num, length);
  83. num += length;
  84.     }
  85. }
  86. void
  87. fxArray::remove(u_int start, u_int length) {
  88.   if (length>0) {
  89.     start *= elementsize;
  90.     length *= elementsize;
  91.     assert(start+length <= num);
  92.     destroyElements(data+start,length);
  93.     if (start+length < num) {
  94. memmove((void*)(data + start),
  95.     (void*)(data + start+length), num - (start+length));
  96. // we don't use copyElements because they are just being moved.
  97.     }
  98.     num -= length;
  99.     // we don't destroy the end elements because they still exist; they've
  100.     // just been moved.
  101.   }
  102. }
  103. void
  104. fxArray::resize(u_int length) {
  105.     length *= elementsize;
  106.     maxi = length;
  107.     if (length>num) {
  108. getmem();
  109. createElements(data + num, length - num);
  110.     } else if (num>length) {
  111. destroyElements(data + length, num - length);
  112. getmem();
  113.     }
  114.     num = length;
  115. }
  116. void
  117. fxArray::setMaxLength(u_int length)
  118. {
  119.     length *= elementsize;
  120.     length = fxmax(length,num);
  121.     if (maxi != length) {
  122. maxi = length;
  123. getmem();
  124.     }
  125. }
  126. void
  127. fxArray::createElements(void*, u_int)
  128. {
  129. }
  130. void
  131. fxArray::destroyElements(void*, u_int)
  132. {
  133. }
  134. void
  135. fxArray::copyElements(const void * source, void * dest, u_int length) const
  136. {
  137.     memmove(dest,source,length);
  138. }
  139. int
  140. fxArray::compareElements(const void * e1, const void * e2) const
  141. {
  142.     return memcmp(e1,e2,elementsize);
  143. }
  144. void
  145. fxArray::expand()
  146. { // by default, grab 4 more element spaces
  147.     maxi += elementsize*4;
  148.     getmem();
  149. }
  150. // this function keeps `data' up to date when maxi has just been changed
  151. void
  152. fxArray::getmem()
  153. {
  154.     if (maxi == 0) {
  155. if (data)
  156.     free((void*) data);
  157. data = 0;
  158.     } else {
  159. if (data)
  160.     data = realloc(data,maxi);
  161. else
  162.     data = malloc(maxi);
  163.     }
  164. }
  165. void
  166. fxArray::insert(fxArray const & a, u_int posn)
  167. {
  168.     u_int length = a.num;
  169.     if (a.length()>0) {
  170. assert(elementsize == a.elementsize);
  171. posn *= elementsize;
  172. assert(posn <= num);
  173. if (maxi < num + length) {
  174.     maxi = num + length;
  175.     getmem();
  176. }
  177. if (posn < num) {
  178.     memmove((void*)(data+posn+length), (void*)(data+posn), num-posn);
  179.     // we don't need to do a copyElements because we're not
  180.     // making new copies of objects, we're just moving
  181.     // existing ones.
  182. }
  183. copyElements(a.data, data+posn, length);
  184. num += length;
  185.     }
  186. }
  187. void
  188. fxArray::insert(void const * item, u_int posn)
  189. {
  190.     posn *= elementsize;
  191.     assert(posn <= num);
  192.     if (maxi <= num) {
  193. maxi = num+elementsize;
  194. getmem();
  195.     }
  196.     if (posn<num) {
  197. memmove((void*)(data+posn+(u_int)elementsize),
  198.     (void*)(data+posn), num-posn);
  199.     }
  200.     copyElements(item, data+posn, elementsize);
  201.     num += elementsize;
  202. }
  203. #define TEMPSIZE 1024
  204. void
  205. fxArray::swap(u_int p1, u_int p2)
  206. {
  207.     char buffer[TEMPSIZE];
  208.     void *tmp;
  209.     p1 *= elementsize;
  210.     p2 *= elementsize;
  211.     if (elementsize>TEMPSIZE) tmp=malloc(elementsize);
  212.     else tmp = buffer;
  213.     memcpy(tmp,(void*)(data+p1),elementsize);
  214.     memcpy((void*)(data+p1),(void*)(data+p2),elementsize);
  215.     memcpy((void*)(data+p2),tmp,elementsize);
  216. }
  217. u_int
  218. fxArray::find(void const * item, u_int start) const
  219. {
  220.     assert(start*elementsize <= num);
  221.     fxAddress p = data + (u_int)(start*elementsize);
  222.     while (p < data + num) {
  223. if (0 == compareElements(item,p)) return start;
  224. p = p+elementsize;
  225. start++;
  226.     }
  227.     return fx_invalidArrayIndex;
  228. }
  229. void
  230. fxArray::qsortInternal(u_int l, u_int r, void * tmp)
  231. {
  232.     register u_int i=l;
  233.     register u_int k=r+1;
  234.     u_int e = elementsize;
  235.     assert(k<=length());
  236.     void * item = that[l];
  237.     for (;;) {
  238. for (;;) {
  239.             if(i>=r)break;
  240.             ++i;
  241.             if (compareElements(that[i],item) >= 0) break;
  242.         }
  243.         for (;;) {
  244.             if (k<=l) break;
  245.             --k;
  246.             if (compareElements(that[k],item) <= 0) break;
  247.         }
  248.         if (i>=k) break;
  249. memcpy(tmp,that[i],e);
  250. memcpy(that[i],that[k],e);
  251. memcpy(that[k],tmp,e);
  252.     }
  253.     memcpy(tmp,that[l],e);
  254.     memcpy(that[l],that[k],e);
  255.     memcpy(that[k],tmp,e);
  256.     if (k && l<k-1) qsortInternal(l,k-1,tmp);
  257.     if (k+1 < r) qsortInternal(k+1,r,tmp);
  258. }
  259. #define SMALLBUFFERSIZE 32
  260. void
  261. fxArray::qsort(u_int posn, u_int len)
  262. {
  263.     if (len == 0) return;
  264.     char smallbuffer[SMALLBUFFERSIZE];
  265.     assert(posn+len <= num);
  266.     void *tmp = (elementsize > SMALLBUFFERSIZE)
  267. ? malloc(elementsize)
  268. : smallbuffer;
  269.     qsortInternal(posn,posn+len-1,tmp);
  270.     if (tmp != smallbuffer) free(tmp);
  271. }
  272. void
  273. fxArray::qsort()
  274. {
  275.     qsort(0,length());
  276. }
  277. void *
  278. fxArray::raw_extract(u_int start, u_int len) const
  279. {
  280.     if (len == 0) return 0;
  281.     start *= elementsize;
  282.     len *= elementsize;
  283.     assert(start+len<=num);
  284.     void * ret = malloc(len);
  285.     copyElements(data+start, ret, len);
  286.     return ret;
  287. }
  288. void *
  289. fxArray::raw_cut(u_int start, u_int len)
  290. {
  291.     if (len == 0) return 0;
  292.     start *= elementsize;
  293.     len *= elementsize;
  294.     assert(start+len <= num);
  295.     void * ret = malloc(len);
  296.     // we don't copy because we aren't making copies, we're just
  297.     // moving existing elements from one array to another.
  298.     memcpy(ret, (void*)(data+start), len);
  299.     if (start+len < num) {
  300. // we don't use copyElements because they are just being moved.
  301. memmove((void*)(data + start),
  302.     (void*)(data + start+len), num - (start+len));
  303.     }
  304.     num -= len;
  305.     return ret;
  306. }
  307. void *
  308. fxArray::raw_copy() const
  309. {
  310.     if (num == 0) return 0;
  311.     void * ret = malloc(num);
  312.     copyElements(data,ret,num);
  313.     return ret;
  314. }
  315. void *
  316. fxArray::raw_head(u_int len) const
  317. {
  318.     if (len == 0) return 0;
  319.     assert(len <= num);
  320.     return raw_extract(0,len);
  321. }
  322. void *
  323. fxArray::raw_tail(u_int len) const
  324. {
  325.     if (len == 0) return 0;
  326.     len *= elementsize;
  327.     assert(len <= num);
  328.     void * ret = malloc(len);
  329.     copyElements(data+(num-len), ret, len);
  330.     return ret;
  331. }