bsearch.c 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
  1. /*
  2. * Copyright (c) 1990 Regents of the University of California.
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions
  7. * are met:
  8. * 1. Redistributions of source code must retain the above copyright
  9. * notice, this list of conditions and the following disclaimer.
  10. * 2. Redistributions in binary form must reproduce the above copyright
  11. * notice, this list of conditions and the following disclaimer in the
  12. * documentation and/or other materials provided with the distribution.
  13. * 3. [rescinded 22 July 1999]
  14. * 4. Neither the name of the University nor the names of its contributors
  15. * may be used to endorse or promote products derived from this software
  16. * without specific prior written permission.
  17. *
  18. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  19. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  22. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28. * SUCH DAMAGE.
  29. */
  30. #include <stdlib.h>
  31. // Do not use register a5; callback function might need it.
  32. register long __tbl asm ("a5");
  33. /*
  34. * Perform a binary search.
  35. *
  36. * The code below is a bit sneaky. After a comparison fails, we
  37. * divide the work in half by moving either left or right. If lim
  38. * is odd, moving left simply involves halving lim: e.g., when lim
  39. * is 5 we look at item 2, so we change lim to 2 so that we will
  40. * look at items 0 & 1. If lim is even, the same applies. If lim
  41. * is odd, moving right again involves halving lim, this time moving
  42. * the base up one item past p: e.g., when lim is 5 we change base
  43. * to item 3 and make lim 2 so that we will look at items 3 and 4.
  44. * If lim is even, however, we have to shrink it by one before
  45. * halving: e.g., when lim is 4, we still looked at item 2, so we
  46. * have to make lim 3, then halve, obtaining 1, so that we will only
  47. * look at item 3.
  48. */
  49. void *bsearch(const void *key asm("a0"), const void *bptr asm("a1"), short n asm("d0"), short w asm("d1"), compare_t cmp_func asm("a2")) __ATTR_LIB_ASM__;
  50. asm("
  51. .text
  52. .even
  53. .globl bsearch
  54. bsearch:
  55. movem.l %d3-%d5/%a3-%a4,-(%sp)
  56. move.l %a0,%d5 ;# key, key
  57. move.w %d1,%d4 ;# w, w
  58. move.l %a1,%a3 ;# bptr, base
  59. move.w %d0,%d3 ;# n, lim
  60. beq.s .L2 ;#
  61. .L3:
  62. move.w %d3,%d0 ;# lim, tmp40
  63. lsr.w #1,%d0 ;#, tmp40
  64. mulu.w %d4,%d0 ;# w, tmp41
  65. lea 0(%a3,%d0.l),%a4 ;# base, tmp41, rptr
  66. move.l %a4,-(%sp) ;# rptr,
  67. move.l %d5,-(%sp) ;# key,
  68. jsr (%a2) ;#* cmp_func
  69. addq.l #8,%sp ;#,
  70. tst.w %d0 ;# rcmp
  71. beq.s .L4 ;#
  72. ble.s .L5 ;#
  73. lea 0(%a4,%d4.w),%a3 ;#, base
  74. subq.w #1,%d3 ;#, lim
  75. .L5:
  76. lsr.w #1,%d3 ;#, lim
  77. bne.s .L3 ;#
  78. .L2:
  79. suba.l %a4,%a4 ;# rptr
  80. .L4:
  81. move.l %a4,%a0 ;# rptr, <result>
  82. movem.l (%sp)+,%d3-%d5/%a3-%a4
  83. rts
  84. ");
  85. // The assembly routine above was created using the following C code as a starting point:
  86. /*{
  87. char *base = (char *)bptr;
  88. unsigned short lim;
  89. short rcmp;
  90. void *rptr;
  91. for (lim = n; lim != 0; lim >>= 1) {
  92. rptr = base + ((long)(lim >> 1) * (unsigned short)w);
  93. rcmp = cmp_func(key, rptr);
  94. if (rcmp == 0)
  95. return rptr;
  96. if (rcmp > 0) { // key > p: move right
  97. base = (char *)rptr + w;
  98. lim--;
  99. } // else move left
  100. }
  101. return NULL;
  102. }*/