← Back to branch summary

~bkerensa/ubuntu/raring/valgrind/merge-from-deb

« back to all changes in this revision

Viewing changes to include/pub_tool_xarray.h

  • Committer: Bazaar Package Importer
  • Author(s): Andrés Roldán
  • Date: 2008-06-13 02:31:40 UTC
  • mto: (1.4.1 upstream) (2.2.1 squeeze)
  • mto: This revision was merged to the branch mainline in revision 24.
  • Revision ID: james.westby@ubuntu.com-20080613023140-iwk33rz9rhvfkr96
Import upstream version 3.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/pub_tool_xarray.h
 
1
 
 
2
/*--------------------------------------------------------------------*/
 
3
/*--- An expandable array implementation.        pub_tool_xarray.h ---*/
 
4
/*--------------------------------------------------------------------*/
 
5
 
 
6
/*
 
7
   This file is part of Valgrind, a dynamic binary instrumentation
 
8
   framework.
 
9
 
 
10
   Copyright (C) 2007-2007 OpenWorks LLP
 
11
      info@open-works.co.uk
 
12
 
 
13
   This program is free software; you can redistribute it and/or
 
14
   modify it under the terms of the GNU General Public License as
 
15
   published by the Free Software Foundation; either version 2 of the
 
16
   License, or (at your option) any later version.
 
17
 
 
18
   This program is distributed in the hope that it will be useful, but
 
19
   WITHOUT ANY WARRANTY; without even the implied warranty of
 
20
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
21
   General Public License for more details.
 
22
 
 
23
   You should have received a copy of the GNU General Public License
 
24
   along with this program; if not, write to the Free Software
 
25
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 
26
   02111-1307, USA.
 
27
 
 
28
   The GNU General Public License is contained in the file COPYING.
 
29
*/
 
30
 
 
31
#ifndef __PUB_TOOL_XARRAY_H
 
32
#define __PUB_TOOL_XARRAY_H
 
33
 
 
34
//--------------------------------------------------------------------
 
35
// PURPOSE: Provides a simple but useful structure, which is an array
 
36
// in which elements can be added at the end.  The array is expanded
 
37
// as needed by multiplying its size by a constant factor (usually 2).
 
38
// This gives amortised O(1) insertion cost, and, following sorting,
 
39
// the usual O(log N) binary search cost.  Arbitrary element sizes
 
40
// are allowed; the comparison function for sort/lookup can be changed
 
41
// at any time, and duplicates (modulo the comparison function) are
 
42
// allowed.
 
43
//--------------------------------------------------------------------
 
44
 
 
45
 
 
46
/* It's an abstract type.  Bwaha. */
 
47
typedef  void  XArray;
 
48
 
 
49
/* Create new XArray, using given allocation and free function, and
 
50
   for elements of the specified size.  Alloc fn must not fail (that
 
51
   is, if it returns it must have succeeded.) */
 
52
extern XArray* VG_(newXA) ( void*(*alloc_fn)(SizeT), 
 
53
                            void(*free_fn)(void*),
 
54
                            Word elemSzB );
 
55
 
 
56
/* Free all memory associated with an XArray. */
 
57
extern void VG_(deleteXA) ( XArray* );
 
58
 
 
59
/* Set the comparison function for this XArray.  This clears an
 
60
   internal 'array is sorted' flag, which means you must call sortXA
 
61
   before making further queries with lookupXA. */
 
62
extern void VG_(setCmpFnXA) ( XArray*, Int (*compar)(void*,void*) );
 
63
 
 
64
/* Add an element to an XArray.  Element is copied into the XArray.
 
65
   Index at which it was added is returned.  Note this will be
 
66
   invalidated if the array is later sortXA'd. */
 
67
extern Int VG_(addToXA) ( XArray*, void* elem );
 
68
 
 
69
/* Sort an XArray using its comparison function, if set; else bomb.
 
70
   Probably not a stable sort w.r.t. equal elements module cmpFn. */
 
71
extern void VG_(sortXA) ( XArray* );
 
72
 
 
73
/* Lookup (by binary search) 'key' in the array.  Set *first to be the
 
74
   index of the first, and *last to be the index of the last matching
 
75
   value found.  If any values are found, return True, else return
 
76
   False, and don't change *first or *last.  Bomb if the array is not
 
77
   sorted. */
 
78
extern Bool VG_(lookupXA) ( XArray*, void* key, 
 
79
                            /*OUT*/Word* first, /*OUT*/Word* last );
 
80
 
 
81
/* How elements are there in this XArray now? */
 
82
extern Word VG_(sizeXA) ( XArray* );
 
83
 
 
84
/* Index into the XArray.  Checks bounds and bombs if the index is
 
85
   invalid.  What this returns is the address of the specified element
 
86
   in the array, not (of course) the element itself.  Note that the
 
87
   element may get moved by subsequent addToXAs/sortXAs, so you should
 
88
   copy it out immediately and not regard its address as unchanging.
 
89
   Note also that indexXA will of course not return NULL if it
 
90
   succeeds. */
 
91
extern void* VG_(indexXA) ( XArray*, Word );
 
92
 
 
93
/* Drop the last n elements of an XArray.  Bombs if there are less
 
94
   than n elements in the array. */
 
95
extern void VG_(dropTailXA) ( XArray*, Word );
 
96
 
 
97
 
 
98
#endif   // __PUB_TOOL_XARRAY_H
 
99
 
 
100
/*--------------------------------------------------------------------*/
 
101
/*--- end                                        pub_tool_xarray.h ---*/
 
102
/*--------------------------------------------------------------------*/