array.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170
  1. /*
  2. * Copyright (C) 2007 The Android Open Source Project
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. #include <cutils/array.h>
  17. #include <assert.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20. #include <limits.h>
  21. #define INITIAL_CAPACITY (4)
  22. #define MAX_CAPACITY ((int)(UINT_MAX/sizeof(void*)))
  23. struct Array {
  24. void** contents;
  25. int size;
  26. int capacity;
  27. };
  28. Array* arrayCreate() {
  29. return calloc(1, sizeof(struct Array));
  30. }
  31. void arrayFree(Array* array) {
  32. assert(array != NULL);
  33. // Free internal array.
  34. free(array->contents);
  35. // Free the Array itself.
  36. free(array);
  37. }
  38. /** Returns 0 if successful, < 0 otherwise.. */
  39. static int ensureCapacity(Array* array, int capacity) {
  40. int oldCapacity = array->capacity;
  41. if (capacity > oldCapacity) {
  42. int newCapacity = (oldCapacity == 0) ? INITIAL_CAPACITY : oldCapacity;
  43. // Ensure we're not doing something nasty
  44. if (capacity > MAX_CAPACITY)
  45. return -1;
  46. // Keep doubling capacity until we surpass necessary capacity.
  47. while (newCapacity < capacity) {
  48. int newCap = newCapacity*2;
  49. // Handle integer overflows
  50. if (newCap < newCapacity || newCap > MAX_CAPACITY) {
  51. newCap = MAX_CAPACITY;
  52. }
  53. newCapacity = newCap;
  54. }
  55. // Should not happen, but better be safe than sorry
  56. if (newCapacity < 0 || newCapacity > MAX_CAPACITY)
  57. return -1;
  58. void** newContents;
  59. if (array->contents == NULL) {
  60. // Allocate new array.
  61. newContents = malloc(newCapacity * sizeof(void*));
  62. if (newContents == NULL) {
  63. return -1;
  64. }
  65. } else {
  66. // Expand existing array.
  67. newContents = realloc(array->contents, sizeof(void*) * newCapacity);
  68. if (newContents == NULL) {
  69. return -1;
  70. }
  71. }
  72. array->capacity = newCapacity;
  73. array->contents = newContents;
  74. }
  75. return 0;
  76. }
  77. int arrayAdd(Array* array, void* pointer) {
  78. assert(array != NULL);
  79. int size = array->size;
  80. int result = ensureCapacity(array, size + 1);
  81. if (result < 0) {
  82. return result;
  83. }
  84. array->contents[size] = pointer;
  85. array->size++;
  86. return 0;
  87. }
  88. static inline void checkBounds(Array* array, int index) {
  89. assert(array != NULL);
  90. assert(index < array->size);
  91. assert(index >= 0);
  92. }
  93. void* arrayGet(Array* array, int index) {
  94. checkBounds(array, index);
  95. return array->contents[index];
  96. }
  97. void* arrayRemove(Array* array, int index) {
  98. checkBounds(array, index);
  99. void* pointer = array->contents[index];
  100. int newSize = array->size - 1;
  101. // Shift entries left.
  102. if (index != newSize) {
  103. memmove(array->contents + index, array->contents + index + 1,
  104. (sizeof(void*)) * (newSize - index));
  105. }
  106. array->size = newSize;
  107. return pointer;
  108. }
  109. void* arraySet(Array* array, int index, void* pointer) {
  110. checkBounds(array, index);
  111. void* old = array->contents[index];
  112. array->contents[index] = pointer;
  113. return old;
  114. }
  115. int arraySetSize(Array* array, int newSize) {
  116. assert(array != NULL);
  117. assert(newSize >= 0);
  118. int oldSize = array->size;
  119. if (newSize > oldSize) {
  120. // Expand.
  121. int result = ensureCapacity(array, newSize);
  122. if (result < 0) {
  123. return result;
  124. }
  125. // Zero out new entries.
  126. memset(array->contents + sizeof(void*) * oldSize, 0,
  127. sizeof(void*) * (newSize - oldSize));
  128. }
  129. array->size = newSize;
  130. return 0;
  131. }
  132. int arraySize(Array* array) {
  133. assert(array != NULL);
  134. return array->size;
  135. }
  136. const void** arrayUnwrap(Array* array) {
  137. return (const void**)array->contents;
  138. }