← Back to branch summary

~linuxjedi/drizzle/trunk-bug-667053

« back to all changes in this revision

Viewing changes to mysys/array.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/array.c
 
1
/* Copyright (C) 2000 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
/* Handling of arrays that can grow dynamicly. */
 
17
 
 
18
#include "mysys_priv.h"
 
19
#include "m_string.h"
 
20
 
 
21
/*
 
22
  Initiate dynamic array
 
23
 
 
24
  SYNOPSIS
 
25
    init_dynamic_array2()
 
26
      array             Pointer to an array
 
27
      element_size      Size of element
 
28
      init_buffer       Initial buffer pointer
 
29
      init_alloc        Number of initial elements
 
30
      alloc_increment   Increment for adding new elements
 
31
 
 
32
  DESCRIPTION
 
33
    init_dynamic_array() initiates array and allocate space for 
 
34
    init_alloc eilements. 
 
35
    Array is usable even if space allocation failed.
 
36
    Static buffers must begin immediately after the array structure.
 
37
 
 
38
  RETURN VALUE
 
39
    TRUE        my_malloc_ci() failed
 
40
    FALSE       Ok
 
41
*/
 
42
 
 
43
my_bool init_dynamic_array2(DYNAMIC_ARRAY *array, uint element_size,
 
44
                            void *init_buffer, uint init_alloc, 
 
45
                            uint alloc_increment CALLER_INFO_PROTO)
 
46
{
 
47
  DBUG_ENTER("init_dynamic_array");
 
48
  if (!alloc_increment)
 
49
  {
 
50
    alloc_increment=max((8192-MALLOC_OVERHEAD)/element_size,16);
 
51
    if (init_alloc > 8 && alloc_increment > init_alloc * 2)
 
52
      alloc_increment=init_alloc*2;
 
53
  }
 
54
 
 
55
  if (!init_alloc)
 
56
  {
 
57
    init_alloc=alloc_increment;
 
58
    init_buffer= 0;
 
59
  }
 
60
  array->elements=0;
 
61
  array->max_element=init_alloc;
 
62
  array->alloc_increment=alloc_increment;
 
63
  array->size_of_element=element_size;
 
64
  if ((array->buffer= init_buffer))
 
65
    DBUG_RETURN(FALSE);
 
66
  if (!(array->buffer=(uchar*) my_malloc_ci(element_size*init_alloc,
 
67
                                            MYF(MY_WME))))
 
68
  {
 
69
    array->max_element=0;
 
70
    DBUG_RETURN(TRUE);
 
71
  }
 
72
  DBUG_RETURN(FALSE);
 
73
} 
 
74
 
 
75
my_bool init_dynamic_array(DYNAMIC_ARRAY *array, uint element_size,
 
76
                           uint init_alloc, 
 
77
                           uint alloc_increment CALLER_INFO_PROTO)
 
78
{
 
79
  /* placeholder to preserve ABI */
 
80
  return my_init_dynamic_array_ci(array, element_size, init_alloc, 
 
81
                                  alloc_increment);
 
82
}
 
83
/*
 
84
  Insert element at the end of array. Allocate memory if needed.
 
85
 
 
86
  SYNOPSIS
 
87
    insert_dynamic()
 
88
      array
 
89
      element
 
90
 
 
91
  RETURN VALUE
 
92
    TRUE        Insert failed
 
93
    FALSE       Ok
 
94
*/
 
95
 
 
96
my_bool insert_dynamic(DYNAMIC_ARRAY *array, uchar* element)
 
97
{
 
98
  uchar* buffer;
 
99
  if (array->elements == array->max_element)
 
100
  {                                             /* Call only when nessesary */
 
101
    if (!(buffer=alloc_dynamic(array)))
 
102
      return TRUE;
 
103
  }
 
104
  else
 
105
  {
 
106
    buffer=array->buffer+(array->elements * array->size_of_element);
 
107
    array->elements++;
 
108
  }
 
109
  memcpy(buffer,element,(size_t) array->size_of_element);
 
110
  return FALSE;
 
111
}
 
112
 
 
113
 
 
114
/*
 
115
  Alloc space for next element(s) 
 
116
 
 
117
  SYNOPSIS
 
118
    alloc_dynamic()
 
119
      array
 
120
 
 
121
  DESCRIPTION
 
122
    alloc_dynamic() checks if there is empty space for at least
 
123
    one element if not tries to allocate space for alloc_increment
 
124
    elements at the end of array.
 
125
 
 
126
  RETURN VALUE
 
127
    pointer     Pointer to empty space for element
 
128
    0           Error
 
129
*/
 
130
 
 
131
uchar *alloc_dynamic(DYNAMIC_ARRAY *array)
 
132
{
 
133
  if (array->elements == array->max_element)
 
134
  {
 
135
    char *new_ptr;
 
136
    if (array->buffer == (uchar *)(array + 1))
 
137
    {
 
138
      /*
 
139
        In this senerio, the buffer is statically preallocated,
 
140
        so we have to create an all-new malloc since we overflowed
 
141
      */
 
142
      if (!(new_ptr= (char *) my_malloc((array->max_element+
 
143
                                         array->alloc_increment) *
 
144
                                        array->size_of_element,
 
145
                                        MYF(MY_WME))))
 
146
        return 0;
 
147
      memcpy(new_ptr, array->buffer, 
 
148
             array->elements * array->size_of_element);
 
149
    }
 
150
    else
 
151
    if (!(new_ptr=(char*) my_realloc(array->buffer,(array->max_element+
 
152
                                     array->alloc_increment)*
 
153
                                     array->size_of_element,
 
154
                                     MYF(MY_WME | MY_ALLOW_ZERO_PTR))))
 
155
      return 0;
 
156
    array->buffer= (uchar*) new_ptr;
 
157
    array->max_element+=array->alloc_increment;
 
158
  }
 
159
  return array->buffer+(array->elements++ * array->size_of_element);
 
160
}
 
161
 
 
162
 
 
163
/*
 
164
  Pop last element from array.
 
165
 
 
166
  SYNOPSIS
 
167
    pop_dynamic()
 
168
      array
 
169
  
 
170
  RETURN VALUE    
 
171
    pointer     Ok
 
172
    0           Array is empty
 
173
*/
 
174
 
 
175
uchar *pop_dynamic(DYNAMIC_ARRAY *array)
 
176
{
 
177
  if (array->elements)
 
178
    return array->buffer+(--array->elements * array->size_of_element);
 
179
  return 0;
 
180
}
 
181
 
 
182
/*
 
183
  Replace element in array with given element and index
 
184
 
 
185
  SYNOPSIS
 
186
    set_dynamic()
 
187
      array
 
188
      element   Element to be inserted
 
189
      idx       Index where element is to be inserted
 
190
 
 
191
  DESCRIPTION
 
192
    set_dynamic() replaces element in array. 
 
193
    If idx > max_element insert new element. Allocate memory if needed. 
 
194
 
 
195
  RETURN VALUE
 
196
    TRUE        Idx was out of range and allocation of new memory failed
 
197
    FALSE       Ok
 
198
*/
 
199
 
 
200
my_bool set_dynamic(DYNAMIC_ARRAY *array, uchar* element, uint idx)
 
201
{
 
202
  if (idx >= array->elements)
 
203
  {
 
204
    if (idx >= array->max_element && allocate_dynamic(array, idx))
 
205
      return TRUE;
 
206
    bzero((uchar*) (array->buffer+array->elements*array->size_of_element),
 
207
          (idx - array->elements)*array->size_of_element);
 
208
    array->elements=idx+1;
 
209
  }
 
210
  memcpy(array->buffer+(idx * array->size_of_element),element,
 
211
         (size_t) array->size_of_element);
 
212
  return FALSE;
 
213
}
 
214
 
 
215
 
 
216
/*
 
217
  Ensure that dynamic array has enough elements
 
218
 
 
219
  SYNOPSIS
 
220
    allocate_dynamic()
 
221
    array
 
222
    max_elements        Numbers of elements that is needed
 
223
 
 
224
  NOTES
 
225
   Any new allocated element are NOT initialized
 
226
 
 
227
  RETURN VALUE
 
228
    FALSE       Ok
 
229
    TRUE        Allocation of new memory failed
 
230
*/
 
231
 
 
232
my_bool allocate_dynamic(DYNAMIC_ARRAY *array, uint max_elements)
 
233
{
 
234
  if (max_elements >= array->max_element)
 
235
  {
 
236
    uint size;
 
237
    uchar *new_ptr;
 
238
    size= (max_elements + array->alloc_increment)/array->alloc_increment;
 
239
    size*= array->alloc_increment;
 
240
    if (array->buffer == (uchar *)(array + 1))
 
241
    {
 
242
       /*
 
243
         In this senerio, the buffer is statically preallocated,
 
244
         so we have to create an all-new malloc since we overflowed
 
245
       */
 
246
       if (!(new_ptr= (uchar *) my_malloc(size *
 
247
                                         array->size_of_element,
 
248
                                         MYF(MY_WME))))
 
249
         return 0;
 
250
       memcpy(new_ptr, array->buffer, 
 
251
              array->elements * array->size_of_element);
 
252
     }
 
253
     else
 
254
 
 
255
 
 
256
    if (!(new_ptr= (uchar*) my_realloc(array->buffer,size*
 
257
                                       array->size_of_element,
 
258
                                       MYF(MY_WME | MY_ALLOW_ZERO_PTR))))
 
259
      return TRUE;
 
260
    array->buffer= new_ptr;
 
261
    array->max_element= size;
 
262
  }
 
263
  return FALSE;
 
264
}
 
265
 
 
266
 
 
267
/*
 
268
  Get an element from array by given index
 
269
 
 
270
  SYNOPSIS
 
271
    get_dynamic()
 
272
      array     
 
273
      uchar*    Element to be returned. If idx > elements contain zeroes.
 
274
      idx       Index of element wanted. 
 
275
*/
 
276
 
 
277
void get_dynamic(DYNAMIC_ARRAY *array, uchar* element, uint idx)
 
278
{
 
279
  if (idx >= array->elements)
 
280
  {
 
281
    DBUG_PRINT("warning",("To big array idx: %d, array size is %d",
 
282
                          idx,array->elements));
 
283
    bzero(element,array->size_of_element);
 
284
    return;
 
285
  }
 
286
  memcpy(element,array->buffer+idx*array->size_of_element,
 
287
         (size_t) array->size_of_element);
 
288
}
 
289
 
 
290
 
 
291
/*
 
292
  Empty array by freeing all memory
 
293
 
 
294
  SYNOPSIS
 
295
    delete_dynamic()
 
296
      array     Array to be deleted
 
297
*/
 
298
 
 
299
void delete_dynamic(DYNAMIC_ARRAY *array)
 
300
{
 
301
  /*
 
302
    Just mark as empty if we are using a static buffer
 
303
  */
 
304
  if (array->buffer == (uchar *)(array + 1))
 
305
    array->elements= 0;
 
306
  else
 
307
  if (array->buffer)
 
308
  {
 
309
    my_free(array->buffer,MYF(MY_WME));
 
310
    array->buffer=0;
 
311
    array->elements=array->max_element=0;
 
312
  }
 
313
}
 
314
 
 
315
/*
 
316
  Delete element by given index
 
317
 
 
318
  SYNOPSIS
 
319
    delete_dynamic_element()
 
320
      array
 
321
      idx        Index of element to be deleted
 
322
*/
 
323
 
 
324
void delete_dynamic_element(DYNAMIC_ARRAY *array, uint idx)
 
325
{
 
326
  char *ptr= (char*) array->buffer+array->size_of_element*idx;
 
327
  array->elements--;
 
328
  memmove(ptr,ptr+array->size_of_element,
 
329
          (array->elements-idx)*array->size_of_element);
 
330
}
 
331
 
 
332
 
 
333
/*
 
334
  Free unused memory
 
335
 
 
336
  SYNOPSIS
 
337
    freeze_size()
 
338
      array     Array to be freed
 
339
 
 
340
*/
 
341
 
 
342
void freeze_size(DYNAMIC_ARRAY *array)
 
343
{
 
344
  uint elements=max(array->elements,1);
 
345
 
 
346
  /*
 
347
    Do nothing if we are using a static buffer
 
348
  */
 
349
  if (array->buffer == (uchar *)(array + 1))
 
350
    return;
 
351
    
 
352
  if (array->buffer && array->max_element != elements)
 
353
  {
 
354
    array->buffer=(uchar*) my_realloc(array->buffer,
 
355
                                     elements*array->size_of_element,
 
356
                                     MYF(MY_WME));
 
357
    array->max_element=elements;
 
358
  }
 
359
}
 
360
 
 
361
 
 
362
/*
 
363
  Get the index of a dynamic element
 
364
 
 
365
  SYNOPSIS
 
366
    get_index_dynamic()
 
367
     array      Array
 
368
     element Whose element index 
 
369
 
 
370
*/
 
371
 
 
372
int get_index_dynamic(DYNAMIC_ARRAY *array, uchar* element)
 
373
{
 
374
  uint ret;
 
375
  if (array->buffer > element)
 
376
    return -1;
 
377
 
 
378
  ret= (element - array->buffer) /  array->size_of_element;
 
379
  if (ret > array->elements)
 
380
    return -1;
 
381
 
 
382
  return ret;
 
383
 
 
384
}